电子科技大学-图论第一次作业-

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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 ）AC DA B CD6．下列图中，不是偶图的是（ 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 13图G由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。

图论作业3一、填空题1. 完全图K2n共有个不同的完美匹配。

2. 超方体Q6的最小覆盖包含的点数为。

3. 图K m,n (m≤n)的最小覆盖包含的点数为。

4. 完全图K60能分解为个边不重的一因子之并。

5. 完全图K61能分解为个边不重的二因子之并。

6. 假设G是具有n个点、m条边、k个连通分支的无圈图，则G的荫度为。

7. 图G是由3个连通分支K1, K2, K4组成的平面图，则其共有个面。

8. 设图G与K5同胚，则至少从G中删掉条边才可能使其成为可平面图。

9. 设连通平面图G具有5个顶点，9条边，则其面数为。

10. 若图G是10阶极大平面图，则其面数等于。

11. 若图G是10阶极大外平面图，其内部面共有个。

二、不定项选择题1. 关于非平凡树T，下面说法错误的是( )(A) T至少包含一个完美匹配；(B) T至多包含一个完美匹配；(C) T的荫度大于1；(D) T是只有一个面的平面图；(E) T的对偶图是简单图。

2. 下列说法正确的是( )(A) 三正则的偶图存在完美匹配；(B) 无割边的三正则图一定存在完美匹配；(C) 有割边的三正则图一定没有完美匹配；(D) 有完美匹配的三正则图一定没有割边；(E) 三正则哈密尔顿图存在完美匹配。

3. 下列说法正确的是( )(A) 在偶图中，最大匹配包含的边数等于最小覆盖包含的点数；(B) 任一非平凡正则偶图包含完美匹配；(C) 任一非平凡正则偶图可以1-因子分解；(D) 偶度正则偶图可以2-因子分解；(E) 非平凡偶图的最大匹配是唯一的。

4. 下列说法中错误的是( )(A) 完全图K101包含1-因子；(B) 完全图K101包含2-因子；(C) 完全图K102包含1-因子；(D) 完全图K102包含2-因子；(E) 图G的一个完美匹配实际上就是它的一个1因子；(F) 图G的一个2-因子实际上就是它的一个哈密尔顿圈。

5. 下列说法正确的是( )(A) 方体Q n可以1-因子分解；(B) 非平凡树可以1-因子分解；(C) 无割边的3正则图可以1-因子分解；(D) 有割边的3正则图一定不可以1-因子分解；(E) 可1-因子分解的3正则图一定是哈密尔顿图。

图论第三次作业一、第六章2.证明：根据欧拉公式的推论，有m ≦l*(n-2)/(l-2),(1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4;(2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10;(3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6.3.证明：∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6;又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4.4.证明：(1)∵G 是极大平面图，∴每个面的次数为3，由次数公式：2m==3φ,由欧拉公式：φ=2-n+m,∴m=2-n+m,即：m=3n-6.(2)又∵m=n+φ-2,∴φ=2n-4.(3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。

5.证明：假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。

6.证明：(1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5.(2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5.二、第七章2.证明：设n=2k+1,∵G 是Δ正则单图，且Δ>0,∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.28.解： (1)又：=k(k-1)(k-2)2(k-3)+k(k-1)2(k-2)=k(k-1)(k-2)(k2-4k+5)=k(k-1)(k-2)2(k-3),所以，原图色多项式为：k(k-1)(k-2)2(k2-4k+5)-k(k-1)(k-2)2(k-3)=k(k-1)(k-2)2(k2-5k+8)(2)∵原图与该图同构，又，同构的图具有相同的色多项式，所以原图色多项式为：k(k-1)(k-2)2(k2-5k+8)。

电子科技大学研究生试卷（测试时间：至，共__2_小时）课程名称图论及其使用教师学时60 学分教学方式讲授考核日期_2012__年___月____日成绩 考核方式：（学生填写）一、填空题（填表题每空1分，其余每题2分，共30分)1．n 阶k 正则图G 的边数()m G =______2nk； 2．3个顶点的不同构的简单图共有___4___个；3．边数为m 的简单图G 的不同生成子图的个数有__2___m 个；4. 图111(,)G n m =和图222(,)G n m =的积图12G G ⨯的边数为1221____n m n m +；5. 在下图1G 中，点a 到点b 的最短路长度为__13__；6. 设简单图G 的邻接矩阵为A ，且23112012*********102001202A ⎛⎫⎪⎪⎪= ⎪ ⎪⎪⎝⎭，则图G 的边数为__6__； 7. 设G 是n 阶简单图，且不含完全子图3K ，则其边数一定不会超过2___4n ⎢⎥⎢⎥⎣⎦；8．3K 的生成树的棵数为__3__;9. 任意图G 的点连通度()k G 、边连通度()G λ、最小度()G δ之间的关系为__()()()____k G G G λδ≤≤；10. 对下列图，试填下表（是⨯⨯类图的打〝√ 〞，否则打〝⨯〞）。

① ② ③学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………4 5 6 6 4 1 1 2 7 243 ab G 1能一笔画的图 Hamilton 图 偶图 可平面图 ① ⨯ √ ⨯ √ ② ⨯ ⨯ ⨯ √ ③⨯√√ √二、单项选择(每题2分，共10分)1．下面命题正确的是(B )对于序列(7,5,4,3,3,2)，下列说法正确的是：(A) 是简单图的度序列；(B) 是非简单图的度序列; (C) 不是任意图的度序列; (D)是图的唯一度序列.2．对于有向图，下列说法不正确的是(D)(A) 有向图D 中任意一顶点v 只能处于D 的某一个强连通分支中； (B) 有向图D 中顶点v 可能处于D 的不同的单向分支中;(C) 强连通图中的所有顶点必然处于强连通图的某一有向回路中; (D)有向连通图中顶点间的单向连通关系是等价关系。

图论第一次作业答案（2010.9.9）：1：证明 ()|E G |2v ⎛⎫≤ ⎪⎝⎭，其中G 是单图。

证：因为G 是单图，所以|()||()|v E G E K ≤又因为v |()|2v E K ⎛⎫≤⎪⎝⎭ ，所以()|E G |2v ⎛⎫≤ ⎪⎝⎭5：若N 个人的人群中至少有一个人未与每个人握手，求可能与每个人握手的最多有几个人？解：假设每个人为一个顶点，共有N 个顶点（V 1,V 2,。

V N ），俩人握手可看做两顶点相连，从而构成图G不是一般性，假设V i 与V j 没有握手，则V i 与V j 均未与所有人握手，所以至多有N-2个人与每个人握手。

4：画出不同构的一切四顶点图。

解：20： 证明每个顶皆2次的连通图是圈。

证：设P=v 0v 1v 2…. v n 为最长轨，由于()d v 2≡，所以v i （0<i<n ）只能与v i -1和v i +1相连v 0除了与v 1相连，还与v x 相连，若v x 不P 上，则P 还可以加长，与最长轨定义矛盾，所以v x 在P 上。

对于P 上的任一顶点v i （0<i<n ），已经存在d （v i ）=2，每个顶不可能有与之关联的第三条边，又因为此图是连通图，所以v x就是v n，此时原图为圈。

29，证明二分图的子图是二分图。

证明：设S是二分图G的子图。

且有，。

因，不妨设包含X中顶点子集和Y中顶点子集。

（1）若和都不为空。

又因，且X中任二顶不相邻，Y中任二顶不相邻，所以，中任二顶不相邻，中任二顶不相邻。

因此，S是二分图。

（2）若不为空，为空。

因X中任二顶不相邻，所以，中任二顶不相邻。

将分为，中任二顶不相邻，中任二顶不相邻。

因此，S是二分图。

（3）若为空，为空。

同（2）。

命题得证。

32，证明。

证明：对任意顶点有：。

(i=1,2, (v)因此，v，即，。

由Euler定理，得：。

命题得证。

1电子科技大学研究生试卷（考试时间： 至 ，共__2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2013__年_6__月__20__日 成绩 考核方式： （学生填写）一．填空题(每空2分，共20分)1． n 阶k 正则图G 的边数m =_____。

2．4个顶点的不同构单图的个数为________。

3．完全偶图,r s K (,2r s ≥且为偶数)，则在其欧拉环游中共含____条边。

4．高为h 的完全2元树至少有_______片树叶。

5. G 由3个连通分支124,,K K K 组成的平面图，则其共有_______个面。

6. 设图G 与5K 同胚，则至少从G 中删掉_______条边，才可能使其成为可平面图。

7. 设G 为偶图，其最小点覆盖数为α，则其最大匹配包含的边数为________。

8. 完全图6K 能分解为________个边不重合的一因子之并。

9. 奇圈的边色数为______。

10. 彼得森图的点色数为_______。

二．单项选择(每题3分，共15分) 1．下面说法错误的是( )学 号 姓 名 学 院…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效……………………2(A) 图G 中的一个点独立集，在其补图中的点导出子图必为一个完全子图；(B) 若图G 连通，则其补图必连通； (C) 存在5阶的自补图； (D) 4阶图的补图全是可平面图. 2．下列说法错误的是（ ） (A) 非平凡树是偶图；(B) 超立方体图(n 方体,1n ≥)是偶图； (C) 存在完美匹配的圈是偶图； (D) 偶图至少包含一条边。

3.下面说法正确的是( )(A) 2连通图一定没有割点（假定可以有自环）； (B) 没有割点的图一定没有割边；(C) 如果3阶及其以上的图G 是块，则G 中无环，且任意两点均位于同一圈上；(D) 有环的图一定不是块。

12017年图论课程练习题一．填空题1.图1中顶点a 到顶点b 的距离d (a ,b )= 。

ab9 图112.已知图G 的邻接矩阵0110110100110100010110010A=，则G 中长度为2的途径总条数为 。

3.图2中最小生成树T 的权值W (T )= 。

4.图3的最优欧拉环游的权值为 。

12 图 22图35.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。

二．单项选择1．关于图的度序列，下列说法正确的是( )(A) 对任意一个非负整数序列来说，它都是某图的度序列；(B) 若非负整数序列12(,,,)n d d d π= 满足1ni 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 是哈密尔顿图。

第一章：图论基本概念 1.定义平凡图/非平凡图 简单图/复合图 空图 n 阶图 连通图/非连通图完全图n K12n n n m K偶图,m n K 完全偶图,m n m K mn K 正则图图和补图，自补图 自补图判定方法 定点的度 d v 最小度 最大度 握手定理2d v m图的度序列与图序列，图序列判定方法（注意为简单图） 图的频序列 2.图运算删点/删边 图并/图交/图差/图对称差 图联 积图/合成图111122,u adjv u v u adjv 或 超立方体 3.连通性 途径 迹 路图G 不连通，其补图连通一个图是偶图当且仅当它不包含奇圈 4.最短路算法（b t A T ） 5.矩阵描述邻接矩阵及其性质，图的特征多项式 关联矩阵 6.极图？？L 补图 完全L 部图 完全L 几乎等部图 托兰定理第二章：树 1.定义树：连通的无圈图 森林 树的中心和树的形心？入<=sqrt(2m(n-1)/n)生成树 根树 出度 入度 树根 树叶 分支点 m 元根树 完全m 元根树 2.性质每棵非平凡树至少有两片树叶图G 是树当且仅当G 中任意两点都被唯一的路连接T 是(n,m)树，则m = n – 1 具有k 个分支的森林有n-k 条边每个n 阶连通图边数至少为n-1（树是连通图中边的下界） 每个连通图至少包含一棵生成树 3.计算 生成树计数 递推计数法： G G e G e关联矩阵计数法：去一点后，每个非奇异阵对应一棵生成树最小生成树（边赋权）避圈法 破圈法完全m 元树： 11m i t第三章：图的连通性1. 割边、割点和块（性质使用反证法） 割边： w G e w G边e 为割边当且仅当e 不在任何圈中割点： w G v w Gv 是无环连通图G 的一个顶点，v 是G 的割点当且仅当V(G-e)可以被划分为两个子集，v 在两个子集内点互连的路上 块：没有割点的连通子图 G 顶点数>=3，G 是块当且仅当G 无环且任意两顶点位于同一圈上v 是割点当且仅当v 至少属于G 的两个不同的块2. 连通度点割 k 顶点割 最小点割（最少用几个点把图割成两份） G 的连通度 G连通图没顶点割时连通度 1G n ，非连通图 0G边割 k 边割 最小边割（最少用几条边把图割成两份） G 的边连通度 G递推到无圈，自环不算圈性质： 任意图G 有 G G GG 是(n,m)连通图， 2m G nG 是(n,m)单图，若 2n G，则G 必定连通 G 是(n,m)单图，对应k n ，若 22n k G，则G 是k 连通G 是(n,m)单图，若 2n G，则 G G敏格尔定理： G 中分离不相邻x,y 的最小点数等于独立的x,y 路最大数目G 中分离x,y 的最小边数等于边不重x,y 路最大数目第四章 E 图与H 图 一、 E 图（走完所有边） 1. 定义，性质与判定E 图（欧拉环游）与E 迹，走完所有边回到出发点与不回到出发点E 图性质与判定：E 图 G 的顶点度数为偶数度 G 的边集合能划分为圈 E 迹性质与判定：E 迹 G 中只有两个顶点度为奇数 2. 求解路径算法 找欧拉环游：都是偶数度点：Fleury 算法（避割边行走）两奇数点欧拉环游：奇数点补充最短路后得到欧拉环游多奇数点欧拉环游：补充偶数度并不断交换 （中国邮路问题算法） 二、 H 图（走完所有点） 1. 定义与性质H 图（H 圈）与H 路：走完所有点回到出发点与不回到出发点 G 图是H 图 w G S S 2. H 图判定3n 的单图G ，如果 2nGG 是H 图3n 的单图G ，任意不相邻u,v 有 d u d v n G 是H 图图G 的闭包是H 图 G 是H 图 度序列判定法：123n d d d d ，3n ，若对任意的2nm，有m d m 或n m d n m ，则G 是H 图123n d d d d ，3n ，若对任意的2nm，有m d m 且n m d n m ，则G 是非H 图 2. 极大非哈密尔顿图定义：如果图G 的度大于等于其他非H 图，则称G 为极大非H 图（非H 图的度上限）,m n C 图： ,2m n m m n m C K K K,m n C 图是非H 图G 是非H 图 G 度弱于某个,m n C 图（证） N 阶单图G 度优于所有,m n C 图 G 为H 图 彼得森图是超H 图4. TSP 问题（边赋权近似最优H 圈求解）最优H 图下界：去点求最小生成树，选最小关联边12e e ， 11w T w e w e第五章 图的匹配与因子分解 1.边匹配定义： 匹配 饱和点/非饱和点 最大匹配/完美匹配 M 交错路/M 可扩路 贝尔热定理：G 的匹配M 是最大匹配，当且仅当G 不包含M 可扩路（反证） 2.偶图匹配Hall 定理（偶图匹配存在性定理，完美匹配）： N S S 推论：k 正则偶图G 存在完美匹配（证） 匹配算法： 匈牙利算法最优匹配算法3.点覆盖边匹配数等于点覆盖数时匹配为最大匹配覆盖为最小覆盖 哥尼定理：偶图中最大匹配边数等于最小覆盖点数（用） 4.托特定理一般图G 有完美匹配当且仅当 G S S推论：没有割边的3正则图存在完美匹配（充分条件）（证） 5.因子分解因子分解，n 度正则因子 一因子分解：2n K 可一因子分解具有H 圈的三正则图可一因子分解 若三正则图有割边，则它不能一因子分解 二因子分解： G 的一个H 圈肯定是一个二因子，但二因子不一定是H 圈（二因子可以不连通）21n K 可2因子分解2n K 可分解为一个1因子和n-1个2因子之和。

习题43： 1）、画一个有Euler闭迹和Hamilton圈的图。

2）、画一个有Euler闭迹但没有Hamilton圈的图。

3）、画一个有Hamilton圈但没有Euler闭迹的图4）、画一个既没有Hamilton圈也没有Euler闭迹的图7、证明：将G中的孤立点去掉后的图为G1，则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1，在G1 –S1中去除孤立的点，得到一个新的图G2，显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2，这样一直下去，指导Gm中有圈Sm，且Gm-Sm都是孤立的点。

这样E(G) = E(G1)并E(G2)…..并E(Gm).命题得证。

10、证明：1）、如果G不是而连通的图，那么G存在割点v或则G是不连通的，G-v的连通分支数大于等于2.由定理：若G是H图，则对于V的每个飞空真子集S，均有G-S的连通分支数小于等于S的顶点数，知，G是非H图。

2）、G 是2部图，且|X|<|Y|,则有G-X的连通分支数等于|Y|>|X|由上边的定理知，G是非H图。

12、证明：假设G中新加入的一点，为V,它和G中的每一个顶点均相连，这样得到新的图G^,这样G^的度序列为(d1+1,d2+1……,dv+1,V)。

因为不存在正整数m<(v+1)/2,使其满足dm<m和dv-m+1<v-m,即不存在m<(v+1)/2,满足dm+1<=m和dv-m+1<v-m+1 = (v+1) –m。

由定理知，G^中含有Hamilton圈C，这样G^-C就是G的H路，命题得证。

习题51、1）、证明：每个k方体都有完美匹配(k>=2)。

假设K方体的顶点坐标为：(x1,x2…,xk)，取(x1,x2,….,xk-1,0)和(x1,x2,…,xk-1,1)两个顶点之间的边的全体集合为M，这样M,中的边均不相邻，所以M是一个匹配，且|M| = 2^(k-1)。

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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图G二．单项选择(每题3分，共21分)1．下面给出的序列中，是某简单图的度序列的是( A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2．已知图G 如图所示，则它的同构图是（ D ）3． 下列图中，是欧拉图的是（ D ）4． 下列图中，不是哈密尔顿图的是（B ）5． 下列图中，是可平面图的图的是（B ）A Bb c123A B 3CDAD6．下列图中，不是偶图的是（ B ）7．下列图中，存在完美匹配的图是（B ）三．作图(6分)1．画出一个有欧拉闭迹和哈密尔顿圈的图；2．画出一个有欧拉闭迹但没有哈密尔顿圈的图；3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解：四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。

A B DC123A B DC解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五．(8分)求下图G 的色多项式P k(G).解：用公式)()()(e G P G P e G P k k k •+=-，可得G 的色多项式：)3)(2()1()()(3)()(2345---=++=k k k k k k k G P k 。

六．(10分) 一棵树有n 2个顶点的度数为2，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。

电⼦科技⼤学《图论及其应⽤》复习总结--第⼀章图的基本概念⼀、重要概念图、简单图、图的同构、度序列与图序列、偶图、补图与⾃补图、两个图的联图、两个图的积图1.1 图⼀个图G定义为⼀个有序对(V, E)，记为G = (V, E)，其中（1）V是⼀个有限⾮空集合，称为顶点集或边集，其元素称为顶点或点；（2）E是由V中的点组成的⽆序点对构成的集合，称为边集，其元素称为边，且同⼀点对在E中可出现多次。

注：图G的顶点数（或阶数）和边数可分别⽤符号n(G) 和m(G)表⽰。

连接两个相同顶点的边的条数，叫做边的重数。

重数⼤于1的边称为重边。

端点重合为⼀点的边称为环。

1.2 简单图⽆环⽆重边的图称为简单图。

（除此之外全部都是复合图）注： 1.顶点集和边集都有限的图称为有限图。

只有⼀个顶点⽽⽆边的图称为平凡图。

其他所有的图都称为⾮平凡图。

边集为空的图称为空图。

2.n阶图：顶点数为n的图，称为n阶图。

3.(n, m) 图：顶点数为n的图，边数为m的图称为(n, m) 图1.3 邻接与关联：顶点u与v相邻接：顶点u与v间有边相连接(u adj v)；其中u与v称为该边的两个端点。

注：1.规定⼀个顶点与⾃⾝是邻接的。

2.顶点u与边e相关联：顶点u是边e的端点。

3.边e1与边e2相邻接：边e1与边e2有公共端点。

1.4 图的同构设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：u1,v1∈V1,u2,v2∈ V2 ，设u1↔u2，v1↔v2,; u1v1∈E1 当且仅当u2v2∈E2,且u1v1与u2v2的重数相同。

称G1与G2同构，记为：G1≌G2注：1、图同构的两个必要条件： (1) 顶点数相同；(2) 边数相同。

2、⾃⼰空间的理解：通过空间的旋转折叠可以进⾏形态转换1.5 完全图、偶图1、在图论中，完全图是⼀个简单图，且任意⼀个顶点都与其它每个顶点有且只有⼀条边相连接。

图论复习提纲及练习题(10级,西安电子科技大学数学系)一.要求:1.熟悉讲义中的基本概念.2.能独立完成课后大部分习题.3.重点内容(1).可以独立证明定理2.3；熟悉最优前缀编码的Huffman算法;会用Kruskal和Prim算法求最小生成树.(2).会证明关于二部图的K¨o nig定理和Hall定理.(3).会证明关于图的2-连通的Whitney定理.(4).会证明K5和K3,3不是可平面图;会用欧拉定理或其推论判别一些具体的图是否为可平面图.(5).会给一些简单图形进行顶点着色;会判别一些简单图形是否为哈密尔顿图.(6).会用鸽巢原理证明一些简单的命题.二.练习题:练习题1证明:Petersen图不含长度为7的圈.(Petersen图参见讲义27页.提示:注意此图最短圈的长度为5)练习题2如果G是n个顶点的简单图且δ(G)≥(n−1)/2,证明:G是连通的.举例说明δ(G)<(n−1)/2时，G未必连通.注意δ(G)表示G的最小顶点度.练习题3设G是至少有两个顶点的图.判定下列命题是否成立:若成立请证明；否则举出反例.(1)删除一个度为∆(G)的顶点不会增加度的平均值.∆(G)表示最大顶点度，平均度即度数和除以顶点的个数.(2)删除一个度为δ(G)的顶点不会减小度的平均值.练习题4证明：∆(T)>1的一棵树T至少有∆(T)个叶子.对于任意满足n>∆>1的n和∆,构造一棵恰好有∆个叶子n个顶点的树.练习题5设G是n个顶点的图,且删除任意一个顶点后得到的图均是一棵树,确定此图的边数，并由此确定此图.练习题6令d1,d2,...,d n是正整数(n>2).证明存在一个顶点度为d1,d2,...,d n的树当且仅当∑i=1,2,...,n d i=2n−2.练习题7设T是一棵有偶数个顶点的树.证明:T恰有一个生成子图使得其中每个顶点的度数为奇数.练习题8在下图中(图随后发上)，给出一个完美匹配或者简要证明它没有完美匹配.练习题9如果图G的度序列为d1≥d2...≥d n，则χ(G)≤1+maxi∈{1,2,...,n}{min{d i,i−1}}注意，此练习题即讲义中22页习题4.提示:用我们介绍的贪心着色算法对顶点度非递增的顶点序列着色.练习题10设G是最短圈长为k的n个顶点的简单可平面图.证明:|e(G)|≤(n−2)k.k−2其中|e(G)|表示G的边数.由此结论证明Petersen图不是可平面图.注意，此题即讲义中26页习题5，利用欧拉公式或其推论.练习题11一只小老鼠想吃掉3×3×3立方体的蛋糕，为此它必须吃掉所有的1×1×1单位的蛋糕.如果它从立方体的一个角开始，并且下一个吃掉的1×1×1单位的蛋糕与前一个1×1×1单位的蛋糕必须有公共面.问小老鼠能完成目标并且最后吃掉中心的那块吗？练习题12一个正方形的房子被分成了6×6个正方形的小房子举办展览，设相邻的两个房子有门相连.问一个人是否可以从一个角的房子出发参观完所有的展览,且每个房子只参观一次，而从与初始的小房子相对的另一个角的小房子出去呢？说明:这十二个题作为最后一次课的讲义仅仅用来熟悉我们前面学过的知识.也并非按难易程度排列.感兴趣的同学都可以试试，周四上课时主要由大家一起来完成.会做的同学做好上台讲解的准备.希望大家能积极争取机会.参考文献：[1] D.B.West,Introduction to graph theory,Pearson Education,2001.(中译本:图论导引,李建中等译，北京:机械工业出版社，2006)[2]J.A.Bondy,U.S.R.Murty,Graph theory with applications,Macmillan,1976.。