下载文档原格式
图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。
注意：元素可以重复出现的集合称作多重集合。
某元素重复出现的次数称作该元素的重复度。
例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。
从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。
1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。
通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。
与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。
通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。
⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。
（2）顶点数称作图的阶，n个顶点的图称作n阶图。
（3）⼀条边也没有的图称作零图，n阶零图记作N n。
1阶零图N1称作平凡图。
平凡图只有⼀个顶点，没有边。
（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。
（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。
（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。
（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。
有向图的名词解释一、有向图的名词解释有向图是指把由几个点及其连线所构成的一种有序图形称为有向图。
有向图按其点和连线所经过的路径，分为点有向图和连通有向图；按照顶点和边的关系，可以分为单向有向图和无向有向图；按照边与顶点的数目，又可分为简单有向图和非简单有向图。
在实际应用中，若不要求一定给出有向图的具体表示方法，常采用以下命名方式。
将点和边的集合记作(1)将点和边的连接记作(2)( 3)。
例如用一个有向边围成的空间，称为一个n边有向图(n≥0)。
例如将由n个点所组成的有向图记作x0-1，也就是说x0-1是由一个顶点x的集合点(x∈{(0， 1)，(0， 2)}， n≥0)所组成的有向图。
例如在有向图中，每个顶点只出现一次，故有向图又叫一次图。
有向图是一类重要的图，例如电路网络图、运输线路图等都是有向图。
这类图具有层次清楚、网络结构简单、便于计算等优点。
有向图具有以下两个基本性质：(1)同度线必互相平行，或者至少平行的那条边平行。
(2)如果两条边不平行，则从一条边出发的直线必能到达另一条边，反之亦然。
有向图是由一些不同特征的有向子图构成的，每一个有向子图对应着一类特殊的有向图。
如在图论中可用x0-1表示x0图，也就是说， x0-1图有唯一确定的开始和结束，但没有开始和结束的图。
有向图可分为有向可连通图和有向不可连通图。
无向图就是这样的有向图。
有向图在图论中有广泛的应用。
这类图可由矩阵构成。
每一个n×n的矩阵都叫做一个n阶有向图，记作y。
因此，有向图是非空的当且仅当它的非空子集是无向图。
一个有向图x的子集f的任何一点p有且仅有一条路径不经过其余点而到达该点，即有向图x的每一点都至多有一条路径。
图的强连通性(strong connectivity)定义为存在两个不同图x与y有着不同度数的边集合，使得对任意两个点p，存在一条不同路径从p到y的p而又到x的一个点的集合。
(1)在无向图上，如果每个顶点被有向边(有向边)环绕的数目都是固定的，那么，该无向图就是简单有向图。
有向图与无向图的性质与算法1. 引言在图论中，有向图和无向图是两种最基本的图模型。
它们在表达和解决各类实际问题时具有重要的应用价值。
本文将介绍有向图和无向图的性质以及相关算法，以便读者对其有更深入的理解。
2. 有向图的性质有向图是由一系列顶点和有方向的边组成的图模型。
以下是有向图的几个重要性质：2.1 有向边的方向性与无向图不同，有向图中的边是有方向的，它们从一个顶点指向另一个顶点。
这种方向性在描述一些实际问题时非常有用，比如描述物流运输的路径。
2.2 顶点的入度和出度有向图中的每个顶点都有一个入度和一个出度。
顶点的入度是指指向该顶点的边的数量，而出度是指从该顶点出发的边的数量。
通过计算入度和出度，我们可以了解顶点在图中的连接情况。
2.3 有向环和拓扑排序有向图中存在一个重要的概念，即有向环。
有向环是指从一个顶点出发，经过若干个有向边后又回到该顶点的路径。
有向环在一些问题的分析和解决中具有特殊意义。
而拓扑排序是一种常用的对有向无环图进行排序的方法，它可以按照顶点之间的依赖关系进行排序。
3. 无向图的性质无向图是由一系列顶点和无方向的边组成的图模型。
以下是无向图的几个重要性质：3.1 无向边的无方向性与有向图不同，无向图中的边是无方向的，它们连接着两个顶点，代表了两个顶点之间的关系。
无向图可以用来表示一些没有方向性的问题，比如社交网络中的好友关系。
3.2 顶点的度数无向图中的顶点的度数是指与该顶点相连的边的数量。
顶点的度数越高，说明该顶点在图中的重要性越高，具有更多的连接关系。
3.3 联通性和连通分量无向图中有一个关键性质，即联通性。
若两个顶点之间存在一条连接它们的路径，则称这两个顶点是连通的。
连通分量则是将图中所有连通的顶点分为若干个集合，每个集合内的顶点都是连通的。
4. 算法与应用4.1 有向图的最短路径算法有向图中的最短路径算法是指寻找从一个顶点到另一个顶点的最短路径的方法。
其中，Dijkstra算法和Bellman-Ford算法是常用的有向图最短路径算法。
离散数学有向图的路径表示方法有向图是离散数学中的一个重要概念，它由一组顶点和一组有向边组成。
在有向图中，每条边都有一个方向，表示从一个顶点指向另一个顶点。
有向图可以用于表示不同实际问题中的关系和流程，因此了解有向图的路径表示方法对于解决问题至关重要。
在离散数学中，有向图的路径表示方法有多种，以下将介绍三种常见的方法，分别是邻接矩阵表示法、邻接表表示法和关联矩阵表示法。
1. 邻接矩阵表示法：邻接矩阵是一个二维矩阵，用于表示有向图中各顶点之间的关系。
矩阵的行和列代表图中的顶点，矩阵中的元素表示对应顶点之间是否存在直接连接的边。
如果两个顶点之间存在边，则对应的矩阵元素为1；如果两个顶点之间不存在边，则对应的矩阵元素为0。
例如，对于一个有向图G，如果存在一条从顶点A到顶点B的边，则在邻接矩阵中的第A行第B列的元素为1。
邻接矩阵表示法可以通过矩阵的行、列索引来表示有向图中的路径，路径上的顺序即为顶点在矩阵中的索引顺序。
2. 邻接表表示法：邻接表是一种更加紧凑的表示有向图的方法。
它由一个顶点数组和一个边链表组成。
顶点数组中的每个元素表示图中的一个顶点，边链表中的每个节点表示从该顶点出发的边。
邻接表使用链表的方式记录每个顶点所连接的边，其中链表的节点保存了边的终点以及指向下一条边的指针。
在邻接表表示法中，可以通过遍历链表来获取某个顶点的所有直接连接的顶点，从而表示有向图中的路径。
遍历链表的顺序即为顶点与顶点之间路径的顺序。
3. 关联矩阵表示法：关联矩阵是一个二维矩阵，用于表示有向图中顶点和边之间的关系。
矩阵的行代表顶点，矩阵的列代表边，矩阵中的元素表示对应顶点与边之间的连接关系。
关联矩阵表示法可以将有向图中的路径转化为矩阵中的非零元素组成的向量。
矩阵中的每一列表示一条边，矩阵中的每一行表示一个顶点。
如果某个顶点在路径上通过某条边，则对应的矩阵元素为-1；如果某个顶点是路径的起点，则对应的矩阵元素为1；如果某个顶点是路径的终点，则对应的矩阵元素为-1。
有向图（4.dijkstra算法详解）在图的应⽤中，有⼀个很重要的需求：我们需要知道从某⼀个点开始，到其他所有点的最短路径。
这其中，Dijkstra算法是典型的最短路径算法。
它的关键思想是以起始点为中⼼，向外⼀层层扩散，直到扩展到终点为⽌。
Dijkstra算法能够得出最短路径的最优解，不过它需要遍历计算的节点相当多，所以效率不⾼。
⾸先，⽤最通俗的语⾔解释。
假定有3个顶点，A、B、C，如图：要求A到其余各点的最短路径。
很明显，A到C⽐A到B更短。
有疑惑的是从A->B的最短距离，要么是直接A->B的边，要么是A经过C到B的边更短。
我们⾸先找到最短的边（A->C),然后在此基础上扩展，于其余边去对⽐找到最⼩值。
顶点再进⼀步扩充增加，按照这个思想，我们总可以找到A到所有点的最短路径。
算法描述：从节点1开始到其余各点的dijkstra算法，其中Wa->b表⽰边a->b的权，d(i)即为最短路径值，顶点集合为V={1,2,3...n}1.置集合S={1}，置顶点集合U={2,3,4...n}，数组d(1)=0,d(i)=W1->i（1，i之间存在边）or ⽆穷⼤（1，i之间不存在边）；2.在U中，令d(j)=min{d(i),i属于U}，将j从U中移⾄S中，若U为空集则算法结束，否则转3；3.对全部i属于U，如果存在边j->i,那么置d(i)=min{d(i), d(j) + Wj->i},转2Dijkstra算法的思想为;设G=(V, E)是⼀个带权有向图，把图中顶点集合V分为两部分，第⼀组为已求出最短路径的顶点集合（⽤S表⽰，初始时S中只有源点，以后每求出⼀条最短路径，就将顶点加⼊到S中，直到所有顶点都加⼊到S中，算法结束），第⼆组为其余未求出最短路径的顶点集合（⽤U表⽰），按最短路径的长度次序依次将第⼆组中的顶点加⼊到第⼀组中。
在加⼊过程中，总保持着从源点v到S中各顶点的最短路径不⼤于从源点v到U中各顶点的最短路径长度。
第7章：有向图很多应用问题涉及有向图。
有向图除了有与（无向）图类似的性质之外，还有一些在图中所不具备的特殊性质。
本章除介绍有向图的基本概念外，着重介绍有向树、有向网络及其应用等问题。
§7.1有向图概述1. 基本概念定义7.1 一个有向图D 是指一个序偶><E V ，，其中V 是一个非空集合，称为D 的点集，其中的元称为D 的顶点。
E 是笛卡儿集V V ⨯的某个多重子集，称为D 的边集，其中的每一个元素均是序偶><v u ，，称为有向边，而u 称为边的始点，v 称为边的终点。
通常记>=<E V D ，，)(D V V =，)(D E E =。
从有向图的定义来看，它与上一章定义的（无向）图是相似的，最关键的区别在于有向边是有方向的，而（无向）边是无方向的。
在（无向）图中， )(v u ，和)(u v ，表示同一条边（不考虑多重边情况），但在有向图中，><v u ，和><u v ，表示的却是两个不同的边，称为对称边，虽然这两条边的端点一样。
对无向图G 的每条无向边指定一个方向，由此得到的有向图D ，称为G 的定向图。
反之，如果把一个有向图D 的每条有向边的方向去掉，由此而得到的无向图G ，称为D 的底图。
把一个有向图D 的每一条有向边反向，由此而得到的有向图称为D 的逆图，记为D ~在有向图中，两个顶点之间若有两条或两条以上的边，并且方向相同，则称为平行边，它强调了边的方向性。
有向图中的其它一些概念，像重数、圈、带圈图、无圈图、多重图、简单图、)(q p ，图、图的阶、平凡图、零图、有限图、无限图、赋权图、邻接、关联、孤立点、孤立边等等，都与（无向）图中相应概念的定义一样，这里不再重复。
在有向图中有如下的度数定义。
定义7.2 设>=<E V D ，是有向图， V v ∈，E 中以v 为起始点的有向边的个数称为v 的出度，记作)(v d +；E 忠以v 为终点的有向边的个数称为v 的入度，记作)(v d -。
一、无向图：方法1：∙如果存在回路，则必存在一个子图，是一个环路。
环路中所有顶点的度>=2。
∙ n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。
第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点，则存在环，否则没有环。
∙ n算法分析：由于有m条边，n个顶点。
i)如果m>=n，则根据图论知识可直接判断存在环路。
（证明：如果没有环路，则该图必然是k棵树k>=1。
根据树的性质，边的数目m = n-k。
k>=1，所以：m<n）ii)如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。
这两种操作的总数不会超过m+n。
由于m<n，所以算法复杂度为O(n)。
∙注：该方法，算法复杂度不止O(V)，首先初始时刻统计所有顶点的度的时候，复杂度为(V + E)，即使在后来的循环中E>=V，这样算法的复杂度也只能为O(V + E)。
其次，在每次循环时，删除度为1的顶点，那么就必须将与这个顶点相连的点的度减一，并且执行delete node from list[list[node]]，这里查找的复杂度为list[list[node]]的长度，只有这样才能保证当degree[i]=1时，list[i]里面只有一个点。
这样最差的复杂度就为O(EV)了。
方法2：DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。
该算法的复杂度为O(V)。
方法3：摘自：/lzrzhao/archive/2008/03/13/2175787.aspx PS：此方法于2011-6-12补充假定：图顶点个数为M，边条数为E遍历一遍，判断图分为几部分（假定为P部分，即图有P 个连通分量）对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1只要有一个满足边数> 结点数－1原图就有环将P个连通分量的不等式相加，就得到：P1:E1=M1-1P2:E2=M2-1...PN:EN>MN-1所有边数(E) > 所有结点数(M) - 连通分量个数(P)即： E + P > M 所以只要判断结果 E + P > M 就表示原图有环，否则无环.实例代码如下：1.#include<iostream>2.#include<malloc.h>ing namespace std;4.#define maxNum 100 //定义邻接举证的最大定点数5.int visited[maxNum];//通过visited数组来标记这个顶点是否被访问过，0表示未被访问，1表示被访问6.int DFS_Count;//连通部件个数，用于测试无向图是否连通，DFS_Count=1表示只有一个连通部件，所以整个无向图是连通的7.int pre[maxNum];8.int post[maxNum];9.int point;//pre和post的值10.11.//图的邻接矩阵表示结构12.typedef struct13.{14.char v[maxNum];//图的顶点信息15.int e[maxNum][maxNum];//图的顶点信息16.int vNum;//顶点个数17.int eNum;//边的个数18.}graph;19.void createGraph(graph *g);//创建图g20.void DFS(graph *g);//深度优先遍历图g21.void dfs(graph *g,int i);//从顶点i开始深度优先遍历与其相邻的点22.void dfs(graph *g,int i)23.{24.//cout<<"顶点"<<g->v[i]<<"已经被访问"<<endl;25. cout<<"顶点"<<i<<"已经被访问"<<endl;26. visited[i]=1;//标记顶点i被访问27. pre[i]=++point;28.for(int j=1;j<=g->vNum;j++)29. {30.if(g->e[i][j]!=0&&visited[j]==0)31. dfs(g,j);32. }33. post[i]=++point;34.}35.36.void DFS(graph *g)37.{38.int i;39.//初始化visited数组，表示一开始所有顶点都未被访问过40.for(i=1;i<=g->vNum;i++)41. {42. visited[i]=0;43. pre[i]=0;44. post[i]=0;45. }46.//初始化pre和post47. point=0;48.//初始化连通部件数为049. DFS_Count=0;50.//深度优先搜索51.for(i=1;i<=g->vNum;i++)52. {53.if(visited[i]==0)//如果这个顶点为被访问过，则从i顶点出发进行深度优先遍历54. {55. DFS_Count++;//统计调用void dfs(graph *g,int i);的次数56. dfs(g,i);57. }58. }59.}60.void createGraph(graph *g)//创建图g61.{62. cout<<"正在创建无向图..."<<endl;63. cout<<"请输入顶点个数vNum:";64. cin>>g->vNum;65. cout<<"请输入边的个数eNum:";66. cin>>g->eNum;67.int i,j;68.//输入顶点信息69.//cout<<"请输入顶点信息："<<endl;70.//for(i=0;i<g->vNum;i++)71.// cin>>g->v[i];72.//初始画图g73.for(i=1;i<=g->vNum;i++)74.for(j=1;j<=g->vNum;j++)75. g->e[i][j]=0;76.//输入边的情况77. cout<<"请输入边的头和尾"<<endl;78.for(int k=0;k<g->eNum;k++)79. {80. cin>>i>>j;81. g->e[i][j]=1;82. g->e[j][i]=1;//无向图对称83. }84.}85.int main()86.{87. graph *g;88. g=(graph*)malloc(sizeof(graph));89. createGraph(g);//创建图g90. DFS(g);//深度优先遍历91.//连通部件数，用于判断是否连通图92. cout<<"连通部件数量：";93. cout<<DFS_Count<<endl;94.if(DFS_Count==1)95. cout<<"图g是连通图"<<endl;96.else if(DFS_Count>1)97. cout<<"图g不是连通图"<<endl;98.//各顶点的pre和post值99.for(int i=1;i<=g->vNum;i++)100. cout<<"顶点"<<i<<"的pre和post分别为："<<pre[i]<<" "<<post[i]<<endl;101.//cout<<endl;102.//判断无向图中是否有环103.if(g->eNum+DFS_Count>g->vNum)104. cout<<"图g中存在环"<<endl;105.else106. cout<<"图g中不存在环"<<endl;107.int k;108. cin>>k;109.return 0;110.}111./*112.输入：113.正在创建无向图...114.请输入顶点个数vNum:10115.请输入边的个数eNum:9116.请输入边的头和尾117.1 2118.1 4119.2 5120.2 6121.4 7122.5 9123.6 3124.7 8125.9 10126.*/注意：有向图不能使用此方法。
