第五章图的基本概念图论起源于1736年欧拉（Enler）的第一篇图论论文，解决了“哥尼斯堡的七桥问题”。在哥尼斯堡的匹格河上有七座桥如图所示。a啤止式
第五章 图的基本概念 • 图论起源于1736年欧拉(Enler)的第一篇 图论 论文, 解决了“哥尼斯堡的七桥问 题” 。在哥尼斯堡的匹格河上有七座桥, 如图所示
很显然，通过哥尼斯堡七座桥中每一座一次且仅一次的问题等价BC于在图5.13(b)中找一特睡家推条闭链，个震只上使得它的每一边出现明玉一次且仅一次，也就是(b)尚海i如何一笔画的问题。·后来称此问题为哥尼斯堡七桥问题·在图a中，用边表示桥.顶点表示岛屿和河的两岸，便得到一个图，如图b所示
• 当时人们热衷于这样的游戏：设想从任一 个地方出发通过每座桥一次且仅一次后回 到原地, 这是否可能?但多次实践都发现不 行 • 1727 年欧拉的朋友向欧拉提出了这个问题 是否有解？ • 1736 年欧拉用图论的方法解决了这个问题, 写了第一篇图论的论文,成为图论的创始人。 • 后来称此问题为哥尼斯堡七桥问题。 • 在图a中,用边表示桥,顶点表示岛屿和河的 两岸,便得到一个图,如图b所示。 很显然,通过哥尼斯堡 七座桥中每一座一次 且仅一次的问题等价 于在图5.13 (b)中找一 条闭链, 使得它的每一边出现 一次且仅一次, 也就是 如何一笔画的问题
但在此之后100年间，没有大的进展。直到Kirchhoff(克希霍夫）用树的理论解决了电网络问题1857年Cayler（凯莱）用统计不同构树的方法来计算C,H，同分异构体数目，这些结果引起了人们的重视，图论的研究进入了一个发展时期，在此期间，出现了两个著名的问题：四色问题和Hamilton回路问题，成为不少数学家的研究目标。，但在19世纪后期和二十世纪初，图论的研究再次处于停顿状态。直到1920年，科尼格（Konig）檬写了许多图论方面的论文在1936年科尼格（Konig）发表了第一本图论书籍《有限图与无限图理论》，总结了200年来图论研究的主要成果
• 但在此之后100年间，没有大的进展。 • 直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题， • 1 8 5 7年 Cayler(凯莱 )用统计不同构树的方法来计算 CnH2n+1同分异构体数目, • 这些结果引起了人们的重视,图论的研究进入了一个发展 时期, • 在此期间,出现了两个著名的问题:四色问题和Hamilton 回路问题,成为不少数学家的研究目标。 • 但在19世纪后期和二十世纪初，图论的研究再次处于停 顿状态。 • 直到1920年,科尼格(Konig)攥写了许多图论方面的论文, • 在1936 年科尼格(Konig)发表了第一本图论书籍《有限图 与无限图理论》，总结了200年来图论研究的主要成果
·此后的50年，图论经历了一场爆炸性的发展成为数学科学中一门独立的学科。·主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。，几十年来图论在理论上和应用上都得到很大的发展，特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。·在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。，这里主要讨论图的基本概念和算法，为今后的学习和研究打下基础
• 此后的50年，图论经历了一场爆炸性的发展， 成为数学科学中一门独立的学科。 • 主要分支有图论、超图理论、极值图论、算法 图论、网络图论和随机图论等。 • 几十年来图论在理论上和应用上都得到很大的 发展,特别是在近30多年来由于计算机的广泛应 用而又得到飞跃的发展。 • 在计算机科学、运筹学、化学、物理和社会科 学等方面都取得了不少成果，对计算机学科中 的操作系统研究、编译技术、人工智能和计算 机网络等方面都有广泛的应用。 • 这里主要讨论图的基本概念和算法，为今后的 学习和研究打下基础
5.1 引言一、图的定义：·在集合论中离散对象之间的关系可以用关系图来描述，这种图就是图论中所述的有向图。·定义5.1：设V是一个非空集，E是V上的二元关系,称有序对(V,E)为有向图，记为G-(V,E）或G(V,E)。V中的元素称为顶点（或点）,V称顶点集。E是VXV的子集，E中的元素是有序对，称为弧，E称为弧集
5.1 引言 • 一、图的定义： • 在集合论中离散对象之间的关系可以用关 系图来描述,这种图就是图论中所述的有向 图。 • 定义5.1：设V是一个非空集,E是V上的二元 关系,称有序对(V, E)为有向图,记为G=(V,E) 或G(V,E)。V中的元素称为顶点(或点),V称 顶点集。E是V×V的子集,E中的元素是有 序对,称为弧,E称为弧集