Chap6 图 ¶

概念 ¶

图（graph） G= 由顶点（vertex）的集合 V 和顶点对称为边（edge）的集合 E 定义

邻接（ada）

邻接到 邻接于 度 deg 环为顶点的度有双倍贡献 孤立点 \(deg=0\) 悬挂点 \(deg=1\) 握手定理 无向图有偶数个度为奇数的顶点 入度（in-degree） \(deg^{-}(v)\) 出度（out-degree）\(deg^{+}(v)\) 环对入度和出度的贡献均为1

特殊简单图 ¶

完全图（complete graph） \(K_n\) 圈图（cycle） \(C_n\) 轮图（wheel）\(W_n\) \(n\)立方体图（n-cube） \(Q_n\)

完全二分图（complete bipartite graph） \(K_{m,n}\) 二部图判定 当且仅当G中无奇数长度的回路 完全匹配 霍尔婚姻定理

构图 ¶

生成子图 导出子图

无向图的描述 ¶

邻接矩阵（adjacent matrix）¶

邻接链表（adjacency list）¶

邻接数组（）¶

连通性 ¶

连通性（connectivity） 无环性（acyclicity）

连通分支 割点 割边/桥 点连通度 \(\kappa (G)\) 边连通度 \(\lambda(G)\) \(\kappa(G)<\lambda(G)<min\ deg(v)\) 有向图连通性 弱连通 无向图连通 单向连通 单向可达 强连通 a->b,b->a

匹配 ¶

Hall 定理：v1 任意 k 个顶点与 v2 至少 k 个顶点相连

通路 ¶

• 欧拉通路 恰有两个度为奇数的顶点
• 欧拉回路 每个顶点的度都为偶数（有向图基图为连通图，且所有顶点出入度都相等）
• 哈密顿通路 >=n-1
• p(G-v1)<=|v1|+1)
• 哈密顿回路 >=n
• 必要条件 p(G-V1)<=|v1|)p 为连通分支数量
• 有桥非哈密顿图 欧尔定理 deg(u)+deg(v)>=n 狄拉克定理 deg(v)>=n/2

最短通路问题 ¶

迪克斯特拉算法（Dijkstra's algorithm） 旅行商问题

平面图 ¶

面与次数关系：平面图各面次数之和等于边数的两倍 欧拉公式 r=e-v+2 r为面数，G为连通平面简单图 推论 v>=3 则 \(e\le3v-6\) 推论 有度数不超过5的顶点 推论 v>=3 且没有长度为 3 的回路，则\(e\le2v-4\) 库拉图斯基定理 初等细分得到的图为同胚的 非平面图当且仅当包含一个同胚于\(K_{3,3}\)和\(K_5\)的子图 平面图无子图可同胚或收缩为\(K_{3,3}\)和\(K_5\)的子图

图着色 ¶

对偶图 ¶

任意 map 均可构造为 graph

• 用顶点表示区域
• 用边表示这些区域的公共边界
• 这样构造的图称为对偶图（dual graph）

着色数（chromatic number）：对图上色所使用的最少颜色数量，使得任意两个相邻顶点颜色相异，记作 \(\chi(G)\)

对任意图（无自环无向图），\(\chi(G) \le \Delta(G)+1\)

Welsh-Powell 算法 ¶

1. 将当前未着色顶点按度数降序排列
2. 将第一个染为一种未使用的颜色
3. 顺序遍历接下来的顶点，若当前点和所有与第一个点颜色相同的点不相邻，则将该点染成与第一个点相同的颜色
4. 若仍有未着色的点，则返回步骤 1，否则结束

评论区