图#

图(graph)是一个二元组$G = (V, E)$, 其中$V$非空, 称为点集, $E$称为边集.

当$V$与$E$均为有限集合时称为有限图, 否则称为无限图.

图可以被简单分类为无向图, 有向图和混合图.

每条边可以赋权.

图的顶点数量被称为图的阶.

相邻#

无向图中, 若存在连边$e = (u, v)$, 则称$u$或$v$与$e$是关联的(或相邻的), $u$与$v$是相邻的. $u$的邻居(邻域)指的是其所有相邻顶点组成的集合, 记作$N(u)$. 对于点集$S$来说, 其邻居(邻域)指的是其所有顶点的邻居取并集得到的集合, 记作$N(S)$.

简单图#

自环: 对于边$e = (u, v)$, 若$u = v$则称$e$是一个自环.

重边: 若图中存在两条相同的边, 则称它们为一组重边.

无自环和重边的图被称为简单图. 否则被称为多重图.

具有至少两个顶点的简单无向图中一定存在度相同的点.

度数#

与顶点$v$关联的边数称为顶点$v$的度, 记作$d(v)$, 特别地, 每个自环会对度数产生$2$的贡献, 而非$1$.

对于无向简单图, 有$d(v) = |N(v)|$.

若$d(v) = 0$, 则称$v$为孤立点; 若$d(v) = 1$, 则称$v$为叶节点/悬挂点. 若$d(v)$为偶数, 则称$v$为偶点, 若$d(v)$为奇数, 则称$v$为奇点.

若$v$与其他所有顶点相连, 则称$v$为支配点. 在无向简单图中支配点的度数为$|V| - 1$.

握手定理(图论基本定理): 对于无向图, 所有顶点的度数之和等于两倍边的数目.

推论: 任意图中奇点有偶数个.

图$G$中所有节点度数的最小值称为图$G$的最小度, 记作$\delta(G)$; 所有节点度数的最大值称为图$G$的最大度, 记作$\Delta(G)$.

在有向图中, 出边数量被称为出度, 记作$d^+(v)$, 入边数量被称为入度, 记作$d^-(v)$. 显然有$d^+(v) + d^-(v) = d(v)$.

对于任何有向图, 有$\displaystyle \sum_{v\in V}d^+(v) = \sum_{v\in V}d^-(v) = |E|$.

若图$G$中所有节点的度数均为$k$, 则称$G$为k-正则图.

如果给定序列$a$, 可以找到某个图$G$使得$G$以$a$为度数列, 则称$a$是可图化的; 如果能找到简单图以其为度数列, 则称$a$是可简单图化的.

路径#

途径(walk): 连接一连串顶点的边的序列. 边的数量称作途径的长度.

迹(trail): 若途径中不存在相同的边, 则称为迹.

路径(path)或称简单路径(simple path): 若迹中连接的点序列两两不同, 则称为路径.

回路(circuit): 若迹起点与终点相同, 则称为回路.

环(cycle)或称简单回路(simple circuit): 若回路删去起点和终点后形成一条路径, 则称该回路为一个环.

子图#

若图$G, H$满足$V(H)\subset V(G)$, $E(H) \subset E(G)$, 则称$H$是$G$的子图, 记作$H\subset G$.

若对于$H\subset G$, 满足$\forall u, v\in V(H)$, 只要$(u, v)\in E(G)$, 就有$(u, v)\in E(H)$, 则称$H$是$G$的导出子图/诱导子图(induced subgraph). 容易发现一个图的导出子图只由点集决定, 因此$G$的点集为$V'$的导出子图可以记作$G[V']$.

若对于$H\subset G$, $V(H) = V(G)$, 则称$H$是$G$的生成子图(spanning subgraph).

若无向图$G$的某个生成子图$F$为k-正则图, 则称$F$是$G$的一个k-因子.

对于有向图$G$的某个导出子图$G[V^*]$, 若$V^*$中所有点在$G$中的出边都被保留到了$G[V^*]$中, 则称$G[V^*]$是$G$的一个闭合子图.

连通#

对于无向图: 若存在点$u$到点$v$的途径, 则称$u$与$v$连通. 由定义, 一个点与自己是连通的. 若无向图$G$中任意两个顶点均连通, 则称$G$是连通图, $G$具有连通性. 极大连通子图称为连通分量.

对于有向图: 若存在$u$到$v$的途径, 则称$u$可达$v$; 若节点两两互相可达, 则称该图为强连通图; 若将有向边替换为无向边后形成连通图, 则称该图为弱连通图. 类似地可以定义强连通分量和弱连通分量的概念.

邻接表#

使用结构体定义边, 使用的时候直接结构化绑定auto [y, dy] : adj[x]即可.

1
struct Edge {
2
    int to;
3
    int w;
4
};
5
// 带权图
6
vector<Edge> adj[N];
7
inline void buildgraph(int n) {
8
    for (int i = 0; i <= n; i++) adj[i].clear();
9
}

DFS#

1
// vector<Edge> adj[N];
2
auto dfs = [&](int s) -> void {
3
    stack<int> st;
4
    vector<bool> vis(n + 1, 0);
5
    st.push(s);
6
    while (!st.empty()) {
7
        int x = st.top();
8
        st.pop();
9
        if (vis[x]) continue;
10
        vis[x] = 1;
11
        for (const auto& [y, dy] : adj[x]) {
12
            if (!vis[y]) st.push(y);
13
        }
14
    }
15
};

BFS#

1
// vector<Edge> adj[N];
2
auto bfs = [&](int s) -> void {
3
    queue<int> q;
4
    vector<bool> vis(n + 1, 0);
5
    q.push(s);
6
    while (!q.empty()) {
7
        int x = q.front();
8
        q.pop();
9
        for (const auto& [y, dy] : adj[x]) {
10
            if (!vis[y]) {
11
                q.push(y);
12
                vis[y] = 1;
13
            }
14
        }
15
    }
16
};

拓扑排序#

得到有向无环图(DAG)的拓扑序列. 能够判断环. 进一步地, 拓扑排序可以用于解决有向无环图上的类DP问题. 如果某节点的状态只由其前驱节点决定, 那么就可以在拓扑排序中使用dp进行状态转移.

P1113 P4017 P1807

1
// vector<int> adj[N];
2
int ind[N];
3
vector<int> topseq;
4
auto toposort = [&]() {
5
    queue<int> q;
6
    for (int i = 1; i <= n; i++) {
7
        if (ind[i] == 0) {
8
            q.push(i);
9
        }
10
    }
11

12
    while (!q.empty()) {
13
        int x = q.front();
14
        q.pop();
15
        topseq.push_back(x);
16
        for (const auto& y : adj[x]) {
17
            // dp[y] = f(dp[x]);
18
            ind[y]--;
19
            if (ind[y] == 0) q.push(y);
20
        }
21
    }
22
    return topseq.size() == n;  // 拓扑排序是否成功, 不成功则说明有环.
23
};

全源最短路#

1
ll f[N][N];
2
auto floyd = [&](int n) -> void {
3
    // 初始化
4
    for (int i = 1; i <= n; i++) {
5
        for (int j = 1; j <= n; j++) {
6
            f[i][j] = INFLL;
7
        }
8
        f[i][i] = 0;
9
        for (const auto& [y, dy] : adj[i]) {
10
            f[i][y] = dy;
11
        }
12
    }
13

14
    // dp
15
    for (int k = 1; k <= n; k++) {
16
        for (int i = 1; i <= n; i++) {
17
            for (int j = 1; j <= n; j++) {
18
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
19
            }
20
        }
21
    }
22
};

单源最短路#

1
// const ll INFLL = 1e18;
2
// using ll = long long;
3
// vector<Edge> adj[N];
4
// vector<ll> dis;
5

6
auto dijkstra = [&](int s = 1) -> void {
7
    dis.assign(n + 1, INFLL);
8
    using pli = pair<ll, int>;
9
    priority_queue<pli, vector<pli>, greater<pli>> q;
10
    q.emplace(0, s);
11
    dis[s] = 0;
12
    while (!q.empty()) {
13
        auto [dx, x] = q.top();
14
        q.pop();
15
        if (dx > dis[x]) continue;      // lazy deletion
16
        for (const auto& [y, dy] : adj[x]) {
17
            if (dis[x] + dy < dis[y]) {
18
                dis[y] = dis[x] + dy;
19
                q.emplace(dis[y], y);
20
            }
21
        }
22
    }
23
};