Graph Theory, Discrete Mathematics

Graph Theory

What is graph

A graph is a mathematical structure that consists of a set of vertices (or nodes) and a set of edges that connect pairs of vertices. It is a powerful tool for representing and analyzing relationships between objects or entities.

Graph Terminologies

1. Vertex (Plural: Vertices): A vertex, also known as a node, represents an object or entity in the graph. It is typically denoted by a circle or a point.

2. Edge: An edge represents a connection or a relationship between two vertices. It is typically denoted by a line segment connecting two vertices.

3. Adjacency: Two vertices are said to be adjacent if they are connected by an edge. In other words, if there is an edge between two vertices, they are considered adjacent.

4. Degree: The degree of a vertex is the number of edges that are incident to (connected to) that vertex. In an undirected graph, the degree of a vertex is the number of edges connected to it. In a directed graph, the degree is further divided into in-degree (number of incoming edges) and out-degree (number of outgoing edges).

5. Walk: A walk is a sequence of vertices and edges in a graph, where each edge is incident to the vertices preceding and following it. A walk can revisit vertices and edges multiple times.

6. Trail: A trail is a walk in which no edge is repeated, although vertices may be repeated.

7. Path: A path is a sequence of vertices connected by edges, where no vertex is repeated except possibly the starting and ending vertices. The length of a path is the number of edges it contains.

8. Cycle: A cycle is a path in which the starting and ending vertices are the same, and no other vertex is repeated. In other words, it is a closed path.

9. Circuit: A circuit is a closed path in a graph, where all vertices are distinct except the starting and ending vertices.

10. Subgraph: A subgraph is a graph formed by a subset of vertices and edges from a given graph.

11. Connected Graph: A graph is said to be connected if there exists a path between every pair of vertices. In other words, it is possible to reach any vertex from any other vertex by traversing the edges.

12. Disconnected Graph: A graph is disconnected if it is not connected. In a disconnected graph, there exist at least two vertices such that there is no path between them.

13. Component: A component of a graph is a maximally connected subgraph. In other words, it is a connected subgraph that is not part of any larger connected subgraph within the original graph.

14. Strongly Connected Graph (Directed Graphs): A directed graph is strongly connected if for any two vertices u and v, there exists a directed path from u to v and a directed path from v to u, considering the directions of the edges.

15. Weakly Connected Graph (Directed Graphs): A directed graph is weakly connected if, when disregarding the directions of the edges, there exists a path between every pair of vertices in the underlying undirected graph.

Types of Graphs

1. Simple Graph: A simple graph is a graph that has no loops (edges connecting a vertex to itself) and no multiple edges (more than one edge connecting the same pair of vertices).

2. Multigraph: A multigraph is a graph that allows multiple edges between the same pair of vertices.

3. Pseudograph: A pseudograph is a graph that allows loops and multiple edges.

4. Directed Graph (Digraph): A directed graph, or digraph, is a graph in which edges have a specific direction associated with them. The edges are represented by arrows, and they can only be traversed in the specified direction.

5. Undirected Graph: An undirected graph is a graph in which the edges have no specific direction associated with them. The edges are represented by simple lines, and they can be traversed in either direction.

6. Weighted Graph: A weighted graph is a graph in which each edge is assigned a numerical value called weight. These weights can represent various properties, such as distances, costs, or strengths of connections.

7. Unweighted Graph: An unweighted graph is a graph in which the edges have no associated weights or values.

8. Complete Graph: A complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. In a complete graph with n vertices, there are n(n-1)/2 edges.

9. Null Graph: A null graph is a graph with no edges. It consists of a set of vertices with no connections between them.

10. Regular Graph: A regular graph is a graph in which all vertices have the same degree.

11. Bipartite Graph: A bipartite graph is a graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex in one set to a vertex in the other set. In other words, there are no edges between vertices within the same set.

12. Complete Bipartite Graph: A complete bipartite graph is a bipartite graph in which every vertex in one set is connected to every vertex in the other set.

13. Cycle Graph: A cycle graph is a graph that consists of a single cycle. In other words, it is a closed path with no repeated vertices (except for the starting and ending vertices).

14. Acyclic Graph: An acyclic graph is a graph that does not contain any cycles.

15. Tree: A tree is an undirected acyclic connected graph. In other words, it is a connected graph with no cycles.

16. Planar Graph: A planar graph is a graph that can be drawn on a plane without any edges crossing each other.

17. Sparse Graph: A sparse graph is a graph with relatively few edges compared to the number of vertices.

18. Dense Graph: A dense graph is a graph with a high number of edges compared to the number of vertices.

Representation of Graphs

Graphs can be represented in various ways, depending on the problem and the operations that need to be performed on the graph. Three common representations are:

1. Adjacency List:

   • An adjacency list is a collection of lists, where each list represents a vertex in the graph.
   • For each vertex, the corresponding list contains all the vertices that are adjacent to it (connected by an edge).
   • This representation is efficient for sparse graphs (graphs with fewer edges compared to the number of vertices) and is suitable for operations like finding all vertices adjacent to a given vertex.

2. Adjacency Matrix:

   • An adjacency matrix is a two-dimensional square matrix, where the rows and columns represent vertices in the graph.
   • If there is an edge between vertices i and j, then the value at position (i, j) in the matrix is set to 1 (or the weight of the edge if it is a weighted graph). Otherwise, it is set to 0.
   • For an undirected graph, the adjacency matrix is symmetric about the main diagonal.
   • This representation is efficient for dense graphs (graphs with many edges compared to the number of vertices) and is suitable for operations like checking if there is an edge between two vertices.

3. Incidence Matrix:

   • An incidence matrix is a two-dimensional matrix, where the rows represent vertices, and the columns represent edges in the graph.
   • If a vertex i is incident on (connected to) an edge j, then the value at position (i, j) in the matrix is set to 1 (or the weight of the edge if it is a weighted graph). Otherwise, it is set to 0.
   • For an undirected graph, each edge will have two 1's in the corresponding column, one for each vertex it connects.
   • This representation is useful for analyzing the relationships between vertices and edges and is commonly used in algebraic graph theory.

Trees

A tree is a connected, acyclic, undirected graph. It is a graph that has no cycles, and there is a unique path between every pair of vertices. Trees are fundamental data structures in computer science and have numerous applications in areas like data organization, algorithm design, and network topologies.

Properties of Trees:

1. A tree with n vertices has exactly n-1 edges.
2. There exists a unique path between every pair of vertices in a tree, meaning that there is only one way to traverse from one vertex to another.
3. Removing any edge from a tree disconnects the graph, resulting in two separate components.
4. If all edges are removed from a tree with n vertices, it results in n disconnected components (isolated vertices).
5. Any connected graph with n vertices and n-1 edges is a tree.
6. Trees are minimally connected graphs, meaning that the removal of any edge disconnects the graph.

Rooted Tree

A rooted tree is a tree in which one vertex is designated as the root, serving as the starting point for exploration or traversal. The root vertex provides a hierarchical structure to the tree, and it is the unique node with no parent.

Properties of Rooted Trees:

1. Every vertex in a rooted tree, except the root, has exactly one parent (the vertex it is directly connected to on the path towards the root).
2. The root vertex has no parent.
3. Vertices with no children are called leaf nodes or external nodes.
4. Vertices with at least one child are called internal nodes.
5. The level of a node is the number of edges on the path from the root to that node. The root is at level 0.
6. The height of a rooted tree is the maximum level of any node in the tree.

Spanning Trees

A spanning tree of a connected, undirected graph G is a subgraph that is a tree and includes all the vertices of G. In other words, a spanning tree is a tree that spans (includes) all the vertices of the original graph, with a minimum number of edges required to connect all the vertices.

Properties of Spanning Trees:

1. A spanning tree of a graph G with n vertices has exactly n-1 edges.
2. A spanning tree is a minimally connected subgraph that includes all vertices of the original graph.
3. Every connected, undirected graph with n vertices has at least one spanning tree, and it may have multiple spanning trees.
4. If a graph is not connected, it does not have a spanning tree.

Minimum Spanning Trees

A minimum spanning tree (MST) of a connected, weighted undirected graph is a spanning tree with the minimum possible total weight, where the weight is the sum of the edge weights in the spanning tree.

Properties of Minimum Spanning Trees:

1. A minimum spanning tree is a spanning tree with the smallest possible sum of edge weights.
2. Every connected, weighted undirected graph has a unique minimum spanning tree if all edge weights are distinct.
3. If there are edges with equal weights, there can be multiple minimum spanning trees.
4. The minimum spanning tree of a graph is not necessarily unique if there are edges with equal weights.

Graphs are versatile mathematical structures that provide a powerful framework for representing and analyzing relationships between entities. Understanding the fundamental concepts of graphs, such as different types, representations, and properties, is crucial for developing efficient algorithms and solving complex problems. The study of graph theory continues to be an active area of research, contributing to the advancement of numerous fields and enabling innovative solutions to real-world challenges.