图论

出自 MBA智库百科(https://wiki.mbalib.com/)

图论(Graph Theory)

　　图论是指研究图和网络的数学分支，常被认为包含于组合数学中，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题。

　　图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

　　由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的应用。特别是电子计算机的大量应用，更使大规模图论问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。

　　目前图论在电信网络、开关理论、编码理论、可靠性理论、计算机程序设计、故障诊断、人工智能、印刷电路板的设计、图案识别、地图着色等计算科学的学科领域都有十分广泛的应用。