《离散数学》些特殊的图.ppt

注意： (1) 一个平面图的无限面只有一个。 (2) 同一个平面图可以有不同形状的平面嵌入 (互相同构)。 (3) 不同的平面嵌入可能将某个有限面变成 无限面，而将无限面变成有限面。 例5、 图(2)，(3)都是图(1)的平面嵌入， 图(2)中， ， 图(3)中， ， 它们虽然形状不同，但都与(1)同构。 2、平面图中面次数与边数的关系。 为面数) ( 3、欧拉公式。 设 为连通的平面图，顶点数为 ，边数为 ， 面数为 ，则 第三节　无向树 内容：无向树 重点：无向树的概念 最小生成树的概念 了解：避圈法求最小生成树 一、无向树的定义 1、 连通而不含回路的无向图称为无向树，简称树，常用 表示树． 2、连通分支数大于等于2，且每个连通分支均是树的非连通无向图称为森林．平凡图称为平凡树． 二、生成树的定义 1、设 是无向连通图， 是 的生成子图， 并且 是树，则称 是 的生成树． 2、 在 中的边称为 的树枝， 不在 中的边称为 的弦． 设无向连通带权图 的所有弦的集合的导出子图称为 的余树． 三、最小生成树的定义 1、 是 ， 的一棵生成树． 各边带权之和称为 的权，记作 。 带权最小的生成树称为最小生成树． 的所有 生成树中 2、 克鲁斯克尔 法，又称“避圈法”，求 最小生成树 第四节 根树及其应用 内容：根树，树根，树叶，树高，家族树， 有序树，最优２元树，Huffman算法 ,前缀码 重点：根树的基本概念，最优２元树，Huffman算法 了解：2元树的3种周游方式 一、根树的定义 1、 一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树． 入度为0的顶点称为树根； 入度为1、出度大于0的顶点称为内点， 内点和树根统称为分支点． 入度为1、出度为0的顶点称为树叶； 在根树中，从树根到任意顶点 的通路长度称为 的层数，记为 称层数相同的顶点在同一层上．层数最大的顶点的层数称为树高，记为 2、一棵根树也常称为一棵家族树： 若顶点 邻接到顶点 ，则称 为 的儿子， 为 的父亲； 若 同为 的儿子，则称 为兄弟； 若 ，而 可达 ，则称 为 的祖先， 的后代． 为 3、如果将根树每一层上的顶点都规定次序，这样的根树称为有序树． 在编码理论和计算机程序等问题中，常常要考虑同一层上的顶点的顺序，因而需要有序树的概念． 二、最优2元树． 1、设2元树 有 片树叶，分别带权为 （ 为实数， ），称 为 的权，其中 为带权 的树叶 的层数．在所有的带权 中，带权最小的2元树称为最优2元树． 的2元树 算法： 2、 给定实数 ，且 （1）连接 为权的两片树叶，得一分支点，其权为 ； * * 内容：二部图、欧拉图。 重点：二部图、欧拉图的定义及判定。 第八章 一些特殊的图 第一节 二部图与欧拉图 一、二部图的定义。 1、若存在无向图 的顶点集 的一个 划分， ， ，使得 中任何 一条边的两个端点分别在 和 中，则称 为二部图 (或偶图)。 其中 称互补顶点子集， 记为 。 2、完全二部图 (或完全偶图)。 若 中任一顶点与 中每一顶点均有且只有 一条边相关联，则称此二部图 为完全二部 图 (或完全偶图)。 若 ，则记完全二部图为 ， 。 例1、 二部图 完全二部图 完全二部图 二、判定定理。 一个无向图 是二部图当且仅当 中无奇数长度的回路。 例2、判断以下是否二部图。 (1) 二部图 图(1)中所有的回路长度均为偶数。 (思考，求其互补顶点子集) 二部图 例1 同构 以上二图均为 。 例1 同构 二部图 以上二图均为 。 不是二部图，因图中存在长为3的回路 。 三、欧拉图问题的提出。 1736年，瑞士数学家欧拉，哥尼斯堡七桥问题 四、欧拉图定义。 欧拉通路 (欧拉迹) ——通过图中每条边一次 且仅一次，并且过每一顶点的通路。 欧拉回路 (欧拉闭迹) ——通过图中每条边一次 且仅一次，并且过每一顶点的回路。 欧拉图 ——存在欧拉回路的图。 注意： (1) 欧拉通路与欧拉回路不同。 (2) 欧拉图指具有欧拉回路(并非通路)的图。 (3) 欧拉通路(回路)必是简单通路(回路)。 (4) 连通是具有欧拉通路(回路)的必要条件。 (5) 欧拉通路(回路)是经过图中所有边的通路 (回路)中最短的通路(回路)。 三、无向图是否具有欧拉通路或回路的判定。 有欧拉通路 连通， 中只有两个奇度 顶点(它们分别是欧拉通路的 两个端点)。 有欧拉回路( 为欧拉图) 连通， 中均 为偶度顶点。 例3、以下图形能否一笔画成？ 四、有向图是否具有欧拉通路或回路的判定。 有欧拉通路 连通，除两个顶点外，其 余顶点的入度均等于出度，