图论

---

研究抽象地描述客观世界诸事物诸现象间相互联系的图示的性质、规律性的理论。

早在18世纪，就出现了图论，它是由欧拉(Euler)首先解决著名的königsberg七桥问题而产生出来的。因此，欧拉被公推为图论之父。

图G一般是由非空结点集合v和边集合E组成，记作G=(v，E)。结点表示诸事物或现象，边表示两结点的某种联系。

例如：结点表示城市，边表示两城市间有一条公路，这就构成了一张城市交通图。对于一个图G，如果要考虑联系的次序性，则G是有向图，否则，G是无向图。

在上例中，公路的方向如果需要考虑时(例如公路是单向的)，就是有向图了。图论研究的内容很多。

例如，在同构和偶图等概念下，讨论了图的结构和性质；在引进无向图的链和圈，有向图的路和回路以及连通性等概念后，探讨了欧拉图、哈密尔顿图以及图的联接性。特别是，对最佳路径问题和图的特例树形的研究，在计算机科学方面有很广泛的应用。

图论是一门很有实际背景的学科，正因为如此，近年来，发展迅速，渗透到各门学科之中，它在形式语言、数据结构、分布式系统、操作系统等计算机科学的重要领域都有很重要的应用。