本文格式为Word版，下载可任意编辑离散数学第七章图的基本概念知识点总结 1 / 13 图论片面 第七章、图的根本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复展现的集合 无序积: A 若v i = v j , 那么称e k 为环, 此时称e k 与v i 的关联次数为2; 若v i 不是e k 端点 , 2 / 1 3 那么称e k 与v i 的关联次数为0. 无边关联的顶点称作孤立点. 定义 设无向图G =, v i ,v j ∈V , e k ,e l ∈E , 若(v i ,v j ) ∈E , 那么称v i ,v j 相邻; 若e k ,e l 至少有一个公共端点, 那么称e k ,e l 相邻. 对有向图有类似定义. 设e k =?v i ,v j ?是有向图的一条边,又称v i 是e k 的始点, v j 是e k 的终点, v i 邻接到v j , v j 邻接于v i . 邻域和关联集 顶点的度数 设G =为无向图, v ∈V , v 的度数(度) d (v ): v 作为边的端点次数之和 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 G 的最大度?(G )=max{d (v )| v ∈V } G 的最小度δ(G )=min{d (v )| v ∈V } 例如 d (v 5)=3, d (v 2)=4, d (v 1)=4,?(G )=4, δ(G )=1,v 4是悬挂顶点, e 7是悬挂边, e 1是环 设D =为有向图, v ∈V , v 的出度d +(v ): v 作为边的始点次数之和 v 的入度d -(v ): v 作为边的终点次数之和 v 的度数(度) d (v ): v 作为边的端点次数之和 d (v )= d +(v )+ d -(v ) D 的最大出度?+(D ), 最小出度δ+(D ) 最大入度?-(D ), 最小入度δ-(D ) 最大度?(D ), 最小度δ(D ) 例如 d +(a )=4, d -(a )=1, d (a )=5, d +(b )=0, d -(b )=3, d (b )=3, 3 / 13 ?+(D )=4, δ+(D )=0, ?-(D )=3, δ-(D )=1, ?(D )=5, δ(D )=3. 握手定理 定理 任意无向图和有向图的全体顶点度数之和都等于边数的2倍, 并且有向图的全体顶点入度之和等于出度之和等于边数. 证 G 中每条边（包括环）均有两个端点，所以在计算G 中各顶点度数之和时，每条边均供给2度，m 条边共供给2m 度. 有向图的每条边供给一个入度和一个出度, 故全体顶点入度之和等于出度之和等于边数. 图的度数列 设无向图G 的顶点集V ={v 1, v 2, …, v n } G 的度数列: d (v 1), d (v 2), …, d (v n ) 如右图度数列:4,4,2,1,3 设有向图D 的顶点集V ={v 1, v 2, …, v n } D 的度数列: d (v 1), d (v 2), …, d (v n ) D 的出度列: d +(v 1), d +(v 2), …, d +(v n ) D 的入度列: d -(v 1), d -(v 2), …, d -(v n ) 如右图度数列:5,3,3,3 出度列:4,0,2,1 入度列 :1,3,1,2 例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗? 解不成能. 它们都有奇数个奇数. 例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G 至少有多少个顶点? 解设G有n个顶点. 由握手定理, 4?3+2?(n-4)≥2?10 解得n≥8 例3 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体. 证用反证法. 假设存在这样的多面体, 作无向图G=, 其中V={v | v为多面体的面}, E={(u,v) | u,v∈V∧u与v有公共的棱∧u≠v}. 根据假设, |V|为奇数且?v∈V, d(v)为奇数. 这与握手定理的推论冲突. 多重图与简朴图 定义 (1) 在无向图中,假设有2条或2条以上的边关联同一对顶点, 那么称这些边为平行边, 平行边的条数称为重数. (2)在有向图中,假设有2条或2条以上的边具有一致的始点和终点, 那么称这些边为有向平行边, 简称平行边, 平行边的条数称为重数. (3) 含平行边的图称为多重图. (4) 既无平行边也无环的图称为简朴图. 留神:简朴图是极其重要的概念 图的同构 定义设G1=, G2=为两个无向图(有 4 / 13 5 / 13 向图), 若存在双射函数 f : V 1→V 2, 使得对于任意的 v i ,v j ∈V 1, (v i ,v j )∈E 1（∈E 1）当且仅当 (f (v i ),f (v j ))∈E 2（∈E 2）， 并且, (v i ,v j )（）与 (f (v i ),f (v j ))（） 的重数一致，那么称G 1与G 2是同构的，记作G 1?G 2. 几点说明： 图之间的同构关系具有自反性、对称性和传递性. 能找到多条同构的必要条件, 但它们都不是充分条件: ① 边数一致，顶点数一致 ② 度数列一致(不计度数的依次) ③ 对应顶点的关联集及邻域的元素个数一致，等等 若破坏必要条件，那么两图不同构 至今没有找到判断两个图同构的多项式时间算法 完全图：n 阶无向完全图K n : 每个顶点都与其余顶点相邻的n 阶无向简朴图. 简朴性质: 边数m =n (n -1)/2, ?=δ=n -1 n 阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n 阶有向简朴图. 简朴性质: 边数m =n (n -1), ?=δ=2(n -1), ?+=δ+=?-=δ-=n -1 子图：定义设G=, G '=是两个图 (1) 若V '?V且E '?E,那么称G '为G的子图, G为G '的 母图, 记作G '?G (2) 若G '?G 且V '=V，那么称G '为G的生成子图 (3) 若V '?V 或E '?E，称G '为G的真子图 (4) 设V '?V 且V '≠?, 以V '为顶点集, 以两端点都在 V '中的全体边为边集的G的子图称作V '的导 出子图，记作G[V '] (5) 设E '?E且E '≠?, 以E '为边集, 以E '中边关联的 全体顶点为顶点集的G的子图称作E '的导出子 图, 记作G[E '] 补图：定义设G=为n阶无向简朴图，以V为顶点集,全体使G成为完全图K n的添加边组成的集合为边集的图，称为G的补图，记作 . 若G? , 那么称G是自补图. 例对上一页K4的全体非同构子图, 指出互为补图的每一对子图, 并指出哪些是自补图. 7.2 通路、回路、图的连通性 简朴通(回)路, 初级通(回)路, 繁杂通(回)路 定义给定图G=（无向或有向的），G中顶点与边的交替序列Γ=v0e1v1e2…e l v l， (1) 若?i(1≤i≤l), v i-1, v i是e i的端点(对于有向图, 要求v i-1是始点, v i是终点), 那么称Γ为通路, v0是通路的起点, v l是通路的终点, l为通路的长度. 又若v =v l，那么称Γ为回路. (2) 若通路(回路)中全体顶点(对于回路, 除v0=v l)各异，那么称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈. (3) 若通路(回路)中全体边各异, 那么称为简朴通路(简朴回路), 否那么称为繁杂通路(繁杂回路). 说明: 表示方法 ① 用顶点和边的交替序列(定义), 如Γ=v0e1v1e2…e l v l 6 / 13 ② 用边的序列, 如Γ=e1e2…e l ③ 简朴图中, 用顶点的序列, 如Γ=v0v1…v l ④ 非简朴图中,可用混合表示法,如Γ=v0v1e2v2e5v3v4v5 环是长度为1的圈, 两条平行边构成长度为2的圈. 在无向简朴图中, 全体圈的长度≥3; 在有向简朴图中, 全体圈的长度≥2. 在两种意义下计算的圈个数 ① 定义意义下 在无向图中, 一个长度为l(l≥3)的圈看作2l个不同的圈. 如v0v1v2v0 , v 1v 2 v v 1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l≥3)的圈看作l个不同的圈. ② 同构意义下 全体长度一致的圈都是同构的, 因而是1个圈. 定理在n阶图G中，若从顶点v i到v j（v i≠v j）存在通 路，那么从v i到v j存在长度小于等于n-1的通路. 推论在n阶图G中，若从顶点v i到v j（v i≠v j）存在通 路，那么从v i到v j存在长度小于等于n-1的初级通路. 定理在一个n阶图G中，若存在v i到自身的回路，那么 确定存在v i到自身长度小于等于n的回路. 推论在一个n阶图G中，若存在v i到自身的简朴回 路，那么确定存在长度小于等于n的初级回路. 无向图的连通性 设无向图G=, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系R={| u,v∈V且u~v}是V上的等价关系 连通图:任意两点都连通的图. 平凡图是连通图. 连通分支: V关于连通关系R的等价类的导出子图 设V/R={V1,V2,…,V k}, G[V1], G[V2], …,G[V k]是G的连通分支, 其个数记作p(G)=k. G是连通图?p(G)=1 短程线与距离 u与v之间的短程线: u与v之间长度最短的通路 (u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长度 若u与v不连通, 规定d(u,v)=∞. 性质： d(u,v)≥0, 且d(u,v)=0 ?u=v d(u,v)=d(v,u) d(u,v)+d(v,w)≥d(u,w) 点割集与割点 记G-v: 从G中删除v及关联的边 G-V ': 从G中删除V '中全体的顶点及关联的边 7 / 13 8 / 13 G -e : 从G 中删除e G -E ': 从G 中删除E '中全体边 定义 设无向图G =, V '?V, 若p (G -V ')>p (G )且?V ''?V ', p (G -V '')=p (G ), 那么称V '为G 的点割集. 若{v 。