第1章图的基本概念
迷人的图论世界可以追溯至近300年前，其中蕴藏着大量深刻理论和众多未解难题.本章概述图论发展历史、现状、图论问题的特点，主要介绍图、度、子图等基本概念和常用术语.
1.1图论发展历史与特点
伴随着人类社会的发展进步，人们逐渐发现：在人类的生产实践中，越来越多的研究对象可以用“图”来描述.
1.1.1图论起源
1736年，Euler研究并解决了一个著名问题——Konigsberg七桥问题.这一年是图论的诞生元年，Euler是图论的创始人.
18世纪，属于德国东普鲁士的K6nigsberg市被Pregel河穿城而过，河上有七座桥，如图1.1(a)所示.这七座桥把两岸与河中的两个小岛连接起来.Konigsberg的市民在桥上经过时提出了这样一个有趣的问题：四块陆地中的某一块出发，通过每座桥一次且仅一次再回到原出发地，是否可能？人们不断探索都没能成功，便去请教瑞士的大数学家Euler，Euler指出这个问题的答案是：不可能.
Euler并不像K6nigsberg市民那样去桥上实地考察，而是把四块陆地抽象成四个几何点，把桥抽象成连接相应几何点间的线得到图1.1(b)，从而使问题得到解决.Euler把他的研究成果整理成文字，把几何点称为顶点，几何点间的连线称为边，发表图论*篇论文，标志图论诞生.
Konigsberg七桥问题表面上看起来只是一种游戏而已，似乎没有多大意义，但随着图论的发展，与其相关的理论在编码及计算机磁鼓设计丨见第5章)等领域都有重要的应用.更重要的是Euler解决这一问题的论证方法开创了图论科学研究的先河.
1.1.2图论发展
Euler解决K6nigsberg七桥问题后，人们在其他领域也发现了图论相关问题.
1.电网络中的图论
1847年，KirchhofF为了解一类线性方程组而发展了树的理论.这个线性方程组描述一个电网络的每条支路中电流和环绕每一个回路的电流.Kirchhoff虽然是一个物理学家，但却可以像数学家那样思考问题，他把一个电网络和其中的电阻、电容、电感等抽象化：像Euler那样，用一个只由点和线组成的相应的组合结构来代替原来的电网络，而并不指明每条线所代表的电气元件的种类(图1.2).这样一来，Kirchhoff实际上是把每个电网络用它的基本图代替.他还证明，解这个方程组时，只要考虑一个图的任何一个支撑树所决定的那些基本圈就足够了.他的这个方法现在已成为一个标准的方法.
2.有机化学中的图论
1857年，Cayley非常自然地在有机化学领域里发现了一族重要的图一树.在研究给定碳原子数n的饱和碳氢化合物的同分异构物的数目的过程中，把碳原子和氢原子都抽象成点，把化学键抽象成相应原子间的连线，于是问题转化为求有3n+2个点的树的数目，其中每个点的度丨与该点相连的线的数目)等于1或4.Cayley没有能够立即成功地解决这个问题，所以他改换了这个问题，逐步计数了：有根树、树、每个点的度至多等于4的树，并*终解决了每个顶点的度为1或4的树的计数问题.后来，Jordan从一个纯数学的角度*立地发现了树.
3.四色问题
1852年，一个叫FrancisGuthrie的伦敦学生提出了四色问题：在地图或地球仪上，能否*多有四种颜色即可把每个国家的版图染好，使得国界两侧异色？在图论中，也许在整个数学中，*出名的没有解决的问题就是著名的四色问题.这个问题是如此之简单，以至于任何一个数学家都可以在五分钟之内将这个非凡的问题向马路上的任何一个普通人讲清楚，可另一方面，这个问题又是如此之复杂，以至于时至今日，尚未能找到完整的理论性证明.
19世纪，图论研究越来越广泛深入，大批优秀的数学家潜心研究，为图论宝库增添了一个又一个精彩成果.同时，也积累了大量的各种各样的难题，如Hamilton图问题.Hamilton图是指顶点分布在同一个圆周上的图.1857年，Hamilton玩环游世界的游戏时提出了该问题.至今Hamilton图的非平凡的充要条件尚未建立.又如，Ramsey问题，直观地讲，Ramsey问题就是：任给一群人，要么该人群中有k个人互相认识，要么有I个人互相不认识，问满足这种要求的人群至少有多少人？用表示人群中的人数.目前，人们已知的Ramsey数只有有限的几个，如，大部分的Ramsey数都是未知的.
20世纪，随着现代生产和科学技术的发展，图论经历了一场爆炸性的发展.1936年，**本图论著作诞生了，这就是著名的匈牙利图论专家K6nig所著的《有限图和无限图理论》，它总结了图论两百年的主要成果，是图论发展史上的重要里程碑.此后，图论开始迅速发展，并*终从组合数学中*立出来，成长为数学科学中一门*立分支.科技的迅猛发展向图论提出了越来越多的需要解决的问题，使图论在科学界活跃非常，尤其是计算机科学的快速发展，为图论及其算法的实现提供了强大的计算与证明的手段，这进一步促进了图论广泛应用，图论被称为离散领域“微积分图论已经形成了自身比较固定的理论体系框架.书后的文献就是国内外介绍图论基本概念、理论和算法的典型著作，这些著作的内容和文风为本书稿提供了理论滋养与风格供鉴.
1.1.3图论现状与特点
进入21世纪，图论更加迅速地向前发展，其应用领域更为广泛，可以说，21世纪的人们正生活在图(网络)的世界里.比如，社交网络图(见图1.3(a))、无人机集群的通信网络图(见图l.3(b))等等.
生活中充满各种图，而且图的规模越来越大，结构越来越复杂.
例如，网购时，客户和购买的产品之间构成图.把客户和产品都用小圆圈表示，若客户购买了某产品，就在相应小圆圈间连接一条带箭头的线(称为有向边)，如图1.4(a)是一个客户-产品图.进一步地，若发现客户之间还有认识关系，则可以在客户之间连接带箭头的线，如图1.4(b)所示，在此图中，客户2有可能因为看到他认识的客户4在用产品1而成为潜在客户，商家可以向客户2**产品1.同样，产品之间也可能有上下游产品，或者替代产品等关系，从而可以获得更为复杂的客户-产品图.
又如，在工作中，公司的成员间形成了组织结构图；发邮件、发微博时，则产生交流图；等等.
工程技术研究中充满各种图.在自然语言处理中常用知识图谱，它是用来表示领域知识、促进知识推理不可或缺的图；在生物研究中的蛋白质网络，它是能够表示蛋白质之间相互作用的图；在物联网传感器之间需要连接共同获取监测状态，它是表示传感器相互连接状态的图；互联网中的链接关系是让所有网页形成链接图；论文中的引用关系是让所有论文形成引文图；金融交易是让交易双方形成交易图 此类例子不胜枚举.
甚至在很多看起来没有明显图关系的研究中，人们也发现可以利用图去获得新的突破.比如，文本摘要中利用句子之间的相似性构建的图，就是一个典型的例子，它对早期文档摘要领域做出了巨大的贡献；在定理证明中，逻辑表达式可以表示成由变量和操作构成的图；程序也可以表示成由变量构成的图，用来判断正确性;在多智能体系统中，智能个体之间的隐性交互也被当作图来处理.
自从1736年，Euler研究K6nigsberg七桥问题以来，图论经历了近300年由慢到快的发展历程.目前，图论领域形成了两个不同的研究方向：一个是以研究图的性质为主，我们称之为抽象图论；另一个是以研究网络算法为主，我们称之为算法图论，也称之为网络*优化.作为一本入门级教材，本书中我们将兼顾两者，以介绍基本图论理论和算法为主要目标.
图论之所以迅速发展，究其原因，除了现代科学技术的推进作用之外，更重要的是图论自身的特点：表达直观和思维方法巧妙灵活.
图论问题表达直观.图论往往把所研究的对象抽象成几何点，把对象间的关系抽象成相应几何点间的连线，这种研究方法就把所研究的问题转化为一个符合美学外形的图，使问题变得直观，形式简洁，从而使人们更容易理解问题的本质并对问题产生兴趣.同时，也正是图论的图解式表示方法，为科学探索提供了一种自然的而又非常重要的语言和框架.
图论问题思维方法巧妙灵活.许多图论问题都是从智力难题和游戏中提炼出来的，有些问题在本质上是初等的，但其中也有大量的问题可以难倒*老练的数学家.
图论问题的解决需要巧妙的方法，没有可循的程式.问题外表的简单朴素和本质上的难以解决，使每个从事图论研究的人在图论问题面前都必须谨慎、严肃、深入地思考.因而，学习图论可以锻炼思维，借助图论的思维方法可以提高解决问题的能力.
运用图论知识解决实际问题是锻炼数学思维的有效途径之一.要获得图论思维，除了掌握大量图论知识和理论，以及勤奋和努力外，更需要的是智慧和技巧，是智力上的投入.有人将图论学习比喻为思维体操，它可以让思维高度活跃，充分延伸.
1.2图的定义
在图论问题研究中，人们感兴趣的是研究对象之间是否具有某种特定的二元关系.比如，Konigsberg七桥问题中，我们关心的是，两块陆地之间是否有以及有几座桥相连.因此，小圆圈之间有多少连线是重要的，而小圆圈的位置以及连线的长短*直则无关紧要.也就是说，图论中所研究的图并不是几何图形、工程图或美术图画，它在本质上是二元关系的抽象描述.
1.2.1定义
图论中的图由小圆圈和连线构成，我们把图中的小圆圈叫做顶点，把连线叫做边.下面介绍它的严格数学定义.
定义1.1(图)图(graph)是指一个三元组(F(G)，E(G)，如\其中F(G)+0，F(GO门五(GO=0，V(G)中的元素称为顶点(vertex或node)，通常用v表示，V(G)称为顶点集;五(G)中的元素称为边(edge)，通常用e表示，丑(G)称为边集；如称为关联函数(incidence function)，它是使G中的每条边对应于G的无序顶点对的函数.图G中顶点数|F(G)|称为图的阶(order)，用p(G)表示;边数用s(G)表示.
例1.1设
解用小圆圈表示顶点，若边e与和;关联，则在相应顶点小圆圈间连一条线，于是，可得到G的图形表示，如图1.5所示.该图有6个顶点7条边，故.
为了书写方便，以后我们通常把图简记为，此时G中的边只需要用它的两个端点的无序对来表示.比如，例1.1中的图0可表示为0=7(0)，五(0))，其中
需要指出的是，在这种记号下，E(G)中有些元素是重复的，如边在E(G)中出现两次.同时，当我们只讨论一个图时，常常省略G，分别用V，五代替.
若eGE(G)，且如(e)=uv，则称e连接u和或称e与u及v失联(incident)，而m和称为e的端点(end)，也称u与v是相邻的(adjacent).把G中所有与v顶点相邻的顶点的集合称为v的邻域(neighbour)，记为NG(v)或N(v).把G中所有与v顶点相关联的边的集合称为v的边邻域(edge neighbour)，记为N岂{v)或NE(v).如图1.5中，边e；L与顶点Vi和v2关联;v6与相邻且.
与同一个顶点关联的两条边称为是相邻的(adjacent);两个端点重合的边称
展开
