|
1. 引言 图论是数学中有着广泛实际应用的一个分支，图是用点和边来描述事物和事物之间的关系，是对实际问题的一种抽象，之所以用图来解决问题，是因为图能够把纷杂的信息变得有序、直观、清晰. 自然界和人类社会中的大量事物以及事物之间的关系，常可用图形来模拟并转化为图论的问题. copyright paper51.com 图论的起源 内容来自www.paper51.com 1735年8月26日, 欧拉向圣彼得堡科学院提交了一篇名为“有关位置几何的一个问题的解”的论文, 其中涉及的问题据他说在当时是广为人知的:“在普鲁士的哥尼斯堡有一个称为‘奈发夫’的岛A；普雷格尔河的两支从岛的两旁流过，并且有七座桥横跨这两条支流(图1—1). 问能否设计一次散步，使得人们恰 内容来自www.paper51.com
http://www.paper51.com
图1—1 图1—2 内容来自www.paper51.com 好走过每座桥一次.”对此欧拉给出了否定的解答并在更一般的意义上进行了讨论. 欧拉给出的最终结论是：“如果通奇数座桥的地方不止两个，则满足要求的路线是找不到的（图1—2） ，然而, 如果只有两个地方通奇数座桥, 则可以从这两个地方之一出发, 找出所要求的路线. 最后, 如果没有一个地方是通奇数座桥的, 则无论从哪里出发, 所要求的路线总能实现.” paper51.com 2. 图论的基本概念 http://www.paper51.com 2. 1. 图的定义 copyright paper51.com 定义1 内容来自www.paper51.com 有序三元组G=(V,E,)称为一个图. http://www.paper51.com (1) V=是有穷非空集，称为顶点集，其中的元素叫图G的顶点. http://www.paper51.com (2) E称为边集，其中的元素叫图G的边. http://www.paper51.com
(3) 是从边集E到顶点集V中的有序或无序的元素偶对的集合的映射，称为关联函数. http://www.paper51.com
例1 设G=(V,E,)，其中V={v1 ,v2, v3 , v4}，E={e1, e2 , e3, e4, e5,e6}, paper51.com
G的图示（图1—3）. http://www.paper51.com
copyright paper51.com 图1—3 图1—4 内容来自论文无忧网 www.paper51.com 定义2 内容来自论文无忧网 www.paper51.com 在图G中，与V中的有序偶(vi copyright paper51.com |