<div>
<p></p>
<div style="text-align:center;">
<img alt="b5a434e73993fbf8af9291da81a8f03d.png" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-d8fdd5f1ec145ddc123f558e7e10fbe0.png">
</div>
<h2>图与树</h2>
<h2>图的基本概念</h2>
<h3>图及其图解表示</h3>
<ul><li> 一个图 G 是一个有序二元组(V， E)，记作 G = (V， E)
<ul><li>V是一个非空的有限集合，V 中的元素称为图 G 的结点或顶点</li><li>V 称为图 G 的结点集，记作 V(G)</li><li>E是一个由 V 中元素构成的对偶的集合，E 中的元素称为图 G 的边或弧</li><li>E 称为图 G 的边集，记作 E(G)</li><li> V(G)，#E(G)分别称为图的结点数和边数．图的结点数也称为图的阶，n 个</li><li>结点的图称为 n 阶图．</li><li>具有 n 个结点和 m 条边的图称为(n，m)图．</li><li>特别，(n，0)图称为零图，(1，0)图称为平凡图．</li></ul></li><li> 图 G = (V，E)中
<ul><li>若 E 的元素 e 为 V 中两个元素 u 和 v 的非有序的对偶，则称边 e 为图 G 的无向边</li><li>结点 u 和 v 称为无向边 e 的端点</li><li>若 E 的元素 e 为 V 中两个元素 u 和 v 的有序的对偶，则称边 e为图 G 的有向边</li><li>结点 u 和 v 分别称为有向边 e 的起点（或始点）和终点，也称为有向边的端点</li><li>以结点 u 为端点的边称为结点 u 的关联边</li><li>显然，对于相异结点 u 和 v，{u，v}和{v，u}是同一条边，而(u，v)和(v，u)是两条不同的边．</li></ul></li></ul>
<ul><li> 图 G = (V，E)中
<ul><li>端点相同的边{u，u}或(u，u)称为结点 u 的自环</li><li>E 中相同的边{u，v}或(u，v)称为平行边或重复边，并称重复边的条数为该边的重数</li><li>含有平行边的图称为多重图．既不含自环又不含平行边的图称为简单图</li></ul></li><li> 无向有向
<ul><li>所有边都是无向边的图称为无向图</li><li>所有边都是无向边的简单图称为无向简单图</li><li>所有边都是有向边的图称为有向图</li><li>所有边都是有向边的简单图称为有向简单图</li><li>既含无向边又含有向边的图称为混合图．</li><li>将有向图的各条有向边略去方向后所得到的无向图称为该有向图的基础图，简称基图．</li><li>如果将无向图的各条边任意定一个方向后所得到的有向图称为该无向图的一个定向图</li></ul></li></ul>
<ul><li> 表示方法
<ul><li>集合表示法</li><li>图解表示法</li><li>矩阵表示法</li></ul></li><li> 有权图
<ul><li>如果图 G 的每条边都赋以一个实数作为该边的权，则称图 G 为赋权图或有权图．</li><li>有权图可定义为一个有序三元组(V，E， f)，其中 f 是一个定义在边集 E 上的函数，通过 f 将权分配给各边．</li></ul></li></ul>
<ul><li> 点边
<ul><li>图中关联于同一条边的两个结点称为是邻接点，关联于同一结点的两条边称为是邻接边．</li><li>图中不与其他任何结点相邻接的结点称为是孤立点，不与其他任何边相邻接的边称为是孤立边．</li><li>特别，零图是仅由孤立结点组成的图；平凡图是仅由一个孤立结点组成的图．</li></ul></li></ul>
<h3>完全图与补图</h3>
<ul><li>在无向简单图中，如果任意两个不同的结点都是邻接的，则称该无向图为无向完全图．n 阶无向完全图记作 Kn．</li><li>在有向简单图中，如果任意两个不同的结点之间均有两条方向相反的有向边，则称该有向图为有向完全图．</li><li>在有向简单图中，如果任意两个不同的结点之间有且仅有一条有向边，则称该有向图为竞赛图．</li><li>例如：无向完全图的一个定向图就是一个竞赛图．</li><li>设 G 是一个简单图，由 G 的所有结点和为了使 G 成为完全图所需添加的那些边组成的图，称为 G 的相对于完全图的补图，简称为 G 的补图</li><li>显然， G 与 G 的补图 互为补图．</li></ul>
<h3>结点的度与握手定理</h3>
<ul><li> 度的定义
<ul><li>图中关联于结点 v 的边的总数称为该结点的度，记作 deg(v)． </li><li>在有向图中，以 v 为起点的有向边的条数称为结点 v 的出度，记作 deg+(v)</li><li>以 v 为终点的有向边的条数称为结点 v 的入度，记作 deg–(v)． </li><li>有向图中结点 v 的度为 deg(v) = deg+(v) + deg–(v)． </li><li>无向图中的自环在其对应结点的度上增加 2，有向图中的自环在其对应结点的度上增加一个入度和一个出度．</li></ul></li><li> 握手定理
<ul><li>图中所有结点度数的和为边数的两倍．</li><li>图中度为奇数的结点个数为偶数． </li></ul></li></ul>
<ul><li> 正则图
<ul><li>若无向简
转播
