图（Graph）

\(G=(V,E\text{ or }\overrightarrow{E})\)

Two standard ways to represent a graph, adjacency list or matrix. (alternative: node-arc adjacency matrix)
Adjacency list is more compact to represent sparse graphs, whose \(|V|^2\) is much more than \(|E|\). But when \(|V|^2\) is close to \(|E|\) in a dense graphs, or when you need to check edges quickly, adjacency matrix is prefered. For adjacency matrix representation of an undirected graph, \(A=A^T\). Memory could be cut to half.
Graphs could be directed or undirected. If edge (u,v) exists in u's adjacency list of an undirected graph, edge (v,u) must also exist in v's adjacency list. We can also say that edge (u,v) is unordered in undirected graph.
If (u,v) is an edge in a directed graph, we say that (u,v) is incident from or leaves vertex u and is incident to or enters vertex v. If (u,v) is an edge in a undirected graph, we say that (u,v) is incident on vertices u and v.
DAG: Directed Acyclic Graph.
BFS: Breadth-First Search.
DFS: Depth-First Search.
An undirected graph is connected if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected. If a directed graph is not strongly connected, but the underlying graph (without direction to the arcs) is connected, then the graph is said to be weakly connected.
The connected components of an undirected graph are the equivalence classes of vertices under the "is reachable from" relation. The strongly connected components of a directed graph are the equivalence classes of vertices under the "are mutually reachable" relation.
A complete graph is an undirected graph in which there is an edge between every pair of vertices. So, a complete graph is connected and is often referred to as a clique since it represents a group of vertices where each pair is connected.
MST: Minimum Spanning Tree.
An acyclic undirected graph is a forest, and a connected acyclic undirected graph is a (spanning) tree. In spanning tree, \(|E|=|V|-1\).
The degree of a vertex (\(d_v\)) in an undirected graph is the number of edges incident on it. A vertex whose degree is 0 is isolated. In a directed graph, the out-degree of a vertex is the number of edges leaving it, and the in-degree of a vertex is the number of edges entering it. The degree of a vertex in a directed graph is its in-degree plus its out-degree.
For an undirected graph, \(\sum_{v\in V}d_v=2|E|\).
An undirected graph is bipartite if V can be partitioned into two sets and all edges go between the two sets.

Weighted or Unweighted, Directed or Undirected，其实都一样。Unweighted可以认为所有Weight都相等，Undirected可以认为每条Edge都是双向的。这样就理解了好些个图论中的基础算法，本质上都是一样的！

-- 目录[0] --

-- 文章[6] --