📄 content-7-5.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF" background="IMAGE/Di.gif">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td>
<p style="line-height: 200%"><a name="content-7-4"></a>本节将介绍:</p>
<p style="line-height: 200%"><a href="#content-7-4-3">无向树</a>
、<a href="#有向树">有向树</a>及<a href="#二元树">二元树</a> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%" align="center" ><b><font size="5"><a name="content-7-4-3">无向</a>树</font></b></p>
<p style="line-height: 200%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
定义：</b>设 T=<V,E> 是一个连通无向图，如果 T 中没有任何循环，则称
T 是棵<b><font color="#0000FF">无向树</font></b>。 </p>
<table border="1" width="100%">
<tr>
<td width="25%">
<p align="center" style="line-height: 200%"><img border="0" src="Image/shu01.gif" width="11" height="11"></td>
<td width="25%">
<p style="line-height: 200%"><img border="0" src="Image/shu02.gif" width="83" height="77"></td>
<td width="25%">
<p style="line-height: 200%"><img border="0" src="Image/shu03.gif" width="164" height="129"></td>
<td width="25%">
<p style="line-height: 200%"><img border="0" src="Image/shu04.gif" width="95" height="119"></td>
</tr>
</table>
<p style="line-height: 200%"> 树中度数为1的结点称为<b><font color="#0000FF">叶</font></b>结点，度数大于1的称为<b><font color="#0000FF">分支</font></b>结点。<br>
互不相交的几棵树总称为<b><font color="#0000FF">森林</font></b> </p>
<p style="line-height: 200%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
性质1（等价定义）</b>设 T 为一棵(n,m)无向树 </p>
<ol>
<li>
<p style="line-height: 200%">T 无简单回路,且有 m = n-1.</li>
<li>
<p style="line-height: 200%">T 连通且 m = n-1.</li>
<li>
<p style="line-height: 200%">T
中无简单回路,但是增加任意一条边,即可形成一条且仅有一条基本回路.</li>
<li>
<p style="line-height: 200%">T 连通但删去任意一条边,T
便不连通.</li>
<li>
<p style="line-height: 200%">T
中每一对顶点间有唯一的一条基本路径</li>
</ol>
<p style="line-height: 200%"><b>证明(1)(数学归纳法)</b> </p>
<p style="line-height: 200%"> 当 k=1 时,m=0,结论显然成立.<br>
假设, k<n 时,结论成立.<br>
设 k=n 时,把树分成两棵树 T1,T2,(在 T
删去一条边)<br>
设 T1,T2 分别是 (n1,m1),(n2,m2) 树,且满足: <br>
n1<n, n2<n,
n1+n2=n, m1+m2=m-1<br>
由假设可知,m1=n1-1, m2=n2-1,<br>
所以,(n1-1)+(n2-1)=m-1,即 m=n-1.<br>
所以结论成立
#<br>
</p>
<p style="line-height: 200%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
性质2,</b> 在任意一棵树 T 中,至少有2片树叶. </p>
<p style="line-height: 200%"> 证明:(略) </p>
<p style="line-height: 200%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
生成树</b> </p>
<p style="line-height: 200%"><b> </b>无向图 G=<V,E>
的生成子图是树,则称 T 为 G 的<b><font color="#0000FF">生成树</font></b>. </p>
<p style="line-height: 200%"> 设:G=<V,E>为 (n,m)图,
T=<V',E'> 为 (n',m')树,有:<br>
V'=V,
E'<img border="0" src="Image/baohan.gif" width="11" height="10">E, n'=n, m'=n'-1<br>
即: m-m'=m-n+1<br>
所以,从 G 中删去 m-n+1
条边,即变成一棵生成树 T .如: </p>
<div align="center">
<center>
<table border="1" width="92%">
<tr>
<td width="25%" align="center"><img border="0" src="Image/shu05.gif" width="155" height="155"></td>
<td width="25%" align="center"><img border="0" src="Image/shu06.gif" width="143" height="142"></td>
</tr>
<tr>
<td width="25%" align="center"><img border="0" src="Image/shu07.gif" width="143" height="142"></td>
<td width="25%" align="center"><img border="0" src="Image/shu08.gif" width="151" height="157"></td>
</tr>
</table>
</center>
</div>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
最小生成树</b> </p>
<p style="line-height: 200%"><b> </b>图 G=<V,E>
为赋权连通图,T 为 G 的生成树,设w(T)为树 T
中所有边的权重之和,在所有 G
的生成树中,具有最小权的树,称为<b><font color="#0000FF">最小生成树</font></b>,或<b><font color="#0000FF">最优树</font></b>. </p>
<p style="line-height: 200%">
任意一棵赋权连通图必定存在一个最小生成树. </p>
<p style="line-height: 200%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
克鲁斯克尔(Kruskal)算法</b> </p>
<ol>
<li>
<p style="line-height: 200%">选取权重最小的边;</li>
<li>
<p style="line-height: 200%">选取剩余的边中,权重最小的且不构成回路的边.</li>
<li>
<p style="line-height: 200%">直到所有的结点都被选取为止.</li>
</ol>
<table border="1" width="100%">
<tr>
<td width="50%" align="center"><img border="0" src="Image/shu09.gif" width="237" height="237"></td>
<td width="50%" align="center"><img border="0" src="Image/shu10.gif" width="237" height="237"></td>
</tr>
<tr>
<td width="50%" align="center"><img border="0" src="Image/shu11.gif" width="115" height="154"></td>
<td width="50%" align="center"><img border="0" src="Image/shu12.gif" width="97" height="157"> <img border="0" src="Image/shu13.gif" width="98" height="155"></td>
</tr>
</table>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%" align="center"><b><a name="有向树"><font size="5">有向树</font></a></b> </p>
<p style="line-height: 200%"><b><a name="有向树"><img border="0" src="Image/gif/bluered.gif" width="12" height="12"></a>
定义:</b>有向树是满足下列条件的有向图,<br>
(1)有且仅有一个结点的入度为0,称为<b><font color="#0000FF">根结点</font>或<font color="#0000FF">树根;</font></b><font color="#0000FF"><br>
</font> (2)除了根结点以外的每个结点的入度均为
1 ;<br>
(3)树的每一个结点a,都有从根结点到a的一条有向路径. </p>
<p style="line-height: 200%"> 如(图1),在讨论有向图时,通常把根结点在顶上,所有的弧都向下的画法,这样可以省略每条有向边的方向,所以(图1)可以等价的画成(图2). </p>
<div align="center">
<center>
<table border="1" width="82%">
<tr>
<td width="50%" align="center"><img border="0" src="Image/shu14.gif" width="186" height="191"></td>
<td width="50%" align="center"><img border="0" src="Image/shu15.gif" width="183" height="191"></td>
</tr>
</table>
</center>
</div>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -