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

图论部分第七章、图的基本概念7.1 无向图及有向图无向图与有向图多重集合: 元素可以重复出现的集合无序积: A&B=(x,y) | xÎAÙyÎB 定义 无向图G=<V,E>, 其中(1) 顶点集V¹Æ，元素称为顶点(2) 边集E为V&V的多重子集，其元素称为无向边，简称边.例如, G=<V,E>如图所示, 其中V=v1, v2, ,v5, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) ,定义 有向图D=<V,E>, 其中(1) V同无向图的顶点集, 元素也称为顶点(2) 边集E为V´V的多重子集，其元素称为有向边，简称边.用无向边代替D的所有有向边所得到的无向图称作D的基图，右图是有向图，试写出它的V和E 注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的 通常用G表示无向图, D表示有向图, 也常用G泛指无向图和有向图, 用ek表示无向边或有向边.V(G), E(G), V(D), E(D): G和D的顶点集, 边集.n 阶图: n个顶点的图有限图: V, E都是有穷集合的图零图: E=Æ 平凡图: 1 阶零图空图: V=Æ 顶点和边的关联与相邻：定义 设ek=(vi,vj)是无向图G=<V,E>的一条边, 称vi,vj为ek的端点, ek与vi ( vj)关联. 若vi ¹ vj, 则称ek与vi ( vj)的关联次数为1;若vi = vj, 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不是ek端点, 则称ek与vi 的关联次数为0. 无边关联的顶点称作孤立点.定义 设无向图G=<V,E>, vi,vjÎV, ek,elÎE, 若(vi,vj) ÎE, 则称vi,vj相邻; 若ek,el至少有一个公共端点, 则称ek,el相邻.对有向图有类似定义. 设ek=ávi,vjñ是有向图的一条边,又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻接于vi.邻域和关联集顶点的度数设G=<V,E>为无向图, vÎV, v的度数(度) d(v): v作为边的端点次数之和 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 G的最大度D(G)=maxd(v)| vÎV G的最小度d(G)=mind(v)| vÎV例如 d(v5)=3, d(v2)=4, d(v1)=4,D(G)=4, d(G)=1,v4是悬挂顶点, e7是悬挂边, e1是环 设D=<V,E>为有向图, 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-(D) 最大度D(D), 最小度d(D) 例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, D+(D)=4, d+(D)=0, D-(D)=3, d-(D)=1, D(D)=5, d(D)=3. 握手定理定理 任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数.证 G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度. 有向图的每条边提供一个入度和一个出度, 故所有顶点入度之和等于出度之和等于边数. 图的度数列设无向图G的顶点集V=v1, v2, , vnG的度数列: d(v1), d(v2), , d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V=v1, v2, , vnD的度数列: d(v1), d(v2), , d(vn)D的出度列: d+(v1), d+(v2), , d+(vn)D的入度列: d-(v1), d-(v2), , d-(vn)如右图度数列: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,E>, 其中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=<V1,E1>, G2=<V2,E2>为两个无向图(有向图), 若存在双射函数 f: V1®V2, 使得对于任意的vi,vjÎV1, (vi,vj)ÎE1（<vi,vj>ÎE1）当且仅当 (f(vi),f(vj)ÎE2（<f(vi),f(vj)>ÎE2），并且, (vi,vj)（<vi,vj>）与 (f(vi),f(vj)（<f(vi),f(vj)>）的重数相同，则称G1与G2是同构的，记作G1G2. 几点说明：图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件, 但它们都不是充分条件: 边数相同，顶点数相同 度数列相同(不计度数的顺序) 对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构至今没有找到判断两个图同构的多项式时间算法完全图：n阶无向完全图Kn: 每个顶点都与其余顶点相邻的n阶无向简单图.简单性质: 边数m=n(n-1)/2, D=d=n-1n阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n阶有向简单图.简单性质: 边数m=n(n-1), D=d=2(n-1), D+=d+=D-=d-=n-1子图：定义 设G=<V,E>, G ¢=<V ¢,E ¢>是两个图(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 ¢的导 出子图，记作 GV ¢(5) 设E ¢ÍE且E ¢¹Æ, 以E ¢为边集, 以E ¢中边关联的 所有顶点为顶点集的G的子图称作E ¢的导出子 图, 记作 GE ¢ 补图 ：定义 设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 .若G , 则称G是自补图. 例 对上一页K4的所有非同构子图, 指出互为补图的每一对子图, 并指出哪些是自补图. 7.2 通路、回路、图的连通性简单通(回)路, 初级通(回)路, 复杂通(回)路定义 给定图G=<V,E>（无向或有向的），G中顶点与边的交替序列G=v0e1v1e2elvl，(1) 若"i(1£i£l), vi-1, vi是ei的端点(对于有向图, 要求vi-1是始点, vi是终点), 则称G为通路, v0是通路的起点, vl是通路的终点, l为通路的长度. 又若v0=vl，则称G为回路.(2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈.(3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).说明:表示方法 用顶点和边的交替序列(定义), 如G=v0e1v1e2elvl 用边的序列, 如G=e1e2el 简单图中, 用顶点的序列, 如G=v0v1vl 非简单图中,可用混合表示法,如G=v0v1e2v2e5v3v4v5环是长度为1的圈, 两条平行边构成长度为2的圈.在无向简单图中, 所有圈的长度³3; 在有向简单图中, 所有圈的长度³2. 在两种意义下计算的圈个数 定义意义下 在无向图中, 一个长度为l(l³3)的圈看作2l个不同的圈. 如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l³3)的圈看作l个不同的圈. 同构意义下 所有长度相同的圈都是同构的, 因而是1个圈. 定理 在n阶图G中，若从顶点vi到vj（vi¹vj）存在通路，则从vi到vj存在长度小于等于n-1的通路.推论 在n阶图G中，若从顶点vi到vj（vi¹vj）存在通路，则从vi到vj存在长度小于等于n-1的初级通路.定理 在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论 在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路. 无向图的连通性设无向图G=<V,E>,u与v连通: 若u与v之间有通路. 规定u与自身总连通.连通关系 R=<u,v>| u,v ÎV且uv是V上的等价关系连通图:任意两点都连通的图. 平凡图是连通图.连通分支: V关于连通关系R的等价类的导出子图 设V/R=V1,V2,Vk, GV1, GV2, ,GVk是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及关