图论 图基本概念.pptx
《图论 图基本概念.pptx》由会员分享,可在线阅读,更多相关《图论 图基本概念.pptx(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、3 3、有关图的术语、有关图的术语1 1)用)用G G表示无向图,表示无向图,D D表示有向图。表示有向图。有时用有时用V(G)V(G),E(G)E(G)分别表示分别表示G G的顶点集和边集,的顶点集和边集,2 2)用)用 V(G)V(G),E(G)E(G)分别表示分别表示G G的顶点数和边数的顶点数和边数(有向图类似)有向图类似)若若V(G)V(G)n n,则称,则称G G为为n n阶图。对有向图可做类似规定。阶图。对有向图可做类似规定。3 3)在图)在图G G中,若中,若边集边集E(G)E(G),则称,则称G G为为零图零图 若若G G为为n n阶图,则称阶图,则称G G为为n n阶零图阶
2、零图,记作,记作N Nn n,特别是称,特别是称N N1 1为为平凡图平凡图 4)4)常用常用e ek k表示无向边表示无向边(vi(vi,vj)(vj)(或有向边或有向边vi)vj)设设G GV E 为无向图,为无向图,e ek k=(vi=(vi,vj)Evj)E,则称则称vjvj,vjvj为为e ek k的端点的端点,e ek k与与vivi、vjvj是彼此是彼此相关联的相关联的 起终点相同的边称为环起终点相同的边称为环 不与任何边关联的结点称为孤立点(包括有向向图不与任何边关联的结点称为孤立点(包括有向向图)5 5)邻接:)邻接:边的相邻边的相邻:e ek k,e el lEE若若e
3、ek k与与e el l至少有一个公共端点,则称至少有一个公共端点,则称e ek k与与e el l是是相邻的相邻的 顶点的相邻顶点的相邻:若若 e et tEE,使得,使得e et t=vi=vj,则称则称vivi为为etet的始点,的始点,vjvj为为e et t的终点,的终点,并称并称vivi邻接到邻接到vjvj,vjvj邻接于邻接于vi vi 两个结点为一条边的端点,则称两个结点两个结点为一条边的端点,则称两个结点互为邻接点互为邻接点,也称也称边关联于这两个结点边关联于这两个结点,或称两个结点邻接于此边,或称两个结点邻接于此边。第1页/共21页 6 6)平行边:)平行边:在无向图中,关
4、联一对顶点的无向边如果多于在无向图中,关联一对顶点的无向边如果多于1 1条,则称这些边为平条,则称这些边为平行边,平行边的条数称为重数行边,平行边的条数称为重数 在有向图中,关联一对顶点的有向边如果多于在有向图中,关联一对顶点的有向边如果多于1 1条,并且这些边的条,并且这些边的始点与终点相同始点与终点相同(也就是它们的方向相同也就是它们的方向相同),则称这些边为平行边,则称这些边为平行边 7 7)多重图和简单图:)多重图和简单图:含平行边的图称为多重图含平行边的图称为多重图 既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图(主要讨论简单图)(主要讨论简单图)4 4、结点的
5、度、结点的度 1 1)定义)定义4 4 设设G GVE为无向图,为无向图,v Vv V,称,称v v作为边的端点次数之作为边的端点次数之和和为为v v的度数,简记为度记作的度数,简记为度记作d d G G(v)(v),简记为简记为d dG G(v)(v)即为:结点即为:结点v v 所关联的边的总条数所关联的边的总条数 关于有向图关于有向图D DV E 有:有:v Vv V,称,称v v 作为边的作为边的始点的次数之和始点的次数之和为为v v的出度,记作的出度,记作d d-(v)(v),称称v v作为边的终点的次数之和为作为边的终点的次数之和为v v的入度,记作的入度,记作d d+(v)(v),
6、称称d d+(v)+d(v)+d-(v)(v)为为 v v的度数,记作的度数,记作d dD D(v)(v)2)2)称度数为称度数为1 1的顶点为悬挂顶点,与它关联的边称为悬挂边的顶点为悬挂顶点,与它关联的边称为悬挂边 根据结点的度数可将结点分为:根据结点的度数可将结点分为:度为偶数度为偶数(奇数奇数)的顶点称为的顶点称为偶度偶度(奇度奇度)顶点顶点.有环的结点提供的度为有环的结点提供的度为2 2(有向图的环提供入度(有向图的环提供入度1 1和出度和出度1 1)第2页/共21页3 3)定义:)定义:(G)=maxd(v)|vV(G)(G)=maxd(v)|vV(G)为图为图G G中结点最大的度中
7、结点最大的度 (G)=mind(v)|vV(G)(G)=mind(v)|vV(G)为图为图G G中结点最小的度中结点最小的度 简记为简记为、定义:定义:(D)=maxd(v)|vV(D)(D)=maxd(v)|vV(D)为图为图D D中结点最大的入度中结点最大的入度 (D)=maxd(v)|vV(D)(D)=maxd(v)|vV(D)为图为图D D中结点最大的出度中结点最大的出度 (D)=mind(v)|vV(D)(D)=mind(v)|vV(D)为图为图D D中结点最小的入度中结点最小的入度 -(D)=mind(v)|vV(D)(D)=mind(v)|vV(D)为图为图D D中结点最小的出度
8、中结点最小的出度5 5、握手定理(欧拉)、握手定理(欧拉)1)1)定理定理1 1 设设G G为任意无向图为任意无向图,V,Vvv1 1,v v2 2,v vn n,E E =m m,则则 d(vd(vi i)2 m (2 m (所有结点的度数值和为边数的所有结点的度数值和为边数的2 2倍倍)证证:G:G中每条边中每条边(包括环包括环)均有两个端点,所以在计算均有两个端点,所以在计算G G中各顶中各顶点度数之和时,每条边均提供点度数之和时,每条边均提供2 2度,当然,度,当然,m m条边共提供条边共提供2m2m度度 2)2)定理定理2 2 设设D D为任意有向图为任意有向图,V,Vvv1 1,v
9、 v2 2,v vn n,|E|=m,|E|=m,则则 d d+(v(vi i)d d-(v(vi i)=m)=m 且且d(vd(vi i)2 m2 m3)3)推论推论 任何图任何图(无向的或有向的无向的或有向的)中,中,奇度顶点的个数是偶数奇度顶点的个数是偶数第3页/共21页4)4)结点的度数序列结点的度数序列 (1)(1)设设G GVE为一个为一个n n阶无向图,阶无向图,V Vvv1 1,v v2 2,v vn n 称称d(vd(v1 1),d(vd(v2 2),d(vd(vn n)为为G G的度数列的度数列 注:由于推论可知,不是任何一个非负整数序列均可作为一个图的度数注:由于推论可知
10、,不是任何一个非负整数序列均可作为一个图的度数列。列。条件:条件:奇度数奇度数的结点个数应该是的结点个数应该是偶数个偶数个 (2 2)序列的可图化:)序列的可图化:d=(dd=(d1 1,d,d2 2,d dn n)对一个整数序列对一个整数序列d,d,若存在以若存在以n n个顶点的个顶点的n n阶无向图阶无向图G G,有,有d(vd(vi i)=d)=di i 称该序列是可图化的称该序列是可图化的 (3 3)定理)定理 设非负整数列设非负整数列d d(d1(d1,d2d2,dn)dn),则,则d d是可图化的当且是可图化的当且仅当仅当 d di i=0(mod 2)=0(mod 2)(序列之和
11、必须是偶数序列之和必须是偶数)(4 4)由于简单图中没有平行边及环)由于简单图中没有平行边及环 结论:结论:n n个结点的个结点的简单图简单图中结点的最大中结点的最大度数(度数(G)G))应小于等于)应小于等于n-n-1 1 每个结点至多与其他每个结点至多与其他n-1n-1个结点相邻个结点相邻 例:给定例:给定5 5个序列哪些是可图化的?哪些是可简单图化的?个序列哪些是可图化的?哪些是可简单图化的?d1=5,5,4,4,2,1 d1=5,5,4,4,2,1 d2=5,4,3,2,2d2=5,4,3,2,2 d3=3,3,3,1d3=3,3,3,1 d4=4,4,3,3,2,2d4=4,4,3,
12、3,2,2 第4页/共21页二、图的同构二、图的同构定义定义 设设G1G1Vl E1,G2=V2G2=E2为两个无向图为两个无向图(两个有向图两个有向图),若存在双射函数若存在双射函数f f:V1 V2 V1 V2 顶点的一一对顶点的一一对应应 对于对于 vivi,vjV1vjV1,(vi(vi,vj)E1(vivj)E1(E1)vj E1)当且仅当当且仅当(f(vi)(f(vi),f(vj)E2(f(vi)f(vj)E2(E2)f(vj)E2),边的边的对应对应 并且并且(vi(vi,vj)vj)()()与与(f(vi),f(vj(f(vi),f(vj)()()的重数的重数相同相同,则称则称
13、G1G1与与G2G2是同构的,记作是同构的,记作Gl Gl G2 G2 定义说明了定义说明了:两个图的各结点之间,如果存在着一一对应关系两个图的各结点之间,如果存在着一一对应关系f f 这种对应关系又保持了这种对应关系又保持了结点间的邻接关系结点间的邻接关系,那么这两个图就是同构,那么这两个图就是同构的的 在有向图的情况下,在有向图的情况下,f f不但应该保持结点间的邻接关系,还应该不但应该保持结点间的邻接关系,还应该保持边的方向保持边的方向注:注:1)1)互为互为同构的两个图(必要条件)同构的两个图(必要条件)有有相同样的阶数相同样的阶数(结点)和(结点)和同样数量的边数同样数量的边数及顶点
14、的及顶点的度数序列度数序列 但这对于形成图的同构来说,三个条件并不是充分条件(仅是必要条但这对于形成图的同构来说,三个条件并不是充分条件(仅是必要条件)件)2)2)图之间的图之间的同构关系同构关系可看成全体图集合上的二元关系可看成全体图集合上的二元关系 具有自反性,对称性和传递性,具有自反性,对称性和传递性,是等价关系是等价关系 同构的图为一个等价类,在同构的图为一个等价类,在同构的意义之下都可以看成是一个图。同构的意义之下都可以看成是一个图。例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的条边的所有非同构的无向简单图无向简单图 结点个数结点个数与与边数相同边数相同,只需找出,只需
15、找出顶点度数序列不同顶点度数序列不同的图(的图(2 23 36 6):):第5页/共21页例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的无向简单图条边的所有非同构的无向简单图 非同构的图但结点个数与边数相同非同构的图但结点个数与边数相同 只需找出只需找出顶点度数序列不同的图顶点度数序列不同的图 结点总度数:结点总度数:2 23 36 6 如何将度数如何将度数6 6分配给分配给4 4个结点个结点 1 1 1 3 1 1 1 3 相应的图相应的图 2 2 1 1 2 2 1 1 2 2 2 0 2 2 2 0(2)(2)画出画出3 3阶阶2 2条边的所有非同构的条边的所有非同构的有向
16、简单图有向简单图 结点个数与边数相同,只需找出结点个数与边数相同,只需找出顶点度(出度及入度)数序列不同顶点度(出度及入度)数序列不同的图的图 结点总度数:结点总度数:2 22 24 4 度数分配度数分配 1 2 1 1 2 1 按出度与入度分配:按出度与入度分配:入度列入度列 1 1 01 1 0出度列出度列 0 1 10 1 1入度列入度列 0 2 00 2 0出度列出度列 1 0 11 0 1入度列入度列 1 0 11 0 1出度列出度列 0 2 00 2 0度数分配度数分配 2 2 0 2 2 0 按出度与入度分配:按出度与入度分配:入度列入度列 1 1 01 1 0出度列出度列 1
17、1 01 1 0这只是对较为简单的情这只是对较为简单的情况给出的非同构图,对况给出的非同构图,对于一般的情况(于一般的情况(n,m)n,m)图图到目前为止还没有解决到目前为止还没有解决第6页/共21页三、特殊图完全图与正则图三、特殊图完全图与正则图 1 1)完全图)完全图 定义定义 设设G G为为n n阶无向简单图,若阶无向简单图,若G G中每个顶点均与其余的中每个顶点均与其余的n n1 1个顶点个顶点相邻,则称相邻,则称G G为为n n阶无向完全图,简称阶无向完全图,简称n n阶完全图阶完全图,记作,记作KnKn(n1)(n1)设设D D为为n n阶有向简单图,若阶有向简单图,若D D中每个
18、顶点都中每个顶点都邻接到邻接到其余的其余的n n1 1个个顶点,又顶点,又邻接于邻接于其余的其余的n n1 1个顶点,则称个顶点,则称D D是是n n阶阶有向完全图有向完全图 可画图表示(无向图可画图表示(无向图5 5阶、有向图阶、有向图3 3阶和阶和4 4阶)阶)2)2)完全图的性质:完全图的性质:n n阶无向完全图阶无向完全图G G的边数与结点的关系的边数与结点的关系 m=m=n(n-1)/2n(n-1)/2 n n阶有向完全图阶有向完全图G G的边数与结点的关系的边数与结点的关系 m=m=n(n-1)n(n-1)3)3)正则图正则图 定义定义 设设G G为为n n阶无向简单图,若阶无向简
19、单图,若 v V(G)v V(G),均有,均有d(v)d(v)k k,则称则称G G为是为是 k-k-正则图正则图 k-k-正则图的边数与结点个数的关系正则图的边数与结点个数的关系 :m=k n/2m=k n/2 可画可画 3 3正则图和正则图和4 4正则图正则图第7页/共21页四、子图、生成子图、导出子图四、子图、生成子图、导出子图 1 1、定义、定义 设设G GVE,G GV 为两个图为两个图(同为无向图或同为同为无向图或同为有向图有向图),若若V V V V 且且E E E E ,则称,则称G G是是G G的子图,的子图,G G为为G G的母图,的母图,记作记作G G G G,又又若若V
20、 V V V或或E E E E,则称,则称G G为为G G的真子图的真子图 若若V VV(V(且且E E E),E),则称则称G G为为G G的的生成子图生成子图 2 2、设、设G GVE为图,为图,V1V1 V V 且且V1 V1 ,称以,称以V1V1为顶点集,以为顶点集,以G G中两个端中两个端点都在点都在V1V1中的边组成边集中的边组成边集E1E1的图为的图为G G的的V1V1导出的子图导出的子图,记作,记作GV1GV1 可画图表示可画图表示 G G 及及 G GV1V1 (按书上的例)(按书上的例)结点导出的子图结点导出的子图 又设又设E1 E1 E E且且 E1 E1 ,称以,称以
21、E1E1为边集,以为边集,以E1E1中边关联的顶点为中边关联的顶点为顶点集顶点集V1V1的图为的图为G G的的E1E1导出的子图导出的子图,记作,记作GE1GE1 边导出的子边导出的子图图3 3、补图、补图 1 1)定义)定义 设设G G VE 为为n n阶无向简单图,以阶无向简单图,以V V为顶点集,以为顶点集,以所有使所有使G G成为完全图成为完全图KnKn的添加边组成的集合为边集的添加边组成的集合为边集的图,的图,称为称为G G的补图的补图,记作,记作G G 2 2)性质性质:设设G G是是n n阶阶k-k-正则图,证明正则图,证明G G的补图的补图G G也是正则图也是正则图 对图中任何
22、结点对图中任何结点v v的度有的度有 d G(v)+d d G(v)+d G G(v)(v)=d =d KnKn(v)=n-1(v)=n-1 d d G G(v)(v)=n-1 =n-1 d G(v)d G(v)n-1-k=n-1-k=n-(k+1n-(k+1)3 3)自补图:若图)自补图:若图 G G(G G(同构同构)则称则称G G为自补图为自补图 作业:作业:p291 1、3、5、7、8、9、14、15、16、25第8页/共21页14.2 14.2 通路、回路通路、回路一、通路与回路一、通路与回路1 1、通路、通路 1 1)定义:给定有向图)定义:给定有向图D D中的任何一个边序列中的任
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论 图基本概念 基本概念
限制150内