[工学]图论及其应用第1章

《[工学]图论及其应用第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、电子科技大学数学科学学院王也洲图论及其应用yzwang@uestc.edu.cn§1.1图和简单图一．图的定义定义1一个图G定义为一个有序对(V,E)，记为G=(V,E)，其中（1）V是一个非空集合，称为顶点集或点集，其元素称为顶点或点；（2）E是由V中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一点对在E中可出现多次。第一章图的基本概念符号说明:图G的顶点集也记为V(G),边集也记为E(G)。图G的顶点数（或阶数）和边数可分别用符号n(G)(或

2、V(G)

3、)和m(G)表示。例1设V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，则G=(V,

4、E)是一个4阶图。若用小圆点代表点，连线代表边，则可将一个图用“图形”来表示,如例1中的图可表为v1v2v3v4注:也可记边uv为e，即e=uv。v1v2v3v4e1e2e3e4e5例2设V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，其中e1=v1v2，e2=v2v3，e3=v2v3，e4=v3v4，e5=v4v4则G=(V,E)是一个图。相关概念:(1)若边e=uv,此时称u和v是e的端点;并称u和v相邻，u(或v)与e相关联。若两条边有一个共同的端点，则称这两条边相邻。（2）特殊点、边孤立点：不与任何边相关联的点；自环：两端点重合的边；重边：连接两

5、个相同顶点的边的条数，叫做边的重数。重数大于1的边称为重边。(4)既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。简单图非简单图例3平凡图●(3)点集与边集均为有限集合的图称为有限图，本书只讨论有限图。只有一个顶点而无边的图称为平凡图。边集为空的图称为空图。二、图的同构定义2设有两个图G1=(V1,E1)和G2=(V2,E2)，若在其顶点集合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：设，对应关系为：当且仅当的重数与的重数相同，则称两图同构，记为G1≌G2。，且例如≌说明：(1)两个同构的图均有相同的结构，没有本质上的差异,差异只是顶点和边的名称不

6、同。（2）图同构的几个必要条件：①顶点数相同；②边数相同；③度数相等的顶点个数相同。定义设v为G的顶点，G中与v为端点的边的条数（环计算两次）称为点v的度数，简称为点v的度，记为dG(v)，简记为d(v)。图中d(v1)=5d(v2)=4d(v3)=3d(v4)=0d(v5)=2v1v2v3v4v5例注：该图中各点的度数之和等于14，恰好是边数7的两倍(3)易证，图的同构关系是一个等价关系。该关系将所有的图的集合，划分为一些等价类，即相互同构的图作成同一个等价类。（4）在图的图形表示中我们可以不给图的点和边标上符号，称这样的图为非标定（号）图，否则称为标定（号）图。非标定图实

7、际上是代表一类相互同构的图。（5）判定图的同构是很困难的，属于NP完全问题。对于规模不大的两个图，判定其是否同构，可以采用观察加推证的方法。不误解时我们也不严格区分标定图与非标定图。例证明下面两图同构。证明作映射f:vi↔ui(i=1,2….10)，易知该映射为双射。容易验证，对vivjE((a)),有f(vivj,)ui,uj,E((b))，(1i10,1j10)由图的同构定义知，图(a)与(b)是同构的。例判断下面两图是否同构。u1v1解两图不同构。这是因若同构，则两图中唯一的与环关联的两个点u1与v1一定相对应，而u1的两个邻接点与v1的两个邻接点状况不

8、同（u1邻接有4度点，而v1没有）。所以，两图不同构。三、完全图，偶图，补图完全图：任意两点均相邻的简单图称为完全图，在同构意义下，n阶完全图只有一个，记为Kn。例如K2,K3,K4分别为如下图所示。K2K3K4具有二分类（X,Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中。。完全偶图：是指具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若

9、X

10、=m，

11、Y

12、=n，则这样的偶图记为Km,n例K3,3K1,3G1G2四个图均为偶图;K1,3,K3,3为完全偶图例偶图不是偶图简单图G的补图:设

13、G=（V,E），则图H=（V，E1E）称为G的补图，记为,其中集合例如,下图中的(a)，(b)两图是互补的。（a）（b）定理1若n阶图G是自补的（即），则n=0,1（mod4）证明因为G是自补的，则G和其补图有同样多的边数，且边数m(G)+m=m(Kn)=从而又因G的边数m(G)是整数，故n(n-1)/4为整数，即只能有n≡0（mod4）,或(n-1)≡0（mod4）。四．顶点的度（续）,度序列前已定义：设v为G的顶点，G中与v为端点的边的条数（环计算两次）称为点v的度数，简称为点v的度，记为dG(v