图论基本概念

图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。一个图G=(V,E)由一些点及点之间的连线（称为边）构成，V、E分别记G的点集合和边集合。在图的概念中，点的空间位置、边的曲直长短都是无关紧要的，重要的是其有几个点以及哪些点之间有边相连。v1v2v3v4v5v1v2v3v4v554321,,,,vvvvvV},{},,{},{},,{},,{5154433221vvvvvvvvvvE≌如果用点表示要研究的对象，则图的边可以用来反映对象之间是否存在某种关系。用点表示人，边表示两个人是否互相认识；在地区公路图中，用点表示城市，边表示城市之间是否有公路直接相连；在分子结构图中，用点表示原子，边表示原子之间是否存在化学键；……哥尼斯堡七桥问题)nigsbergo(KABCDABCD(Euler,1736)右图是否存在经过每条边恰好一次的回路，即是否为Euler图？是否可以一笔画?化学药品存放问题某单位需要存放一些化学药品，其中某些药品不能放在同一个库房里，问至少需要几个库房？用点表示药品，在不能放在同一个库房的两种药品之间连边。需要几个库房等价于需要用几种颜色给图的点着色可以使得相邻的点有不同的颜色。abcdefg图中的7种药品需要3个库房，例如{a,b,e}，{c,d,g}，{f}各放一个库房。排课表问题有m位教师x1,…,xm和n个班级y1,…,yn，教师xi需要给班级yj上wij节课，试编制一张课表使得课时尽量少。构造图G=(V,E)，其中V={x1,…,xm,y1,…,yn},点xi与yj之间连有wij条边。给G的边着色，使得相邻的边有不同的颜色。需要3种颜色给边着色y1y2y3x1x2x3x4图的基本概念一个有序二元组(V,E)称为一个图,记G=(V,E),其中①V或V(G)称为G的顶点集,V≠Φ,其元素称为顶点或结点,简称点;②E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.的顶点数和边数。表示图或可以用GEV点v的度数：与v相连的边的条数，记作d(v)。与顶点v出关联的边的数目称为出度，记作d+(v),与顶点v入关联的边的数目称为入度，记作d-(v)。命题：图的所有点的度数之和等于边数的两倍，即。||2)deg(EvVv例.碳氢化合物中氢原子的个数为偶数。CHHHHCCHHHHCCCCCCHHHHHH两个图G=(V,E)和，如果有),(EVG,VV,EE则称G是G的子图。若G是G的子图，且V=V，则称G是G的生成子图。GG'G''G'和G''都是G的生成子图。边数k称为链P的长度。.)1(},{1kivveiiiv1v2v4v3v5v6v7v8kkvevevevP22110称为链，其中当v0=vk时，称P为闭链。边不重复的链称为迹。点不重复的链称为路，v0=vk的回路称为圈。图G的一条点与边的交替序列76435421vvvvvvvv迹的长度为72346542vvvvvvv闭迹的长度为623542vvvvv圈的长度为4命题：若点v与v之间有Walk，则点v与v之间必有Path。在图G中，若点u、v之间有路，则称u、v连通。若G的任何两点之间有路，则称G是连通图。G的极大连通子图称为连通分支。有三个连通分支若删去某条边e之后图的连通分支数增加，则称e为割边或桥；若删去某个点v及相连的边后连通分支数增加，则称v为割点。euvwe为割边u、v、w皆为割点简单图：任何一条边连结两个不同的点，任何两个点之间至多有一条边的图。完全图：任何两个点之间都有边相连的简单图。n个点的完全图记作Kn。K3K4K5该图非简单图多重边自环二分图：点集V能划分成两个子集X、Y，使得每条边的两个端点分别属于X和Y的图。二分图G也记作G=(X,Y,E)。称G=(X,Y,E)为完全二分图，若X中的每个点和Y中的每个点之间皆有边相连，记作。||,||YXKK1,3K2,3K3,3命题：图G是二分图当且仅当G中不存在长度为奇数的圈。在图G=(V,E)的边集上定义权函数后就得到一个赋权图，记为G=(V,E,w)。REw:对于赋权图，路的长度（即路的权）通常指路上所有边的权之和。最短路问题：求赋权图上指定点之间的权最小的路。邻接矩阵A=(aij)n×n,EvvEvvajijiij,0,1例:写出右图的邻接矩阵：0101100101001010A解：图的矩阵表示权矩阵W=(wij)n×n,0,,ijijijijwvvvvEwijvvE例:写出右图的权矩阵：06807302450W解：图的矩阵表示关联矩阵A=(aij)n×m不关联与若的终点是若的始点是若iiiiiiijeveveva,0,1,1有向图：无向图：1,0,ijijijvav若与e关联若与e不关联图的矩阵表示例:写出右图与其基本图的关联矩阵解：分别为：1101100011011000000111011001A1101100011011000000111011001A图的矩阵表示用图论思想求解以下各题例1、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。图论的基本概念解：用四维0-1向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取1，否则取0.）共24=16种状态，由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，图论的基本概念人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。例2、证明：在任意6人的集会上，总有3人互相认识，或总有3人互相不认识。解：以顶点表示人，以边表示认识，得6个顶点的简单图G。问题：3人互相认识即G包含K3为子图，3人互相不认识即G包含（3,0）图为子图。图论的基本概念为子图。包含点不相邻，则点至少、这图为子图。包含点两两相邻，则、这。这又包含两种情况：点不相邻个顶即至少与另外个顶点相邻至多与另外）（为子图。包含点相邻，则点至少、这图为子图。包含点互不相邻，则、这两种情况：个顶点相邻，这又包含至少与另外则有两种情况：任取0,323231)3(222320,33131,33GKGvKGGvGVv图论的基本概念