Graph Theory: Terminologies

Graph Theory: Terminologies

Graph theory is a branch of discrete mathematics that studies graphs, which are mathematical structures used to model pairwise relations between objects. A graph consists of two main components: vertices (or nodes) and edges (or arcs). Graph theory has numerous applications in fields such as computer science, biology, social networks, transportation, and more.

Here are the key terminologies and concepts in graph theory:

---

1. Graph

A graph is a collection of vertices (also called nodes) connected by edges (also called arcs).

• Vertex (Node): A point in the graph, representing an object or entity.
• Edge (Arc): A connection between two vertices, representing a relationship between them.

A graph can be either directed (where edges have a direction) or undirected (where edges have no direction).

• Directed Graph (Digraph): A graph in which edges have a direction. The edges are ordered pairs of vertices $(u, v)$, where $u$ is the starting vertex and $v$ is the ending vertex.
• Undirected Graph: A graph in which edges do not have a direction. The edges are unordered pairs of vertices $\{u, v\}$, where $u$ and $v$ are related.

---

2. Types of Graphs

2.1 Simple Graph

A simple graph is a graph where each pair of vertices is connected by at most one edge, and there are no loops (edges that connect a vertex to itself).

2.2 Multigraph

A multigraph is a graph where multiple edges between the same pair of vertices are allowed, and loops are also allowed.

2.3 Weighted Graph

A weighted graph assigns a weight or cost to each edge. These weights represent distances, costs, or any other quantity associated with the edge.

2.4 Complete Graph

A complete graph is a graph in which there is an edge between every pair of vertices. A complete graph with $n$ vertices is denoted as $K_n$.

2.5 Bipartite Graph

A bipartite graph is a graph whose vertex set can be divided into two disjoint subsets such that every edge connects a vertex in one subset to a vertex in the other subset. In other words, no edge connects vertices within the same subset.

2.6 Subgraph

A subgraph of a graph $G$ is a graph formed from a subset of the vertices and edges of $G$.

---

3. Degree of a Vertex

• Degree of a vertex $v$, denoted as $\deg(v)$, is the number of edges incident to $v$.

  • In an undirected graph, the degree is simply the number of edges connected to the vertex.
  • In a directed graph, the in-degree is the number of edges coming into a vertex, and the out-degree is the number of edges leaving a vertex.

  For example, in the graph with vertices $A$, $B$, and $C$, if there are edges $(A, B)$, $(B, C)$, and $(C, A)$, then:

  • The degree of each vertex in an undirected graph is 2.
  • The in-degree and out-degree of each vertex would be 1 each in a directed graph.

---

4. Path and Walk

• Path: A path in a graph is a sequence of vertices where each consecutive pair of vertices is connected by an edge. The path is simple if no vertex is repeated.

  • Length of a Path: The number of edges in the path is called the length of the path.
  • Simple Path: A path where no vertex is repeated.

• Walk: A walk in a graph is similar to a path, but vertices and edges can be repeated.

• Cycle: A cycle is a path that starts and ends at the same vertex without repeating any other vertex in between.

• Circuit: A circuit is a closed walk, meaning a walk that starts and ends at the same vertex.

---

5. Connectedness

• Connected Graph: A graph is said to be connected if there is a path between every pair of vertices.

• Disconnected Graph: A graph is disconnected if it is not connected, meaning there exists at least one pair of vertices that are not connected by a path.

• Strongly Connected Graph (for directed graphs): A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.

• Weakly Connected Graph (for directed graphs): A directed graph is weakly connected if, when the direction of edges is ignored, the graph becomes connected.

---

6. Components

• Component: A component of a graph is a connected subgraph in which there is a path between every pair of vertices in the subgraph.

• Connected Component: The largest connected subgraph in a graph is called its connected component. If the graph is disconnected, it may have multiple connected components.

---

7. Trees and Forests

• Tree: A tree is an acyclic connected graph. A tree with $n$ vertices has $n-1$ edges.

  • Rooted Tree: A tree in which one vertex is designated as the root, and every edge is directed away from the root.
  • Leaf: A leaf is a vertex in a tree with a degree of 1 (i.e., it is only connected to one other vertex).
  • Parent and Child: In a rooted tree, a parent is a vertex that has a directed edge to a child vertex.

• Forest: A forest is a disjoint set of trees, or equivalently, a graph without cycles.

---

8. Directed Acyclic Graph (DAG)

• Directed Acyclic Graph: A DAG is a directed graph with no cycles. In other words, it is a directed graph in which it is impossible to start at a vertex, follow the edges, and return to the same vertex.

DAGs are widely used in applications like task scheduling, dependency analysis, and representing workflows.

---

9. Isomorphism

• Graph Isomorphism: Two graphs $G_1$ and $G_2$ are isomorphic if there is a one-to-one correspondence between their vertices and edges such that the adjacency of vertices is preserved. In other words, you can transform one graph into the other by relabeling the vertices.

---

10. Planar Graph

• Planar Graph: A graph is planar if it can be drawn on a plane without any edges crossing each other.
• Kuratowski’s Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (complete graph on 5 vertices) or $K_{3,3}$ (complete bipartite graph with partitions of 3 vertices each).

---

11. Adjacency Matrix and Adjacency List

• Adjacency Matrix: The adjacency matrix of a graph is a square matrix used to represent a graph. The element at row $i$ and column $j$ indicates whether there is an edge from vertex $i$ to vertex $j$.

  • In an undirected graph, the matrix is symmetric.
  • In a directed graph, the matrix is not necessarily symmetric.

• Adjacency List: An adjacency list is an array or list of lists where each vertex has a list of all other vertices that it is connected to by edges.

---

12. Eulerian and Hamiltonian Graphs

• Eulerian Graph: A graph is Eulerian if there exists a cycle that visits every edge exactly once. A graph has an Eulerian circuit if every vertex has an even degree.
• Hamiltonian Graph: A graph is Hamiltonian if there exists a path or cycle that visits every vertex exactly once. There is no simple criterion for a graph to be Hamiltonian, unlike Eulerian graphs.

---

13. Matching and Bipartite Matching

• Matching: A matching in a graph is a set of edges such that no two edges share a common vertex.
• Bipartite Matching: A bipartite matching is a matching where the graph is bipartite, meaning its vertex set is divided into two disjoint sets, and each edge connects a vertex in one set to a vertex in the other set.

---

Summary Table

Terminology	Definition
Vertex (Node)	A point in the graph.
Edge (Arc)	A connection between two vertices.
Path	A sequence of vertices connected by edges.
Cycle	A path that starts and ends at the same vertex.
Connected Graph	A graph in which there is a path between every pair of vertices.
Tree	A connected acyclic graph.
Graph Isomorphism	A one-to-one correspondence between two graphs preserving adjacency.
Eulerian Graph	A graph with a cycle that visits every edge exactly once.
Hamiltonian Graph	A graph with a cycle that visits every vertex exactly once.

Graph theory is vast and essential in various domains, helping model and analyze real-world systems and problems effectively.