当前位置：文档之家 › 图论有向图

图论有向图

  • 格式：pptx
  • 大小：611.18 KB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

chap14 有向图

chap14 有向图

19
有向H图的应用
任务的最佳排序问题：假设有任务t1, t2, …tn需在
同一设备上串行执行，从任务ti转到任务tj所需的 设备调整时间是aij，如何排任务执行次序，使设 备调整需时间最少？
1、建图：建立有向图D, 顶点对应于要执行的任务，
vivjA(D)当且仅当aijaji。边vivj带权aij。
T的高度为3 ;
T中的蓝色结点及弧构成 T的一个以v2为根的子树.
27
有序树
定义14.3.3：若对一个树T的结点(弧)从
上至下，同一层结点(弧)从左至右规定了 一个次序，则称T为有序树。 v0 有序树的编号：
v1 v2 v3
v21
v211 v212
v22
v213
v31
28
m元(有序)树
定义14.3.4：设T是(有序)树，m 1。
3 v3
D D’
17
竞赛图
竞赛图：完全图的定向图称为竞赛图。
n阶竞赛图可用来表示n个选手之间进行
循环赛的胜负状态。
有一人全胜，其余各胜 一场： 有一人全输，其余各胜 两场：
18
竞赛图都含有向H通路
有向图D的有向H通路是指一条包含D的所有顶
点的有向通路（有向哈密尔顿通路）。 推论14.2.1：每个竞赛图都含有向H通路。 证明：设D是竞赛图， D的基础图G是完全图， 于是， (G) = |V(D)| =p , 由定理14.2.1知，D中含长为p–1的有向通路， 也就是说，该通路上包含了所有的p个顶点， 即为有向H通路。
3(a). D 中任何一条有向(u, v)-通路(u≠v)P均满足 (u)≠(v) 3(b). D 中的任何弧(u,v) v 1 的首尾不同色 2 4. 总之，基础图G的 任何两个邻接的顶 点在下均不同色， 4 即是G的正常(k+1) v2 着色。 故k≥ (G) –1
图论第二章(1)

图论第二章(1)

12
m=|E1|+|E2| ≤ n1(n1-1)/2+ n2(n2-1)/2 ≤(n-1)(n1-1)/2+(n-1)(n2-1)/2 ≤(n-1)(n-2)/2， ，
2.2
道路与回路的判定
1.判定各点对间是否有道路相通:邻接矩阵方法 1.判定各点对间是否有道路相通: 判定各点对间是否有道路相通
有向图或无向图)的 设A＝(aij)n×n是图 有向图或无向图 的 ＝ × 是图G(有向图或无向图 邻接矩阵， 的长度为1的道路 邻接矩阵，则aij是vi到vj的长度为 的道路 (边)的条数。 的条数。 边 的条数 一般地， 一般地，设Ak＝( aij(k) )n×n ，则aij(k)是vi到 × vj的长度恰为 的道路的条数 k=1,2,…。 的长度恰为k的道路的条数 的道路的条数, 。 这可用数学归纳法予以证明： 这可用数学归纳法予以证明： 因为 Ak＝ Ak-1A, 所以
16
定义道路矩阵 定义道路矩阵P=(pij) n×n ，其中 道路矩阵 × , v 路 通 1 若 i , v j 有 相 pij = , v 路 通 0 若 i , v j无 相 则 P=A∨A(2)∨A (3)∨…∨A (n) ∨ ∨ (布尔运算 布尔运算) 布尔运算
17
v1
例 v2
命题：若简单 1 命题： 图G的每个结点 的每个结点 的度数≥ ， 的度数≥3，则G 中必含带弦的回 路。 5
3
4
6
证明： 证明：设 P=(e1,e2,…,ek)是G的一条最长 是 的一条最长 的初级道路， 的初级道路，e1=(v0,v1)。由于 为最长的 。由于P为最长的 初级道路，所以与v 初级道路，所以与 0有边相边的结点都在 P上。( 否则与 是最长的假设矛盾 否则与P是最长的假设矛盾 是最长的假设矛盾) 上 v0至少有三个相邻结点 1, vi, vj,它们与 1 至少有三个相邻结点v 它们与v 它们与 相连的边e 中最多有两个在P中 即 相连的边 1, e’, e”中最多有两个在 中,即 中最多有两个在 其中至少有一边不在P上 此边就是C的 其中至少有一边不在 上，此边就是 的 一条弦 一条弦。 v1 e2 e1 v0 e” e’
图论及其应用

图论及其应用


Prim算法及思想
• • • • • 首先我们将V分成两部分U,S U∩S=∅ U∪S=V 一开始S中只有任意以个节点 每次我们枚举每条U，S之间的边权最小的边S中 这条边的端点 删除并加入U • 我们可以每次更新S中点的这个值不需要每次枚 举边复杂度O(n^2) • 如果使用堆优化可以做到O(nlogn+nlogm)
tarjan算法
tarjan算法
拓扑排序
• 每次选择一个入度为0的点加入队列，然后 删掉这个点的所有出度
小试身手
• APIO2009 atm • 有一个城市有若干条有向道路 • 一个小偷从一个点出发想偷这个城ATM机， 他从一个点出发，最后偷完之后需要到一 个酒吧庆祝，给定道路情况，每个路口atm 的钱数和有没有酒吧，求最多能偷多少钱。 • n<=100000
小试身手
对于n<=1000我们依然可以直接暴力建出图 来进行Dijsktra算法但是对于n<=10000的测 试点，所有边一共有10^10条，我们无法存下 来但是我们发现，只有x坐标相邻和y坐标相 邻的边才有意义(为什么？)，然后就可以建出 图来用堆优化的Dij或者spfa过掉
小试身手
• 给你一个n个点的图，小Q有q个询问，每次 询问任意两点之间的最短路 • n<=200,q<=4000000
Байду номын сангаас
最短路算法
• 如果我们需要知道所有的点对之间的最短 路，可以使用floyed的传递闭包方法。 • floyed算法思想： • 我们每次选择一个中间点，然后枚举起点 和终点，用通过中间点的最短路径更新起 点和终点之间的最短路径时间复杂度O(n^3)
floyed代码实现
• 代码非常简单 • 注意枚举顺序
第7章 图论 [离散数学离散数学(第四版)清华出版社]

第7章 图论 [离散数学离散数学(第四版)清华出版社]


6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
21
例：
a j i h c g d
1(a)
无 向 图
b
f
e

2(b)
7(j) 8(g) 9(d) 10(i)
6(e)
3(c) 4(h)
5(f)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
22
例：
1(b)
有向图
第四部分：图论（授课教师：向胜军）
6
[定义] 相邻和关联
在无向图G中，若e=(a, b)∈E，则称a与 b彼此相邻(adjacent)，或边e关联 (incident) 或联结(connect) a, b。a, b称为边e的端点或 结束顶点(endpoint)。 在有向图D中，若e=<a, b>∈E，即箭头 由a到b，称a邻接到b，或a关联或联结b。a 称为e的始点(initial vertex)，b称为e的终点 (terminal/end vertex)。
证明思路：将图中顶点的度分类，再利用定理1。
6/27/2013 6:02 PM 第四部分：图论（授课教师：向胜军） 9
[定理3] 设有向图D=<V, E>有n个顶点，m 条边，则G中所有顶点的入度之和等于所 有顶点的出度之和，也等于m。
即：
d ( v i ) d ( v i ) m.
i 1 i 1
n
n
证明思路：利用数学归纳法。
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
10
一些特殊的简单图：
(1) 无向完全图Kn(Complete Graphs)
13级离散数学(3-1图论)

13级离散数学(3-1图论)


【作业6】在一个部门的25个人中间，由于意见不
同，是否可能每个人恰好与其他5个人意见一致？ 分析：考虑一个图，其中顶点代表人，如果两个人 意见相同，可用边连接，所以每个顶点都是5度。 解：令 25 个人分别为 v1 v2 …v25 . 则 degv1 = degv2 =…= degv25 =5 degv1 + degv2 +…+degv25 =125 是奇数 但在任何图中, 度数为奇数的结点必定是偶数， 所以是不可能的。
【作业5】求出下列各图的补图？
测试题
【测试题1】
a)画出无向完全图K4 和K6 并求出它们的边数。 b)画出完全二部图K4,2 ,和K3,3 并求出它们的边数。
【测试题2】
a)判断下列各图是否是（1）图的生成图、导出图或补图？ b)画出（1）图的补图，并求出完全图K5的边数。
例：G1是无向图，deg(v1)=3，deg(v2)=1
G2是有向图，deg+(v1)=3，deg-(v1)=2，
deg(v1)=5，
v1 v2 v1
G2
v2
v3
G1
d(v1)＝3(注意，环提供2
度)， v2是悬挂顶点，
v4
【作业4】求下列各图顶点的度数
【注意】d-(a)＝4，d+(a)＝1
(环e1提供出度1，提供入度1) d(a)＝4+1＝5。
【说明】无向完全图：每一条边都是无向边不
含有平行边和环，每一对顶点间都有边相连。
完全图举例
K5
3阶有向完全图
4阶有向完全图
n阶无向完全图的边数为：
n(n-1)/2
【作业2】画出无向完全图K3 ,K4 和K6 并求出
它们的边数。
《离散数学》第6章 图的基本概念

《离散数学》第6章 图的基本概念


E ' E )。
生成子图—— G ' G 且 V ' V 。
导出子图 ——非空 V ' V ，以 V ' 为顶点集， 以两端均在 V ' 中的边的全体为边集的 G 的 子图，称 V ' 的导出子图。 ——非空 E ' E ，以 E ' 为边集，以
E ' 中边关联的顶点的全体为顶点集的 G 的子
0 vi与ek 不关联 无向图关联的次数 1 vi与ek 关联1次 2 v 与e 关联2次(e 为环) i k k
1 vi为ek的始点 有向图关联的次数 0 vi与ek 不关联 1 v 为e 的终点 (无环) i k
点的相邻——两点间有边，称此两点相邻 相邻 边的相邻——两边有公共端点，称此两边相邻
孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边 为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所
对应的边叫悬挂边。
(3) 平行边——关联于同一对顶点的若干条边 称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。
简单图——不含平行边和环的图。
如例1的(1)中，
第六章 图的基本概念 第一节 无向图及有向图
内容：有向图，无向图的基本概念。
重点：1、有向图，无向图的定义， 2、图中顶点，边，关联与相邻，顶点 度数等基本概念，
3、各顶点度数与边数的关系
d (v ) 2m 及推论，
i 1 i
n
4、简单图，完全图，子图， 补图的概念， 5、图的同构的定义。
一、图的概念。 1、定义。 无序积 A & B (a, b) a A b B 无向图 G V , E E V & V ， E 中元素为无向边，简称边。 有向图 D V , E E V V ， E 中元素为有向边，简称边。
第8章_有向图

第8章_有向图



图论及其应用
5
8.1 有向图——习题




10.1.1. 一个简单图有多少个定向图？ 10.1.2. 证明： = = 。 10.1.3. 设有向图D中无有向圈，则 d (v ) d (v ) v V v (a) = 0V； (b) 存在一个顶点排序v1，……，v ，使对1 i ，每条 以vi为 头的弧其尾都在{v1，……，vi-1} 中。 10.1.4. 证明：D是双向连通的 D是连通的，且D的每个块 是双向连通的。 10.1.5. D的逆图 是把D中每弧的方向都改为其反向所得的 有向图。试用逆图慨念及习题10.1.3.(a) 来证明： 若有向图D中 无有向圈，则+ = D 。 0 10.1.6. 证明：严格有向图包含长 max{ ，+}的有向路。 10.1.7. 证明：严格有向图中若max{ ，+} = k 1，则 D包含长 k+1 的有向圈。
图论及其应用
第8章 有向图
8.1 有向图
有向图（directed graph；digraph） D =（V，A） V(D) —— 顶点集。 a u v A(D) —— 弧集。 弧a = (u,v)：其头为v，其尾为u； 弧a从u连到(join to)v。 有向子图（subdigraph） 有向图D的基础图（underlying graph） 对应于D的无向图G（称D为G的一个定向 （orientation）图）
8.1 有向图


易见，有向图D = (V, A)中顶点间的双向连通性是V上 的一个等价关系，它的等价类确定了V的一个划分 （V1，……，Vm）， 使顶点u与v双向连通 u与v 同属某等价类Vi 。 称每个导出子图D[V1]，……，D[Vm]为有向图D的一 个双向分支（dicomponent；strong component）。 当D只有一个双向分支时，称D为双向连通的。 易见，D的任二双向分支之间的弧都是同一个方向的。 例
《离散数学》图论 (上)

《离散数学》图论 (上)

12
无向图与有向图
v2
e1
e2
e3
v3
e4
v1
e5 (e1)={( v42, v24 )}
v4
(e2)={( v32, v23 )} (e3)={( v3, v4 )}
(e4)=({ v43, v34 )}
(e5)=({ v4,}v4 )
13
无向图与有向图
A B C
D E F
14
无向图与有向图
第八章 图论
第八章 图论
§8.1 基本概念
§8.1.1 无向图、有向图和握手定理 §8.1.2 图的同构与子图 §8.1.3 道路、回路与连通性 §8.1.4 图的矩阵表示
§8.2 欧拉图 §8.3 哈密尔顿图 §8.4 平面图 §8.5 顶点支配、独立与覆盖
2
无向图与有向图
3
无向图与有向图
一个无向图（undirected graph, 或graph） G 指一个三元组 (V, E, )，其中
vV
vV
24
特殊的图
假设 G=(V, E, ) 为无向图，若 G 中所有 顶点都是孤立顶点，则称 G 为零图（null graph）或离散图（discrete graph）；若 |V|=n，|E|=0，则称 G 为 n 阶零图 所有顶点的度数均相等的无向图称为正 则图（regular graph），所有顶点的度数 均为 k 的正则图称为k度正则图，也记作 k-正则图 注：零图是零度正则图
19
握手定理
定理（图论基本定理/握手定理）
假设 G=(V, E, ) 为无向图，则deg(v) 2 E ， vV
即所有顶点度数之和等于边数的两倍。
推论
在任何无向图中，奇数度的顶点数必是偶 数。
第七章 第一讲 无向图及有向图

第七章 第一讲 无向图及有向图


完全图举例
K5
3阶有向完全图
4阶竞赛图
子图(subgraph)
定义8 设G＝<V,E>，G＝<V ,E>为两个图(同为无 向图或同为有向图)，若V V且E E，则称G 是G的子图，G为G 的母图，记作G G。 若V V或E E，则称G 为G的真子图。
若et∈E，使得et＝<vi，vj>，则称vi为et的始点，vj为 et的终点，并称vi邻接到vj，vj邻接于vi。
若ek的终点为el的始点，则称ek与el相邻(adjacent)。 el ek vi vj
定义3 在无向图中，关联一对顶点的无向边如果多于1条 ，则称这些边为平行边，平行边的条数称为重数。
3
欧拉：传奇的一生
年少时，听从父亲的安排，巴塞尔大学，学习神学和希伯来语 ，结果被约翰· 伯努利欣赏，17岁获得硕士学位之后，才开始 专供数学。
为获得圣彼得堡科学院的医学部的职位空缺，欧拉在巴塞尔便 全力投入生理学的研究，并出席医学报告会。1727年，等他到 达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。 1733年，欧拉回到瑞士，并结婚，一生共生育13个孩子，5个 存活。 为了赢得巴黎奖金而投身于一个天文学问题，那是几个有影响 的大数学家搞了几个月时间的，欧拉在三天之后把它解决了。 可是过分的劳累使他得了一场病，病中右眼失明了。 欧拉到底出了多少著作，直至1936年人们也没有确切的了解。 但据估计，要出版已经搜集到的欧拉著作，将需用大4开本60 4 至80卷。彼得堡学院为了整理他的著作整整花了 47年。
解： (3,3,2,1)，(3,2,2,1,1) 不可以图化
(3,3,2,2)可以图化
(3,2,2,2,1)可以图化
图论讲义第8章-有向图

图论讲义第8章-有向图


A = {< v1 , v2 >, < v2 , v3 >, < v2 , v3 >, < v3 , v4 >, < v3 , v5 >, < v1 , v5 >, < v1 , v5 >, < v5 , v5 >} 。
这便定义出一个有向图。 注： （1）相应地，前面所说的边不带有方向的图称为无向图。 （2）一个无向图 G 可以对应若干个有向图，它称为所对应的有向图的基础图或底图。 （3）将有向图的顶点可用平面上的一个点来表示，弧可用平面上的有向线段来表示（直 的或曲的） ，这样画出的平面图形称为图（有向图）的图示。 （4）对一条弧 e=<u, v>，其第二分量顶点 v（即箭头指向的顶点）称为它的首顶点，另一 顶点称为它的尾顶点。一条首尾顶点相同的弧称为环弧（如下图中 e8） ，两条具有相同首顶 点和相同尾顶点的弧称为并行弧（如下图中 e2 和 e3） 。既无环弧又无并行弧的有向图称为简 单有向图（或严格有向图） 。 例如，例 8.1.1 中有向图的一个图示为 e1 v2 e2 e3 v3 v1 e6 e5 e4 e7 v5 v4
§8.4 Euler 有向图和 Hamilton 有向图
定义 8.4.1 经过有向图 G 的所有弧恰一次的有向迹称为 G 的一条 Euler 有向迹。经过有向图
G 的所有弧恰一次的有向闭迹称为 G 的一条 Euler 有向闭迹。存在 Euler 有向迹的有向图称
为 Euler 有向图。经过有向图 G 的所有顶点恰一次的有向路称为 G 的一条 Hamilton 有向路； 经过有向图 G 的所有顶点恰一次的有向圈称为 G 的一个 Hamilton 有向圈。存在 Hamilton 有 向圈的有向图称为 Hamilton 有向图。 定理 8.4.1 非平凡弱连通有向图 G 是 Euler 有向图的充分必要条件是对任何 v ∈ V (G ) ，都 有 d (v ) = d (v ) 。
第八章图论

第八章图论


3. 图的结点与边之间的关系 定义 如果边e={vi,vj}是G的边, 则称结点vi 和vj邻接的, 边e和结点vi ，边e和结点vj称为关联的。 没有与边关联的结点称为孤立点。 关联于同一结点的相异边称为邻接的。 不与任何边邻接的边称为孤立边。
例1
在上图中显然e1和e2, e1与e4是邻接的, 结点v1和v2,v2和v4等是邻接的, 没有孤立点和孤立边。
例2.如下图中:
图(a)是伪图。图(b)是有向多重 图。 最右第三个图是简单图有权图。
三、结点的度
1.定义 图G中关联于结点vi的边的总数称为 结点vi的度, 用deg(vi)表示。
2.定理1(握手定理) 图G的所有结点的度的总和为边数 的二倍。即若G为具有n结点的(n,m)图, 则有： n deg(vi ) 2m
例8 如下图
(a)是连通图。 (b)是一个具有三个分图 的非连通图。 结论： (1)一个图的分图必是连通的； (2)一个连通图一定只能有一个分图。
例11 对于图的连通性，常常由于删除了 图中的结点和边而影响了图的连通性。
在连通图(a)中删除边e后, 则变成了不连通 的图(b)。
8.2 图的矩阵表示
2. 有向图的定义 定义 设G=(V,E), V是一个有限非空集合, E是V中不同元素的有序对偶的集合, 则称G是一有向图。在有向图G中 若vi≠vj,则(vi,vj)和(vj,vi)表示两条 不同的边,且用一个从结点vi指向vj 的箭头表示边(vi,vj)。
定义 具有n个结点和m条边的图称为(n,m)图。 (n,0)图称为零图。(1,0)图称为平凡图。
三、边割集、点割集 定义3 设图G=<V,E>是连通图,若有E的子集S, 使得在图G中删去了S的所有边后, 得到的子图G-S变成具有两个分图的不连通图, 删去了S的任一真子集后所得子图仍是连通图， 则称S是G的一个边割集。 注：割边是边割集的一个特例。

图的基本概念 无向图及有向图


d (v4)=4
d (v5)=2
31
最大(出/入)度,最小(出/入)度
在无向图G中， 最大度: Δ(G) = max{ dG(v) | v∈V(G) } 最小度: δ(G) = min{ dG(v) | v∈V(G) } 在有向图D中， 最大出度: Δ+(D) = max{ dD+(v) | v∈V(D) } 最小出度: δ+(D) = min{ dD+(v) | v∈V(D) } 最大入度: Δ-(D) = max{ dD-(v) | v∈V(D) } 最小入度: δ-(D) = min{ dD-(v) | v∈V(D) } + + - 简记为Δ, δ, Δ , δ , Δ , δ

i 1
i
证明 必要性。由握手定理显然得证。 充分性。由已知条件可知，d中有偶数个奇数 度点。 奇数度点两两之间连一边，剩余度用环来实现。
5 3
3
1
例7.1： 1. (3, 3, 2, 3), (5, 2, 3, 1, 4)能成为图的度 数序列吗？为什么？ 2. 已知图G中有10条边，4个3度顶点，其余顶点的 度数均小于等于2，问G中至少有多少个顶点？为 什么？ 解： 1.由于这两个序列中，奇数度顶点个数均为奇数， 由握手定理的推论可知，它们都不能成为图的度 数序列。 2.显然，图G中的其余顶点度数均为2时G图的顶点 数最少. 设G图至少有x个顶点. 由握手定理可知， 3×4+2×(x-4)=2 ×10 解得: x=8 所以G至少有8个顶点。
度数列举例
按顶点的标定顺序，度数列为 4,4,2,1,3。
度数列举例
按字母顺序， 度数列：5,3,3,3 出度列：4,0,2,1

5.图论


注意:在无向图中,无向边(a,b)是从顶点a到顶点b的 线段,无方向.在有向图中,有向边<a,b>是有方向的, 且箭头必须从a指向b.也常用e=<vi,vj>表示边.有时 用G泛指无向图或有向图,而D只能表示有向图. 几个概念: 设G=<V,E>为一无向图或有向图, (1)若V,E都是有穷集合,则称G是有限图. (2)若|V|=n,则称G为n阶图.(此处|V|表示V中元素个 数;这里n≥1) (3)若E=,则称G为零图(仅包含孤立结点的图).特别 的,若此时又有|V|=1,则称G为平凡图(只有一个结点 的图).
第三部分 图论
在计算机科学领域,如开关理论,逻辑设 计,形式语言,操作系统,编译程序,数据结 构和信息检索等,都以图论为工具来解决实 际问题和理论问题,图论有着广泛的应用. 图论的内容十分丰富,涉及面也比较广, 本部分所涉及的只是图论中最基本的,但在 实际中经常用到的知识.
第7章 图的基本概念
7.1 无向图和有向图
定义 一个无向图G是一个二元组<V,E>, 即 G=<V,E>,其中
(1)V是一个非空的集合(在图的运算中,有时产生 顶点集合为的结果,因而规定顶点集为的图 是无意义的),称为G的顶点集,V中元素称为顶 点或结点. (2)E是无序积V&V的一个多重子集(元素可重复出 现的集合为多重集),E中元素称为无向边,也简 称边. 在一个图G=<V,E>中,为了表示V和E分别为G的顶 点集和边集,常将V记成V(G),E记成E(G).
在上图中,(2),(3)均为(1)的子图,(3)是生成图,(2) 是顶点集{v1,v2}的导出子图,也是边子集{e4,e5}的 导出子图.(3)是边子集{e1,e3,e4}的导出子图. (5),(6)是(4)的子图,(5)是生成子图,也是边子集 {e1,e2}的导出子图.(6)边子集{e1}的导出子图.

离散数学第七章图的基本概念


4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

第8章 有向图


有向图 D
D 的双向分支
图论及其应用 4
8.1 有向图
− 入度（indegree）d D (v ) 。 入度 d+ 出度（outdegree） D (v ) 。 出度 记号 δ+，δ− ：最小出、入度； ∆+ ， ∆- ：最大出、入度。 称有向图D为严格的 严格的（strict） 严格的 ⇔ 无环、且不存在两弧其端点及方向相同。
定理10.1 (Roy,1967; Gallai,1968) 有向图 包含一 有向图D包含一 定理 长为 χ - 1 的有向路。 的有向路
证明：令D’ 为D的极大 极大无有向圈、有向生成子图（注：D’ 可由空生成子 极大 图作为开始，在保持无有向圈的条件下，通过逐步加弧而得） 。令k为D’ 中最长有向路的长。今用色1，2，……，k+1对D’ 进行顶点着色如下： 将v着以色i ⇔ D’ 中以v为起点的最长有向路的长为i 1。 来证这是D的正常(k+1)-顶点着色： 先证，D’ 中任一有向(u,v)-路P的起、终点u与v一定不同色：设v被着以色 i 。则由着色法知，在 D’ 中以v为起点的一最长有向路，设为，Q的长为i - 1 。由于D’ 中无有向圈，PQ为一有向路，起点为u，长 ≥ i 。从而u上的 色j > i。 只要再证，D中任一弧(u,v)的两端一定不同色：当 (u,v)为D’ 中的弧时， 它就是D’ 中的一有向(u,v)-路，从而u与v不同色。 9 图论及其应用
10.2 有向路
当 (u,v)不是D’ 中的弧时，由D′ 之极大性知 D’ + (u,v) 包含一有向圈C。于是， C - (u,v) 是 D’ 中的有向(v,u)-路，从而u与v也不同色。 由上述知，D为(k+1)-可着色的，因此 χ ≤ k+1 ，得k ≥ χ - 1 ， 故D中有长为χ - 1 的有向路。 #

与图论相关的算法

if map[q^.v].visited=false then dfs(q^.v); q:=q^.nextarc; end; end;
广度优先搜索
procedure bfs(i:integer); var p:arcptr;
closed,open:integer; q:array[1..maxn] of integer; begin 访问并处理顶点i; map[i].visited:=true; 顶点i进入队列q; closed:=0; open:=1; repeat
编号都不超过k的路径。 递推公式：
t(k)[i,j]= t(k-1)[i,j] or (t(k-1)[i,k] and t(k-1)[k,j])
Johnson算法
Johnson算法常用于求顶点个数较多的稀 疏图的每对点间最短路问题。
感兴趣的同学请参阅《国际信息学奥林 匹克竞赛指导——实用算法的分析与程 序设计》
inc(closed); v:=q[closed]; p:=map[v].firstarc; while p<>nil do begin
if map[p^.v].visited=false then begin 访问并处理顶点q^.v; map[q^.v].visited=true; inc(open); q[open]:=q^.v; end;
q:=q^.nextarc; end; until closed=open; end;
计算连通分支数
count:=0; for i:=1 to n do
map[i].visited:=false; for i:=1 to n do
if map[i].visited=false do begin inc(count); dfs(i); end;

总结-图论


生成树
设 T 为无向连通图 G 中一棵生成树，e 为 T 的任意一条弦，则 T ∪e 中含 G 中只含一条弦其余边均为树枝的圈，而且不同的弦对应的圈 也不同。
设 T 是连通图 G 的一棵生成树，e 为 T 的树枝，则G 中存在只含树 枝 e，其余边都是弦的割集，且不同的树枝对应的割集也不同。
r 叉完全正则树——树叶的层数均为树高的 r 叉正则树
r 叉完全正则有序树——r 叉完全正则树是有序的的
平面图
G 是可平面图或平面图——如果能将无向图 G 画在平面 上，使得除顶 点处外无边相交。
G 的平面嵌入——画出的无边相交的平面图。 非平面图——无平面嵌入的图。
K5 和 K3,3 都不是平面图。
平面图
(1)设 T 为根树，若将 T 中层数相同的顶点都标定次序，
则称 T 为有序树。 (2)分类：根据根树 T 中每个分支点儿子数以及是否有序 r 叉树——每个分支点至多有 r 个儿子
r 叉有序树——r 叉树是有序的
r 叉正则树——每个分支点恰有 r 个儿子 r 叉正则有序树——r 叉正则树是有序的
T 是 n (n≥2) 阶有向树， (1) T 为根树— T 中有一个顶点入度为 0， 其余顶点的入度均为 1
(2) 树根——入度为 0 的顶点
(3) 树叶——入度为 1，出度为 0 的顶点 (4) 内点——入度为 1，出度不为 0 的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T 中层数最大顶点的层数 (8) 根树——平凡树(规定)
d
i 1
n
i
0( mod 2)
图的基本概念
图同构、子图、生成子图、导出子图等。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

点v的出度与入度之和称为点v的度，记为d(v)。
d (v4 ) 2 d (v4 ) 2 d (v4 ) 4
v1
e4 v4
e7 e6
e5
v2 e1
e2
v3
有向图D
6
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
例1 一个简单图有多少个定向图？ 答：因为每条边有2种定向方式，所以共有2 m(G)种定向。 例2 求证：G存在一个定向图D，使得对 v V (D) ，有
例如：
v1 e4
e7 e6
v2
v4
e5
e3
e1
e2
v3
有向图D
e1 v3, v2
v3与v2分别是e1 的起点与终点。 定义2 在一个有向图D中，具有相同起点和终点的边 称为平行边。两点间平行边的条数称为该两点间的重数。
例如，在上图中，e6与e7是平行边。
4
1
0.5 n 0
0.5
1 2 1.5 t1
如果e是D的一条边，而u与v是使得фD(u,v)=e的顶点， 那么称e是由u连接到v，记为e=<u, v>。同时，称u为e的 弧尾(起点), v为e的弧头(终点)。
注：有向图可以简单地理解为“边有方向的图”。
3
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
d (v) d (v) 1
证明：不失一般性，设G是连通图。G中奇度顶点个数必 然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对 顶点间连一条边得到欧拉图G1。在G1中用Fluery算法求出G 的一欧拉环游C,然后顺次地在C上标上方向，由此得到C的 定向图C1。
在C1中，去掉添加的边后，得到G的定向图D.显然：
3) 若D的中任意两点是双向连通的，称D是强连通图；
D1
D2
D3
12
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
在上面三图中，D1是强连通的，D2是单向连通的，而D3 仅为弱连通图。
关于强连通图，我们有如下结论： 定理1： 有向图D=(V,E)是强连通的，当且仅当D中存在 包含D中所有顶点的回路。
0.5
00
1 0.8
0.6 0.4 x 0.2
定义3 在一个有向图D中，如果没有有向环和平行边， 则称该图为简单有向图。
v1 e4
e7 e6
v2
v4
e5
e3
e1
e2
v3
非简单有向图D
v1 e4 v4
e2
e6
v2
e5 e1
v3
简单有向图D
定义4 设D是有向图，去掉D中边的方向后得到的无向 图G，称为D的基础图。又若G是无向图，给G的每条边 加上方向后得到的有向图D称为G的一个定向图。
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
图论及其应用
应用数学学院
1
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
本次课主要内容 有向图
(一)、有向图的概念与性质 (二)、有向图的连通性 (三)、图的定向问题 (四)、有向路与有向圈
5
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
定义5 设D是有向图，v是D中顶点。以v为始点的边的条 数称为点v的出度，以v为端点的一个自环算1度。点v的出度 记为d+(v);以v为终点的边的条数称为点v的入度，以v为端点 的一个自环算1度。点v的入度记为d-(v);
7
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
对 v V (D) ，有
d (v) d (v) 1
2、性质
定理1 设D=(V, E)是有向图，则：
d (v) d (v) m(D)
vV (D)
vV (D)
证明：由出度与入度的定义立即可得上面等式。
v2
v1
v2
e1
v1
e2
e4
e3
v3 D1
v4
v3
e5
v4
D2
0 1 0 0
A(
D1
)
0 0
2 0
1 0
2
0
0 0 1 0
1 0 0 0 0
M
(
D2
)
1 0
1 1
1 1
1 0
0
1
0 0 0 1 1
10
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
11
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
3) 若D中存在一条(u，v)路和一条(v, u)路，则称u与v是 双向连通的或强连通的。
定义8 设D=(V, E)是有向图。 1) 若D的基础图是连通的，称D是弱连通图； 2) 若D的中任意两点是单向连通的，称D是单向连通图；
(二)、有向图的连通性
1、相关概念
(1) 有向途径(闭途径)、迹(闭迹)和路(圈) 上面概念与无向图中相关概念类似。
(2) 有向图中顶点间的连通性
定义7 设D=(V, E)是有向图，u与v是D中两个顶点。
1) 若D中存在一条(u，v)路，则称u可达v,记为u→v。 规定u →u。
2) 若D中存在一条(u，v)路或(v, u)路，则称u与v是单 向连通的。
3、有向图的矩阵表示
8Leabharlann 10.5 n 00.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
定义6 设D=(V,E)是有向图，其中V=｛v1,v2,…,vn｝
E=｛e1,e2,…,em｝
(1) 称A(D)=(aij) n×n是D的邻接矩阵，其中aij是vi为始点， vj为终点的边的条数，1≦i≦n,1≦j≦n。
(2) 若D无环。称矩阵M=(mij)n×m是D的关联矩阵，其中
1,
vi是e
的始点，
j
mij -1，vi是边ej的终点，(1 i n,1 j m),
0, 其它.
9
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
例1 写出下面有向图D1的邻接阵和D2的关联阵。
证明：“必要性”
设V(D)=｛v1,v2,…,vn｝。由于D是强连通图，所以，对任 意两点vi与vj, 都存在(vi, vj)路，同时也存在(vj ,vi)路。所以 存在如下闭途径：v1→v2→…→vn→v1。这是一条包含D的 所有顶点的回路。
2
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
(一)、有向图的概念与性质
1、概念
定义1 一个有向图D是指一个三元组(V(D) , E(D), фD)。 其中，V(D)是非空的顶点集合，E(D)是不与V(D)相交的 边集合，而фD是关联函数，它使D的每条边对应D的有序 顶点对(不必相异)。