Graph Theory
This page contain my notes for my design & analysis of algorithm class where I learned about graph theory.
Graph theory is the study of graphs, a mathematical structure used to model pairwise relations between objects. In this context, a graph is made up of vertices, also called nodes or points, which are connected by edges, also called arcs, links, or lines. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically.
Directed Graph
A directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs. A directed graph may contain a cycle.
A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
Directed Acyclic Graph
A directed acyclic graph (DAG) is a directed graph with no directed cycles. It consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions
Each edge has an orientation, from one vertex to another vertex. The path is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence.
Connected Graph
Semi-Connected
A semi-connected graph means that for every pair of vertices (x,y), either there exists a path from x to y or a path from y to x with all steps of the path obeying the directionality of edges.
Weakly-Connected
A weakly-connected graph means that if you replace all the directed edges with undirected edges then the resulting undirected graph is connected.
Strongly-Connected
A graph is strongly connected if there is a path in each direction between each pair of vertices of the graph such as a path that exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first.
Topological Ordering
A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. In other words, topological ordering is a graph traversal in which each node v is visited only after all its dependencies are visited.
A directed graph can be topologically ordered if and only if the graph has no directed cycles, only if and only if it is a directed acyclic graph. Topological ordering is possible even when the directed acyclic graph has disconnected components.
Depth-First Search
Depth-first search searches “deeper” in the graph whenever possible. It does explore edges out of the most recently discovered vertex v, which still has unexplored edges leaving it. Once all of v’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered until all vertices that are reachable from the original source vertex have been discovered.
Minimum Spanning Tree (MST)
A minimum spanning tree is a subset of the edges of a connected, weighted, and undirected graph that connects all the vertices together without anything cycle and with the minimum possible total edge weight. A graph is a spanning tree when the sum of all edges weight (path between nodes) is as small as possible.
Possible Multiplicity
If there are n vertices in the graph, then each spanning tree has n-1 edges. There may be more than one minimum spanning tree if the same weight, in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum.
Single Source Shortest Path Algorithms
Dijkstra Algorithm [1959]
Let G = (V, E) be a weighted graph.
The edges in G have weights.
Can be directed/undirected.
Can be connected/disconnected.
Let S be a special vertex: S = Source
Target: For each vertex V, compute the length of the shortest path from S to V.
Dijkstra Pseudocode:
Relaxing a node means that from this node, you cannot go anywhere else. (1) -> (2) -> (5) then (1) -> (6) you can relax node (2) because only one path from (2) to (5). If a node has been relaxed, you cannot update its weight afterward, thus Dijkstra algorithm won’t work all the time.
Dijkstra Algorithm time complexity is O(n^2).
Bellman Ford [1958 - 1962]
When you have negative edges, you need an algorithm to make sure your answers are correct. That algorithm is the Bellman-Ford Algorithm.
The Bellman-Ford algorithm is a way to find single source shortest paths in a graph with negative edge weights (but not negative cycles). If there is a negative weight cycle in the graph, the algorithm will not work.
Relax all edges (n-1) times when n = |V|
Similar to the Dijkstra algorithm, you update the weight from node to node, then run again from the root to nodes to find the shortest path.
Bellman-Ford Algorithm time complexity is also O(n^2).
Last updated
