图论与代数-test

习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3,则总度数为27,与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

（或者利用度数为奇数的点的个数必须为偶数个）m <= (n-1)( n-2)/2,与题设矛盾。

3•记a i为结点V i的正度数，a「为结点V i的负度数，则n n n nv a j 2「[ (n -1) - a" ]2 = n(n -1)2-2( n-1)、a「a「i 4 i 4n因为Z a「= c n = n(n -1)/2,i討4. 用向量（a1,a2,a3）表示三个量杯中水的量，其中a i为第i杯中水的量,i = 1,2,3.以满足a1+a2+a3 = 8 （a1,a2,a3为非负整数）的所有向量作为各结点，如果⑻耳厲）中某杯的水倒满另一杯得到（a' a' a'）,则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由（8, 0, 0 ）到（4, 4, 0 ）的一条有向路，以下即是这样的一条：(8 0 0 ).(5 0 3 )■( 5 3 0 )• f 0 Q \(2, 5, 1 ) (8, 0, 0丿 f ( 5, 0, 3丿r ( 5, 3, 0丿----- r■t / 4 4 O \ -----►(4, 4, 0 )T(7, 0, 1 )■ ( 7, 1, 0 )1^ ( 4, 1, 3 )5. 可以。

6若9个人中没有4个人相互认识，构造图G,每个点代表一个点，两个人相互认识则对应的两个点之间有边。

1）若可以找到点v, d（v）＞5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作K6并给边涂色：红=认识，蓝=不认识，只要证图中必有同色三角形。

集合论、图论重要习题100例：1、设A,B是两个集合,B≠￠,试证:若A×B=B×B, 则A=B。

2、设A,B,C,D是任意四个集合，证明：（A∩B)×(C∩D)=(A×C)∩(B×D)3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？(|AC∩BC|+|A∪B|=30, |AC∩BC|=21人)4、令N={1,2,3,…}，S:N→N，则(1)?n∈N,S(n)=n+1,Ｓ称为自然数集N上的后继函数。

(2)S(1)=1,?n∈N,S(n)=n-1,n≥2,Ｓ称为自然数集N 上的前仆函数。

5、设f:N×N →N,f((x,y))=xy。

则（1）说明f是否是单射、满射或双射？（2）求f(N×{1}),f-1({0})。

(1,4)≠(2,2),f((1,4))=f((2,2))=4；y∈N,f((1,y))=1·y=y,任一元都有原象；[f不是单射,f是满射]f(N×{1})={n·1|n ∈N}=N；f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。

6、设R、I、N是实数、整数、自然数集合，下面定义映射f1,f2,f3,f4,f5,f6，试确定它们的性质。

（0 ∈N）（1）f1:R→R,f1(x)=2x；（2）f2:I→N,f2(x)=|x|；f1单射，不是满射。

f2不是单射，满射。

（3）f3:N→N,f3(n)=n(mod3)；（4）f4:N→N×N,f4(n)=(n,n+1)；f3不是单射，不是满射；f4单射，不是满射。

（5）f5:R→R,f5(x)=x+2；（6）f6:R→R,f6(x)=x2,x≥0,f6(x)=-2,x<0；f5是双射(单射,满射)；f6不是单射,不是满射。

7、证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。

离散数学知识点总结1. 集合论- 集合的基本概念：集合、元素、子集、幂集、并集、交集、差集、补集。

- 集合的运算：德摩根定律、分配律、结合律、交换律。

- 有限集合和无限集合：可数与不可数集合、阿列夫零、阿列夫一。

2. 数理逻辑- 命题逻辑：命题、联结词、真值表、逻辑等价、逻辑蕴含、逻辑独立。

- 一阶谓词逻辑：量词、谓词、解释、满足、逻辑公式、全称量词、存在量词。

- 证明方法：直接证明、间接证明、反证法、数学归纳法。

3. 递归关系和函数- 递归定义：递归方程、初始条件、递归函数。

- 递归函数的例子：阶乘、斐波那契数列。

- 函数的性质：单射、满射、双射、复合函数。

4. 图论- 图的基本概念：顶点、边、路径、回路、图的同构。

- 图的类型：无向图、有向图、简单图、多重图、连通图、强连通图。

- 图的算法：欧拉路径、哈密顿回路、最短路径（Dijkstra算法）、最小生成树（Prim算法、Kruskal算法）。

5. 组合数学- 排列与组合：排列数、组合数、二项式定理。

- 组合恒等式：Pascal三角形、组合恒等式。

- 组合问题：计数原理、Inclusion-Exclusion原理。

6. 布尔代数- 布尔运算：AND、OR、NOT、XOR、NAND、NOR、XNOR。

- 布尔表达式的简化：卡诺图、奎因-麦克拉斯基方法。

- 布尔函数的表示：真值表、卡诺图、逻辑表达式。

7. 关系论- 关系的基本概念：笛卡尔积、自反性、对称性、传递性。

- 关系的类型：等价关系、偏序关系、全序关系。

- 关系的闭包：自反闭包、对称闭包、传递闭包。

8. 树和森林- 树的基本概念：节点、边、根、叶、子树、兄弟、祖先、子孙。

- 特殊类型的树：二叉树、平衡树、B树、B+树。

- 树的遍历：前序遍历、中序遍历、后序遍历、层次遍历。

9. 算法复杂度- 时间复杂度：最好情况、最坏情况、平均情况、大O表示法。

- 空间复杂度：算法空间需求的分析。

- 渐进分析：渐进紧确界、大Θ表示法、小o和大O的非正式描述。

图论简介图论属于拓扑学topology。

拓扑学分为一般拓扑学和代数拓扑学，前者来源于数学分析，最终研究一般的拓扑空间和一般的拓扑结构，而后者来源于几何，实际上是一种几何学的分支。

我们主要讨论后者，重点是利用图形的几何拓扑性质。

拓扑性质，就是几何图形在弯曲、变形、拉大、缩小下仍然保持的性质，只是这种变形要求原来不再一起的点不能粘在一起，原来一起的点也不能断开，也就是图形变换前后每点附近的点还是在附近。

这种变换和它的逆变换都是连续的一一对应，称为同胚。

一个图形和它同胚的图形称为拓扑等价。

拓扑学就是研究图形的拓扑性质。

也就是图形经过连续变换下，保持不变的性质。

图论以图为研究对象的数学分支。

图论中的图指的是一些点以及连接这些点的线的总体。

通常用点代表事物，用连接两点的线代表事物间的关系。

图论则是研究事物对象在上述表示法中具有的特征与性质的学科。

看一些例子：一、哥尼斯堡七桥问题。

当时的图论问题是盛行的迷宫问题和游戏问题。

最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。

东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。

如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。

于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。

这就是有名的哥尼斯堡七桥问题。

哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。

瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。

这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。

欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。

第7章 图论图论是建立和处理离散型数学模型的重要数学工具，它已发展成具有广泛应用的一个数学分支。

图论的发展已有200多年的历史，它最早起源于一些数学游戏的难题研究。

1736年瑞士数学家欧拉（L.Eluer ）发表了关于解决哥尼斯堡七桥问题的一篇文章，标志着图论的正式诞生。

从19世纪中叶到20世纪中叶，图论问题大量出现，如汉密尔顿图问题、四色猜想等。

这些问题的出现进一步促进了图论的发展。

1847年，克希霍夫（Kirchhoff ）用图论分析电网络，这是图论最早应用于工程科学的一个例子。

随着计算机科学的迅猛发展，在现实生活中的许多问题，如交通网络问题，运输的优化问题，社会学中某类关系的研究，都可以用图论进行研究和处理。

图论在计算机领域中，诸如算法、语言、数据库、网络理论、数据结构、操作系统、人工智能等方面都有重大贡献。

本章主要介绍图论的基本概念、基本性质和一些典型应用。

7.1 图的基本概念7.1.1 图的基本概念1.图的定义图在现实生活中随处可见，如交通运输图、旅游图、流程图等。

此处我们只考虑由点和线所组成的图。

这种图能够描述现实世界的很多事情。

例如，用点表示球队，两队之间的连线代表二者之间进行比赛，这样，各支球队的比赛情况就可以用一个图清楚地表示出来。

到底什么是图呢？可用一句话概括：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。

因为上述描述太过于抽象，难于理解，因此下面给出图作为代数结构的一个定义。

定义7.1.1 一个图（Graph ）是一个三元组〈)(G V ，)(G E ，G ϕ〉，其中)(G V 是一个非空的节点集合，)(G E 是有限的边集合，G ϕ是从边集合E 到点集合V 中的有序偶或无序偶的映射。

例7.1.1 图G =〈)(G V ，)(G E ，G ϕ〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ，),()(1b a e G =ϕ，),()(2c a e G =ϕ，),()(3d b e G =ϕ，),()(4c b e G =ϕ，),()(5c d e G =ϕ，),()(6d a e G =ϕ。

图论第二版答案【篇一：图论与代数结构第一二三章习题解答】厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

（或者利用度数为奇数的点的个数必须为偶数个） 2. 若存在孤立点，则m不超过kn-1的边数, 故m = (n-1)(n-2)/2, 与题设矛盾。

?－3. 记ai为结点vi的正度数，ai为结点vi的负度数，则nnnn? 2? 22－ai?[(n?1)?ai]?n(n?1)?2(n?1)ai＋ai－2， i?1i?1i?1i?1 nnn－2? 2 因为ai?cn?n(n?1)/2，所以ai?ai－ 2。

i?1i?1i?14. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的量, i = 1,2,3.以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点, 如果(a1,a2,a3)中某杯的水倒满另一杯得到( a’1, a’2, a’3 ) , 则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条： ( 8, 0, 0 ) ( 5, 0, 3 ) ( 5, 3, 0 ) ( 2, 3, 3 ) ( 2, 5,1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 1, 3 ) ( 4, 4, 0 )5. 可以。

???????6 若9个人中没有4个人相互认识，构造图g，每个点代表一个点，两个人相互认识则对应的两个点之间有边。

1）若可以找到点v，d(v)5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作k6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。

代数⽅法在图论中的精彩应⽤⽬录Preface⼀直想对GTAC讨论班的⼀些精彩内容做⼀次整理，却⼀直挖不出时间来。

昨晚我们在讨论班教室吃披萨，喝果汁，听了⼀些代数⽅法在图论中的应⽤，度过了愉快的平安夜。

新的⼀年（和ddl）快要来了，是时候做个整理了。

由于 eden 上课不做笔记，忘记了⼀些定理的名字以及来源，再由于时间关系 eden 不能整理得特别详细。

所以凑合着看吧：）Graham-Pollack theoremTheorem 1. (Graham-Pollack theorem) 若完全图K_n可以表⽰为m个互不相交的完全⼆分图的并，则m\ge n-1。

设图K_n的邻接矩阵为A，那么A=J-I（约定J为全1矩阵，I为单位矩阵）。

如果K_n的⼀个⼦图G是完全⼆分图，⼀边的点集为V_1，另⼀边的点集为V_2。

那么该⼦图的邻接矩阵B满⾜：B_{x,y}=B_{y,x}=1,\forall x\inV_1,y\in V_2。

所以B可以拆成⼀个秩⼀矩阵与它的转置之和：B=C^T+C\ (C_{x,y}=1,\forall x\in V_1,y\in V_2)。

K_n可以拆成m个互不相交的完全⼆分图的并，所以A可以表⽰为(C_1+\cdots+C_m)^T+(C_1+\cdots+C_m)，其中C_1,\cdots,C_m都是秩⼀矩阵。

可以推出：\begin{align} I&=J-A=(\frac{1}{2}J-C_1-\cdots-C_m)^T+(\frac{1}{2}J-C_1-\cdots-C_m)\\ &=D^T+D \tag{1.1} \\设\ D&=\frac{1}{2}J-C_1-\cdots-C_m \end{align}假设m<=n-2，那么rank(D)\le rank(J)+rank(C_1)\cdots+rank(C_m)=n-1，取D的右零空间中的⼀个⾮零向量\boldsymbol \alpha，在(1.1)式中左乘\boldsymbol \alpha^T，右乘\boldsymbol \alpha，(1.1)式变为：\boldsymbol \alpha^TI\boldsymbol \alpha=(D\boldsymbol \alpha)^T\boldsymbol \alpha+\boldsymbol \alpha^T(D\boldsymbol \alpha)=0\tag{1.2}这与\boldsymbol \alpha是⾮零向量⽭盾。

一些有关几何的代数图论问题
代数图论是数学的一个分支,是近几年发展迅速的一个方向.有限域上的几何学和几何图是十分重要的几何结构和组合结构,它们涉及到很多领域,如结合方案、信息科学、编码等等.一些学者将各类几何空间和图论联系起来研究几何图的性质,并取得了很多研究成果.但是,关于有限域的一些几何图(例如,经典极图,经典对偶极图,格拉斯曼图)的色数与无关数的计算与估计等重要问题还尚未完全解决.在代数图论中,图同态的研究是一个核心问题.一个图G称作核,如果G 的每个图自同态都是图自同构.对于一个图G,一个重要的问题是判别G是否为一个核.本文共分三章.第一章简要介绍了本文的课题研究背景、预备知识和主要结果.第二章主要讨论了经典极图与经典对偶极图的性质、部分几何和它的点图,主要结果是进一步解决了经典极图是否为一个核的判别.本章所得到的主要结果是定理2.1.7和推论2.1.9,定理2.2.15和定理2.3.4.这些结果对代数图论与矩阵几何的研究有一定的意义.第三章主要讨论了格拉斯曼图的性质,研究了低阶格拉斯曼图J_q(4,2)的顶点集的划分与它的最大无关集的计算.。

图论与代数结构
图论
图论是一种抽象的数学结构，用来描述复杂的关系。

它用一组节点和边的集合来表示，节点表示实体，边表示实体之间的关系。

图论是用来描述网络结构的理论，它可以用来解决许多实际问题，如路径规划、社交网络分析等。

代数结构
代数结构是一种抽象的数学结构，它用来描述一组元素之间的结构关系。

它是由一组元素和一些运算组成的，这些运算可以用来操作元素，从而得到新的元素。

代数结构可以用来描述群、环、域等数学概念，并可以用来解决许多实际问题，如密码学、编码理论等。