图论

1.什么是图论

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

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

2.图论的发展

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

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