MathIsimple
DM-12
Course 12

Graphs and Trees

Explore the fundamental structures of graph theory: vertices, edges, paths, and trees. Essential for modeling networks, relationships, and hierarchies.

Learning Objectives
  • Understand graph terminology
  • Represent graphs using matrices and lists
  • Perform BFS and DFS traversals
  • Identify Euler and Hamilton paths
  • Work with trees and spanning trees
  • Apply shortest path algorithms

1. Graph Basics

Definition 12.1: Graph

A graph G=(V,E)G = (V, E) consists of vertices V and edges E.

In an undirected graph, edges are unordered pairs. In a directed graph, edges are ordered pairs.

Theorem 12.1: Handshaking Lemma
∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

Each edge contributes 2 to the sum of degrees.

Definition 12.2: Graph Terminology
  • Adjacent: Vertices connected by an edge
  • Degree: Number of edges incident to a vertex
  • Path: Sequence of vertices connected by edges
  • Cycle: Path that starts and ends at the same vertex
  • Connected: Path exists between every pair of vertices

2. Graph Traversals

Definition 12.3: BFS and DFS

BFS (Breadth-First Search): Explores level by level using a queue.

DFS (Depth-First Search): Explores as deep as possible using a stack.

Example: BFS vs DFS Applications

BFS:

  • Shortest path (unweighted)
  • Level-order traversal

DFS:

  • Cycle detection
  • Topological sorting

3. Euler and Hamilton Paths

Definition 12.4: Euler Path/Circuit

An Euler path visits every edge exactly once.

An Euler circuit is an Euler path that returns to the start.

Theorem 12.2: Euler Conditions
  • Euler circuit: All vertices have even degree
  • Euler path: Exactly 2 vertices have odd degree
Definition 12.5: Hamilton Path/Cycle

A Hamilton path visits every vertex exactly once.

Finding Hamilton paths is NP-complete (no efficient algorithm known).

4. Trees

Definition 12.6: Tree

A tree is a connected graph with no cycles.

Equivalent: connected with n-1 edges, or unique path between any two vertices.

Theorem 12.3: Tree Properties
  • A tree with n vertices has exactly n-1 edges
  • Adding any edge creates exactly one cycle
  • Removing any edge disconnects the tree
Definition 12.7: Spanning Tree

A spanning tree of a connected graph G is a subgraph that is a tree containing all vertices of G.

5. Shortest Paths

Algorithm 12.1: Dijkstra's Algorithm

Finds shortest paths from source to all vertices:

  1. Initialize distances: source = 0, others = ∞
  2. Pick unvisited vertex with minimum distance
  3. Update distances to neighbors
  4. Repeat until all visited

Complexity: O(V²) or O((V+E) log V) with priority queue.

6. Graph Coloring

Definition 12.8: Graph Coloring

A proper vertex coloring assigns colors so no adjacent vertices share a color.

The chromatic number χ(G) is the minimum colors needed.

Theorem 12.4: Four Color Theorem

Every planar graph can be colored with at most 4 colors.

Practice Quiz

Graphs and Trees Quiz
10
Questions
0
Correct
0%
Accuracy
1
A graph with nn vertices and no cycles can have at most how many edges?
Easy
Not attempted
2
In an undirected graph, if every vertex has degree 3, the number of edges is:
Medium
Not attempted
3
A connected graph has an Euler circuit if and only if:
Medium
Not attempted
4
The complete graph K5K_5 has how many edges?
Easy
Not attempted
5
Which traversal visits all vertices at distance kk before any at distance k+1k+1?
Easy
Not attempted
6
A tree with 10 vertices has how many edges?
Easy
Not attempted
7
The chromatic number of a graph is:
Medium
Not attempted
8
A bipartite graph can be characterized as:
Hard
Not attempted
9
Dijkstra's algorithm finds:
Medium
Not attempted
10
A planar graph with n≥3n \geq 3 vertices has at most how many edges?
Hard
Not attempted

Frequently Asked Questions

When should I use BFS vs DFS?

BFS: Shortest path, level-by-level exploration.

DFS: Path finding, cycle detection, topological sort.

What's the difference between a tree and a graph?

A tree is a connected graph with no cycles—it has exactly n-1 edges for n vertices.

Why is the Hamilton path problem hard?

Unlike Euler paths (polynomial time), Hamilton paths are NP-complete—no efficient algorithm exists.

What are common applications of graphs?

Social networks, road maps, web links, dependency management, circuit design.