图论（1）

DuskDawn · 2022-11-10 21:30:46 · 个人记录

本文介绍图的基础知识。

1.什么是图

图是由有限个数的顶点和边组成，通常表示为 G(V,E)。其中，G 是一个图,V 是图 G 中的顶点集，E 是图 G 中的边集。

2.图的一些定义和概念

无向图：边没有方向（无向边，用圆括号将两端的顶点括起来： (V_i,V_j)，其中 (V_i,V_j) 和 (V_j,V_i) 是同一条边），可以从起点到终点，反之亦然（如下图）。
有向图：边有方向（有向边，用尖括号将两端的顶点括起来：\left\langle V_i,V_j\right\rangle，其中 \left\langle V_i,V_j\right\rangle 和 \left\langle V_j,V_i\right\rangle 是两条边），只能沿边（箭头）的方向走，反之不行（如下图，只能从 4 走到 1，不能从 1 走到 4）。
完全图：一个 n 阶的有向完全图包含 n(n-1) 条边，一个 n 阶的无向完全图包含 \frac{n(n-1)}{2} 条边。
稠密图：一个边数接近完全图的图。
稀疏图：一个边数远远少于完全图的图。
度：无向图中与节点相连的边的数目，称为结点的度。
入度：有向图中，以这个节点为终点的边的数目。
出度：有向图中，以这个节点为起点的边的数目。
权值：写在边的旁边的数字，可以形象地理解为边的长度。
回路：起点和终点相同的路径，也叫“环”。
子图：图中取出的部分集合。如下图，图 2 就是图 1 的子图。
强连通分量：有向图中任意两点都联通的最大子图。如下图，1 - 2 - 5 构成一个强连通分量。特殊地，单个点也算一个强连通分量。

3.图的存储

一般使用二维邻接矩阵存图。定义 G[i][j] 表示 i 到 j 的边的权值，定义如下：

G[i][j]=\begin{cases}1 \text{或权值}&\text{当 vi 与 vj 之间有边或弧时，取 1或权值}\\0 \text{或} \infty&\text{ 当 vi 与 vj 之间无边或弧时，取 0或}\infty\end{cases}

以上三个图的邻接矩阵分别是：

G(A)=\begin{bmatrix}0&1&1&1\\1&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}G(B)=\begin{bmatrix}\infty&1&2\\1&\infty&3\\2&3&\infty\end{bmatrix}G(C)=\begin{bmatrix}\infty&\infty&2\\1&\infty&3\\\infty&\infty&\infty\end{bmatrix}

当然还有邻接表建图、链式前向星建图等存图方法，感兴趣自行查阅资料。

4.图的遍历

图有两种遍历方法：深度优先遍历和广度优先遍历。他们和深搜 Dfs、广搜 Bfs 相似（从任意一个点开始搜），比如第 2 节开头那一个无向图，它的深度优先遍历、广度优先遍历都是 1 - 2 - 4 - 3（这里从 1 开始搜，有多种遍历方式）。代码很简单，就不放了。

5.欧拉图

如果一个图存在一笔画，则该图叫做欧拉图，一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径就叫欧拉回路。

我们定义奇点是指度为奇数的点。对于能够一笔画的图，有以下两个定理：

存在欧拉路的条件：图是联通的，且只有 2 个奇点。
存在欧拉回路的条件：图是联通的，且没有奇点。这就是著名的欧拉定理。定理很好证明：对于欧拉路，除了起点和终点，其他点肯定是进去一次，出来一次，肯定不是奇点。对于欧拉回路，所有点都是进去一次、出来一次，都不是奇点。

寻找欧拉路可以用 Dfs。如果有奇点，则从其中一个奇点开始 Dfs。否则从任意一个点开始 Dfs。时间复杂度 O(V+E)。

Code:

#include <iostream>
using namespace std;
int n,m,a[10][10],sum[10],vis[10],id=1,ci,c[10];
void dfs(int x)
{
    for (int i=1;i<=n;i++)
    {
        if (a[x][i])
        {
            a[x][i]=a[i][x]=0;//删边，避免重复
            dfs(i);
        }
    }
    c[++ci]=x;//记录路径（不可写在函数开头，否则文章末尾的数据可以 hack。请自行探究原理）
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int p,q;
        cin>>p>>q;
        a[p][q]=a[q][p]=1;
        sum[p]++;
        sum[q]++;
    }
    if (m<n-1)
    {
        cout<<-1;
        return 0;
    }
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (sum[i]%2)
        {
            id=i;
            cnt++;
        }
    }
    if (cnt!=0&&cnt!=2)
    {
        cout<<-1;
        return 0;
    }
    dfs(id);
    for (int i=1;i<=ci;i++)
    {
        cout<<c[i]<<" ";
    }
    return 0;
}

板子题：P1636

特别水，甚至连输出路径都不需要

hack:

练习

尝试画出一个图。

写出它的邻接矩阵。
判断它是不是欧拉图。
写出它的深度优先遍历和广度优先遍历。