Define a graph and its various components

A graph is a mathematical structure used to model relationships or connections between objects. It consists of a set of vertices (or nodes) and edges (or arcs) that connect these vertices.

Here's a more detailed breakdown of its various components:

1. Vertices (Nodes)

• Definition: The fundamental units of a graph, which represent objects or entities.
• Notation: Often denoted as $V$ or $V(G)$ in a graph $G$. Each vertex is typically labeled or identified by a unique identifier.
• 
  

2. Edges (Arcs)

• Definition: The connections between pairs of vertices in the graph. They represent the relationship or interaction between the vertices.
• Notation: Often denoted as $E$ or $E(G)$. In a directed graph, an edge is an ordered pair $(u, v)$, while in an undirected graph, it's an unordered pair $\{u, v\}$.
• 
  

3. Degree

• Definition: The degree of a vertex is the number of edges incident to it.
• In Undirected Graphs: The degree is simply the number of edges connected to the vertex.
• In Directed Graphs: It is split into two types:
  • In-degree: The number of incoming edges to a vertex.
  • Out-degree: The number of outgoing edges from a vertex.
  • 
    

4. Path

• Definition: A sequence of edges that connects a sequence of vertices.
• Simple Path: A path where no vertex is repeated.
• Length: The number of edges in the path.
• 
  

5. Cycle

• Definition: A path that starts and ends at the same vertex, with no other vertex repeated.
• Simple Cycle: A cycle with no repeated vertices, except for the starting and ending vertex.
• 
  

6. Connected Graph

• Definition: A graph is connected if there is a path between any pair of vertices.
• Connected Components: In a disconnected graph, each subgraph that is connected is called a connected component.
• 
  

7. Subgraph

• Definition: A graph formed from a subset of the vertices and edges of the original graph.
• 
  

8. Adjacency Matrix

• Definition: A square matrix used to represent a graph, where the entry at position (i, j) indicates whether there is an edge between vertices i and j.
• For Directed Graphs: The matrix is not necessarily symmetric.
• For Undirected Graphs: The matrix is symmetric.
• 
  

9. Adjacency List

• Definition: A list where each vertex has a list of the vertices to which it is connected by an edge.
• 
  

10. Degree Sequence

• Definition: A list of the degrees of all vertices in a graph, usually ordered in non-increasing order.
• 
  

11. Graph Types

• Simple Graph: No loops (edges connected to themselves) and no multiple edges between the same pair of vertices.
• Multigraph: May have multiple edges between the same pair of vertices.
• Weighted Graph: Edges have weights or costs associated with them.