【数学建模算法】(9)树

2024-01-23 17:41| 来源: 网络整理| 查看: 265

1.基本概念

联通的无圈图叫做树，记做为T。若图 $G$ 满足 $V(G)=V(T)$ ， $E(T) \subset E(G)$ 则称 $T$ 是 $G$ 的生成树。图 $G$ 联通的充分必要条件为 $G$ 有生成树。一个连通数的生成树很多，用 $\tau(G)$ 表示 $G$ 的生成树的公式，则有公式：

$\tau\left(K_{n}\right)=n^{n-2}$ （ $K_{n}$ 代表有 $n$ 个顶点的完全图） $\tau(G)=\tau(G-e)+\tau(G \cdot e)$ （ $G-e$ 代表从 $G$ 中删除边 $e$ ， $G \cdot e$ 表示把 $e$ 的长度）

树有下面常用的五个充要条件：

1. $G$ 是树当且仅当 $G$ 中任二顶点之间有且仅有一条轨道。 2. $G$ 是树当且仅当 $G$ 无圈，且 $\varepsilon=v-1$ 3. $G$ 是树当且仅当 $G$ 联通，且 $\varepsilon=v-1$ 4. $G$ 是树当且仅当 $G$ 联通，且 $\forall e \in E(G), \quad G-e$ 不连通。 5. $G$ 是树当且仅当 $G$ 无圈， $\forall e \notin E(G), \quad G+e$ 恰有一个圈。

2.应用——连线问题

欲修筑连接n个城市的铁路，已知 $i$ 城和 $j$ 城之间的铁路造价为 $C_{i j}$ ，设计一个线路图，使总造价最低。连线问题的数学模型是在联通赋权图上求权最小的生成树。赋权图上具有最小权的生成树叫做最小生成树。下面介绍构造最小生成树的两种常用算法。

2.1.prim算法构造最小生成解

设置两个集合 $P$ 和 $Q$ ，其中 $P$ 用于存放 $G$ 的最小生成树中的边。令集合 $P$ 的初值为 $P=\left\{v_{1}\right\}$ （假设最小生成树时，从顶点 $v_{1}$ 出发），集合 $Q$ 的初值为 $Q=\Phi$ 。prim算法的思想是，从所有 $p \in P, \quad v \in V-P$ 的边中，选取具有最小权值的边 $pv$ ，将顶点 $v$ 加入集合 $P$ 中，将边 $pv$ 加入集合 $Q$ 中，如此不断重复，直到 $P=V$ 时，最小生成树构造完毕，这时集合 $Q$ 中包含了最小生成树的所有边。

prime算法如下： 1. $P=\left\{v_{1}\right\}, \quad Q=\Phi$ 2.while $P \sim=V$ $\quad$ 找最小边 $pv$ ，其中 $p \in P, v \in V-P$ $\quad$ $P=P+\{v\}$ $\quad$ $Q=Q+\{p v\}$ end

例1 利用Matlab生成下面这张图的最小生成树

例1图

clc;clear; a=zeros(7);%定义权值矩阵 a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;%赋值 a=a+a';%对称矩阵 a(find(a==0))=inf;%没有直接通路的定义为无限大 result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result 2.2 Kruskal算法

1.选 $e_{1} \in E(G)$ ，使得 $w\left(e_{1}\right)=\min$ 。 2.若 $e_{1}, e_{2}, \cdots, e_{i}$ 已选好，则从 $E(G)-\left\{e_{1}, e_{2}, \cdots, e_{i}\right\}$ 中选取 $e_{i+1}$ ，使得： (1) $G\left[\left\{e_{1}, e_{2}, \cdots, e_{i}, e_{i+1}\right\}\right]$ 中无圈 (2) $w\left(e_{i+1}\right)=\min$ 3.直到选得 $e_{\mathrm{v}-1}$ 为止

Matlab程序：

a(4,7)=42; a(5,6)=70; [i,j,b]=find(a); data=[i';j';b'];index=data(1:2,:); loop=max(size(a))-1; result=[]; while length(result)

【本文地址】

【数学建模算法】(9)树

【数学建模算法】(9)树

今日新闻

推荐新闻