图论与抽象代数复习

2013-2014二学期图论与抽象代数复习

第一部分

1.第三篇总复习题 1，2，3题 2.第四篇总复习题 1，4，6题 3.习题9 9.1题

4. *运算如下表所示，哪个能使({a,b},*)成为单元半群？（ ）

5. Q 是有理集，（Q，*）（其中*为普通乘法）不能构成（ ）。 A．群 B．单元半群 C．半群 D．交换半群 6.设Z 是整数集，＋，· 分别是普通加法和乘法，则（Z，＋，·）是（ ）。 A．域 B．整环和域 C．整环 D．含零因子环 7. 在代数系统中，整环和域的关系为（ ）。 A．整环一定是域 B．域不一定是整环 C．域一定是整环 D．域一定不是整环 8. 设D =< V,E >为有向图，V = {a, b, c, d, e, f }，E = {( a,b),( b,c),( a, d), ( d, e) ,( f, e)}是（ A．强连通图 B．单向连通图 C．弱连通图 D．不连通图 9. 在有n 个结点的连通图中，其边数（ ）。 A．最多有n?1 条 B．至少有n?1 条 C．最多有n 条 D．至少有n 条

10设G = (n,m)为无向简单图，可构成邻接矩阵的数目为（ ）。 A．n! B．m! C． D． 11. 欧拉回路是（ ）。

A．通路 B．简单回路 C．既是基本回路也是简单回路 D．既非基本回路也非简单回路 12. 哈密尔顿回路是（ ）。

A．通路 B．简单回路 C．既是基本回路也是简单回路 D．既非基本回路也非简单回路 13. 下面哪一种图不一定是树?（ ）

A．无回路的连通图 B．有 n 个结点n ?1条边的连通图 C．每对结点间都有通路的图 D．连通但删去一条边则不连通的图 下述偏序集（见下图）中能构成格的是（ ）

下述偏序集中哪一个不构成格？（ ）

。 ）

第二部分

1第三篇总复习题 11，12，13题 2.第四篇总复习题 16，21题 3.定理6.14，定理7.10推论2

4.Z是整数集，群(Z,+)是一个循环群，其生成元是______和________.

5.G是n个节点，m条边的无向图，v是次数为k的结点，则G-v(G中去掉节点的图)中有_______个结点，________条边。 6.设（G，*）是一个半群，若存在单位元且每个元素都有右逆元，则（G，*）是_____________. 7.由一个孤立结点构成的图称为________;简单图不包含___________ 第三部分

1. 设代数系统（A,*），其中A={ a ,b , c , d }，*乘法表定义如下：问*是否是可交换的；A 是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆元。

2. 第三篇总复习题 20题

3.找出 的所有子群。

3

4.有向图D 如下图所示：

(S,?)

求：(1) D 的邻接矩阵A

(2) D 中v1 到v4 长度为4 的通路数为多少？

(3) D 中长度为4 的通路总数为多少？其中有几条回路？ (4) D 中v1 到自身长度为3 的回路数为多少？

(5) D 中长度小于等于4 的通路有多少条？其中有多少条是回路？ (6) D 是哪类连通图？

5.下图给出的赋权图表示七个城市a，b，c，d，e，f，g 及架起城市间直接通信线路的预测造价，试给出一个设计方案使得各城市间能够通信且总造价最小，要求计算出最小总造价。

第四部分

1.证明：定理6.18 2.证明：定理 8.1 3.证明：定理9.1

4.第三篇总复习题 27题

5. 证明：循环群一定是可换群。

第三篇 代数系统

代数系统是建立在集合论基础上以代数运算为研究对象的学科。本篇共三章，第五章代数系统基础介绍代数系统的一般原理与性质， 第六章群论，主要介绍具有代表性的代数系统－群，最后第七章其它代数系统，介绍除群外常见的一些代数系统，如环、域、格与布尔代数等，这三章相互配合构成了代数系统的完整的整体。 第五章 代数系统基础 §5.1 代数系统一般概念

1．代数系统中的基本概念

（1）代数系统：集合上具有封闭性的运算组成代数系统（S , ）。 （2）子代数：代数系统（S, ），（S?，?）满足： ① S??S

② 如 a , b?S?，a?b = a b 则称（S?，?）为（S, ）的子代数。 §5.2 代数系统常见的一些性质 （3）代数系统常见性质 1）结合律：（a b） c＝a （b c） 2）交换律：a b＝b a

3）分配律：a （b＋c）＝（a b）＋（a c） 4）单位元：a 1＝a

5）逆元：a a－1＝1 6）零元：a 0＝0 7）生成元 §5.3 同构与同态 （4）同构：（X， ）与（Y，?）存在一一对应函数g : X?Y使得如x1 , x2?X，则有：g（x1 x2）＝g（x1）?g（x2）此时则称（X, ）与（Y，?）同构。 （5）同态：（X , ）与（Y，?）存在函数g : X?Y使得如x1 , x2?X，则有：g（x1 x2）＝g（x1）?g（x2）此时则称（X， ）与（Y，?）同态。 §5.4 常用代数系统

（6）代数系统的构成

交换律 ?可换群 生成元 （一个二元运算 ） 子集上的群 ?循环群 特殊群 结合律 半群 单位元、逆元 群 ? ? 特殊群 ?子群 交换律 单位元 ?可换半群 ?变换群 生成元 ?单元半群 ?正规子群、商群

?循环半群 （两个二元运算：?, ) 代数系统 ?可换群, 半群, 对?分配群 环 交换律 可换环 单位元, 逆元 ?域 ? ? ?单位元，无零因子

特殊子环 ?理想 特殊环 （两个二元运算：?, ) ? ?商环 ?布尔代数 ? 两个运算的单位元、逆元

两个运算有单位元 ?有界格 两个运算有逆元 ?有补格 两个运算的结合律、交换律、吸收律 格 两个运算的分配律 分配格 ?整环

第六章 群论

§6.1 一些群的定义

（7）半群——代数系统满足交换律 （8）单元半群——半群存在单位元 （9）群——半群存在单位元与逆元 （10）可换群——群满足交换律

（11）变换群——集合A上所有的变换构成的集合E（A），对于复合变换?所构成的代数系统（E（A）, ）是一个群，称变换群。 （12）循环群——群有生成元。

（13）有限群：群（S, ）中S为有限集。

（14）子群：群（G，?）上G的子集所构成的群。

（15）正规子群：（H，?）是群（G，?）的子群，如对a?G都有：aH = Ha

则称（H，?）是（G，?）的正规子群。

（16）陪集：H是G的子群，Ha＝{ha | h?H}, aH = {ah | h?H }分别称H在G中的一个右陪集或左陪集。

（17）商群：H是G的正规子群，对Ha，Hb?G/H，二元运算（Ha)?(Hb)＝Hab构成群，则称H是G的商群。 （18）单元半群性质：

? 单元半群的子系统若包含单位元也是单元半群。

? 可列个元素的单元半群的运算组合表每行（列）均不相同。 ? 循环单元半群是可换单元半群。

? 可换单元半群的所有等幂元素是一个子单元半群。 §6.2 一些群的理论与半群性质： ? 半群的子代数也是半群。 ? 循环半群是可换半群。 （19）关于群的基本理论

? 群方程可解性：a x = b（或x a = b）对x存在唯一解； ? 群的消去律：a b = a c（或b a = c a）必有b = c； ? 任一群必与变换群同构；

? 与一个群同构或满同态的代数系统必为群；

? 一个代数系统有限群满足结合律及消去律则必为群；

? 有限群必与置换群同构；

? 循环群要么与（I,＋）同构，要么与（Zm，＋m）同构；

? 一个群子集H构成群（H,o）的充分必要条件：a,b?H 则a b?H ,a?H 则a－1 ?H；

? 一个群子集H构成子群（H,o）的充分必要条件：a,b ?H 则a b－1 ?H ； ? 一个有限群的阶一定被它的子群的阶所等分（拉格朗日定理）； ? f是群（G, ）与（G?，?）的满同态，K是f的核，则必有：（G/k , ?）与（G?，?）同构；

第七章 其它代数系统

§7.1 环、理想、整环和域 （20）环：（R，＋, ），对＋的可换群，对 的半群， 对＋的分配律； （21）理想：（D，＋, ），环（R，＋, ）的子环，满足：a?R , b?D，必有：a b?D , b a?D；

（22）整环：环（R，＋, ）中，运算 有单位元，无零因子； （23）域：环（P，＋, ）中，运算 交换律，有单位元，逆元； （24）环的基本理论 环的基本运算性质： ? a 0 = 0 a = 0；

? a （－b）=（－a） b = －（a b） ? (－a) (－b)＝a b

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

? 环中子系统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中寻找基本回路，寻到后删除边，并继续寻找，直到无基本回路出现为止。

本文来源：https://www.bwwdw.com/article/swt3.html