Directed vs Undirected Graphs
Undirected Graph:
Edges have no direction
Edge {u, v} means u and v are connected
Adjacency matrix is symmetric
Directed Graph (Digraph):
Edges have direction
Edge (u, v) means u points to v
Adjacency matrix is NOT necessarily symmetric
Special Types of Graphs
Complete Graph (Kₙ):
Every pair of vertices is connected
Number of edges: n(n-1)/2
Bipartite Graph:
Vertices divided into two sets
Edges only connect vertices from different sets
Weighted Graph:
Each edge has an associated weight/cost
Used in shortest path problems
Regular Graph:
Every vertex has the same degree
Sparse vs Dense:
Sparse: Few edges (|E| << |V|²)
Dense: Many edges (|E| ≈ |V|²)
Special Graphs
Planar Graph:
Can be drawn without edge crossings
Euler's formula: V - E + F = 2
Eulerian Graph:
Contains a circuit that uses every edge exactly once
All vertices have even degree
Hamiltonian Graph:
Contains a cycle that visits every vertex exactly once
No simple characterization exists