第7章第1讲无向图及有向图.pptVIP

;;第一讲 无向图及有向图; ;欧拉：传奇的一生;问题2(哈密顿环球旅行问题，1857年): 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？;问题3(四色问题): 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.;二、图的概念 ;定义1 一个无向图（undirected graph）是一个有序的二元组V，E,记作G，其中 （1）V≠?称为顶点集，其元素称为顶点或结点（vertices, nodes）。 （2）E称为边集，它是无序积VV的多重子集，其元素称为无向边，简称边（edges）。;例1 （2）E＝{a,a,a,b,a,b, a,d,c,d,d,c,c,b}　;图的一些概念和规定;关联与关联次数、环、孤立点 ;相邻与邻接 ;简单图与多重图 ;顶点的度数(degree);设G＝V,E为一个n阶无向图，V＝{v1,v2,…,vn}，称d(v1)，d(v2)，…，d(vn)为G的度数列。 对于顶点标定的无向图，它的度数列是唯一的。 类似地，设D＝V,E为一个n阶有向图，V＝{v1,v2,…,vn}，称d(v1)，d(v2)，…，d(vn)为D的度数列，另外称d+(v1)，d+(v2)，…，d+(vn)与d-(v1)，d-(v2)，…，d-(vn)分别为D的出度列和入度列。;图的度数的相关概念;图的度数举例;握手定理(The Handshaking Theorem);推论;例：(3,3,2,1)，(3,2,2,1,1) (3,3,2,2)、 (3,2,2,2,1) 是否可图化？ 解： (3,3,2,1)，(3,2,2,1,1) 不可以图化 (3,3,2,2)可以图化 (3,2,2,2,1)可以图化;定理4 设G为任意n阶无向简单图，则△(G)≤n-1。 证明 因为G既无平行边也无环， 所以G中任何顶点v至多与其余的n-1个顶点均相邻， 于是d(v)≤n-1，由于v的任意性，所以△(G)≤n-1。 例2 判断下列各非负整数列哪些可图化的？哪些可简单图化的？ (1) (5,5,4,4,2,1) 不可图化。 　(2) (5,4,3,2,2) 可图化，不可简单图化。若它可简单图化， 设所得图为G，则(G)＝max{5,4,3,2,2}＝5，这与定理矛盾 ;(3) (3,3,3,1) 可图化，不可简单图化。 假设可以简单图化，设G＝V，E以该序列为度数列 设V＝{v1,v2,v3,v4}且 d(v1)＝d(v2)＝d(v3)＝3,d(v4)＝1， 由于d(v4)＝1，因而v4只能与v1，v2，v3之一相邻，去掉 v4后，与v4关联的边也去掉，于是剩余的v1，v2，v3组成的 图的度数应该是2、3、3，此时因为最大度为3，不满足 ≤n-1=2的要求，因此这三个点构成的图必定有平行边或 者环，不是简单图，此时若加入v4及与v4关联的边构成的 图必定也不是简单图。 即有(3)中序列也不可简单图化。 ;(5) (4,4,3,3,2,2) 可简单图化。下图中两个6阶无向简单图都以(5)中序列为度数列。;定义5 设G1＝V1,E1，G2＝V2,E2为两个无向图， 若存在双射函数f：V1→V2，对于vi,vj∈V1，(vi,vj)∈E1当且仅当 (f(vi),f(vj))∈E2， 并且(vi,vj)与(f(vi),f(vj))的重数相同， 则称G1与G2是同构的(isomorphic)，记做G1≌G2。 说明 (1) 点数、边数和度数列对影响等。 (2) 在图同构的意义下，图的数学定义与图形表示是一一对应的。 ;≌;完全图(complete graph);完全图举例;子图(subgraph);例：画出K4的所有非同构的生成子图。 解 :K4的所有非同构的生成子图如图所示 ;导出子图举例;例3 画出4阶3条边的所有非同构的无向简单图。 由握手定理可知，所画的无向简单图各顶点度数之和为2×3＝6，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：;定义9 设G＝V,E为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图(complementary graph)，记