下载文档原格式
电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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 是非哈密尔顿图。
图论总结（超强大）-标准化文件发布号：（9556・EUATWK・MWUB-WUNN・INNUL-DDQTY-KII 1.图论Graph Theory1 丄定义与术语Definition and Glossary1.1.1.图与网络Graph and Network1.1.2.图的术语Glossary of Graph1.1.3.路径与回路Path and Cycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Sets in graph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorial optimization12 图的表示Expressions of graph1.2.1.邻接矩阵Adjacency matrix1.2.2.关联矩阵Incidence matrix1.2.3.邻接表Adjacency list1.2.4.弧表Arc list1.2.5.星形表示Star1・3・图的遍历Traveling in graph1.3.1.深度优先搜索Depth first search (DFS)1.3.1.1・概念1.3.1.2・求无向连通图中的桥Finding bridges in undirected graph1.3.2.广度优先搜索Breadth first search (BFS)14 拓扑排序Topological sort1.5.路径与回路Paths and circuits1.5.1.欧拉路径或回路Eulerian path1.5.1.1.无向图1.5.1.2.有［句图1.5.13. 7昆合图1.5.1.4 ・无权图Un weighted1.5.1.5・有权图Weighed —中国邮路问题The Chinese post problem1.5.2.Hamiltonian Cycle 哈氏路径与回路1.5.2.1.无权图Un weighted1.5.2.2・有权图Weighed —旅行商问题The travelling salesman problem 1.6.网络优化Network optimization1.6.1.最小生成树Minimum spanning trees1.6.1.1.基本算法Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3・ Sollin ( Boruvka)1.6.1.2.扩展模型Extended models1.6.1.2.1.度限制生成树Minimum degree-bounded spanning trees1.6.1.2.2.k 小生成树The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路Single-source shortest paths1.6.2.1.1.基本算法Basic algorithms1.6.2.1.1.1 ...................................................................................... Dijkstra1.6.2・1・1.2 ......................................................................... B ellman-Ford1.6.2.1.1.2.1 ........................... S hortest path faster algorithm(SPFA)1.6.2.1.2. 应用 Applications1.6.2.1.2.1 ......................差分约束系统 System of difference constraints1. 6.2. 1. 2. 2 ........... 有向无环图上的最短路Shortest paths in DAG1. 6.2. 2.所有顶点对间最短路 Al 1-pairs shortest paths1. 6.2. 2. 1 ........................................................ 基本算法 Basic algor it hms1.6.2. 2.1.1 ..................................................................... Floyd-War shall1.6.2. 2.1.2网络流 Flow network 1. 6. 3. 1.最大流 Maximum flow最小费用流Minimum cost flow............... 找最小费用路 Finding minimum cost pathJohnson 1.6.3 16. 3 1.1 ................................................... 1.6. 3.1.1.1 • •••••• 1.6. 3.1 1.1.1.. • ••••••••• 1.6 3. 1. 1. 1 1・ 1・ ・・・・1.6 3. 1. 1. 1 1.2 ..........1.6. 3.1.1.2 • •••••• • ••••••••1.6. 3.1 1.2.1..1.6. 3.1 1.2. 2..1. 6. 3.1.1. 31.6. 3.1.2 ............1.6. 3.1.2.1 • •••••• • •••••••••基本算法 Basic algor it hmsFord-Fulkerson method Edmonds-Karp algorithmMinimum length path Maximum capability path 预流推进算法Pref low pushmethod Push-relabelRelabel-to-front Dinic method 扩展模型 Extendedmodels 有上下界的流冋题 1.6. 3. 2.1. 6. 3.2. 2 .......................................... 找负权圏Finding negative circle1. 6. 3.2. 3 .................................... 网络单纯形Network simplex algorithm1. 6. 4 ....................................................................................................... 匹酉己Matching1. 6. 4. 1.二分图Bipartite Graph1. 6. 4.1.1.无权图-匈牙利算法Unweighted - Hopcroft and Karp algorithm1. 6. 4.1.2...带权图-KM 算法Weighted - Kuhn-Munkres(KM) algorithm1. 6. 4.2. 一般图General Graph1. 6. 4.2.1 ............ 无权图-带花树算法Unweighted - Blossom (Edmonds) 1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与网络Graph and Network二元组(H,E)称为图(graph) V为结点(node)或顶点(vertex)集。
图论期末总结一、引言图论是一门研究图和网络结构的数学学科。
图论不仅在数学领域中有着广泛的应用，而且在计算机科学、物理学、化学、生物学等交叉学科中也扮演着重要的角色。
在本学期的图论课程中，我系统地学习了图论的基本概念、算法和应用，对图论的知识有了更深入的理解和认识。
在本文中，我将对本学期学习的图论知识进行总结和归纳。
二、基本概念1. 图的定义与表示：图是由一组顶点和一组边组成的数学模型。
在图中，顶点表示图中的实体，边表示顶点之间的关系。
图可以用邻接矩阵或邻接表来表示。
2. 图的类型：图可以分为有向图和无向图、加权图和非加权图、简单图和多重图等。
有向图的边具有方向性，无向图的边没有方向性。
加权图的边带有权重，非加权图的边没有权重。
简单图没有自环和平行边，多重图可以有自环和平行边。
3. 图的基本术语：顶点的度数是指与该顶点相关联的边的数量。
入度是有向图中指向该顶点的边的数量，出度是有向图中从该顶点发出的边的数量。
路径是由边连接的一系列顶点，路径的长度是指路径上边的数量。
连通图是指从一个顶点到任意其他顶点都存在路径。
三、图的算法1. 图的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法。
DFS从一个顶点出发，探索所有可能的路径，直到无法继续深入为止。
BFS从一个顶点开始，逐层探索图中的其他顶点，直到所有顶点都被访问过为止。
2. 最短路径算法：最短路径算法用来计算图中两个顶点之间的最短路径。
迪杰斯特拉算法和弗洛伊德算法是两种常用的最短路径算法。
迪杰斯特拉算法适用于没有负权边的图，通过每次选择到某个顶点的最短路径来逐步扩展最短路径树。
弗洛伊德算法适用于有负权边的图，通过每次更新两个顶点之间的最短路径来逐步求解最短路径。
3. 最小生成树算法：最小生成树算法用于找到连接图中所有顶点的最小代价树。
克鲁斯卡尔算法和普林姆算法是两种常用的最小生成树算法。
克鲁斯卡尔算法通过每次选择代价最小的边来逐步扩展最小生成树。
电⼦科技⼤学《图论及其应⽤》复习总结--第四章欧拉图与哈密尔顿图第四章欧拉图与哈密尔顿图(⼀)、欧拉图及其性质(1)、问题背景---欧拉与哥尼斯堡七桥问题问题：对于图G，它在什么条件下满⾜从某点出发，经过每条边⼀次且仅⼀次，可以回到出发点？注：⼀笔画----中国古⽼的民间游戏（存在欧拉迹）要求：对于⼀个图G, 笔不离纸, ⼀笔画成.拓展：三笔画：在原图上添加三笔，可使其变为欧拉图。
定义1 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。
欧拉闭迹⼜称为欧拉环游，或欧拉回路。
定理1 下列陈述对于⾮平凡连通图G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数；(3) G的边集合能划分为圈。
推论1 连通图G是欧拉图当且仅当G的顶点度数为偶。
推论2 连通⾮欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。
证明：若G和H是欧拉图，则G×H是欧拉图。
若G是⾮平凡的欧拉图，则G的每个块也是欧拉图。
(⼆)、Fleury算法(欧拉图中求出⼀条具体欧拉环游的⽅法)⽅法是尽可能避割边⾏⾛(三)、中国邮路问题（最优欧拉环游，管梅⾕）定理2 若W是包含图G的每条边⾄少⼀次的闭途径，则W具有最⼩权值当且仅当下列两个条件被满⾜：(1) G的每条边在W中最多重复⼀次；(2) 对于G的每个圈上的边来说，在W中重复的边的总权值不超过该圈⾮重复边总权值。
(四)、哈密尔顿图的概念定义1 ：如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。
所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。
定义2: 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。
(五)、哈密尔顿图性质与判定1、性质定理【必要条件】；定理1 (必要条件) 若G为H图，则对V(G)的任⼀⾮空顶点⼦集S，有：w(G−S)≤|S|注：不等式为G是H图的必要条件，即不等式不满⾜时，可断定对应图是⾮H、图。
图论常考知识点总结1. 图的基本概念图是由顶点集合和边集合构成的。
顶点之间的连接称为边，边可以有方向也可以没有方向。
若图的边没有方向，则称图为无向图；若图的边有方向，则称图为有向图。
图的表示方式：邻接矩阵和邻接表。
邻接矩阵适合存储稠密图，邻接表适合存储稀疏图。
2. 图的连通性连通图：如果图中任意两点之间都存在路径，则称该图是连通图。
强连通图：有向图中，任意两个顶点之间都存在方向相同的路径，称为强连通图。
弱连通图：有向图中，去掉每条边的方向之后，所得到的无向图是连通图，称为弱连通图。
3. 图的遍历深度优先搜索（DFS）：从起始顶点出发，沿着一条路往前走，走到不能走为止，然后退回到上一个分支点，再走下一条路，直到走遍图中所有的顶点。
广度优先搜索（BFS）：从起始顶点出发，先访问它的所有邻居顶点，再按这些邻居顶点的顺序依次访问它们的邻居顶点，依次类推。
4. 最短路径狄克斯特拉算法：用于计算图中一个顶点到其他所有顶点的最短路径。
弗洛伊德算法：用于计算图中所有顶点之间的最短路径。
5. 最小生成树普里姆算法：用于计算无向图的最小生成树。
克鲁斯卡尔算法：用于计算无向图的最小生成树。
6. 拓扑排序拓扑排序用于有向无环图中对顶点进行排序，使得对每一条有向边(u,v)，满足排序后的顶点u在顶点v之前。
以上就是图论中一些常考的知识点，希望对大家的学习有所帮助。
当然，图论还有很多其他的知识点，比如欧拉图、哈密顿图、网络流等，这些内容都值得我们深入学习和探讨。
图论在实际应用中有着广泛的应用，掌握好图论知识对于提升计算机科学和工程学的技能水平有着重要的意义。
第一章：图论基本概念 1.定义
平凡图/非平凡图 简单图/复合图 空图 n 阶图 连通图/非连通图
完全图n K
12
n 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 G
v 是无环连通图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 G
G 是(n,m)连通图， 2m G n
G 是(n,m)单图，若 2n G
，则G 必定连通 G 是(n,m)单图，对应k n ，若 2
2
n k G
，则G 是k 连通
G 是(n,m)单图，若 2
n 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 ，如果 2
n
G
G 是H 图
3n 的单图G ，任意不相邻u,v 有 d u d v n G 是H 图
图G 的闭包是H 图 G 是H 图 度序列判定法：
123n d d d d ，3n ，若对任意的2
n
m
，有m d m 或n m d n m ，则G 是H 图
123n d d d d ，3n ，若对任意的2
n
m
，有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因子之和。
第六章 平面图 1.概念 平面图 图G 的面
面的边界边数 deg f 2.公式
deg 2f m
2n m 或1n m k
21
l
m n l
或36m n 3.证明
判非可平面图：用36m n 或含5K 或含3,3K 判可平面图：不含与5K 和3,3K 同胚的子图
第七章：图的着色
一、边着色（边集合划分，解决配对问题）
1.偶图的边色数
2.一般图（单图）的边色数 G 或 1G
3.三类特殊简单图边色数： G 是单图，G 中只有一个最大度或有两个最大度相邻，则 G
G ，若21n k 且m k ，则 1G
G 奇数阶 正则单图，则 1G
二、点着色（点集合划分，解决冲突问题） 1. 任意图G ，1 点着色算法（兀{}，C{}, C-C{}） 2. G 是简单连通图，既不含奇圈也不是完全图，则 3. G 是非空简单图，则21 4. G 中最大度点互不邻接，则 三、色多项式 1.递推计数法
k k k P G P G e P G e
2.理想子图计数法
,m h G x h H x 1
,n
i i i h H x r x
i i r N G 11i x k k k i
第九章：有向图 1.定义
有向图，平行边
出度 d v ，入度 d v 有向图的邻接矩阵和关联矩阵 弱连通 单向连通 强连通
解决图的分配问题：排课表等偶图边划分解决冲突问题：时间冲突
单向连通分支，强连通分支 2.公式
d v d v d v
d v d v m D。
