第6章 图论

•
两个问题：
（1）经过每个顶点一次且仅一次； （2）代价最小的Hamilton回路。
(目前无有效的方法求解)
•
货郎问题（Traveling Salesman Problem）
一个货郎到各村去卖货，要求每个村子 至少去一次，最后返回出发点，为其设计一 种销售路线，使总耗时最短。
求解方法：把路线全排列，求其中最小的。
1930年，波兰数学家库拉托父斯基 (Kuratowski)证明了平面图可以画在平面上；
•
里程碑：1936年，匈牙利数学家寇尼希 (D.Konig)发表名著《有限图和无限图理论》 ，使得图论成为一门独立的数学学科；
蓬勃发展：1946年，随着世界上第一台计算机 的问世，使图论的发展突飞猛进。 其后，图论在现代数学、计算机科学、工程技 术、优化管理等领域有大用而得以大力发展。
图论第01讲
•
课程简介
▪ 《图论》是计算机科学与技术专业、信息 安全专业的选修课程。 通过本课程的学习，使学生对图论的 历史背景、研究内容、相关技术及其发展 有一个较为全面地了解，从而将所学知识 和技术运用于实际应用领域奠定基础。
•
▪ 本课程所介绍的内容包括：
图论的发展历程和经典问题； 图的基本概念； 有关树和图的算法； 网络流问题； 匹配问题、色数问题；
•如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?
•
不少数学家都尝试去解析这个事例。而 这些解析，最后发展成为了数学中的图论。
莱昂哈德·欧拉(Leonhard Euler)在1736 年圆满地解决了这一问题，证明这种方法并 不存在。他在圣彼得堡科学院发表了图论史 上第一篇重要文献。欧拉把实际的问题抽象 简化为平面上的点与线组合，每一座桥视为 一条线，桥所连接的地区视为点。这样若从 某点出发后最后再回到这点，则这一点的线 数必须是偶数。

若 i, j 中有奇数，比如 i 是奇数，则路 P 上 v0 到 vi 的一段与边 v0vi 构成一个偶圈； 若 i, j 都是偶数，则路 P 上 vi 到 v j 的一段与边 v0vi 及 v0v j 构成一个偶圈。证毕。 例 1.1.4 设 G 是简单图，若δ (G) ≥ 3 ,则 G 中各个圈长的最大公因数是 1 或 2。 证明：由上例知，G 中有长分别为 i + 1, j + 1和 j − i + 2 的圈。若 i + 1, j + 1， j − i + 2 三 数有公因数 m > 2 ，则 m | ( j − i) ，于是 m | 2 ，这是不可能的。因此 i + 1, j + 1， j − i + 2
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。

第6章图论一、内容提要1.图的定义定义1.(图的定义一)图G = (V, E)是一个系统，其中(1)V≠∅是一个有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G 的结点集；(2)E是一个有限集合；E中的每一元素e∈E都称为图G的一条边；E称为图G的边集。

定义2. (图的定义二)图G = (V, E)是一个系统，其中(1)V ≠∅是一有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G的结点集；(2)E⊆V⨯V是一有限集合，一个V上的关系；E中的每一元素(u,v)∈E都称为图G的一条边(这里u, v∈V)；E称为图G的边集。

定义3. (图的定义三)图G= (V,∑, E)是一个系统，其中(1)V ≠∅是一有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G的结点集；(2)∑是一有限集合；∑中的每一元素σ∈∑都称为图G中的一个标号；∑称为图G的标号集；(3)E ⊆V⨯∑⨯V是一有限集合，一个三元关系；E中的每一元素(u,σ ,v)∈E都称为图G的一条边或弧,此边起自u而终于v；称u是此边的起点，称σ是此边的标号，称v是此边的终点，起点和终点统称为边的端点(这里u, v∈V , σ∈∑)；E称为图G的边集。

定义4. (图的定义四)图G=(V,E, γ)是一个系统，其中(1)V ≠∅是一有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G 的结点集；(2)E是一个有限集合；E中的每一元素e∈E都称为图G的一条边；E称为图G的边集。

(3)γ是边到结点集的一个关联函数，即γ:E→2V(无向图) 或γ:E→ V⨯V (有向图) 。

一般来说，它将E中的每条边e∈E与结点集V中的一个二元子集{u,v}∈2V (或{u,v}⊆V)相关联或与结点集V上的一个二元组(u,v)∈V⨯V相关联，即γ(e)={u,v} (无向图) 或γ(e)= (u,v) (有向图) ，称u是此边的起点，称v是此边的终点，结点u和v统称为边的端点。

1 0 0 0 A 2 0 1 0
1 0 0 1 1 0 1 0
6.1有向图概述
定义 设D=<V,E>为有向图, V={v1, v2, …, vn}, 令 ={
称(pij)n n为D地可达矩阵, 记作P(D), 简记为P.
性质: P(D)主对角线上地元素全为1. D强连通当且仅当P(D)地元素全为1.
性质:
(1)
a n (1)
j1 ij
d (vi ),
i 1,2,..., n
(2)
a n (1)
i1 ij
d (v j ),
j 1,2,..., n
(3)
a(1) ij
m
D中长度为
1 的通路数
i, j
(4)
a n (1)
i1 ii
D中长度为
1 的回路数
6.1有向图概述
有向图地邻接矩阵 例:
6.2 最短路径
Dijkstra算法步骤: 1,初始化阶段,设置辅助数组Dist,其中每个分量Dist[k] 表 示当前所求得地从源点到其余各顶点 k 地最短路径。 除了起点A外,所有节点地距离Dist设置为无穷大。 一般情况下,Dist[k] = <源点到顶点 k 地边上地权值>
或者 = <源点到其它顶点地路径长度> + <其它顶点到顶点 k 地边上地权值>。 2,更新邻居地距离。
(3) 1地总个数等于-1地总个数, 且都等于m
(4) 平行边对应地列相同
6.1有向图概述
有向图地邻接矩阵
定义 设有向图D=<V,E>, V={v1, v2, …, vn}, E={e1, e2, …,
em},