下载文档原格式
1.1、prim算法:无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。
如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。
【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。
【最小生成树算法实例】现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。
在分析了这张图后发现，任一对城市都是连通的。
现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。
【输出】连通所有城市的公路最小造价。
【输入样例】6 101 2 101 5 191 6 212 3 52 4 62 6 113 4 64 5 184 6 145 6 33【输出样例】50 原图最小生成树#include<cstdio>#include<string>#include<cstring>#include<climits>using namespace std;int i,j,k,n,m,mi,t,s,a[1000][1000]; void prim(){int mi,p,f,k,d[1000];bool v[1000];memset(v,false,sizeof(v));f=1;for (i=2;i<=n;i++){d[i]=INT_MAX;}d[f]=0;s=0;for(i=1;i<=n;i++){mi=INT_MAX;for (j=1;j<=n;j++)if ((v[j]==false) && (d[j]<mi)){p=j;mi=d[j];}s+=mi;v[p]=true;for(j=1;j<=n;j++){if (a[p][j]<d[j]) d[j]=a[p][j];}}}int main(){memset(a,0,sizeof(a));scanf("%d%d",&n,&m);mi=INT_MAX;for (i=1;i<=n;i++){for (j=1;j<=n;j++){a[i][j]=INT_MAX;}}for (i=1;i<=m;i++){scanf("%d%d%d",&k,&j,&t);if ((t<a[k][j])||(t<a[j][k])){a[k][j]=t;a[j][k]=a[k][j];}}prim();printf("%d",s);return 0;}1.2、克鲁斯卡尔算法假设N=(V,{E})是连通网，将N中的边按权值从小到大的顺序排列；①、将n个顶点看成n个集合；②、按权值小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。
习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。
若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。
若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。
2. 若存在孤立点，则m 不超过K n-1的边数, 故 m <= (n-1)(n-2)/2, 与题设矛盾。
3.4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3.以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。
这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条：5. 可以。
7. 同构。
同构的双射如下：8. 记e 1= (v 1,v 2), e 2= ( v 1,v 4), e 3= (v 3,v 1), e 4= (v 2,v 5), e 5= (v 6,v 3), e 6= (v 6,v 4), e 7= (v 5,v 3), e 8= (v 3,v 4), e 9 = (v 6,v 1), 则邻接矩阵为： 关联矩阵为：∑∑∑∑∑∑∑==+====-=++=-==---=--=ni i n i i n i n i n i ni i i n i i n i i i i a a n n a a a n n n a n a v v 1111121212/)1()1(2)1(])1[(。
， 所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－22 222 i i C a a ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡---------100110000001001000010100010011010100000001001100000111, 001101000100000000001001010000001010⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 )( 4, 1, 3 )边列表为：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1). 正向表为：A= (1,3,4,6,6,7,10), B= (2,4,5,1,4,3,3,4,1).习题二1. 用数学归纳法。
C++知识点图论（树）⼀：图论的概念图是表⽰物件与物件之间的关系的数学对象，是图论的基本研究对象。
图和以前所学的变量数组栈这类的东西最⼤的不同就是直观，通过⼀个图就可以说明⼏⼗⾏表达式所要表⽰的关系。
最基本的图由点和线构成，⼀个个离散的点代表着研究的对象，它们被称之为结点，⽽把它们串联起来的这些线我们称之为边。
图能够表达晦涩难懂的⽂字，⽤图解题会更为好懂。
图还分为有向图⽆向图之类的，下⽂看题会有涉及。
⼆：图论能⼲的事图论最⼤的作⽤就是搜索，包括BFS和DFS，这叫做图遍历。
⼴搜和深搜是⽤于在图中搜索节点的两种不同算法。
它们通常⽤于确定我们是否可以从给定节点到达某个节点。
BFS的⽬的是尽可能接近根节点遍历图，⽽DFS算法旨在尽可能远离根节点。
最基本的题型精简⼀下就是下边这样从A到B的最短途径是什么？分别从距离和时间⾓度考虑。
有没有办法从C到D？典型的搜索本⼦题叭（以下⼲货时间）三：图论中常⽤的知识点（性质）①连通性任何两个顶点之间都可以通过⼀条路连接，这样的图称为连通的。
相反称为不连通的。
这就像只考虑铁路运输的时候，亚欧⼤陆显然是⼀个连通图（内陆岛屿不算！），⽽由于海洋的存在，它跟美洲⼤陆就挨不到⼀起，他俩放在⼀起就不是⼀个连通的图。
②树树⽐图论学的早真是令⼈匪夷所思，树作为图的⼀种，在代码领域运⽤极其⼴泛。
⼀棵树主要由爸爸和⼉⼦构成...哦不说错了，是⼦节点和⽗节点每个结点有零个或多个⼦结点；没有⽗结点的结点称为根结点；每⼀个⾮根结点有且只有⼀个⽗结点；除了根结点外，每个⼦结点可以分为多个不相交的⼦树这货真画出来根本不像棵树...你要把它倒过来看才能发现被称作树的真谛树⾥⾯最为常⽤的⼀棵（⼀种）就是⼆叉树，主要是因为所有的树经过改造都能变成它...它也因为所解决的问题不同被赋予了不同的名称空⼆叉树//只有⼀个根结点的⼆叉树//只有左⼦树//只有右⼦树//完全⼆叉树对于完全⼆叉树的问题则极为重要，因为它代表着完成⼀个计划的所有情况，搜索和DP往往就在完全⼆叉树中进⾏深度则指的是⼆叉树的⾼度，也就是所谓的家⾥⼏代⼈⽽普通树转⼆叉树，⼀般采⽤左“⼦⼥”右“兄弟”的⽅式来转化，⼀步⼀步对应⾛便可以得到需要的⼆叉树。
第八章独立集和团§8.1 独立集°独立集：设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则称S为G的一个独立集。
°最大独立集：G的一个独立集S称为G的最大独立集，是说：G不包含适合S′>S的独立集S′。
°例子：(见图8.1)°覆盖：G的一个覆盖是指V的子集K，使得G的每条边都至少有一个端点属于K。
°例子：在图8.1中，两个独立集都是覆盖的补集。
定理8.1：设S⊆V，则S是G的独立集当且仅当V\S是G的覆盖。
证：按定义，S是G的独立集当且仅当G中每条边的两个端点都不同时属于S，即当且仅当G的每条边至少有一个端点属于V\S，亦即当且仅当V\S是G的覆盖。
∎°独立数：G的最大独立集的顶点数称为G的独立数，记为α(G)。
°覆盖数：G的最小覆盖的顶点数称为G的覆盖数，记为β(G)。
推论8.1：α+β=υ。
证：设S是G的一个最大独立集，K是G的一个最小覆盖。
由定理8.1，V\K是独立集，而V\S是覆盖。
因此υ−β=V\K≤α (8.1)υ−α=V\S≥β (8.2)结合8.1式和(8.2)式，即得α+β=υ。
∎°边覆盖：G的一个边覆盖是指E的一个子集L，使得G的每个顶点都是L中某条边的端点。
°边独立集：即对集。
*注意：边覆盖并不总是存在的，G有边覆盖，当且仅当δ>0。
°边独立数和边覆盖数：最大对集的边数称为边独立数，记作α′G;最小边覆盖的边数称为边覆盖数，记作β′(G)。
*注意：对集的补集不一定是边覆盖，边覆盖的补集也不一定是对集。
定理8.2 (Gallai)：若δ>0,则α′+β′=υ。
证：设M是G的一个最大对集，U是M非饱和顶点集。
由于δ>0且M是最大对集，所以存在|U|条边的一个集E′，它的每条边都和U 的每个顶点相关联。
显然，M∪E′是G的边覆盖，因而β′≤M∪E′=α′+υ−2α′=υ−α′即α′+β′≤υ (8.3)再设L是G的一个最小边覆盖，置H=G[L]，并且设M是H的一个最大对集。
二、应用题题0：（1996年全国数学联赛）有n（n≥6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。
证明这n个人中必有3个人互相认识。
注：[n/2]表示不超过n/2的最大整数。
证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。
由条件可知，G是具有n个顶点的简单图，并且有（1）对每个顶点x，)(xN G≥[n/2]；（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。
需要证明G中有三个顶点两两相邻。
反证，若G中不存在三个两两相邻的顶点。
在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。
情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。
情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。
若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。
故k ≠r+1，同理t ≠r+1。
所以t=r,k=r 。
记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。
若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。
图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。
答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。
答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。
答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。
答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。
答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。
答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。
2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。
四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。
答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。
《 离散数学 》同步测试卷10:图的基本概念一．填空：1．一个无向图表示为G=<V , E>，其中V 是 结点 的集合，E 是 边 的集合， 并且要求E 中的任何一条边必须和G 中的两个结点 相关联 。
2．设无向图G 中有12条边，已知G 中度为3的结点有6个，其余的结点度均 小于3，则G 中至少有 9 个结点。
3．设G=(n,m)是简单图，v 是G 中一个度为k 的结点，e 是G 中的一条边，则G – v 中有1n -个结点，m k -条边；G – e 中有n 个结点，1m -条边。
4．设G 是个有向图，当且仅当G 中有一条经过每一个结点的路径时，G 才是 单向 连通图。
5．设图G=<V , E>，则：若E 中的每条边都是_无向边 _，则称图G 为无向图；若E 中的每条边都是_有向边__，则称图G 为有向图。
6．设图G 中 无自环 和 无平行边 ，则称图G 为简单图。
7．设G 是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2，有6条边。
则G 中共有_ 4 个结点。
因此，G 是个多重边_图。
8．一个无向图G 有16条边，若G 中每一个结点的度均为2，则G 有16个结点。
9．设G 是个具有5个结点的简单无向完全图，则G 有__10_条边。
10．设G 是个具有5个结点的简单有向完全图，则G 有_20_条边。
11．设G 是个n 阶简单有向图，G '是G 的子图，已知G '的边数()1E n n '=-，则G 的边数m 为()1n n -。
12．35条边，每个结点的度数至少是3的图最多有__23_个结点。
13、3个结点可构成 4 个不同构的简单无向图，可构成 16 个不同构的简单有向图。
14、设()100,100G =为无向连通图，则从G 中能找到 1 条回路15、5K 的点连通度为 4 ，边连通度为 4 。
16、设图G=<V , E>，{}1234,,,V v v v v =，若G 的邻接矩阵0101101111001000A ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭，则 ()1deg v -= 3 ，()4deg v += 1 ，，从2v 到4v 长度为2的通路有 1 条。
基本知识点：一、图的基本定义：平凡图：只有一个顶点无边的图。
非平凡图：其他所有图。
空图：边集合为空的图。
简单图：既没有环也没有重边的图。
复合图：其他所有的图。
同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。
标定图：给图的点和边标上符号。
非标定图：不标号。
非标定图代表一类相互同构的图。
完全图：每两个不同顶点之间都有一条边相连的简单图。
N 个顶点的完全图只有一个，记为n K 。
偶图（二部图）：具有二分类(,)X Y 的图，他的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。
完全偶图 ：指具有二分类(,)X Y 的简单偶图，其中X 的每个顶点与Y 的每个顶点相连。
若,X m Y n ==，则这样额完全偶图记为：,m n K 。
k —正则图：设(,)G V E =为简单图，如果对所有的结点v V ∈，有()d v k =，称G 为k —正则图。
完全图和完全偶图,n n K 均是正则图。
图划分：若一个n 阶简单图G 各点的度为i d ，则分正整数k 为n 个部分的划分i d ∑称为是图划分。
子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。
生成子图：点集合相等，边集合为原图子集的图。
导出子图：由顶点集为原图G 真子集的所有点，及两端点均在该集合中的边的全体组成的子图V ‘。
'[]G V 和G v -。
边导出子图：由原图G 边的真子集，该图中边的断点全体为顶点组成的子图E ‘。
'[]G E 和{}G e -。
图的运算：并，交，差，对称差，联图，积图，合成图，极图路与图的联通性：途径：迹：边互不相同的途径。
路：边和点都互不相同的途径。
连通的：两个顶点之间存在路。
连通图：每一对顶点之间都有一条路。
连通分支：将V 划分为一些等价类12,,...k V V V 。
两个顶点u 和v 是连通的当且仅当他们属于同一个子集i V ，称子图()i G V 为连通分支。
图论第二章和第四章书后练习题2.2 给出满足下列条件的图或说明这样的图为什么不存在 (a)没有奇点的图。
(b)所有顶点的度为三的图。
(c)阶至少为5的图G ,且对于G 中任意两个邻接的顶点,,v u 均有u deg v deg ≠。
(d)阶至少为5的非完全图H ,且对于H 中任意两个不邻接的顶点,,v u 均有u deg v deg ≠。
解：（a ）（b ）(c)(d)2.4 给出一个阶为6且边数为10的图G ,满足.4)(,3)(=∆=G G δ 解：所求图如下所示：2.6 在一个阶为)1(3≥n n 的图中，若度为n n ,1-和1+n 的顶点数个数均为n ，则n 必为偶数。
证：∵n-1+n+n+1=3n;∴图中仅有度为n+1,n,n-1三种度的顶点∑deg(v)=(n-1)n+n*n+(n+1)n=3n2由图论第一定理知，3n 2为偶数 则n 为偶数。
2.8 设G 为n 阶图，若对G 中任意三个互不邻接的顶点v u ,和w ，都有u deg ,1deg deg -≥++n w v 则G 一定是连通的吗？解：不一定，如下图：2.10 我们已经知道，若n 阶图G 的任意两个不邻接的顶点u 和v 都满足,2deg deg -≥+n v u 则G 可能不连通。
(a) 证明：存在n 阶的连通图G ，它满足：对G 中两个任意不邻接的顶点u 和v ，都有,2deg deg -≥+n v u 且G 有两个不邻接的顶点x 和y ，使得y x deg deg +=2n -。
(b) 证明：若n 阶图G 的任意两个不邻接的顶点u 和v 都满足,2deg deg -≥+n v u 则G 至多有两个连通分支。
(c) (b)中的界是紧的吗？（a ）证：假设deg deg 1u v n +≤-，则由定理4可知G 不是联通的，这与已知矛盾。
∴原结论正确。
（b ）证：假设存在G1，G2,G3 三个连通分支，其阶数分别为n1,n2,n3,且n1+n2+n3≤n;取u ∈G1 v ∈G212123()()()()1123G G G G d u d v d U d v n n n n n +=+≤-+-≤--≤- 矛盾！∴至多有两个连通分支 (c)是的2.12证明：若n 阶图G 满足1)()(-≥+∆n G G δ，则G 是连通的，且4)(≤G diam 。
图论复习题1、 (D)。
将有向图D 各有向边的箭头都去掉，所得图G 为无向图，称为D 的 （ ）。
A 、图 B 、零图 C 、补图 D 、基图2、 (C)。
简单图为 。
A 、不含平行边B 、不含环C 、即不含平行边也不含环D 、没有要求3、 (D)。
无向图的回路包括 。
A 、简单回路B 、初级回路C 、复杂回路D 、简单回路、初级回路和复杂回路4、 (D)。
E ,V D =为无环有向图，[]m n ij m ⨯为D 的关联矩阵，1m ij =则 。
A 、i v 是j e 的终点 B 、i v 与j e 不关联 C 、i v 与j e 关联 D 、i v 是j e 的始点5、 (A)。
图的同构关系是 。
A 、等价关系B 、偏序关系C 、空关系D 、良序关系6、 (C)。
4K 的所有非同构的子图中，有 个生成子图。
A 、8 B 、10 C 、11 D 、127、 (A)。
下列能成为图的度数序列的为 。
A 、（5，2，3，1，4）B 、（3，3，2，3）C 、（3，1，2，1）D 、（1，1，1，1，1）本体错误8、 (D)。
3个顶点2条边的所有可能非同构的有向简单图共有 个图。
A 、1B 、2C 、3D 、49、 (C)。
G 为无向图，V '称为G 的一个点割集，若V '含有 个顶点，则v 叫割点。
A 、0B 、2C 、1D 、310、 (A)。
多重图为 。
A 、含平行边B 、不含环C 、即不含平行边也不含环D 、没有要求11、 (D)。
无向图的通路包括 。
A 、简单通路B 、初级通路C 、复杂通路D 、简单通路、初级通路和复杂通路12、 (B)。
一连通的平面图，8个顶点4个面，则边数为 。
A 、9B 、10C 、11D 、1213、(C)。
G 为无向图，E '称为G 的一个边割集，若E '含有 条边，则e 叫桥。
A 、0 B 、2 C 、1 D 、314、 (D)。
《 离散数学 》同步测试卷10:图的基本概念一．填空：1．一个无向图表示为G=<V , E>，其中V 是 结点 的集合，E 是 边 的集合， 并且要求E 中的任何一条边必须和G 中的两个结点 相关联 。
2．设无向图G 中有12条边，已知G 中度为3的结点有6个，其余的结点度均 小于3，则G 中至少有 9 个结点。
3．设G=(n,m)是简单图，v 是G 中一个度为k 的结点，e 是G 中的一条边，则G – v 中有1n -个结点，m k -条边；G – e 中有n 个结点，1m -条边。
4．设G 是个有向图，当且仅当G 中有一条经过每一个结点的路径时，G 才是 单向 连通图。
5．设图G=<V , E>，则：若E 中的每条边都是_无向边 _，则称图G 为无向图；若E 中的每条边都是_有向边__，则称图G 为有向图。
6．设图G 中 无自环 和 无平行边 ，则称图G 为简单图。
7．设G 是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2，有6条边。
则G 中共有_ 4 个结点。
因此，G 是个多重边_图。
8．一个无向图G 有16条边，若G 中每一个结点的度均为2，则G 有16个结点。
9．设G 是个具有5个结点的简单无向完全图，则G 有__10_条边。
10．设G 是个具有5个结点的简单有向完全图，则G 有_20_条边。
11．设G 是个n 阶简单有向图，G '是G 的子图，已知G '的边数()1E n n '=-，则G 的边数m 为()1n n -。
12．35条边，每个结点的度数至少是3的图最多有__23_个结点。
13、3个结点可构成 4 个不同构的简单无向图，可构成 16 个不同构的简单有向图。
14、设()100,100G =为无向连通图，则从G 中能找到 1 条回路15、5K 的点连通度为 4 ，边连通度为 4 。
16、设图G=<V , E>，{}1234,,,V v v v v =，若G 的邻接矩阵0101101111001000A ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭，则 ()1deg v -= 3 ，()4deg v += 1 ，，从2v 到4v 长度为2的通路有 1 条。
