图论及算法张莉Tongji University
图论及其算法 张莉 Tongji University
S1最小支撑树问题一.基本概念1.树：无回路的无向连通图2.叶：树中度数为1的顶点3.森林：连通分支大于1，且每个连通分支均为树的非连通图
§1 最小支撑树问题 1. 树：无回路的无向连通图. 一.基本概念 2. 叶：树中度数为1的顶点. 3. 森林：连通分支大于1，且每个连通分支均为 树的非连通图
二.最小生成树解：寻找最小生成树
二.最小生成树 解：寻找最小生成树
列2：假设在一个没有良好高速公路的偏远地区涌现了几个城市，理想的是建筑足够多的高速公路使得城市之间或者直接通过高速公路往来，或者可以通过去其他城市来实现彼此的互相往来，现在我们希望成本最小化注：（1)成本最小化即：可以实现城市间的互通，同时每条高速路都不浪费（即去掉后就不能互通了）2)不允许高速路在所研究的城市以外的某点处连接
例2：假设在一个没有良好高速公路的偏远地区涌现 了几个城市，理想的是建筑足够多的高速公路， 使得城市之间或者直接通过高速公路往来，或 者可以通过去其他城市来实现彼此的互相往来. 现在我们希望成本最小化. 注: (1)成本最小化即：可以实现城市间的互通，同时， 每条高速路都不浪费(即去掉后就不能互通了). (2)不允许高速路在所研究的城市以外的某点 处连接
最短网络问题AB此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和(如ABUAC)
此问题可抽象为设△ABC为等边三角形，连接三 顶点的路线（称为网络）。这种网络有许多个， 其中最短路线者显然是二边之和(如AB∪AC). A B C 最短网络问题: