图论与抽象代数复习(2)

? 环中无零因子? 环满足消去律；

? 环中子系统S是子环的充要条件是a?s 则必有a－1?S。 （25）域的基本理论 1）域是整环；

2）有限整环必是域。

§7.2 格与布尔代数 （26）格：（P，＋, ）中，两个运算的结合律、吸收律、交换律；

（27）布尔代数：格（B，＋, ）中，两个运算的分配律、单位元、逆元。 （28）格的基本理论

1） 一个偏序格必是一个代数格，反之亦然； 2）格的运算性质。

? a≤a∨b , b≤a∨b （a∨b≥a , a∨b≥b） ? a≤c且b≤c ?a∨b≤c （a≤c且b≤c?c≥a∨b） ? a∧b≤a , a∧b≤b （a≥a∧b , b≥a∧b） ? c≤a且c≤b ?c≤a∧b （c≤a且c≤b?c≥a∧b≥c） （29）布尔代数的基本理论

— 布尔代数（B，＋， ）满足：（对＋与 ） ? 交换律 ? 结合律 ? 等幂律 ? 吸收律 ? 分配律 ? 零一律 ? 同一律 ? 互补律 ? 双补律 ? 德?摩根律

第四篇 图 论

图论用‘结点’表示事物，而用‘边’表示事物间联系，并用‘结点’与‘边’所构成的图用以研究客观世界。为便于计算，建立了图的矩阵表示，这样可以将图论研究与计算相结合，从而使图论研究具有很大的实用性。由于图的形式很多，在实用中我们一般对若干种常用的图作研究，它们是树、平面图与两步图。

在图论学习中主要要掌握如下几个方面： ① 图论中的基本概念。

② 图论中的基础理论。 ③ 图的矩阵计算。 ④ 几种常用的图。

在本篇中共有两部分组成，它们是图论原理与常用图，其中图论原理部分介绍图的基本概念、理论与计算而常用图部分则介绍树、平面图与两步图等三种常用图，这两部分的有机结合构成了图论的完整的整体。

第八章 图论原理 §8.1 图的基本概念 §8.1.1 图

§8.1.2 图的基本概念 （1）图的概念

图由结点集V＝{v1，v2，…，vn}与边集E＝{l1，l2，…，lm}所组成，可记为：

G＝ （2）有向图与无向图

① 边为有向的图称为有向图 ② 边为无向的图称为无向图

（3）几种特殊的图

① 零图：无边的图。

② 平凡图：仅有一个结点所组成的图。 ③ 完全图：各结点间均有边相联的图。

④补图：G＝，G?＝如有＝为完全图且E∩E?＝?，则称G为G的补图。

⑤ 简单图与多重图：包括多重边的图称为多重图，否则称为简单图。 ⑥ 有权图：边带权的图。

§8.1.3 图的同构

⑦ 同构图：G＝，G?＝，V与V?以及相应边的结点对中有一一对应关系。

§8.1.4 图中结点的次数 （4）图中结点的次数 ? 引入次数deg（v）、引出次数deg（v）、次数deg（v）。 ? 定理： deg（vi）= 2m §8.2 通路、回路与连通性 （5）通路与回路

① 通路：图中vi至vj的通路是在边的序列：（vi，vi1），（vi1，vi 2），…（vi k－1，vi k），其中vi k＝vj

② 基本通路与简单通路：图各边全不同的通路叫简单通路，各点全不同的通路叫基本通路。

③ 环与回路：边的始点与终点相同称环，通路的起始点与终止点相同称回路。 ④ 简单回路与基本回路：简单（基本）通路的起始点与终止点相同称简单（基本）回路。

⑤ 有向图（n , m）的基本通路长度≤ n－1，基本回路长度≤n。

（6）图的连通性

① 图的可达性：图的结点vi到vj间存在通路则称从vi到vj是可达的。 ② 连通图：图的任何两结点间均可达。 ③ 三种连通图：

? 强连通：有向图中任何两结点间相互可达则称强连通。

? 弱连通：有向图忽略其边的方向所构成的无向图为连通则称弱连通。 ? 单向连通：有向图两结点间至少有一向是可达的则称单向连通。

§8.3 欧拉图

（7）欧拉图

? 欧拉回路与欧拉通路：通过G中每边一次的回（通）路称欧拉回（通）路，

具此回路的图称欧拉图。

③ 欧拉图与欧拉通路：欧拉图?每个结点次数为偶数。

由vi到vj欧拉通路?vi，vj结点次数为奇数，其它结点次数为偶数。

§8.4 汉密尔顿图

（8）汉密尔顿图

? 汉密尔顿回路与汉密尔顿通路：通过G中每个结点一次的回（通）路称汉密尔回（通）路，具此回路的图称汉密尔顿图。 ? 汉密尔顿图与汉密尔顿通路中的定理

汉密尔顿图的必要条件G＝中V1?V且P（G－V1）≤|V1|，其中P（G－V1）为从G中删除V1（包括V1中各结点及其关联边）后所得到的连通分支数。 汉密尔顿图的充分条件：G＝无向简单图，|V|≥3，G中每结点对次数之和≥|V|。

汉密尔顿通路：有向图D＝，|V|≥2所有有向边均用无向边替代后得无向图含生成子图Kn。

§8.5 图的矩阵表示法

（9）图的邻接矩阵：G＝为（n，m）图，其邻接矩阵： A＝（aij）n× n.

1（vi，vj）? E aij＝

0（vi，vj）? E （10）通路计算：

B＝A ，B＝（bij）n?×n?，Bij表示从vi到vj长度为 的通路数，Bij表示vi的回路数。

（11）可达性计算：

P＝A（＋）A（2）（＋）……（＋）A（n），P＝（Pij）n × n，Pij表示从vi到vj是否可达（0不可达，1可达）。 （12）连通性计算：

可达性矩阵除对角线元素外均为1

第九章 常用图

§9.1 树

§9.1.1 树的基本性质

（13）树的基本概念与属性 ① 树：不含回路的连通图。

（n , m）树中必有m＝n－1 ② 树的性质

T为树?两结点间只有一条通路。 §9.1.2 有向树 （14）有向树

（15）外向树与内向树：有向树中，仅有一个结点引入次数为0（根），其它结点引入次数为1，有些结点引出次数为0（叶）称外向树。有向树中，仅有一个结点引出次数为0（根），其它结点引入次数为1，有些结点引入次数为0（叶）称内向树。 §9.1.3 二元树

（16）二元树与多元树：一个n个结点的外向树：（vi）≤m（i = 1 , 2 , …, n），称

m元树。如（vi）＝m（i = 1 , 2 , …, n）（除叶外），称m元完全树，当m＝2时称二元树或二元完全树。

§9.1.4 生成树

（17）生成树：连通图G＝的生成树TG＝G的子图，且是树并满足V?＝V，E??E。

? 生成树寻找算法：在G中寻找基本回路，寻到后删除边，并继续寻找，直到无基本回路出现为止。