图论

二次元眼里的图论：

算法中的图论：

图

图是由点和连接这些点的边组成的集合。

其中点集合用 $V$ 表示，边集合用 $E$ 表示，图用 $G$ 表示。

$G=(V(G),E(G))$ 表示一张图由它的点和边组成。

当图中的任意一条边 $e\in E$ 连接两个点 $(u_i,v_i)$ 。

如果任意一条边 $e(u_i,v_i)$，可以从 $u_i$ 到达 $v_i$（ $u_i\to v_i$ ），也可以从 $v_i$ 到达 $u_i$ （$v_i\to u_i$） ，那么称这张图是无向图，边是无向边。

如果任意一条边 $e(u_i,v_i)$，可以从 $u_i$ 到达 $v_i$（ $u_i\to v_i$ ），不可以从 $v_i$ 到达 $u_i$ （$v_i\to u_i$） ，那么称这张图是有向图，边是有向边。

存图

1、邻接矩阵

设一个二维数组 eg。

如果 $x$ 能通过一条边到达 $y$，则 $eg[x][y]=1$ 。

for(int i=1;i<=m;++i)
{
    int x,y;cin>>x>>y;//存在一条 x 到 y 的无向边
    eg[x][y]=eg[y][x]=1;
}

2、vector

以 $x$ 为下标的 vector 中保存 $x$ 出发能通过一条边到达的点 $y$ 。

vector<vector<int> > eg(n+1);
for(int i=1;i<=m;++i)
{
    int x,y;cin>>x>>y;//存在一条 x 到 y 的无向边
    eg[x].emplace_back(y);
    eg[y].emplace_back(x);
}

3、链式前向星

用链表的方式存边，不如直接 vector。

遍历

可以用递归的方式遍历：

void dfs(int now,int fa)//当前节点，从哪个节点来的
{
    vis[now]=1;//这里已经访问过了，如果是树则不必写这句
    for(int t:eg[now])//以 vector 为例，这条语句是遍历 eg[now] 中的元素
    {
        if(t==fa||vis[t]) continue;
        dfs(t,now);
    }
}

相邻

如果两个节点通过一条边直接相连，那么称这两个节点。

度数

与节点 $v$ 直接相连的边数称为该节点的度数，设为 $deg(v)$

如果是有向图：那么以该节点为起点的边数称为出度数，以该节点为终点的边数称为入度数。

握手定理：任何无向图 $G=(E(G),V(G))$，满足所有节点的度数之和等于边数的两倍， $\sum _{v\in V}deg(v)=2|E|$ 。

简单图

自环

一条边起点和终点相同的边，即 $e(v,v)$。

重边

两条边的起点和终点相同，即 $e_1=e_2=(u,v)$。

简单图

没有重边和自环的图。

有重边的自环的图称为多重图。

性质：至少有两个节点的简单无向图一定存在度数相同的节点。

证明：简单无向图每个节点的度数范围是 $1\sim n-1$ ，一共有 $n$ 个节点，根据鸽巢原理。

路径

路径

一连串相邻节点组成的序列：

设路径 $f=(v_1,v_2,v_3,\dots v_m)$，其中，对于任意 $1\le i<m$，都有 $v_i$ 和 $v_{i+1}$ 相邻，且 $v_i$ 两两不同。

环

对于一条路径，$v_1=v_m$。

子图

从 $G=(E,V)$ 中，选择 $E$ 的子集 $E^{\prime }$ 和 $V$ 的子集 $V^{\prime }$ ，组成的图 $G^{\prime }=(E^{\prime },V^{\prime })$ ，称为 $G$ 的子图。

连通

无向图

对于无向图 $G=(E,V)$ ：

如果两个节点 $u,v$ ，存在一条路径$f$ ，使得 $v_1=u,v_m=v$ ，则 $(u,v)$ 是连通的。

若无向图 $G$ 中所有节点都是连通的，则 $G$ 是连通图。

若 $H$ 是 $G$ 的一个子图，且 $H$ 是连通的，则 $H$ 是一个连通子图。

如果 $H$ 不能再加入 $G$ 的任何一个节点和边，使得加入后的 $H$ 是连通的，则称 $H$ 是 $G$ 的一个极大连通子图（连通分量）。

有向图

对于有向图 $G=(E,V)$ ：

如果两个节点 $u,v$ ，存在一条路径$f$ ，使得 $v_1=u,v_m=v$ ，则称 $u$ 可达 $v$。

若有向图中的所有节点互相可达，则称 $G$ 是强连通的。

若有向图的所有边替换成无向边后是连通图，则称 $G$ 是弱连通的。

如果 $H$ 不能再加入 $G$ 的任何一个节点和边，使得加入后的 $H$ 是强连通/弱连通的，则称 $H$ 是 $G$ 的一个极大连通强/弱子图（强/弱连通分量）。

割

见连通性问题。

稀疏图/稠密图

一张图的边数远小于点数的平方，则称稀疏图。

一张图的边数接近点数的平方，则称稠密图。

没有明确的划分概念，凭感觉。

补图

对于原来的图。

如果一条边原本不存在，则补图中存在。

如果一条边原本存在，则补图中不存在。

反图

对于原有向图中的每一条都将反向反转得到的图。

特殊图

完全图

$G=(V,E)$

设 $n=|V|,m=|E|$。

任意两个点之间都有边相连。

竞赛图

有向简单图，且任意两点之间都恰好存在一条有向边。

树

$m=n-1$

边数等于点数减一的连通图。

性质：若图是无向图，则任意两点之间恰好存在一条路径相连。

树根：钦定的树的起始节点。

深度：该节点与树根之间路径上的点数（树根的深度认为是 $1$）。

儿子：与该节点相连直接的远离树根的节点。

父亲：与该节点相连的靠近树根的一个节点。

祖先：该节点与树根的路径上（包括树根，不包括自己）的节点。

子树：某个节点的子树表示该节点删除去父亲相连的边后，剩下的以该节点为根的树。

子节点：子树中的节点。

遍历一棵树：

void dfs(int now,int fa)//当前节点，从哪个节点来的
{
    str[now]=1;
    for(int t:eg[now])//以 vector 为例，这条语句是遍历 eg[now] 中的元素
    {
        if(t==fa) continue;
        dfs(t,now);
        str[now]+=str[t];//统计每个节点有多少子节点。
    }
}

链

存在一个深度为 $n$ 的节点的树。

菊花图

除一个特定节点度数为 $n-1$ 外，其他节点度数都为 $1$ 的树（其他节点与一个特定节点相邻）。

在广义中，其他节点与特定节点的距离也很近的情况也可以称为菊花图。

基环树

$n=m$ 的连通图。

即恰好存在一个环的树。

森林

$m\le n-1$ 的且不存在环的图。

该图中存在着若干个不连通的树。

仙人掌

一张无向简单连通图，每个节点至多在一个环上。

二分图

图中的节点可以分为两部分 $V_1,V_2$，不存在边连接同一部分内部的两个点。

特殊的点集/边集

点支配集

选择一些点，使得任意一条边都有至少一个端点被选中。

边支配集

选择一些边，使得任意一个点都有至少一条相连的边被选中。

点独立集

选择一些点，使得这些点两两不相邻。

边独立集

选择一些边，使得这些边没有公共端点。

团

选择一些点，使得这些点两两之间都有边连接。