Unit 14: Introduction to Graph Theory
Contents
1. Definition of Graphs, Vertices, and Edges
A Graph (G) is a mathematical structure consisting of two sets: a set of Vertices (V) (also called nodes) and a set of Edges (E) that connect pairs of vertices.
Formal Notation: G = (V, E).
Example: V = \{v1, v2, v3\}, E = \{(v1, v2), (v2, v3)\}.
2. Types of Graphs
Graphs are classified based on the nature of their edges and connections:
| Type | Description |
|---|---|
| Undirected Graph | Edges have no direction (connection is two-way). |
| Directed Graph (Digraph) | Edges have a specific direction (represented by arrows). |
| Simple Graph | A graph with no self-loops and no multiple edges between the same vertices. |
| Complete Graph (Kn) | A graph where every vertex is connected to every other vertex exactly once. |
3. Degree of a Vertex
The Degree of a vertex is the number of edges incident (connected) to it. For directed graphs, we distinguish between In-degree (arrows coming in) and Out-degree (arrows going out).
Handshaking Lemma: The sum of the degrees of all vertices in a graph is twice the number of edges.
ā deg(v) = 2 Ć |E|
4. Paths and Connectivity
- Path: A sequence of edges that allows you to travel from one vertex to another.
- Cycle: A path that starts and ends at the same vertex without repeating edges or vertices (except the start/end).
- Connected Graph: A graph where there is a path between every pair of vertices.
5. Introduction to Trees
A Tree is a special type of connected graph that has no cycles. Trees are fundamental in computer science for organizing data (like folder structures or HTML DOM).
Properties of a Tree:
- If a tree has n vertices, it must have exactly n-1 edges.
- There is exactly one unique path between any two vertices.
- Adding any one edge to a tree creates exactly one cycle.
6. Exam Focus Enhancements
- Degree Calculation: In a simple graph, a self-loop (if allowed in a multigraph) counts as two degrees for that vertex.
- The n-1 Rule: If an exam question asks if a connected graph with 10 vertices and 10 edges is a tree, the answer is No (it must have 9 edges).
- Handshaking Application: Use the Handshaking Lemma to find the number of edges if the degrees of all vertices are given.
- Directed vs Undirected: Forgetting to use arrows when drawing a directed graph. In directed graphs, (v1, v2) is NOT the same as (v2, v1).
- Simple Graph Rules: Including multiple edges between two vertices when asked to draw a *simple* graph.
- Disconnected Trees: Thinking a tree can be disconnected. A disconnected graph without cycles is called a **Forest**.
Q: What is an Isolated Vertex?
A: A vertex with a degree of 0 (no connections).
Q: What is a Pendant Vertex?
A: A vertex with a degree of 1 (a "leaf" in a tree).
Q: Why is Graph Theory important for BCA?
A: It is used in networking (topology), database management (relationships), and algorithm design (pathfinding).