第九章平面图与图的着色
9.1平面图
图G称为被嵌入平(曲)面S内,如果G的图解已画在平面S上,而且任何两条边均不相交(除顶点外),已嵌入平面的图称为平面图
如果一个图可以嵌入平面，则称此图是可平面的
1.平面图的面
平面图把平面分成了若干个区域，这些区域都是单连通的，称之为G的面，其中无界的那个连通区域称为G的外部面，其余的单连通区域称为G的内部面Tips:
(1)单连通区域
设D是一区域，若属于D内任何简单闭曲线的内部都属于D，
则称D为单连通区域
1.单连通区域也可以这样描述：D内任何封闭曲线所围成的区域
内只含有D中的点
2.更通俗地说，单连通区域是没有“洞”的区域
3.属于D的任何一条简单闭曲线，在D内可以经过连续的变形
而缩成一点
(2)平面图的每个内部面都是G的某个圈围成的单连通区域
(3)没有圈的图没有内部面，只有一个外部面
(4)每个平面图G中顶点度的最小值不超过5,即δ(G)≤5
2.平面图的面数、顶点数、边数之间的关系
如果一个平面连通图有p个顶点、q条边、f个面，则：
p-q+f=2
Tips:
(1)若平面连通图G有p个顶点，q条边且每个面都是由长为n的圈
围成的，则
q=n(p-2)/(n-2)
注意：
1.2q=n*f—每条边为两个面所用
2.外部面的边
(2)设G是一个(p, q)可平面连通图,而且G的每个面都是一个长为4
的圈围成的，则：q=2p-4
(3)最大可平面图的性质
(4)若G是任一有p个顶点q条边的可平面图p≥3,则q≤3p-6
(5)若G是2-连通的且没有三角形,则q≤2p-4(复习：2-连通)
(6)由以上结论易得：K5与K3,3都不是可平面图
3.最大(极大)可平面图
如果这个可平面图再加入一条边，新图必然是不可平面的，则称这个图为最大可平面图
性质：
设G是一个有p个顶点q条边的最大可平面图(预习：最大可平面图),则G的每个面都是三角形,则
q=3p-6, p≥3
9.4图的顶点着色
图的一种(顶点)着色是指对图的每个顶点指定一种颜色,使得没有两个邻接的顶点有同一颜色
实质上，这是对图的顶点的一种分组，着同一颜色的为一组。
显然地，要求邻接顶点不能分在一组
1.基本术语
(1)n-着色：
图G的一个n着色是用n种颜色对G的顶点着色
(2)色组(V的子集)：
若图G=(V,E)的顶点已着色，则着同一颜色的那些顶点之集称为G 的一个色组
(3)顶点独立集(色组)：
同一色组内的各顶点不邻接，这样的顶点集合称为G的一个顶点独立集
(4)着色确定了顶点集V的一个划分：
如果G有一个n着色,则G的顶点集V被这种n着色划分为n个色组
2.色数
使G为n-着色的数的最小值,图G的色数记为χ(G), χ(G)≤n,则称G是n-可着色的，若χ(G)=n,则称G是n色的
(1)常见图的色数：
1.偶数个顶点的圈：2
2.奇数个顶点的圈：3
3.完全图K p：p
4.完全图的补图K p c：1
5.偶图：2
(2)性质：
1.一个图是可双色的当且仅当它没有奇数长的圈(复习：偶图的充要
条件)
2.设Δ=Δ(G)为图G的顶点度的最大值,则G是(Δ+1)-可着色的(P33)
3.如果G是一个连通图且不是完全图也不是奇数长的圈,则G是
Δ(G)-可着色的(复习：顶点度的最小值)
Tips:
1. 是希腊字母chi，音/ka?/，扭不过来的时候可以写成x。该字母
其实我们已经用过，e.g. Tai Chi
2.Δ(小写：δ)是希腊字母delta，音/'delt?/，值得一提的是，它便是希
腊字母表的第四个字母，自然学科中，常用以表示增长的，变化的或者是
判别式
3.平面图的顶点着色问题
(1)每个平面图都是6-可着色的
(2)每个可平面图是5-可着色的
(3)每个可平面图是4-可着色的
目录 第一章图的基本概念 (2) 二路和连通性 (4) 第二章树 (4) 第三章图的连通度 (6) 第四章欧拉图与哈密尔顿图 (8) 一，欧拉图 (8) 二．哈密尔顿图 (10) 第五章匹配与因子分解 (14) 一．匹配 (14) 二．偶图的覆盖于匹配 (15) 三．因子分解 (16) 第六章平面图 (20) 二．对偶图 (24) 三．平面图的判定 (25) 四．平面性算法 (28) 第七章图的着色 (34) 一．边着色 (34) 二．顶点着色 (35)
第九章 有向图 (40) 二 有向树 (41) 第一章 图的基本概念 1. 点集与边集均为有限集合的图称为有限图。 2. 只有一个顶点而无边的图称为平凡图。 3. 边集为空的图称为空图。 4. 既没有环也没有重边的图称为简单图。 5. 其他所有的图都称为复合图。 6. 具有二分类（X, Y ）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子 集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。 7. 完全偶图：是指具有二分类（X, Y ）的简单偶图，其中 X 的每个顶点与 Y 的每个顶点 相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 Km,n 8. 定理1 若n 阶图G 是自补的（即 ），则 n = 0, 1（mod 4） 9. 图G 的顶点的最小度。 10. 图G 的顶点的最大度。 11. k-正则图: 每个点的度均为 k 的简单图。 例如,完全图和完全偶图Kn,n 均是正则图。 12. 推论1 任意图中，奇点的个数为偶数。 ()G δ()G ?
13. 14.频序列：定理4 一个简单图G的n个点的度数不能互不相同。 15.定理5 一个n阶图G相和它的补图有相同的频序列。 16. 17. 18.对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1) 19.定义：联图在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个 顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2 20.积图：积图设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和u2 adj v2) 或(u2 = v2 和u1 adj v1) 时就把u 和v 连接起来所得到的图G称为G1和G2积图。记为G = G1×G2 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 adj v1) 或(u1= v1 和u2 adj v2) 时就把u 和v 连接起来所得到的图G称为G1和G2的合成图。记为G=G1[G2]。
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G
图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020
习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}
《运筹学》试题样卷（一） 一、判断题（共计10分，每小题1分，对的打√，错的打X ） 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3. 如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量 都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示： 试决定该农场的经营方案，使年净收入为最大。
三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为 (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1 , x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小? 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0
组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714
一、判断题（共计10分，每小题1分，对的打√，错的打X） 1.无孤立点的图一定是连通图。 2.对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3.如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/ 人日，秋冬季收入为20元/ 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中5 4 ,x x 为松弛变量，问题的约束为?形式（共8分）
(1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 的最优单纯形表如下：
08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的 最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={
期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ?
图和子图 图 图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数 E = {e e e 12,,......,ε} E ---边集， ε---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点a 与e 相邻。称有公共端点的一些边彼此相邻，例如p 与af 。 环（loop ，selfloop ）：如边 l 。 棱（link ）：如边ae 。 重边：如边p 及边q 。 简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：νε()(),()().G V G G E G ==。 习题 1.1.1 若G 为简单图，则 εν≤?? ?? ?2 。 1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G 恒等于图H , 记为 G = H ? V （G)=V(H), E(G)=E(H)。 图G 同构于图F ? V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ?F 。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) y z w c G =(V , E ) w c y z H =(V ?, E ?) ?a ? c ? y ? e ?z ? F=(V ??, E ??)
1 2017年图论课程练习题 一．填空题 1.图1中顶点a 到顶点b 的距离d (a ,b )= 。 a b 9 图1 1 2.已知图G 的邻接矩阵0 11011 01001 1010001011001 0A = ，则G 中长度为2的途径总条数为 。 3.图2中最小生成树T 的权值W (T )= 。 4.图3的最优欧拉环游的权值为 。 12 图 2
2 图3 5.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。 二．单项选择 1．关于图的度序列，下列说法正确的是( ) (A) 对任意一个非负整数序列来说，它都是某图的度序列； (B) 若非负整数序列12(,,,)n d d d π= 满足1n i i d =∑为偶数，则它一定是图序 列； (C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数； (D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。 2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。 3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。下面说法错误的是( )
3 (A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<； (C) 设G 是n 阶简单图，若()2n G δ ≥ ，则G 连通，且()()G G λδ=； (D) 图G 是k 连通的，则G 的连通度为k 。 4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图； (B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足 ()()d u d v n +≥，则G 是哈密尔顿图。 5.下列说法错误的是( ) (A) 有完美匹配的三正则图一定没有割边； (B) 没有割边的三正则图一定存在完美匹配； (C) 任意一个具有哈密尔顿圈的三正则图可以1因子分解； (D) 完全图21n K +是n 个哈密尔顿圈的和。 三、 设无向图G 有10条边，3度与4度顶点各2个，其余顶点度数均小于3，问G 中至少有几个顶点？在最少顶点数的情况下，写出G 的度序列，该度序列是一个图序列吗？。
图论及其应用 学时：40 学分：2 课程属性：专业选修课开课单位：理学院 先修课程：高等代数后续课程：无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配，求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配，求最大匹配算法及应用 6
7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材： [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩．图论与网络流．北京：中国林业出版社，2000． 参考书目： [1] Bela Bollobas．Modern Graph Theory（现代图论，影印版）．北京：科学出版社，2001． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学出版社，2003． [3] 谢金星、邢文训．网络优化．北京：清华大学出版社．2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学出版社，2000． [5] 三味工作室．SPSS V10.0 for Windows 实用基础教程．北京：北京希望电子出版社2001． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．MATLAB程序设计语言．西安：西安电子科技大学出版社，1997．八、教学基本内容及要求 第一章图的基本概念 1．教学基本要求 掌握的图的基本概念、特殊图概念，了解最短路问题。 2．教学具体内容 图的基本概念，路和圈，最短路问题。
2015电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A ．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B ．图论中的图，画边时长短曲直无所谓。 C ．图中的边表示研究对象，点表示研究对象之间的特定关系。 D ．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图K 3,3同构？ A ． B ． C ． D ． 有10条边的5顶单图必与K 5同构。 完全二分图K m ,n 的边数是 A ．m B ．n C ．m +n D ．mn 无向完全图K n 的边数为 A ．n B ．n 2 C ．n (n -1) D ．n (n -1)/2 若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。 对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。 有15个顶的单图的边数最多是 A ．105 B ．210 C ．21 D ．45 图G 如右，则dacbeb A ．是G 中的一条道路 B ．是G 中的一条道路但不是行迹 C ．是G 中的一条行迹但不是轨道 D ．不是G 的一条道路 图G 如右，则befcdef A ．是G 的一个圈 B ．是G 的一条道路但不是行迹 C ．是G 的一条行迹但不是轨道 D ．是G 的一条轨道但不是圈
v1 36 7 图G如右图所示，则ω (G)= A．1 B．2 C．7 D．8 下列图形中与其补图同构的是 A．B．C．D． 求下图中顶u0到其余各顶点的最短轨长度。 u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1， v5v 6 =4，v 5 v7=3，v6v7=6， 请画出6阶3正则图。 请画出4个顶，3条边的所有非同构的无向简单图。 设图G={V(G)，E(G)}其中V ={ a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。 一个图的生成子图必是唯一的。 不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4 画出5个具有5个结点5条边的非同构的无向连通简单图。 u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0 到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6 ，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。
习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的
同一分支中，令是与 处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给 出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H
图论的发展及其在生活中的应用 数学与应用数学张佳丽 指导教师刘秀丽 摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application 引言 图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支
第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑
北京大学信息科学技术学院期末试卷考试科目：集合论与图论姓名：学号： 考试时间：2018 年 1 月 2 日任课教师: 参考答案 以下为试题和答题纸，共 5 大题。
一、（20分）设n是某个自然数，N是自然数集，回答下列 问题并给出证明： (1) P(n)是否传递集？ 证明：n为传递集，A为传递集当且仅当P(A)为传递集 所以P(n)为传递集 (2) P(N)是否归纳集？ P(N)不是归纳集，N+=N?{N}?P(N)，因为P(N)的任意元素A都是N的子集，所以A的元素都是自然数。因此是有限集，所以P(N)对后继运算不封闭，故P(N)不是归纳集 二、（20分）对于无向图G1=(V1,E1)和G2=(V2,E2)，如果有 函数f:V1→V2满足以下性质：对于任意的u,v∈ V1， (u,v) ∈ E1 ? ( f(u), f(v) ) ∈ E2， 则说f是从G1到G2的同态。把同态看作全体无向图上的二元关系，试回答下列问题并给出证明。 (1) 同态关系是否自反的？ 是，恒等映射 (2) 同态关系是否反自反的？ 不是，实际是自反的
(3) 同态关系是否对称的？ 不是，K1同态到K2，反之不然。 (4) 同态关系是否反对称的？ 不是，K2和K1,2互相同态 (5) 同态关系是否传递的？ 是，由定义可知同态的合成还是同态 (6) 证明：图G可以k-着色当且仅当G可以同态到k个顶点的完全图。（?）设颜色集为{1,2,…,k}，设完全图的顶点集为{u1,u2,…,u k}，设k-着色为g: V→{1,2,…,k}，则同态为f:V→{u1,u2,…,u k}， f(v)=u g(v)，即着g(v)色的同色顶点都对应到完全图同一个点u g(v)上。（?）设完全图的顶点集为{u1,u2,…,u k}，设同态为f:V→{u1,u2,…,u k}，则给f-1(u i)中的顶点都着颜色i。
学号：201321010808 姓名：马涛 习题1 4．证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )→u i (1≤ i ≤ 10) 容易证明，对?v i v j ∈E((a)),有f(v i v j )=u i u j ∈E((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。 6．设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则? v ∈V(G),有d(v)< n-1 ? ∑ d(v) < n(n-1) ? 2m 证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ? ∣V 1∣= ∣V 2 ∣。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ?v in v ik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题2 证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当)1(21-=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足E d n i i 21 =∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=?∑=n d n i i 证明：若e 是n K 的边，则3)2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2)1(--n n n ，所以，每条边所对应的生成树的棵数 为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ Kruskal 算法能否用来求： 2005年研究生期末试题(120分钟) 《图论及其应用》 一、填空(15分，每空1分) 1、 已知图G 有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则 G 中至少有___8___个顶点 . 2、 m 条边的简单图G 中所有不同的生成子图(包括G 和空图)的个数为 __2____.m 3、 4个顶点的非同构的简单图有__11___个. 4、 图G 1的最小生成树各边权值之和为__28___. 5、若W 是图G 中一条包含所有边的闭通道，则W 在这样的闭通道中具有最短长度的充要条件是： (1) 每一条边最多重复经过_1__次； (2) 在G 的每一个圈上，重复经过的边的数目不超过圈的长度的____.一半 6、5阶度极大非哈密尔顿图族有5 52 1__,_____C C . 7、在图G 2 中，图的度序列为(44443322)，频序列为(422)，独立数为3， 团数为4，点色数为4，边色数为4，直径为3. 二、选择(15分) (1)下列序列中，能成为某简单图的度序列的是( C ) (A) (54221) (B) (6654332) (C) (332222) （2）已知图G 有13条边，2个5度顶点，4个3度顶点，其余顶点的的度数为2，则图G 有( A )个2度点。 图G 1 图G 2 (A) 2 ( B) 4 (C ) 8 (3) 图G 如(a)所示，与G 同构的图是( C ) (4) 下列图中为欧拉图的是( B ),为H 图的是( AB ),为偶图的是( BC ). 5．下列图中可1-因子分解的是( B ) 三、设?和δ分别是(,)n m 图G 的最大度与最小度，求证：2m n δ≤≤?(10分). 证明：() 22().v V G m n m d v n n δδ∈≤= ≤??≤ ≤?∑ 四、正整数序列12(,,,)n d d d 是一棵树的度序列的充分必要条件是1 2(1)n i i d n ==-∑ (10分). 证明：""? 结论显然 ""? 设正整数序列12(,, ,)n d d d 满足1 2(1)n i i d n ==-∑，易知它是度序列。 设G 是这个度序列的图族中连通分支最少的一个图，知m=()1E G n =-. 假设G 不连通，则()2G ω≥，且至少有一个分支1G 含有圈C ，否则，G 是森林， (A) (B) (C) (a) (A) (B) (C) (A) (B) (C) 北京大学信息科学技术学院考试试卷考试科目：集合论与图论姓名：学号： 一、名词解释（共20分，每小题5分） 1) 容斥原理 (2) 皮亚诺系统 (3) 欧拉公式 (4) 中国邮递员问题 二、单项选择题（共20分，每小题2分） (1) 设A,B,C是集合，则B?C?A是(A?B)?C=A的（） A. 充分条件 B. 必要条件 C. 充要条件 D. 都不对 (2) {a,b,c}上既是等价关系又是偏序关系的二元关系有（） A. 0个 B. 1个 C. 2个 D. 都不对 (3) 设A={a,b}，B={1,2}，则{ (8) 互不同构的3阶简单有向图有（） A. 15种 B. 16种 C. 17种 D. 都不对 (9) 非平凡的自补的自对偶简单平面图一定不是（） A. 欧拉图 B. 哈密顿图 C. 平面图 D. 都不对 (10) 彼得森图是（） A. 欧拉图 B. 哈密顿图 C. 平面图 D. 都不对 三、判断题（共20分，每小题2分） 存在唯一的一个最大的集合，称为全集。（） （） (3) 反自反和传递的二元关系一定是反对称的。（） (4) 传递集的后继还是传递集。（） (5) 图与图之间的同胚关系是等价关系。（） (6) 3-正则简单图的点连通度一定等于边连通度。（） (7) 无桥3-正则简单图一定有完美匹配。（） (8) 任何两个奇数长度回路都有公共顶点的简单图，其点色数不超过5。（） (9) 外平面图的充要条件是不含有同胚或可边收缩到K4和K2,3的子图。（） (10) 无孤立点简单图的顶点覆盖一定是支配集。（） 四、填空题（共10分，每空2分） (1) 自然数2的集合表示是。 (2) 良序关系是。 (3) 无向欧拉图的充要条件是。 (4) 简单图有完美匹配的塔特条件是。 (5) 二部图有完备匹配的霍尔条件是。 五、（10分）从自然数集删除有穷个自然数后得到的集合称为补有穷 集。试确定全体补有穷集组成的集合的基数，并给出证明。电子科大研究生图论05-14年图论期末试题
北京大学集合论与图论SG14期末考试题试卷公布
相关主题
文本预览