Unit 4 – Introduction to Graph Theory | Discrete Mathematics SPPU 2024

Introduction to Graph Theory

Graph theory is a fundamental branch of discrete mathematics that deals with the study of graphs. In computer science and engineering, a graph is not a bar chart or a line graph; rather, it is a mathematical structure used to model pairwise relations between objects.

Graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, and routing in navigation systems like Google Maps. Understanding graph theory is essential for designing efficient algorithms and solving complex real-world problems.

Hinglish Explanation: Graph theory mein 'Graph' ka matlab chart nahi hota. Yeh ek network hota hai jisme points (vertices) hote hain aur un points ko jodne wali lines (edges) hoti hain. Jaise alag-alag shehar (cities) aur unko jodne wale highways ek graph banate hain.

Graph Terminology

To study graphs, we must first understand the basic vocabulary used to describe them. A graph G consists of a set of vertices (V) and a set of edges (E), written as G = (V, E).

Basic Terms

• Vertex (Node): The fundamental unit of a graph. It represents an entity or an object, such as a computer in a network or a city on a map.

• Edge (Link): A line that connects two vertices. It represents a relationship or a path between the entities.

• Adjacent Vertices (Neighbors): Two vertices are adjacent if there is a direct edge connecting them.

• Loop: An edge that starts and ends at the exact same vertex.

• Parallel Edges: Two or more edges that connect the same pair of vertices in the same direction.

• Simple Graph: A graph that does not contain any loops or parallel edges.

• Multigraph: A graph that contains parallel edges but no loops.

Types of Edges

• Undirected Edge: An edge that has no direction. If there is an undirected edge between A and B, you can travel from A to B and from B to A.

• Directed Edge: An edge that points in a specific direction, represented by an arrow. If it points from A to B, you can only travel from A to B.

Degree of a Vertex

The degree of a vertex is the total number of edges connected to it.

• In a directed graph, the degree is divided into In-degree (number of incoming edges) and Out-degree (number of outgoing edges).

The Handshaking Lemma

The Handshaking Lemma is a fundamental theorem in graph theory related to the degrees of vertices in an undirected graph.

Statement

The Handshaking Lemma states that the sum of the degrees of all vertices in any undirected graph is exactly twice the total number of edges.

Formula

Sum of degree(v) = 2 × e

(Where 'v' represents every vertex in the graph, and 'e' is the total number of edges).

Why does this happen?

Every single edge connects two vertices. Therefore, when you calculate the degree of all vertices, every edge is counted exactly twice—once for each vertex it connects.

Hinglish Explanation: Handshaking lemma ka concept bohot simple hai. Agar ek party mein log hath milate hain, toh ek handshake mein do hath shamil hote hain. Isiliye, graph mein sabhi nodes ki degree ka total hamesha edges ke total se double (2x) hota hai.

Important Note: A direct consequence of this lemma is that an undirected graph will always have an even number of vertices with an odd degree.

Special Types of Graphs

Certain graph structures appear so frequently in computer science that they are given special names.

1. Complete Graph

A complete graph is a simple undirected graph in which every single vertex is directly connected to every other vertex. It is denoted by K_n, where 'n' is the number of vertices.

• Application: Useful in network topologies where every computer must communicate directly with every other computer (Full Mesh Topology).

2. Regular Graph

A graph is called a regular graph if every vertex has the exact same degree. If every vertex has a degree of 'k', it is called a k-regular graph.

3. Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets, say Set X and Set Y. The rule is that every edge must connect a vertex in Set X to a vertex in Set Y. There can be no edges connecting vertices within the same set.

• Application: Matching problems, such as assigning a set of job applicants to a set of available jobs.

4. Cycle Graph

A cycle graph consists of a single closed loop. It is denoted by C_n (where n is greater than or equal to 3). Every vertex in a cycle graph has a degree of exactly 2.

Representing Graphs

For a computer program to process a graph, it must be stored in the computer's memory using specific data structures. The two most common methods are the Adjacency Matrix and the Adjacency List.

1. Adjacency Matrix

An adjacency matrix is a 2D array (a table) of size V × V, where V is the total number of vertices.

• Working: The rows and columns represent the vertices. If there is an edge from vertex 'i' to vertex 'j', the matrix cell (i, j) is filled with 1 (or the weight of the edge). If there is no edge, the cell is filled with 0.

• Advantages: Checking if an edge exists between any two specific vertices is extremely fast.

• Disadvantages: It consumes a lot of memory space (V × V), even if the graph has very few edges.

2. Adjacency List

An adjacency list represents a graph as an array of linked lists.

• Working: The size of the array is equal to the number of vertices. Each index of the array represents a vertex, and the linked list at that index contains all the adjacent vertices (neighbors) of that vertex.

• Advantages: It saves a tremendous amount of memory for sparse graphs (graphs with few edges) because it only stores the existing connections.

• Disadvantages: Checking if a specific edge exists between two vertices takes slightly more time compared to a matrix.

Hinglish Explanation: Adjacency Matrix ek table jaisa hai jahan har row aur column ek vertex hai. Connection hone par 1 likhte hain, nahi hone par 0. Yeh fast hai par memory zyada leta hai. Adjacency List ek list hai jisme hum sirf unhi nodes ka naam likhte hain jo jude hue hain. Yeh memory bachata hai.

Graph Isomorphism

In graph theory, two graphs may look completely different on paper but can actually be the exact same graph structurally. This concept is called Graph Isomorphism.

Definition

Two graphs G1 and G2 are isomorphic if they have the exact same structure, meaning you can map the vertices of G1 to the vertices of G2 such that the edge connections are perfectly preserved.

Conditions for Isomorphism

To quickly check if two graphs are isomorphic, they must satisfy the following invariant conditions:

1. They must have the same number of vertices.

2. They must have the same number of edges.

3. They must have the same degree sequence (the list of degrees of all vertices must match).

If any of these conditions fail, the graphs are definitely not isomorphic. However, if they pass, you must still find a one-to-one mapping to prove they are isomorphic.

Connectivity in Graphs

Connectivity describes how the vertices in a graph are linked to one another.

Path and Circuit

• Path: A sequence of edges that allows you to travel from one vertex to another. In a simple path, no vertices or edges are repeated.

• Circuit (Cycle): A path that starts and ends at the exact same vertex.

Connected Graph

An undirected graph is considered "connected" if there is at least one path between every single pair of vertices. If the graph is broken into isolated parts, it is called a disconnected graph, and those individual parts are called connected components.

Euler and Hamilton Paths

These are two classic traversal problems in graph theory.

Euler Path and Euler Circuit

• Euler Path: A path in a graph that visits every single edge exactly once. (Vertices can be visited more than once).

• Euler Circuit: An Euler path that starts and ends at the same vertex.

• Condition: According to Euler's Theorem, a connected graph has an Euler circuit if and only if every vertex has an even degree.

Hamilton Path and Hamilton Circuit

• Hamilton Path: A path in a graph that visits every single vertex exactly once.

• Hamilton Circuit: A Hamilton path that ends exactly where it started, connecting the last vertex back to the first vertex.

• Condition: Unlike Euler paths, there is no simple mathematical formula to quickly check if a Hamilton circuit exists. It is a complex computational problem (NP-complete).

Hinglish Explanation: In dono mein confuse nahi hona hai. Euler ka focus EDGES par hota hai (har road ek baar travel karni hai). Hamilton ka focus VERTICES par hota hai (har city ek baar visit karni hai).

Comparison Table

Single Source Shortest Path: Dijkstra’s Algorithm

In many real-world applications, edges have "weights" or costs (like distance in kilometers or time in minutes). Finding the shortest, most efficient route is critical.

What is Dijkstra’s Algorithm?

Dijkstra's Algorithm (created by Edsger W. Dijkstra) is a greedy algorithm used to find the shortest path from one specific starting vertex (the single source) to all other vertices in a weighted graph.

• Important Constraint: Dijkstra's algorithm only works if all edge weights are positive (greater than or equal to zero). It fails if there are negative weight edges.

Step-by-Step Working

1. Initialization: Assign a distance value to every vertex. Set the distance of the starting (source) vertex to 0. Set the distance of all other vertices to Infinity.

2. Marking Unvisited: Create a list of all unvisited vertices. Initially, all vertices are unvisited.

3. Select the Minimum: From the unvisited list, pick the vertex with the smallest distance value. (In the first step, this will be the source vertex).

4. Update Neighbors: Look at all the unvisited neighbors of the current vertex. Calculate the distance to them by adding the edge weight to the current vertex's distance.

   • If this new calculated distance is smaller than the neighbor's currently recorded distance, update it.

5. Mark Visited: Once all neighbors are checked, mark the current vertex as "visited." A visited vertex will never be checked again.

6. Repeat: Repeat steps 3 to 5 until all vertices have been marked as visited.

Real-Life Example

Google Maps uses variations of Dijkstra's algorithm. If you want to travel from your house (Source) to the airport (Destination), the algorithm evaluates all intersections (vertices) and road lengths (edge weights) to give you the path with the minimum total distance.

Hinglish Explanation: Dijkstra algorithm ek smart tareeka hai sabse chhota rasta dhundhne ka. Yeh source se shuru karta hai, apne padosi nodes (neighbors) ka distance calculate karta hai, aur hamesha sabse chote distance wale node ko chunta hai aage badhne ke liye. Yeh process tab tak chalta hai jab tak sabhi nodes tak pahunchne ka sabse chhota rasta fix na ho jaye.

Planar Graphs

Graph drawing is a significant part of discrete mathematics and VLSI (microchip) design.

Definition of a Planar Graph

A graph is called a planar graph if it can be drawn on a flat two-dimensional surface (like a piece of paper) in such a way that no two edges cross or intersect each other.

If edges must cross no matter how you draw it, the graph is non-planar.

Euler’s Formula for Planar Graphs

When a planar graph is drawn without edge crossings, it divides the flat surface into distinct regions (or faces), including the infinite region outside the graph.

Leonhard Euler discovered a beautiful relationship between the vertices (v), edges (e), and regions (r) of a connected planar graph.

Formula: v - e + r = 2

Example: Let's take a simple triangle graph.

• Vertices (v) = 3

• Edges (e) = 3

• Regions (r) = 2 (one inside the triangle, one outside)

• Check formula: 3 - 3 + 2 = 2. The formula holds true.

Hinglish Explanation: Planar graph us graph ko kehte hain jise paper par aise draw kiya ja sake ki uski koi bhi do lines ek dusre ke upar se na guzrein (cross na karein). Euler's formula humesha check karne mein madad karta hai ki nodes, lines, aur enclosed spaces ka balance sahi hai ya nahi.

Graph Colouring

Graph colouring is a classic optimization problem in graph theory.

Concept and Rules

Graph colouring (specifically vertex colouring) is the process of assigning a color to every vertex of a graph subject to one strict rule: No two adjacent vertices (vertices connected by an edge) can have the same color.

Chromatic Number

The Chromatic Number of a graph is the absolute minimum number of colors required to color the graph following the rule above. It is denoted by the Greek letter Chi (χ).

• If a graph requires 3 colors, its chromatic number is 3.

• For a bipartite graph, the chromatic number is always exactly 2.

Real-World Applications of Graph Colouring

1. Map Colouring: When drawing a political map of countries or states, mapmakers use graph colouring. Each state is a vertex, and an edge connects states that share a border. Graph colouring ensures no two adjacent states have the same color, making the map easy to read. (The famous Four Color Theorem states that any planar map can be colored with a maximum of 4 colors).

2. Scheduling (Time Tables): Suppose you have to schedule exams for various subjects. If two subjects have common students, their exams cannot be scheduled at the same time. Subjects are vertices, and common students are edges. The chromatic number gives the minimum number of time slots required.

3. Mobile Network Frequency Assignment: Mobile towers that are close to each other (adjacent) cannot use the same frequency channel because they will interfere. Graph colouring assigns different frequencies (colors) to adjacent towers efficiently.

Important Note on Algorithms

Understanding the theoretical foundation of paths, connectivity, and colouring is critical before writing code. Algorithms like Dijkstra's teach computer science students how to optimize time and space complexities, moving from naive brute-force approaches to highly sophisticated greedy logic.

Summary and Key Takeaways

• Graph Terminology: A graph G=(V,E) represents entities (vertices) and their relationships (edges). Edges can be directed or undirected.

• Handshaking Lemma: The sum of all vertex degrees in an undirected graph equals twice the number of edges.

• Representation: Matrices are fast but memory-heavy; Adjacency Lists are memory-efficient for sparse graphs.

• Isomorphism: Two graphs are isomorphic if they share the exact same structural blueprint, despite visual differences.

• Euler vs. Hamilton: Euler paths must traverse every edge exactly once; Hamilton paths must traverse every vertex exactly once.

• Dijkstra’s Algorithm: A greedy approach to find the shortest path from a single source node to all other nodes, provided edge weights are non-negative.

• Planar Graphs: Graphs that can be drawn without edge crossings, strictly following Euler's formula (v - e + r = 2).

• Graph Colouring: Assigning colors to vertices to avoid adjacent conflicts, heavily used in scheduling and frequency assignment.

SEO Keywords Section

Search keywords related to this topic:

Graph Theory terminology, Discrete mathematics graphs, Directed and undirected graphs, Handshaking lemma proof and examples, Types of graphs complete bipartite regular, Adjacency matrix vs adjacency list, Graph isomorphism conditions, Euler path and Hamilton path difference, Single source shortest path, Dijkstra's algorithm step by step, Planar graphs and Euler's formula, Graph colouring chromatic number, Graph colouring scheduling application, Computer engineering discrete math notes, Basic graph theory concepts for beginners.