Unit V: Graph Theory with Applications
Course: Discrete Mathematics
Code: CADSC102
Table of Contents
Basic Concepts of Graph Theory
A graph consists of a set of vertices (nodes) and edges that connect them.
- Incidence: An edge is incident to the vertices it connects.
- Degree: The number of edges incident to a vertex.
- Sub-graphs: A graph whose vertices and edges are subsets of another graph.
- Union of Graphs: A graph containing all vertices and edges from two or more graphs.
Isomorphism and Homomorphism
- Isomorphism: Two graphs are isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves adjacency.
- Homomorphism: A mapping between two graphs that preserves the structure but does not necessarily require a one-to-one correspondence.
Types of Graphs
Graphs can be categorized by their specific properties and constraints:
- Multigraphs: Graphs that can have multiple edges between the same two vertices.
- Weighted Graphs: Graphs where each edge is assigned a numerical value or "weight".
- Planar Graphs: Graphs that can be drawn in a plane such that no edges cross each other.
Walks, Paths, and Circuits
These terms describe movement within a graph:
- Walk: A sequence of vertices and edges.
- Path: A walk where all vertices (and thus all edges) are distinct.
- Circuit: A closed walk where the start and end vertices are the same.
- Connectedness: A graph is connected if there is a path between every pair of vertices.
Eulerian and Hamiltonian Graphs
- Eulerian Graph: A graph containing a circuit that uses every edge exactly once.
- Hamiltonian Graph: A graph containing a circuit that visits every vertex exactly once.
Complete, Regular, and Bipartite Graphs
- Complete Graph: A graph where every pair of distinct vertices is connected by a unique edge.
- Regular Graph: A graph where every vertex has the same degree.
- Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
Cut-sets and Cut-vertices
- Cut-vertex: A vertex whose removal increases the number of connected components in the graph.
- Cut-set: A set of edges whose removal disconnects the graph.
Exam Focus & Tips
- Exam Tip: To prove a graph is Eulerian, check if all vertices have an even degree.
- Common Mistake: Confusing Eulerian (Edges) with Hamiltonian (Vertices). Euler = Edges.
- Practical Tip: Weighted graphs are frequently used in shortest-path problems like GPS navigation.
Frequently Asked Questions
Q: What makes a graph "Planar"?
A: It can be drawn on a flat surface without any edges intersecting.
Q: What is a Bipartite graph?
A: A graph where vertices are split into two groups, and edges only connect vertices from different groups.