图和子图1课件

1.1基本概念现实世界的许多现象可以用一类图形来描述，这种图形由一个点集和连接这个点集中某些点对的线所构成．例如用点表示车站，线表示连接车站与车站的道路；或者用点表示人，连线表示一对朋友．在这种图形中，人们主要感兴趣的是：两点是否被一条线所连接，而连线的长短曲直则无关紧要．大量的这类事实的数学抽象，产生了图的概念．1.1基本概念现实世界的许多现象可以用一类图形来描述，这1图的概念有序三元组G＝[V(G)，E(G)，ΨG]称为一个图，其中：ⅰ)V(G)称为顶点集合；ⅱ)E(G)∩V(G)=φ，E(G)称为边集合；ⅲ)ΨG是E(G)到{(a,b)|a,b∈V(G)}的映射，称为关联函数．V(G)中的元素称为顶点，E(G)中的元素称为边．V(G)所含元素的个数即顶点个数称为图的阶，用|V(G)|表示．E(G)所含元素的个数称为G的边数，用|E(G)|表示．我们用G(p，q)表添一个阶为p、边数为q的图G，这时也说G是一个(p，q)图．图的概念有序三元组G＝[V(G)，E(G)，ΨG]称为一个图2例题G＝[V(G)，E(G)，ΨG]，其中：V(G)={v1,v2,v3,v4}，E(G)={e1,e2,e3,e4,e5,e6}，ΨG定义为：ΨG(e1)=v2v3，ΨG(e2)=v3v4

ΨG(e3)=v4v4，ΨG(e4)=v2v4

ΨG(e5)=v2v3，ΨG(e6)=v1v3e1e6e5e4e3e2e1e6e5e4e3e2例题G＝[V(G)，E(G)，ΨG]，其中：V(G)={3相关概念在图G＝[V(G)，E(G)，ΨG]中,若e∈E(G)，u,v∈V(G)，而ΨG(e)=(u,v)，则称u和v是e的端点，或e和u,v关联，此时称u和v是邻接的。若两条不同的边ei和ej有一个公共端点，则称是邻接的，不与任何边邻接的边称为孤立边，不与任何边关联的顶点称为孤立点。两端重合的边称为环，端点不同的边称为杆。若V(G)和E(G)都是有限集，则称G为有限图。G(0,0)称为空图，E(G)=φ即G是由孤立点所组成，称为零图。G(1,0)称为平凡图。相关概念在图G＝[V(G)，E(G)，ΨG]中,若e∈E4简单图和完全图图中若连接两个相同顶点的边的条数大于1，则说这对顶点间有重边相连．同一对顶点间边的条数称为边的重数，既没有环也没有重边的图称为简单图，否则称为伪图，没有环的伪图称为多重图．每对不同的顶点均有边相连的简单图称为完全图．n阶完全图记为Kn定理1.1：Kn有条边简单图和完全图图中若连接两个相同顶点的边的条数大于1，则说这5二分图图G的顶点集V(G)若能分成两个子集V1和V2，使得G的每条边有一个端点在V1

，另一个端点在V2中，则G称为二分图或偶图．这样一个把V(G)分成两个集合V1

、V2的分划(V1,V2)称为G的一个二分划．设简单二分图G的二分划为(V1,V2)，如果V1的每个顶点与V2的每一个顶点都邻接，则G称为完全二分图．若|V1|=m,|V2|=n,则这样的图记为Km,n定理1.2

Km,n有mn条边。二分图图G的顶点集V(G)若能分成两个子集V1和V2，使得G6补图G是简单图，如果简单图GC满足，ⅰ)V(GC)=V(G)ⅱ)V(GC)中两点当且仅当它们在G中不邻接时在GC中邻接．那么GC称为G的补图．G：GC：补图G是简单图，如果简单图GC满足，G：GC：7平面图在保持图的顶点和边的关联关系不变的情况下，一个图可以作出许多图形．如果一个图具有这样的图形，它的边仅在顶点处相交，则称它为平面图．判断图1是否为平面图？图1：图2：平面图在保持图的顶点和边的关联关系不变的情况下，一个图可以作8恒同和同构两个图H和G，如果V(H)＝V(G)，E(H)＝E(G)且ΨH＝

ΨG，那么H和G就称为是恒同的，恒同的图当然可以用一个图形来表示．G＝[V(G)，E(G)，ΨG]和H＝[V(H)，E(H)，ΨH]，若存在1-1对应偶(θ,φ)，θ:V(G)→V(H)；φ:E(G)→E(H)，使得当且仅当ΨH(φ(e))=θ(u)θ(v)时，ΨG(e)=uv，则说这两个图同构，记为G≌H恒同和同构两个图H和G，如果V(H)＝V(G)，E(H)＝E9度与正则图设v∈V(G)，G中与顶点v关联的边的数目称为v在G中的度(次)，记为dG(v)或d(v)．一个环的端点的度数计为2．如果d(v)是奇数，就说v是奇顶点；如果d(v)是偶数，就说v是偶顶点．如果一个图的每一个顶点都具有相同的度，则称这个图是正则图。每个顶点的度均为k的正则图，称为k-正则图．度与正则图设v∈V(G)，G中与顶点v关联的边的数目称为v在10有关度的定理定理1.3

图G中各顶点度数之和等于边数的2倍。推论1.4任意一个图奇顶点的个数是偶数．推论1.5正则图的阶与各顶点度数不全为奇数．有关度的定理定理1.3图G中各顶点度数之和等于边数的211子图设H和G是两个图，如果V(H)是V(G)的子集，E(H)是E(G)的子集且ΨH是

ΨG在E(H)内的导出函数，那么H称为G的子图，此时G称为H的母图，记为如果而H≠G，则说H是G的真子图，记为设H是G的子图，如果V(H)=V(G)，则H称为G的生成子图。子图设H和G是两个图，如果V(H)是V(G)的子集，E(H)12导出子图设V’是V(G)的非空子集，H是G的一个子图，如果：ⅰ)V(H)=V’；ⅱ)E(H)={e|e∈E(G),ΨG(e)=uv，u,v∈V’}；ⅲ)ΨH是ΨG在E(H)上的导出函数。那么H称为由V’导出的G的子图，记为G[V’]导出子图G[V-V’]记为G-V’，它是从G中删除V’中的顶点及与这些顶点相关联的边所得到的子图。若V’={v}，则把G-{v}简记为G-v，称为G的删点子图。同理以E’中的端点的全体为集所组成的子图称为由E’导出的子图，记为G[E’]。删去边集合E’中的边之后得出的导出子图记为G-E’G-e,G+e导出子图设V’是V(G)的非空子集，H是G的一个子图，如果：13例GG的一个生成子图G-{2,3}G[{3,4,6}]G-{e,g,h}G[{a,c,e,g,h}]例GG的一个生成子图G-{2,3}G[{3,4,6}]G-{14子图的运算(并、交、差、环和)G1G2G1∪

G2G1∩

G2G2-

G1G1

G2子图的运算(并、交、差、环和)G1G2G1∪G2G1∩G15通路和回路图G中一个点边交替的非空有限序列w＝v0e1v1e2v2…envn称为G的一个途径．其中vi是顶点，ei是边，对于1≤i≤n，e的端点是vi-1和vi，v0和vn分别称为途径的起点和终点，而v1,v2,…,vn-1称为途径的内顶点，整数n称为途径w的长．途径w中若干相连项构成的子序列viei+1vi+1…ejvj称为w的(vi,vj)节．将序列w逆转后所得途径vnenvn-1…v1e1v0记为w-1．在简单图中，途径w可以由它的顶点序列v0e1v1e2v2…envn所确定．因此在简单图中可以用顶点序列表示一个途径．通路和回路图G中一个点边交替的非空有限序列w＝v0e1v1e16相关概念若途径的边e1,e2,

…,en互不相同，则称之为链，此外，若顶点也互不相同，则称w为通路．对G的两个顶点u和v,如果在G中存在一条(u,v)的通路，则称顶点u与v是连通的．如果图G中的任意一对顶点都是连通的，则G称为连通图．设G的顶点u与v是连通的，那么G中最短的(u,v)通路的长就称为u与v的距离，记为d(u,v)．相关概念若途径的边e1,e2,…,en互不相同，则17回路一条具有正的长度且起点、终点重合的途径称为闭途径．类似可以定义闭链、闭通路．闭通路称为回路(亦称圈)．长为K的回路称为K-回路．定理1.7

对于阶数不小于2的图G，当且仅当G不含奇回路时，它才是二分图．证明：充分性易证,下面证必要性。设G是无奇回路的连通图，任取G的一个顶点u并将V(G)作如下的划分(V1,V2)：V1={x|x∈V(G)，d(u,x)是偶数}V2={y|y∈V(G)，d(u,y)是奇数}然后证明这恰是G的一个二分划。回路一条具有正的长度且起点、终点重合的途径称为闭途径．类似可18设v和w是V1的两个顶点，又设P是最短(u,v)-通路，Q是最短(u,w)-通路，以u1记P和Q的最后一个公共顶点，因为P、Q是最短通路，P和Q的(u,u1)-节也是最短的(u,u1)-通路，因此具有相同的长度．又因P和Q的长度是偶数，所以P上(u1,v)-节P1的长度与Q上(u1,w)-节Q1的长度具有相同的奇偶性，由此推出(v,w)通路P1-1Q1的长度为偶数，若v与w邻接，则wv是G的一条奇回路，此与假设矛盾，故V1中任意两点均不邻接，同理V2中任意两个顶点也不邻接，因此G是二分图。设v和w是V1的两个顶点，又设P是最短(u,v)-通路，Q是19最短通路问题如果对图G的一条边，赋以一个实数w(e)，称为这条边的权，那么G连同它的边上的权称为赋权图．若G是一个赋权图，H是G的子图，那么H的权是它所有边的权之和，即如果P是G的一条通路，通路上各边的权也称为该边的长度，通路上各边的长度之和称为通路的长．所谓最短通路问题，就是在G中所有(u0,v0)-通路中，寻找一条长度最小的(u0,v0)-通路．u0到v0的最短通路长记为d(u0,v0),称作u0到v0的距离。最短通路问题如果对图G的一条边，赋以一个实数w(e)，称为这20Dijkst