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

图论有向图

  • 格式：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章_有向图



图论及其应用
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章-有向图


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 ) 。
  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的有序 顶点对(不必相异)。