第七章 图
在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。图论起源于18世纪，它是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 天下第一蛋图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：
第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题：从四块陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。 C
B A A
D
这个问题看似简单，但实际上却非常困难。Euler在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。
Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。
第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四问题(1852年)和Hamilton环游世
界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的Kirchoff(克希霍夫)将图论应用于工程技术的电网络方程组的研究。1857年英国的Cayley(凯莱)提出了树的概念，应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家Konig(哥尼格)写出了第一本图论专著《有限图与无限图的理论》。标志着图论作为一门独立学科。
第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。
7.1孙晋芳丈夫江伟光照片 图的基本概念
图的定义
定义7.1.1 设A，B是任意集合。集合{(a,b)|aA且bB}称为A和B的无序积，记为A＆B。 在无序积中，两个元素间的顺序是无关紧要的，即(a,b)＝(b,a)。
定义7.1.2 无向图G是一个二元组<V，E>，记作G＝<V，E>，其中V是一个非空有限集合，其元素称为结点(顶点)。E是一个V＆V的多重子集，其元素称为边。 我们可用平面上的点来表示顶点，两点间的连线表示边，从而将任一个无向图用图形表示出来。
［例7.1.1］ 无向图G＝<V，E>，其中V={a，b，c，d，e，f}，E={(a,b)，(a,c)，(a,d)，(b,b)，(b,c)，(b,c)，(b,d)，(c,d)}。
解 例7.1.1.doc
注：在无向图G＝<V，E>中，
1) 若边e=(u,v)，则称u和v是边 e的端点，称边 e关联于u和v，并称u和v是的邻接的或相邻的；
2)关联于同一个顶点的边称为自回路；若关联于同一对顶点的边多于一条时，称这些边为
平行边，其称为边(u,v)的重数；
3)不与任何顶点邻接的顶点称为孤立点；全由孤立点组成的图称为零图；含有平行边的图称为多重图，非多重图称为线图；无自回路的线图称为简单图；仅有一个孤立结点的零图称为平凡图；顶点数和边数都是有限的图称为有限图。
［例7.1.2］ 零图，平凡图，多重图，线图和简单图。
解 例7.1.2.doc
定义7.1.3 有向图G是一个二元组<V，E>，记作G＝<V，E>，其中V是一个非空有限集合，其元素称为顶点，E是一个VV的多重子集，其元素称为有向边或弧，简称为边。
注：1)在有向图碱性氧化物G＝<V，E>中，若e=〈u，v〉，则称u和v为e的起点和终点；
2)自回路既可看成是有向边又可看成是无向边；
3)去掉有向图中边的方向得到的图称为该有向图的底图。
［例7.1.3］ 有向图G＝<V，E>，其中V={a，枯草菌素b，c}，E={<a,a>，<a,a>，<a,b>，<b,c>，<b,c>，<c,b>}。
解 例7.1.3.doc
顶点的度数
定义7.1.4 (1)在无向图G=〈V，E〉中，v∈V。与v关联的边数称为v的度数，记为deg(v)；
(2) 在有向图G=〈V，E〉中，v∈V。以v为始点的边数称为v的出度，记为deg＋(v)；以v为终点的边数称为v的入度，记为deg－(v)；称deg(v)= deg＋(v)+ deg－(v)称为v的度(数)。
［例7.1.4］ 求例7.1.1中无向图每个顶点的度数；求例7.1.3中有向图每个顶点的出度、入度和度。
解 例7.1.4.doc
注：若结点有自回路，则结点的度数因此而增加2；若有向图的结点v有自回路，则它的出度和入度分别因此而增加1。孤立结点的度数为0。
定理7.1.1 (Euler握手定理) 在图G=<V，E>中, deg(v)=2|E|。推论7.1.1 任何图中度数为奇数的结点为偶数个。
证明 推7.1.1.doc
定理7.1.2 在有向图G=<V，E>中有
deg＋(v)= deg－(v)=|E|。
子图
定义7.1.5 设图G=<V，E>和G´=<V´，E´>，
（1） 若V´Ｖ，Ｅ´Ｅ，则称Ｇ´是Ｇ的子图，记为G´G；
（2） 若G´G且V´Ｖ或Ｅ´Ｅ，则称Ｇ´是Ｇ的真子图，记为G´G；
（3） 若G´G且V´=V，则称Ｇ´是Ｇ的生成子图(支撑子图)；
（4） 若G´G且Ｅ´是所有端点均在V´中的G的边组成的集合，则称Ｇ´是由V´诱导出的Ｇ的子图；
（5） 若G´G且V´是以E´中边的所有端点组成的集合，则称Ｇ´是由Ｅ´诱导出的Ｇ的子图。
［例7.1.5］ 求例7.1.1中无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。
解 例7.1.5.doc
完全图、补图和图的同构
定义7.1.6 在无向简单图G=〈V，E〉中，|V|=n。若每对结点都邻接(即每对结点之间都有边)，则称之为无向完全图，记为Kn。
类似地，可以定义有向完全图。
［例7.1.6］ K2，K3，K4，K5及2、3、4、5个顶点的有向完全图。解 例7.1.6.doc
定义7.1.7 设G=<V，E>是简单图，|V|=n，H=<V， >。若E=且E=E(Kn)，则称图H是G的补图，记为。
G和互为补图。
［例7.1.7］ 求补图。
解 例7.1.7.doc
定义7.1.8 设图G1=<V1，E1>，G2=<V2，E土工合成材料2>。若存在双射f：V1—>V2，满足： u，v∈V1，[u,v]∈E1 [f(u),f(v) ]∈E2且[u,v]的重数和[f(u),f(v)]的重数相等 ([u,v]指(u,v)或[u,v])，则称G1和G2同构，记为G1≌G2。
由于一个图是由其顶点集和边集所决定的，而同构的两个图中顶点集之间存在一一对应关系，且这种对应关系保持顶点间的邻接关系及边的重数，故抽象地看，两个同构的图本质上是一样的。
［例7.1.8］ 同构图。
叠氮化钠解 例7.1.8.doc
两个图同构的必要条件：
顶点数相等; 边数相等; 所有顶点度数之和相等；度数相同的顶点数相等。
7.2 通路、回路和连通性
通路和回路
定义7.2.1 给定图G=〈V，E〉，设v0,v1,…,vn∈V，e1,e2,…,en∈E，其中vi-1，vi是边ei的端点(i=1,2,…,n)。称v0e1v1e2…en vn为从顶点v0到vn的通路，v0和vn 分别称为该通路的起点和终点；称通路上的边数为该通路的长度。
当v0和vn相等时，称该通路为回路或圈。
若通路(回路)的所有边都各不相同，则称该通路(回路)为简单通路(回路)；若通路(回路)的所有顶点都各不相同，则称该通路(回路)为基本通路(回路)。
［例7.2.1］ 求下图的通路、回路、简单通路、简单回路、基本通路和基本回路。
解 例7.2.1.doc
每一基本通路(回路)一定是简单通路(回路)；反之则不然。
在简单图中，可以用顶点序列来表示通路(回路)，当然在不产生二义性的前提下也可以用边的序列来表示通路(回)路。
定理7.2.1 给定图G=<V，E>，|V|=n，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。
证明 定理7.2.1.doc
推论7.2.1 给定图G=<V，E>，|V|=n，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的基本通路。
定理7.2.2 给定图G=<V，E>，|V|=n，uV。若存在经过u的一条回路，则必有一条经过u的长度不超过n的回路。
注： 在一个具有n 个顶点的图中，
1） 任何基本通路的长度均不大于n-1；
2） 任何基本回路的长度均不大于n。
定义7.2.2 给定图G=〈V，E〉，u,vV。若存在从u到v的通路，则称从u到v是可达的或称u可达v。
规定任一个顶点总是可达自身。
定义7.2.3 给定无向图G=〈V，E〉。若G的任何两个顶点是相互可达的，则称G是连通图，否则称G是非连通图。
在无向图G=〈V，E〉中，定义关系R为： u,vV，uRv u可达v。则R是V上的一个等价关系，从而可以决定V的一个划分，我们称每一个由划分块诱导出的G的子图为G的连通分支，用p(G)表示G的连通分支数。
每个顶点在且仅在一个连通分支中。若p(G)＝1，则G是连通图。
［例7.2.2］ 给出连通图、非连通图；图的连通分支。
解 例7.2.2.doc
定义7.2.4 给定有向图G=〈V，E〉。对任何两顶点u,vV，
（1） 若u和v相互可达，则称G是强连通的；
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议