📄 content-7-1.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">
<p style="line-height: 200%"> </p>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="100%">
<p style="line-height: 200%" align="center" > <a name="content-7-1"></a><b><font size="5">图的基本概念</font></b></p>
<p style="line-height: 200%" >
由于基本概念比较多，本节的内容分为四个知识点，它们一起组成了本节循续渐进的四个部分。这四个部分分别是：</p>
<p style="line-height: 200%" ><a href="#content-7-1-1">图的基本定义和一些基本概念</a></p>
<p style="line-height: 200%" ><a href="#content-7-1-2">子图与图的同构</a></p>
<p style="line-height: 200%" ><a href="#content-7-1-3">路径和循环</a></p>
<p style="line-height: 200%" ><a href="#content-7-1-4">图的连通性</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"><a name="#content-7-1-1"></a><b>图的基本定义和一些基本概念:</b>
<p style="line-height: 200%" > 本部分先给出图的形式化定义，然后分结点、边和图介绍基本概念，最后给出一个量化的结点数和边数的关系。</p>
<table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%">
<p style="line-height: 200%"><b>定义：</b>图G是一个三元组 G=<V,E,<img src="image/kong.GIF" width="11" height="11">>
，其中<br>
(1) V={ <img src="IMAGE/v1.gif" width="11" height="11">, <img src="IMAGE/v2.gif" width="12" height="11">,...,<img src="IMAGE/vn.gif" width="12" height="11">}是个有限非空的结点集合，常称为
G 的结点集合。<br>
(2) E={ <img src="IMAGE/e1.gif" width="11" height="11">, <img src="IMAGE/e2.gif" width="11" height="11">,...,<img src="IMAGE/en.gif" width="11" height="11">}是 G 的有限的边集合。<img border="0" src="Image/ei.gif" width="10" height="11">=<<img src="IMAGE/vi.gif" width="10" height="11">1,<img src="IMAGE/vi.gif" width="10" height="11">2>,<img src="IMAGE/vi.gif" width="10" height="11">1,<img src="IMAGE/vi.gif" width="10" height="11">2分别称为该边的两个端点.<br>
(3) <img src="IMAGE/kong.gif" width="11" height="11">
是从边集合 E 到 V 中的有序或无序的元素偶集合的映射(通常省略)</td msimagelist>
</tr>
</table msimagelist>
<p style="line-height: 200%"> 所以,G也可记为G=<V,E>.<p style="line-height: 200%">
如:上述欧拉图就可以表示成:
<div align="center">
<center>
<table border="0" width="100%" cellspacing="0" cellpadding="0">
<tr>
<td width="49%">
<p align="center" style="line-height: 200%"><img border="0" src="Image/euler.gif" width="155" height="167"></td>
<td width="51%">
<p style="line-height: 200%">G=<V,E></p>
<p style="line-height: 200%">V={a,b,c,d}</p>
<p style="line-height: 200%">E={e1,e2,e3,e4,e5,e6,e7}</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 200%"> </p>
<table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%">
<p style="line-height: 200%">有关边的几个基本概念：
<ol>
<li>
<p style="line-height: 200%">在图 G=<V,E>中,其中每一条边
e 若所对应的序偶<<img src="IMAGE/vi.gif" width="10" height="11">,<img src="IMAGE/vj.gif" width="12" height="13">>为有序的,称为图
G 的<font color="#0000FF"><b>有向边</b></font>；若所对应的序偶<<img src="IMAGE/vi.gif" width="10" height="11">,<img src="IMAGE/vj.gif" width="12" height="13">>为无序的,称为图
G 的<font color="#0000FF"><b>无向边</b></font>。<br>
<img border="0" src="Image/tu_k4.gif" width="157" height="148">
<img border="0" src="Image/tu_k4_1.gif" width="157" height="148"></li>
<li>
<p style="line-height: 200%">联接结点 <img src="IMAGE/vi.gif" width="10" height="11">
和 <img src="IMAGE/vj.gif" width="12" height="13">
的边 e<img src="image/shuyu.gif" width="13" height="11">E，无论它是有向的或无向的，都称作与结点
<img src="IMAGE/vi.gif" width="10" height="11">
和 <img src="IMAGE/vj.gif" width="12" height="13">
相<font color="#0000FF"><b>关联</b></font>的边。联系同一个结点的两个不同的边，称为互为<font color="#0000FF"><b>邻接的边</b></font>。</li>
<li>
<p style="line-height: 200%">在图 G=<V,E>中，关联结点 <img src="IMAGE/vi.gif" width="10" height="11"><img src="image/shuyu.gif" width="13" height="11">V
到该结点 <img src="IMAGE/vi.gif" width="10" height="11">
本身的边，通常称为<font color="#0000FF"><b>闭路(或自回路)</b></font>。</li>
<li>
<p style="line-height: 200%">在有向图中，在结点偶对之间，应把方向相反的两条边，看成是不同的边，方向相同的两条边或更多条边，称为<font color="#0000FF"><b>平行边</b></font>或<font color="#0000FF"><b>多重边</b></font>。</li>
</ol>
</td msimagelist>
</tr>
</table msimagelist>
<p style="line-height: 200%"> </p>
<table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%">
<p style="line-height: 200%"><b>有关结点的几个基本概念：</b>
<ol>
<li>
<p style="line-height: 200%">由一条边联接起来的任何结点偶对,称为<font color="#0000FF"><b>邻接结点</b></font>.</li>
<li>
<p style="line-height: 200%">设 G=<V,E> 是一个图,并且
e<img src="image/shuyu.gif" width="13" height="11">E
是一条有向边，它与有序偶< <img src="IMAGE/vi.gif" width="10" height="11">, <img src="IMAGE/vj.gif" width="12" height="13">>相关联，亦即
e=< <img src="IMAGE/vi.gif" width="10" height="11">, <img src="IMAGE/vj.gif" width="12" height="13">>。于是,可以把边
e<img src="image/shuyu.gif" width="13" height="11">E
说成是起始于结点 <img src="IMAGE/vi.gif" width="10" height="11">，终止于结点 <img src="IMAGE/vj.gif" width="12" height="13">。与此相对应，把结点
<img src="IMAGE/vi.gif" width="10" height="11">称为边 e
的起始结点或<font color="#0000FF"><b>始点</b></font>；把结点 <img src="IMAGE/vj.gif" width="12" height="13">称为边
e 的终止结点或<font color="#0000FF"><b>终点</b></font>。<br>
<img border="0" src="Image/tu_k4_1.gif" width="157" height="148"></li>
<li>
<p style="line-height: 200%">在有向图 G=<V,E> 中,对于任何结点 v<img src="image/shuyu.gif" width="13" height="11">V
来说，以结点 v 为始点的边的条数。称为结点 v 的引出次数或<a name="content-7-1-1-chudu"></a><font color="#0000FF"><b>出度</b></font><img src="Image/chudu.gif" width="31" height="24">
；以结点
v 为终点的边数，称为结点 v 的引入次数或<a name="content-7-1-1-rudu"></a><font color="#0000FF"><b>入度</b></font><img src="Image/rudu.gif" width="31" height="24">。结点
v 的引入次数与引出次数之和，称为结点 v 的<font color="#0000FF"><b>次数或度数</b></font>，并记作 deg(v)。</li>
<li>
<p style="line-height: 200%">在无向图 G=<V,E>中，结点 v<img src="image/shuyu.gif" width="13" height="11">V
的次数或<font color="#0000FF"><b>度数</b></font>，等于与结点 v 相联系的边数，也记作deg(v)。
显然孤立结点的次数为零。<br>
<img border="0" src="Image/tu_k4.gif" width="157" height="148"></li>
</ol>
</td msimagelist>
</tr>
</table msimagelist>
<p style="line-height: 200%" > </p>
<table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%">
<p style="line-height: 200%">有关图的几个基本概念：
<ol>
<li>
<p style="line-height: 200%">具有n个结点和m条边的图,通常称为<font color="#0000FF"><b>(n,m)图</b></font>。</li>
<li>
<p style="line-height: 200%">每一条边都是有向边的图,称为<a name="content-7-1-1-youxiangtu"></a><font color="#0000FF"><b>有向图</b></font>；每一条边都是无向边的图，称为<a name="content-7-1-1-wuxiangtu"></a><font color="#0000FF"><b>无向图</b></font>；一些边是有向边，而其余的边是无向边的图，称为<font color="#0000FF"><b>混合图</b></font>。</li>
<li>
<p style="line-height: 200%">在一个 (n,m)无向图中,如果 n 个结点中的每一个都邻接于其它的 n-1 个结点,则称这样的图为<font color="#0000FF"><b>无向完全图,用Kn表示</b></font>。在(n,m)无向完全图中，应有
m=n(n-1)/2
。如果在图的每一对结点之间，都有且仅有一对方向相反的有向边，则称为<font color="#0000FF"><b>有向完全图</b></font>。<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -