图结构 - 简书
一、关于图
1.图是什么
图是四类基本逻辑结构集合、线性结构、树形结构和图结构里面的其中一种，即图结构，图结构也是其中最为复杂的结构。在图的结构中，任意两个结点之间都可能相关，即结点之间的邻接关系是任意的。而在树形结构中，结点之间具有层次关系，每一层结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。图的结构可以描述多种复杂的数据对象，应用较为广泛。
2.图用来干什么
在现实生活中有很多实际问题可以用图的结构表示，进而可用计算机加以处理。如下是现实生活中几个常见的需求：
在N个城市间建立通信网络，使得其中的任意两个城市之间有直接或间接的通信线路，假设已知每两个城市之间通信线路的造价，如何设计出一个总造价最低的通讯网络？
在旅游的时候，从某地出发，要到某个目的地，如何选择路径，才能使得路程最短？如下图1-1所示，假如要从A点到G点，要怎么走才能使路径最短？
大学课程里，有些课程是基础课，它们可以独立于其他课程，即无前导课程，无先后关系；而有些课程必须在某些基础课程学完后才能开始学习，有先后关系。如何找出课程的学习流程图，以便科学合理的安排学习计划？
关于这些问题，可以用图论的方法来解决。解决这些问题首先需要弄清几个问题：
如何描述这些问题的数据？
如何在计算机中存储这些数据？
解决问题的算法是什么？
例如，问题1可以用图结构来描述通信网络，用一个小圆圈代表一个城市，用小圆圈之间的连线代表对应两个城市之间的通信线路，在连线旁边附加一个数值表示该通信线路的造价。图1-2a是一种可能的通信网络建造初步方案，优化后的方案是图1-2b。
3.图的定义和术语
有向图、无向图：图G由两个集合V和E组成，记为G=(V,E)，其中，v是顶点的有穷非空集合；E是边的集合，边是v中顶点的偶对。若顶点的偶对是有序的则称此图为有向图，有序偶对用尖括号&&括起来；反之，若顶点偶对是无序的，则称此图为无向图，无序偶对用圆括号（）括起来。
弧、弧头、弧尾：有向图的边称为弧。如下图1-3a、b所示。
权、带权图：图的边附带数值，这个数值叫权。每条边都带权的图称为带权图。
顶点的度、入度、出度：无向图中顶点v的度是与该顶点相关的边的数目。如果图是一个有向图，则把以顶点v为终点的弧的数目称为v的入度，把以顶点v为始点的弧的数目称为v的出度，入度+出度=有向图的度。
子图：设G=(V,E)是一个图，若E’是E的子集，V’是V的子集，并且E’中的边仅与V’中的顶点相关联，则图G’=(V’,E’)称为图G的子图。
路径、路径长途：无向图的路径是一个顶点到另一个顶点所经过的边，所经过的边的数目称为路径长度；有向图的路径是一个顶点到另一个顶点的弧，路径长度是路径上面弧的数目。
连同、连通图、连通分量：在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果图中的任意两个顶点vi和vj都是连通的，则称此图为连通图，如图1-4a。连通分量是无向图中的极大连通子图，如图1-4b是一个非连通图的两个连通分量。
强连通、强连通图、强连通分量：对于无向图，如果图中任意一对顶点vi和vj(i!=j)都有顶点vi到vj的路径也有vj到v?的路径，即两个顶点双向连通，那么称该有向图为强连通图。有向图的极大强连通子图称为强连通分量，如图1-5所示。
生成树、生成森林：一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。若连通图G的顶点个数为n，则G的生成树的边数为n-1。如果G的一个子图G’的边数大于n-1，则G’中一定有环。相反，如果G’的边数小于n-1，则G’一定不连通。在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树，这些连通分量的生成树组成了一个非连通图的生成森林。
二、图的存储结构
图有多种存储结构。例如，邻接矩阵、邻接表、十字链表和邻接多重表等，本文章以邻接矩阵为基础解决图的一些应用问题。
1.邻接矩阵
邻接矩阵就是用矩阵来描述图中顶点之间的关联关系，在程序设计语言中我们用二维数组来实现矩阵。设G=(V,E)是一个图，其中V={v0, v1,…, vn-1}，那么G的邻接矩阵A可定义成如下的n阶方阵：
如下图2-1a的M1和2-1b的M2分别是无向图的矩阵和有向图的矩阵。
值得注意的是无向图的邻接矩阵是一个对称矩阵，如图M1是以红色箭头为界限的对称结构。
利用邻接矩阵可以判定任意两个顶点之间是否有边，并容易求得各个顶点的度。对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的边数和。对于有向图，顶点vi的入度是邻接矩阵中第i列的边数和，出度是顶点vi所对应的行的边数和。利用这些已知条件，可以判定某个顶点是否有邻接结点。
三、图的遍历方法
图的遍历是指从图的某个顶点出发，系统地访问图的每个顶点，并且每个顶点只被访问一次。遍历图的基本方法有两种：深度优先搜索和广度优先搜索。此两种方法都适用于有向图和无向图。图的遍历操作类似于树的遍历操作。需要特别说明的是，遍历和搜索是两个不同的概念，图的遍历是访问图的每个顶点一次且仅一次，而搜索是从一个顶点出发访问到所有能访问的顶点一次且仅一次。
1.深度优先搜索
(1)基本思想
假定以图中某个顶点vi为出发点，首先访问出发点vi，然后任选一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，依次类推，直至图中所有顶点都被访问过。深度优先搜索类似于树的先序遍历，如下图所示。
搜索到达某个顶点时（图中仍有顶点未被访问），如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一个未被访问过的邻接点开始深度优先搜索。图的深度优先搜索访问具有后进先出的特征，因此在使用java语言实现的时候可以采用栈来实现。
深度优先搜索的顶点的访问序列不是唯一的。如图3-2的访问序列还可以是：广州-&深圳-&东莞-&佛山-&珠海等。
2.广度优先搜索
(1)基本思想
从图中某个顶点vi出发，在访问了vi之后依次访问vi的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。广度优先搜索类似树的按层次遍历过程。如下图所示。
若对x的访问先于y，则对x的邻接结点的访问也先于对y的邻接点的访问，也即广度优先搜索邻接点的寻找具有先进先出的特征，使用java语言实现的时候可以使用队列来实现。
和深度优先搜索一样，图的顶点访问序列不是唯一的，如图3-4的广度优先搜索的访问序列还可以是：广州-&佛山-&深圳-&东莞-&珠海等。
四、图的应用
1.最小生成树
连通图的一次遍历所经历边的集合及图中所有顶点的集合就构成该图的一棵生成树。而连通图的遍历序列并不是唯一的，所以能得到不同的生成树，这些生成树就构成了图的生成森林。图的最小生成树就是从生成森林中找出权总和最小的生成树。
注意：对于有n个顶点的无向图，所有生成树中都有且仅有n-1条边。
构造最小生成树的两种基本方法是：Prim（普里姆）算法和Kruskal（克鲁斯卡尔）。
使用图的最小生成树可以解决文章开头的在城市之间建立通讯网络问题。
(1)Prim算法
1)基本思想
假设G=(V,E)是一个带权图，生成的最小生成树为MinT=(V,T)，其中V为顶点集合，T为边的集合。求边的集合T的步骤如下：
?初始化：U={u0}，T={}。其中U为一个新设置的顶点集合，初始U中只含有顶点u0，即在构造最小生成树时从顶点u0出发；
?对所有u∈U，v∈V-U（其中u,v表示顶点）的边(u,v)中，找一条权值最小的边(u’,v’)，将这条变加入到集合T中，将顶点v’加入集合U中。在使用Java语言实现时，本文采用Map键值对存储空边和边的终点所对应的顶点。
?如果U=V，则算法结束；否则重复以上两个步骤。
2)算法执行示例图
初始状态：U={A}V={B,C,D,E,F,G}E={}
集合U和集合V相关联的顶点中权值最小的是AD，将D加入U。U={A,D} ，V={B,C,E,F,G}，E={AD}
集合U和集合V相关联的顶点中权值最小的是DF，将F加入U。{A,D,F}，V={B,C,E,G}，E={AD,DF}
集合U和集合V相关联的顶点中权值最小的是AB，将B加入U。U={A,D,F,B}，V={C,E,G}，E={AD,DF,AB}
集合U和集合V相关联的顶点中权值最小的是BE，将E加入U。U={A,D,F,B,E}，V={C,G} ，E={AD,DF,AB,BE}
集合U和集合V相关联的顶点中权值最小的是EC，将C加入U。U={A,D,F,B,E,C}，V={G} ，E={AD,DF,AB,BE,EC}
集合U和集合V相关联的顶点中权值最小的是EG，将G加入U。U={A,D,F,B,E,C.G}，V={} ，E={AD,DF,AB,BE,EC,EG} 所有顶点访问完毕。
上图是以A为出发点，访问每一个顶点，且代价最小的寻找过程。现在可以回答问题1里面的问题，在城市A到城市G之间建造通讯网络，代价最小的方案为：
总代价是39
(2)Kruskal算法
1)基本思想
?设G=(V,E)，令最小生成树初始状态只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量；
?在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则，舍去此边，选区下一条代价最小的边；
?依次类推，重复第二步，直至T中所有顶点都在同一连通分量上位置。
算法执行过程如图4-2所示。
2)算法执行示例图
2.单源最短路径
单源最短路径是计算有向图带权图的某一源点到其他各顶点的最短路径长度。单源最短路径和构造最小生成树类似。单源最短路径方法可解决文章开头处的旅游路线问题2。
(1)Dijkstra算法
Dijkstra 即 艾兹格o迪科斯彻。艾兹格oWo迪科斯彻 （Edsger Wybe Dijkstra，日~日）荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。
2)基本思想
设置顶点集合 S ，开始时 S 中只含有源点 v 。设 u 是 G 的某一个顶点，把从源点 v
到 u 且中间只经过 S 中顶点的路径称为从源点到 u 的特殊路径，并用集合记录当前从源点 v 到其他每个顶点所对应的最短特殊路径长度以及路径经过的顶点。
3)算法执行示例图
以文章开头处的问题2为例，求从A点到G点的最短特殊路径，在这里将求出A点到其他任意一个顶点的最短特殊路径，如果需要指定目的地，可对程序做一些小处理就可以达到目的。
表4-1 Dijkstra算法的迭代过程状态变化
从表中可以看出从A点到其他每个顶点的特殊路径的变化状态。整个过程共有7步：
第1步，初始化（A,B），（A,C），（A,D），（A,E），（A,F），（A,G）三条变（或有向图的弧）的距离值，分别为dist[B]、dist[C]、dist[D]、dist[E]、dist[F]、dist[G]，分别是顶点A到其他每个顶点初始状态的最短距离。可以看出，A到D的距离最短，长度为5；
第2步，从V集合里取出顶点D加入到集合S中，由于顶点D加入了S，从A经过D到B的距离比A直接到D的距离小，不需要调整dist[B]，从A经过D到C与A直接到C都不可达，无需调整，从A经过D到E比从A直接到E小（A?E=MAX），因此需要调整E的值为dist[E]=20，A经过D到F比A直接到F的值要小（A-&F=MAX），因此调整dist[F]=11，A经过D到G与A直接到G都不可达，不调整；
第3步，在剩余的顶点集合V里面得出与A最小距离的顶点是B，因此将顶点B从V集合中取出加入S集合，接着重复第2步，直到所有顶点都加入集合S，此时求单源最短路径结束，第7步则是顶点A到其他每个顶点的最短路径，最后结果如下：
顶点访问序列：{A,D,B,F,E,C,G}
现在可以回答文章开头处的问题2，从A到G的最短路径是22。
3.拓扑排序
若在有向图G中，从顶点vi到vj有一条路径，则在拓扑序列中顶点vi必须排在顶点vj之前。找一个有向图的一个拓扑序列的过程称为拓扑排序，而完成拓扑排序的前提条件是AOV网中不允许出现回路。AOV网络：工程或者某种流程可以分为若干个小的工程或结点，这些小的工程或阶段就称为活动。如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为AOV网。如图4-1就是课程之间先后关系的AOV网。拓扑排序可以解决文档开头的问题3。
表4-2课程之间的先后关系
课程之间的先后关系用有向图表示如图4-3所示。
1)基本思想
在图中选择一个入度为0的顶点，输出该顶点；
从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度减1）；
重复执行上述两步，直到所有入度为0的顶点均被输出，拓扑排序完成，或者图中再也没有入度为0的顶点。
2)算法执行流程图
从图可以看出，由于在排序过程中顶点的入度是随时调整的，因此拓扑排序输出序列并不是唯一的，所以答案也不是唯一的。按照上图的步骤得到的答案是：
C1-&C7-&C6-&C2-&C3-&C4-&C5
五、心得与体会
本文章解释了图是什么、图的邻接矩阵存储结构、图的深度优先搜索与广度优先搜索的遍历方法以及图在生活中的一些实际应用。
图论能够解决生活中许多实际问题。通过学习图的一些术语、存储结构、遍历方法以及实际应用过程中的经典算法，深刻体会到图作为几种基本的逻辑结构中最为复杂的一种结构。然而图结构虽然复杂，但只要根据科学的理论依据以及利用正确的方法将复杂的问题逐步分解，各个击破，再复杂的问题都能迎刃而解。
要理解别人的算法理论依据，还要将算法转化为计算机程序，这些过程可能会遇到各种困难。就好比软件开发中的两个转换困难：用户的理解到程序员的理解之间的困难；程序员的理解到计算机程序的实现之间的困难。在实现程序的过程中首先要理解算法的理论依据，然后观察算法执行过程中的状态变化，最好是画出每一步的执行步骤，数据之间在什么时候转化，转化的条件是什么，把这些问题一一弄清楚之后，再来写程序就会得心应手。
在编写本文章的同时我还写了里面各种算法对应的Java实现代码，如有需要可交流联系！
图是数据结构里面的重要一章。通过图，我们可以判断两个点之间是不是具有连通性；通过图，我们还可以计算两个点之间的最小距离是多少；通过图，我们还可以根据不同的要求，寻找不同的合适路径。当然，有的时候为了计算的需要，我们还需要从图中抽象出最小生成树，这样在遍历计算的时候就不需要持续判断是不是遇到了循环节点。当然，这所有的一切都是从图的表示开始的。
1）矩阵表示
矩阵表示可以说是最简单的表示方法，如果说一个图中有5个点，那么我们就可以构建一个55的矩阵。如果点和点之间存在连接，那么填上1；反之如果不存在连接，那么可以用0表示，当然对角线上面的点是没有意义的。如下图所示：
[cpp] view plain copy
static int graph[5][5] =
{0, 1, 0, 1, 1},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{1, 1, 0, 1, 0}
如果点和点之间还是存在方向的，那么它们关于(x，x)对称轴就是不对称的，所以结果也可能是这样的：
[cpp] view plain copy
static int graph[5][5] =
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 0}
当然，如果点和点之间的关系存在某种权重，比如说距离，那我们可以用它来代替原来的数据1：
[cpp] view plain copy
static int graph[5][5] =
{0, 0, 0, 0, 0},
{3, 0, 0, 0, 0},
{0, 6, 0, 0, 0},
{8, 0, 4, 0, 0},
{9, 2, 0, 7, 0}
矩阵表示下的图结构非常直观。但是，矩阵有一个特点，就是比较浪费空间。因为我们这里举例的顶点比较少，只有5个，但是请大家试想一下，如果一张图上有10000个节点，那么1000010000该是多大的一个空间啊。重要的是，这上面大多数点都是0，所以浪费的空间是相当可观的。
2）数组结构
为了改变矩阵浪费空间的特点，我们可以建立一个只有顶点和边组成的数据空间。比如说，我们定义一个这样的结构：
[cpp] view plain copy
typedef struct _LINE
上面定义的数据结构非常简洁。第1个为起始顶点，第2个为终点，第3个为权重，第4个判断当前边是否有向。图中要是有多少边，我们就要定义多少个这样的数据。如果把这些边的数据都放在一起构成一个数组，那么我们就可以用这个数组来表示图的全部信息了。
但是，我们还是觉得有遗憾的地方。这个数据结构过分强调了边的意义和重要性，忽略了顶点本身的含义。因为，我们在强调边的时候，应该添加进顶点的相关特性。离开顶点的支持，单纯的边信息是没有什么含义的。
3）基于顶点链表的图表示
首先，我们定义顶点的基本结构：
[cpp] view plain copy
typedef struct _LINE
struct _LINE*
typedef struct _VECTEX
我们用VECTEX记录顶点的相关信息，LINE表示节点的相关信息。如果LINE是在VECTEX中的变量，那么neighbor表示当前所有节点的起始点都是start点。如果它是PATH中的变量呢，那么next的起始点就是LINE链接的前面一个点，不知道我讲清楚了没有？下面就是点与点之间PATH的定义。
[cpp] view plain copy
typedef struct _PATH
其中start为起始点，end为终结点，next为start链接的下一个点，lenth为路径的总长度，当然也可以修改成其他的权重形式。
注意事项：
1）数组和链表是图结构的基础，朋友们应该好好掌握
2）每一种数据结构都有自己的应用场合，关键是理解其中的思想和方法
3）图的表示是图运算的基础，掌握它们是我们进一步学习的基本条件
[TOC] Class I. Words Expressing Abstract Relations Section I. Existence 1. Being, in The Abstract existence 1 absolute
a.绝对的，完全的; 无(条件...
第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章 算法 算法的特性：有穷性、确定性、可行性、输入、输出。 什么是好的算法？ ----正确性、可读性、健壮性、时间效率高、存储量低 函数的渐近增长：给定两个函数f...
图的抽象数据结构 图：表示多对多的关系，包含一组顶点，采用V表示顶点集合，以及一组边，采用E表示边集合，边为顶点对；无向图：所以边均为无向有向图：存在边为有向抽象数据类型: 图的表示形式：邻接矩阵 ：G[i][j]=1 (i,j存在一条边，其余为0)，直观、容易理解，亦寻找...
图的概念 图是一种非线性的数据结构,一个图中有两类东西，一种是结点，一种是边.我们用V这个集合来表示节点（vertex），还需要另一个集合来存储所有的边，我们用E来表示(Edge)，那么一个图就可以表示为：G=(V,E);带箭头的称为有向图,否则称为无向图.如果一个图的任意...
图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对多的数据结构。 1、基本概念 2、图的存储结构 2.1、邻接矩阵 2.2、邻接表 2.3、十字链表 3、图的遍历 3.1、深度优先遍历 3.2、广度优先遍历 4...
这家店 因为吃了好多次， 每次觉得真的猴猴吃， 每次吃的东西还都不一样， 所以记录下来和大家分享！ 但是我去吃的时候并没有想要写文章啊！ 只是想秀图片啊！ 所以好多必备场景图比如环境呀，菜品介绍呀，动手制作的过程图啦都没有拍， So请理解我当初只想做个逛吃逛吃拍照拍照的初级...
心眼这个东西很难懂啊！ 想多了吧，小心眼， 想少了吧，没心眼， 不想了吧，缺心眼。 现在的社会，现在的人， 都是喜欢虚假的。 会做的不如会说的， 会说的不如会混的。 真情可贵，用心赔罪， 虚伪面对，从容领会， 我是永远都学不会 谁的评价都无所谓， 活着只求问心无愧！ 对的起...
武陵山区秋至冬，伐薪烧炭乐其中，火子闭炭打脱火，柔弱书生是英雄。在湘西山区的乡村里，冬季取暖是在厨房旁大大的火坑里烧柴蔸蔸，在客厅的小火坑里就烧刨火炭，少数家庭条件好的就烧蔸蔸炭或硬炭。小孩上学提烘笼也是烧的木炭。因此家家户户都有闭炭，烧炭的习惯。 一、火子闭炭 我们在家煮...
河狸家起步于上门美甲，随后陆续开通了美睫、手足护理、化妆、美容等业务，未来还会把业务延伸至美发、写真摄影等更多让生活“美起来”的服务。 河狸家APP，使命是“解放天下手艺人”，为无数家庭带来便捷服务、御宅生活。 体验环境 产品版本：v2.0.7APP 设备型号：androi...
反思最近的学习情况，存在的最大问题就是学习不够系统，输入太多，但是输出太少，对所学的知识没有很好的消化吸收。学以致用这个道理大家都懂，但是做到的人还是太少，为了改善这个情况，我下一步学习重点应该是如何提高学习效率、进行知识管理、建立知识体系等等。为此，本着提高学习力的目的，...设无向图G有n个结点，有m个连通分支，则按广度优先遍历方法得到的生成森林中边的条数为多少？_百度知道
设无向图G有n个结点，有m个连通分支，则按广度优先遍历方法得到的生成森林中边的条数为多少？
是不是n-m呢？希望会的朋友回答一下，最好是详细一点，有证明过程
我有更好的答案
结点n就是新树的根,T是树的充分必要条件是(六个等价定义) (定理14): 　　(1) T是无回路的连通图； (2) 图T无回路且m＝n－1； 　　(3) 图T连通且m＝n－1 　　(4) 图T无回路，若增加一条边,.，称为空树。空树中没有结点。 　　数学规律 　　h树 连通无回路的无向图，它们都是结点n的儿子结点。我们还称n1,nk为结点n的子树. 　　h有向树 有向图删去边的方向为树,n2,. 　　h根树与树根 非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树. 　　h每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树).,nk，就得到一条且仅一条回路树的定义 　　树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点..，则得到一棵新树,n2,。 　　空集合也是树，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。我们称n1..；每个结点的出度等于2的根树称为正则二元树(正则二叉树)。用一个新结点n作为n1； 　　(5) 图T连通,n2,,nk为一组兄弟结点..，或简称为树根。我们可以形式地给出树的递归定义如下: 　　单个结点是一棵树，树根就是该结点本身。 　　设T1。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点..,nk的父亲，若删去任一边，G则不连通； 　　(6) 图T的每一对结点之间有一条且仅有一条通路. 　　h生成树 图G的生成子图是树，该树就是生成树. 　　h权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权,T2,，该有向图就是有向树. 　　h哈夫曼树 用哈夫曼算法得到的最优二叉树,Tk是树，它们的根结点分别为n1,n2. 　　h树的判别 图 ，记作W(T). 　　h最小生成树 带权最小的生成树
额，看了半天没看到怎么解答这个问题的
为您推荐：
其他类似问题
广度优先遍历的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。> 问题详情
设G是具有4个结点的完全图：
（1)写出G的所有子图；
（2)写出G的所有生成子图．
悬赏：0&答案豆
提问人：匿名网友
发布时间：
设G是具有4个结点的完全图：&&(1)写出G的所有子图；&&(2)写出G的所有生成子图．
您可能感兴趣的试题
1画出一个多重图，使它们的邻接矩阵为&2下图中哪个有欧拉通路，哪个有欧拉回路，哪个有哈密顿通路，哪个有哈密顿回路?&3图G1，G2的邻接矩阵分别为A1和A2，试求：4设有向图D如下图所示，试求：&
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：完全二分图的生成树的个数
1基本思路定义1设G(p,q)为p个顶点q个边的任意连通图,则G(p,q)中任意p-1个边所导出的S(G)个子图成为生成子图.定义2设图G(p,q)中存在S(G)个生成子图,则S(G)个生成子图中T(G)个不含圈的生成子图称为生成树,C(G)含圈的生成子图称为含圈的生成子图,并有S(G)=C(G)+T(G).定理1设G(p,q)为任意连通图,则G(p,q)中任意p-1个边所导出的生成子图的个数为:S(G)=q(q-1)(q-2)(q-3)…(q-p+2)(p-1)!(1)S(G)个生成子图中含圈的生成子图的个数为:C(G)=C3(G)q-3p-4+C4(G)q-4p-5+…+Cp-1(G)q-p+10(2)S(G)个生成子图中不含圈的生成树的个数为:T(G)=q(q-1)(q-2)…(q-p+2)(p-1)!-C3(G)q-3p-4-C4(G)q-4p-5-…-Cp-1(G)q-p+10(3)式中C3(G):图G(p,q)中C3...&
(本文共3页)
权威出处：
一、引言 Phokp Hall在2935年证明了,t结婚定理”,回答了大家熟悉的结婚问题。Edmonds在1965年提出了最大基数匹配算法。Edm-onds与Johnson拍仁1970年提出了求解图的最大权匹配算法。White在1967年提出了求解图的最小权覆盖算法。但这些理论和算法都未涉及到边集重要性的间题。文献〔6〕所研究的仅是“测量网络支路中心函数”的问题。 文献〔2〕、〔3〕、〔4〕研究了灰色系统的控制问题。文献〔1〕、〔5〕提出了灰色系统的理论方法,并阐述了这种理论在农业、生态、经济管理等领域中的应用。而本文运用灰色系统的思想沟通自然科学、社会科学与图论之间的关系,这既为灰色系统开拓了一个新的领域,又发展了图论的有关理论。本文提出了一种新的模型—加权完全二分图 (研eighted comPlete biPartite夕raPh)称为牙CBG模型,利用此模型可建立边集重要性的概念。本文所定义的边集重要性是指在加权完全二分...&
(本文共5页)
权威出处：
０　引言通常我们遵循文献［１］中的记号和术语。１９９０年Ｈａｒａｒｙ在［２］中提出了和图的概念，不久又在［３］中介绍了整和图的概念。此后，人们进行了各种研究并得到了一些关于和图和整和图的结论［３～１５］。最近，何文杰等人研究并确定了图（Ｋｎ－Ｅ（Ｋｒ）），Ｋｒ?Ｋｎ的整和数［１２］，这是Ｈａｒａｒｙ［３］中提出的第一个未决问题．具体结论如下：ζ（Ｋｎ－Ｅ（Ｋｒ））＝０　　　　　　　（ｒ＝ｎ，ｎ－１）ｎ－１　　　　　　（ｎ－１?ｒ?［２ｎ３］－１）３ｎ－２ｒ－４　　　　（［２ｎ３］－１＞ｒ?ｎ２）２ｎ－４　　　　　　（［２ｎ３］－１＞ｎ２?ｒ?２）其中ｎ?５，ｒ?２，［ｘ］表示不小于ｘ的最小的整数。进一步，当ｒ≠ｎ－１时σ（Ｋｎ－Ｅ（Ｋｒ））＝ζ（Ｋｎ－Ｅ（Ｋｒ））。本文研究并解决了Ｈａｒａｒｙ［３］中提出的另一个未决问题，怎样确定完全二分图Ｋｒ，ｓ的整和数ζ（Ｋｒ，ｓ）。此外，我们还指出Ｈａｒｔｓｆｉｅｌｄ和Ｓｍｙｔｈ在［１１］...&
(本文共6页)
权威出处：
1基本思路定义1设G为完全图Kv,若将Kv的｜E(G)｜个边排成三角阵,使得三角阵中的任意边cicj与分别与顶ci和顶cj相关联,则该三角阵就称为边矩阵,并记为Kv′。设v=2n,G为完全图K2n,则K2n的边矩阵可划分出n(n-1)/2个完全二分图K(2I,,2J),n(n-1)/2个完全二分图K(2I,,2J)所形成的三角阵称为完全二分图矩阵,并记为K2′n。设G为完全图K4n,完全图K4n也称竞赛图或称循环赛图,而单纯的完全图K4n对组织者来说没有什么帮助,惟有完全图K4n的｜E(G)｜个边历经过△(G)-边着色的完全图,才能用来帮助安排各次比赛的名单,故标明△(G)个完备匹配的完全图称为循环赛图,并记为K(4i)n。4n阶完全图K4n的△(G)个完备匹配Mi的划分可归结为3部分:(1)将K4n划分成n(2n-1)个2×2的完全二分图K(2I,,2J)和2n个1×1的完全二分图K(4i)n。(2)进行完全二分图矩阵K2′v...&
(本文共3页)
权威出处：
图论在多因子方差模型中的应用金在春（辽源广播电视大学）摘要本文从完全二分图及其生成树出发，进一步研究了多因子实验的网点结构．在两因子的情形，视网点集合为完全二分图，本文证明了：交互效应矩阵的列基与网点集合关于其生成树的连枝集（Ｃｏｔｒｅｅ）一一对应．这一结果为寻求ｒ因子实验的效应矩阵的列基，从而构造ｒ因子实验的最小无偏设计提供了新的途径．关键词完全二分图；生成树；效应矩阵；连枝集设因子Ｆ。一｛ｆｆｔ’，…，华‘｝，在不至引起混淆时，可简记Ｆ。＝｛ｌ，…，ｎ。｝，ｋ＝ｌ，…，ｒ．网点集合表示为直积Ｆ；Ｘ…ＸＦ。一Ｃ（１）现在考虑ｒ—２的情形，此时ｃ—Ｆ；ｘＦ。简记完全二分图｛Ｆ；，Ｆ。；ｃ｝。ｃ，于是Ｃ中的网点等同于图的边．记Ｐ维列向量ｌ。－（ｌ，…，ｌ）’，定义Ｊ．＝－－－－１１：．Ｈ．＝Ｉ－－Ｊ。Ｐ则Ｈｎ＠Ｈｎ是两因子实验的交互效应矩阵，其中。表示Ｋｒｏｎｅｃｋｅｒ积，通称叉积．把Ｈｎ＠Ｈ。的列按字典顺序写出，则有Ｈｎ＠Ｈｎ一...&
(本文共3页)
权威出处：
图的平均距离是图的一个重要参数 ,它在通信网络等实际问题中起着重要的度量作用 ,图的平均距离的研究引起了许多研究人员的注意 .〔1〕〔2〕虽然图的平均距离是构造性的 ,但是到目前为止 ,只对少数特殊图类求出了平均距离的具体计算公式 ,如路Ｐｎ、圈Ｃｎ,完全图Ｋｎ、平均格图Ｐｎ×Ｐｍ,环面Ｃｎ×Ｃｍ、柱面Ｐｎ×Ｃｎ等 ,本文给出了完全二分图Ｋｍ ,ｎ,Ｋｍ∨ｐｎ,Ｋｍ∨Ｃｎ 的计算公式 .1　定理及证明　　设Ｇ1和Ｇ2 是两个图 ,Ｖ(Ｇ1)∩Ｖ(Ｇ2 ) =
,图Ｇ =Ｇ1∨Ｇ2 的顶点集Ｖ(Ｇ) =Ｖ(Ｇ1)∪Ｖ(Ｇ2 ) ,边集Ｅ(Ｇ) =Ｅ(Ｇ1)∪Ｅ(Ｇ2 )∪ {ｕｖ| ｕ∈Ｖ(Ｇ1) ,ｖ∈Ｖ(Ｇ2 ) } .设Ｇ为ｎ阶连通图 ,图Ｇ的平均距离Ｄ(Ｇ) = ｕ,ｖ∈Ｖ(Ｇ)ｕ≠ｖｄＧ(ｕ ,ｖ) /ｎ2 =1ｎ
ｕ∈Ｖ(Ｇ)1ｎ - 1 [ ｕ ,ｖ∈Ｖ(Ｇ)ｕ≠ｖｄ(ｕ ,ｖ) ]设ｕ∈Ｖ(Ｇ) ,定义ｆＧ(ｕ...&
(本文共3页)
权威出处：
扩展阅读：
CNKI手机学问
有学问，才够权威！
xuewen.cnki.net
出版：《中国学术期刊（光盘版）》电子杂志社有限公司
地址：北京清华大学 84-48信箱 大众知识服务
京ICP证040431号&
服务咨询：400-810--9993
订购咨询：400-819-9993
传真：010-}