资源描述：
《第1章 图和子图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论及其应用1图的基本概念2树3连通度4遍历问题5匹配6着色问题7平面图8有向图9网络10NP-完全问题第一章图的基本概念1.1图的概念1.2同构1.3图的矩阵和顶点的度1.4子图1.5路和连通性1.6圈1.7最短路问题1.1图的概念Königsberg七桥问题电网络四色猜想图G=(V(G),E(G))，其中V(G)={}V---顶点集，---顶点数E(G)={}E---边集，ε---边数例如，下图中，V={a,b,…,f},E={k,p,q,ae,af,…,ce,cf}defG=(V,E)pqabck注意，右图仅仅是图G的一个几何实现（geometri
2、crealization,代表representation），它们有无穷多个，随顶点位置及边的形状而不同。真正的图G是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对图G及其几何实现将经常不加以区别。defG=(V,E)pqabck称边ad与顶点a(及d)相关联(incident)。也称顶点b(及f)与边bf相关联。称顶点a与e相邻(adjacent)。也称有公共端点的一些边，例如p与af彼此相邻。称一条边的两个顶点为它的两个端点环（loop，selfloop）：如边k，它的两个端点相同。棱（link）：如边ae，它的两个端点不相同。重边：如边
3、p及边q。简单图：（simplegraph）无环，无重边平凡图：仅有一个顶点的图。注意：任何一图都有V。记号：（,）defG=(V,E)pqabck例题1.1若G为简单图，则。1.2若一群人中，凡相识的两人都无公共朋友，凡不相识的两人都恰有两个公共朋友，则每人的朋友数相等。1.2同构例如在下图中，称图G恒等于图H(记为G=H)VG)=V(H),E(G)=E(H)。ayzxwbcdeG=(V,E)x’d’w’a’b’c’y’e’z’F=(V’,E’)xwbcdeayzH=(V,E)图G同构于图F（记为GF）V(G)与V(F),E(G)与E(F)
4、之间各存在一一映射，及且这二映射保持关联关系，即：ayzxwbcdeG=(V,E)xwbcdeayzH=(V,E)x’d’w’a’b’c’y’e’z’F=(V’,E’)注两个图同构是指”它们有相同的结构”，仅在顶点及边的标号上或两个图的画法上有所不同而已。往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。注判定两个图是否同构是个未解决的困难问题（openproblem）。ayzxwbcdeG=(V,E)xwbcdeayzH=(V,E)x’d’w’a’b’c’y’e’z’F=(V’,E’)完全图(completegraph)Kn空图（empty
5、g.）E=。V’(V)为独立集V’中任二顶点都互不相邻。二部图（偶图，bipartiteg.）G=(X,Y;E)存在V(G)的一个2-划分(X,Y)（即V(G)=X∪Y，且X∩Y=），使X与Y都是独立集。K1K2K3K4K5完全二部图Km,n二部图G=(X,Y;E)，其中X和Y之间的每对顶点都相邻，且X=m,Y=n。类似地可定义，完全三部图（例如，Km,n,p），完全n-部图等。二部图K3,3K1,5K2,2,2例。用标号法判定二部图。用红蓝两种颜色进行顶点标号如下：任取一顶点v标以红色。再将v的所有相邻顶点都标以兰色。这时称v为已
6、扫描顶点。若尚存在一已标号未扫描顶点u，将它的所有相邻顶点，（若不出现矛盾）都标以（其相异色）红色，并称u为已扫描顶点。如此继续下去，直到或者所有顶点都已标号，从而该图为一二部图；或者在标号过程中出现矛盾，该图为非二部图。习题1.2.1GH(G)=(H),(G)=(H)。并证明其逆命题不成立。1..2.2证明下面两个图不同构：1.2.3证明下面图1与图2是同构的；而图1与图3是不同构的：1.2.4证明两个简单图G和H同构存在一一映射f:V(G)V(H)，使得uvE(G)当且仅当f(u)f(v)E(H)。图1图2图31.2.5证明：(a
7、).(Km,n)=mn;(b).对简单二部图有2/4.1.2.6记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明：(a).(Tm,n)=其中k=[n/m].(b)*.对任意的n顶点完全m-部图G，一定有(G)(Tm,n)，且仅当GTm,n时等式才成立。1.2.7所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有2k个顶点，k*2k-1条边，且是一偶图。1.2.8简单图G的补图Gc是指和G有相同顶点集V的一个简单图，在Gc中
8、两个顶点相邻当且仅当它们在G中不相邻。(a).画出Kcn和Kcm,n。(b).如
