第14讲 图的有关概念, 节点的度数 n 主要内容: n 1. 图的有关概念. n 2. 节点的度数. n 3. 子图与图的同构.Chapter 7 图论 n 图论的创始人是瑞士数学家L. Euler ，他于1736 年首次建立“ 图” 模型解决了Kningsberg 七桥问 题. n 图论的应用领域非常广泛，它已经渗透到诸如语 言学、逻辑学、物理学、化学、电信工程、信息 论、控制论、经济管理等各个领域，特别是在计 算机科学中的数据结构、计算机网络、计算 机软件、算法理论、操作系统、分布式系 统、编译程序以及数据挖掘等方面都扮演着 重要角色. 7.1 图的基本概念 n 哥尼斯堡(Kningsberg) 七桥问题: n 问题是: 是否可从某一个地方出发，经过七座桥，每座桥 只经过一次，然后又回到原出发点. n 程序调用的图论模型: n e 8 : v 3 可调用v 2 ; e 1 : v 2 可调用v 1 ; e 4 : v 5 可调用v 5 自身. 单行道; 好感?n 1.图的定义 n 由前面的2个例子可以得出 n Definition 图G(graph) 主要由2部分组成: n (1
