离散数学之图论篇
需积分: 26 164 浏览量
2018-04-11
16:02:38
上传
评论 1
收藏 87KB DOC 举报
1
第五篇 图论
第 14 章 图的基本概念
14.1 图
【定理 14.1】握手定理
设 G=<V，E>为任意无向图，V={v
1
,v
2
,…,v
n
}, |E|=m, 则
【定理 14.2】握手定理
设 D=<V，E>为任意有向图，V={v
1
,v
2
,…,v
n
}, |E|=m, 则
推论：任何图 (无向或有向) 中，奇度顶点的个数是偶数。
【定理 14.3】非负整数列 d=(d
1
, d
2
, …, d
n
)是可图化的当且仅当 为偶数。
【定理 14.4】设 G 为任意 n 阶无向简单图，则 (G) n -1。
14.2 通路与回路
【定理 14.5】在 n 阶图 G 中，若从顶点 v
i
到 v
j
（v
i
v
j
）存在通路，则从 v
i
到 v
j
存在长度小于
或等于 n1 的通路.
推论：在 n 阶图 G 中，若从顶点 v
i
到 v
j
（v
i
v
j
）存在通路，则从 v
i
到 v
j
存在长度小于或等于
n1 的初级通路（路径）
【定理 14.6】在一个 n 阶图 G 中，若存在 v
i
到自身的回路，则一定存在 v
i
到自身长度小于或
等于 n 的回路.
推论：在一个 n 阶图 G 中，若存在 v
i
到自身的简单回路，则一定存在长度小于或等于 n 的初
级回路.
14.3 图的连通性
14.3.1 无向图的连通
【定理 14.7】, , 之间的关系：(G)(G)(G)
14.3.2 有向图的连通性
评论0
最新资源