7.3-图-论(2)(部编)课件

几种特殊的图

欧拉图哈密顿图平面图树17.3.4欧拉图一笔画问题：欧拉通路或欧拉回路。定义7.1.5

在无向连通简单图中，通过图中每边一次且仅一次并行遍每个结点的一条通路(回路)，称为该图的一条欧拉通路(回路)。存在欧拉回路的图称为欧拉图。无欧拉通路或欧拉回路欧拉通路欧拉回路2定理7.3

无向连通图G是欧拉图的充分必要条件是G不含奇数度结点。推论非平凡连通图G含有欧拉通路的充分必要条件是G最多有两个奇数度结点。例下列图是否可以一笔画出来.AB×√√3例1验证哥尼斯堡七桥问题无解.解七桥问题图7-7可简化为图7-20.从图7-20知，此图为无向连通图，并且每个结点度数为奇数，由定理7.3，此图不是欧拉图，即知哥尼斯堡七桥问题无解.4定理连通有向图G含有欧拉回路的充分必要条件是G中每个结点的入度等于出度；连通有向图G含有欧拉通路的充分必要条件是除两个结点外，其余每个结点的入度等于出度，这两个结点中一个结点的入度比其出度多1，另一个结点的入度比其出度少1。57.3.5哈密顿图定义7.1.6经过图中每个结点一次且仅一次的通路(回路)，称为哈密顿通路(回路)。存在哈密顿回路的图称为哈密顿图。哈密顿图哈密顿图无哈密顿通路存在哈密顿通路6例举出满足下列条件具有6个点的图。⑴无哈密顿回路，无欧拉路。⑵有哈密顿回路，无欧拉路。⑶无哈密顿回路，有欧拉路。⑷有哈密顿回路，有欧拉路。⑴⑵⑶⑷7讨论题判断各图是否为哈密顿图，并说明原因，若是哈密顿图，请画出哈密顿回路。×××√√8√√××9(补充)平面图在印刷电路版等方面有应用.定义3

设无向图G=<V,E>，如果能够把G的所有结点和边画在平面上，使得任何两边除公共结点外没有其它交叉点，则称G为可嵌入平面图，或称G是可平面图，可平面图在平面上的一个嵌入称为平面图。否则称G为非平面图。有些图虽然有相交的边，如果经改画后可以不相交，这样的图仍是平面图。10例G可改画为所以G是平面图。二个典型的非平面图.K5K3,311定理

平面图中，所有面的次数之和是其边数的两倍。定理(欧拉公式)设连通平面图G=<V,E>，共有v个结点，e条边和r个面，则有

v－e+r=2.127.3.6树

在计算机科学中树是一种经常使用的数据结构.定义7.1.7

连通且无回路的无向图称为树，用T表示。T中d(v)=1的结点v称为树叶。T中d(v)>1的结点称为分支点或内点。每个连通分图是树的无向图称为森林。一个孤立结点称为平凡树。13树树叶分枝点非树森林非树树树14定理

给定图T=<V,E>，以下关于树的定义是等价的(|V|=n,|E|=m):⑴无回路的连通图；⑵无回路且m=n－1；⑶连通且m=n－1；⑷无回路，但增加一条新边，得到一个且仅一个回路；⑸连通但删去任一边后，就不连通了；⑹每一对结点有一条且仅一条通路。15定理7.4

任何非平凡树至少有两片树叶。证：2m=deg(vi)≥k+2(n－k)=2n－k

i设有k个一度结点其余n－k个结点的度≥2∵m=n－1,∴2(n－1)≥2n－k ∴k≥2 ■16生成树及其应用定义若图G的生成子图(含图G所有结点的子图)是树，则称这棵树为G的生成树。图G的一棵生成树为T。e1e2e3e4e5e6e7e8e9e10Ge1e2e3e6e8e9T17定理7.5

连通图G至少有一棵生成树。G只要删边去回路→连通无回路。GT1T2T318

若连通图G有n个结点，m条边，要确定G的一棵生成树，必须删去G的m－(n－1)条边。定义

在图G的所有生成树中，带权最小的那棵树称为最小生成树。19求最小生成树的克鲁斯克尔算法：

1.在G中选取最小权的边ei，置i=1；

2.当i=n－1时结束，否则转3；

3.设已选择边为T={e1,e2,...,ei},在E－T中选取ei+1,使T

ei+1无回路，且ei+1具有最小的权；

4.置i=i+1，转2。22223311红线组成最小生成树T，w(T)=6.20根树定义

一个有向图，如果删去每条边的方向所得到的无向图是一棵树，则称这个有向图为有向树。定义

一棵非平凡的有向树，如果恰有一个结点的入度为有向树0，其余所有结点的入度均为1，则称这棵有向树为根树。入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为内点，内点同树根统称为分支点。v1v2v3v4v5v6v7v8v9v10v11v12v1321习惯上有向边方向均指向下方，一般可省去全部箭头，上图可画成：在根树中从树根到任意结点的长度，称为该结点的层数，所有结点中最大的层数称为根树的树高。定义

在根树中若vi可达vj

且通路长度≥2，则称vi是vj的祖先，vj是vi的后代。若<vi,vj>是根树的边，则称vi是vj的父亲，vj是vi的儿子，同一结点的儿