1701009750
我和数学有约：趣味数学及算法解析 [:1701004258]
1701009751
我和数学有约：趣味数学及算法解析 8.4 七桥问题
1701009752
1701009753
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”，如图8-14所示，结构简图如图8-15所示。
1701009754
1701009755
1701009756
1701009757
1701009758
图8-14 哥尼斯堡的七座桥 图8-15 结构简图 1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”的游戏，用图论的术语，就是如何找出一个连通图中的生成圈。
1701009759
1701009760
近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学、生物遗传学、心理学、经济学和社会学等学科中。
1701009761
1701009762
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。
1701009763
1701009764
1701009765
1701009766
1701009767
图8-16 七桥模型树形图
1701009768
1701009769
哥尼斯堡七桥问题就是一个典型的例子，简化的树形图如图8-16所示。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连接起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。
1701009770
1701009771
如图8-16所示，图是由一些点和连接这些点的若干线段组成的，这些点称为图的顶点，这些线段称为图的边，称如下二元组为图G：
1701009772
1701009773
G=（V（G），E（G））
1701009774
1701009775
1701009776
1701009777
式中称为顶点集，V中元素的个数称为图G的顶点数；图G的顶点个数又被称为图的阶，只有一个顶点的图称为平凡图；称为边集，E中元素的个数称做图G的边数。在不致混淆的情况下，可以将顶点集和边集简记为V和E，图可简记为G=（V，E）。V和E都是有限集的图称为有限图；否则称为无限图。
1701009778
1701009779
我和数学有约：趣味数学及算法解析 [:1701004259]
1701009780
8.4.1 有向图与无向图
1701009781
1701009782
1701009783
1701009784
1701009785
1701009786
如果对于，均有，称该图为无向图；否则对于该图有，即图中的边具有方向性，是一个有序对，称该图为有向图。对于有向图称如下二元组为有向图G：
1701009787
1701009788
G=（V，A）
1701009789
1701009790
1701009791
1701009792
1701009793
1701009794
1701009795
1701009796
称为图G的顶点集，通常称有向图的边为弧，称为图G的弧集，A中的每一个元素al，即V中某两个元素Vi，Vj的有序对可以记为，被称为该图的一条从Vi到Vj的弧。对于，存在如下关系：且。
1701009797
1701009798
对于有向图G=（V，A），存在着顺序映射关系：
1701009799