离散数学第七章图的基本概念知识点总结docx.docx

图论部分
第七章、图的基本概念

无向图与有向图
多重集合:元素可以重复出现的集合
无序积:A&B={(x,y)|xgAaywB}
定义无向图G=<V,E>,其中
顶点集Vh0，元素称为顶点
边集E为V&n2x10
解得n>8
例3证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.
,
作无向图G=<V,E>,其中V={v|v为多面体的面},
E={(u,v)|u,veVau与v有公共的棱AUHV}.
根据假设，|V|为奇数且WeV,d(v).
多重图与简单图
定义(1)在无向图中,如果有2条或2条以上的边关联同一对顶点,则称这些边为平行边,平行边的条数称为重数.
在有向图中,如果有2条或2条以上的边具有相同的始点和终点,则称这些边为有向平行边,简称平行边,平行边的条数称为重数.
含平行边的图称为多重图.
既无平行边也无环的图称为简单图.
注意:简单图是极其重要的概念
碗和坯疋平行边也和旳是平行边蓮数加
重数为2期和购不是平行边
不是简单图不是简单图
图的同构
定义设G1=<V1,E1>,G2=<V2,E2>为两个无向图(有向图)，若存在双射函数f:V1TV2,使得对于任意的俏討，
(Vi，Vj)eE1(<v”Vj>wE1)当且仅当(f(Vi),f(Vj))wE2(<f(Vi),f(Vj)>wE2),并且,(Vj,Vj)(<Vi，Vj>)与(f(Vi),f(Vj))(<f(Vi),f(Vj)>)的重数相同，则称G1与G2是同构的，记作G梓G2.
几点说明：图之间的同构关系具有自反性、,但它们都不是充分条件:
边数相同，顶点数相同
度数列相同(不计度数的顺序)
对应顶点的关联集及邻域的元素个数相同，等等
若破坏必要条件，则两图不同构
至今没有找到判断两个图同构的多项式时间算法
匚
K
7
例1试画岀4阶3条边的所有同构的无向简单图
度数列不同
例2判断下述每一对图是否同构:<1)CO
不同构
完全图：n阶无向完全图Kn：：边数m=n(n-1)/2,A=5=n-1
n阶有向完全图：每对顶点之间均有两条方向相反的有向边的n阶有向简单图.
简单性质：边数m=n(n-1),A=5=2(n-1),
A+=8+=A-=8-=n-1
⑶
(1)为5阶完全图医⑵为3阶有向完全图
⑶称为彼得森图
子图：定义设G=<V,E>,G，=<V，上，>是两个图
(1)若VuV且EuE,则称G，为G的子图，G为G，的
母图，记作GUG
（2）若GUG且V，=V，则称G，为G的生成子图
⑶若VuV或EUE，称G，为G的真子图
⑷设VUV且VH0,以V为顶点集，以两端点都在
V，中的所有边为边集的G的子图称作V，的导
出子图，记作G[V]
⑸设EUE且E-0,以E，为边集，以E，中边关联的
所有顶点为顶点集的G的子图称作E，的导出子
图,记作G[E]
补图：定义设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完
全图Kn的添加边组成的集合为边集的图，称为G的补图，记作：
若G-,则称G是自补图.
例对上一页K4的所有非同构子图，指出互为补图的每一对子图，并指出哪些是自补图.
、回路、图的连通性
简单通（回）路,初级通（回）路,复杂通（回）路
定义给定图G=<V,E>（无向或有向的），G中顶点与边的交替序列r=voeivie2^eVi，
（1）若Vi（1<i<l）,vi_1,vi是ei的端点（对于有向图，要求Vj_[是始点，《是终点）,则称r为通路，v0是通路的起点，％是通路的终点，=vl，则称r为回路.
⑵若通路（回路）中所有顶点（对于回路，除v0=vl）各异，则称为初级通路（初级回路）.初级通路又称作路径,初级回路又称作圈.
（3）若通路（回路）中所有边各异,则称为简单通路（简单回路）,否则称为复杂通路（复杂回路）.
说明:
表示方法
用顶点和边的交替序列（定义），如r=v0e1v1e2_elvl
用边的序列，如r=e1e2_el
简单图中，用顶点的序列，如r=VoV[...V|
非简单图中,可用混合表示法,如r=v0v1e2v2e5v3v4v5
环是长度为1的圈,两条平行边构成长度为2的圈.
在无向简单图中，所有圈的长度>3;在有向简单图中，所有圈的长度>2.
在两种意义下计算的圈个数
定义意义下
在无向图中，一个长度为1（1>3）,