求这个无向图的： 1.点割集 2.边割集 3.点连通度 4.最小度 5.边连通度 证明:点连通度≤边连通度≤最小度
k(G)≤l(G)≤δ(G)。证明 若 G 不连通， 则k(G)＝λ(G)＝0，故上式成立。 若 G 连通， 1) 证明λ(G)≤δ(G) 如果 G 是平凡图，则 λ(G)＝0≤δ(G)，若G是非平凡图，则因每一结点的所有关联边必含一个边割集，故λ(G)≤δ(G) 。
2) 再证 k(G)≤λ(G) (a) 设λ(G)＝1，即G有一割边，显然这时k(G)＝1，上式成立。 (b) 设λ(G)≥2，则必可删去某λ(G)条边，使G不连通，而删去其中λ(G)-1条边，它仍是连通的，且有一条桥e＝(u，v)。对λ(G)-1条边中的每一条边都选取一个不同于u，v的端点，把这些端点删去，则必至少删去λ(G)-1条边。若这样产生的图是不连通的，则k(G)≤λ(G)-1＜λ(G)，若这样产生的图是连通的，则e仍是桥，此时再删去u或v，就必产生一个不连通图，故 k(G)≤λ(G)。 由 1) 和 2) 得 k(G)≤λ(G)≤δ(G)
在一个无向图G中，若从结点u到结点v存在一条路，则称从u到v是可达的，或简称u可达v.对于无向图来说，两结点的可达关系是对称的,如果u到v可达,则v到u也可达.可达关系也是传递的,如果u到v可达, v到w可达,则将结点u到结点v的路与v到结点w的路连接起来得到一条u到结点w的路，因此u到w可达. 另外约定结点到自身都是可达的.
在无向图G中，如果结点u,v可达,则称这两点是连通的，如果图G中任何两点均是连通的，则称图是连通的,或称该图为连通图,由于结点的可达关系对于无向图来说，是结点集合上的等价关系，因此可达关系给出结点集合的一个划分，划分中的元素是一些等价类,每个等价类中的结点导出一个子图，两结点可达当且仅当它们属于同一个子图，称这种子图为的一个连通分支，图G的连通分支个数记为w(G).显然如果图G只有一个连通分图，则G是连通图.
从一个图中删去一个结点，也将把与它关联的边删去，删去一条边即将该边从图中抹去即可，一般来说删去一些结点或删去一些边有可能改变图的连通性，
设图G=,S是V的子集，T是E的子集,从图G中的结点集V中删去结点集S中的所有结点或从E中删去边集T中所有的边而得到的子图的使其连通分支个数增大，则称S为G一个点割集，T为G一个边割集。图看：
http://hi.baidu.com/lca001/blog/item/39ec5c1e4430bec5a68669cf.html
2) 再证 k(G)≤λ(G) (a) 设λ(G)＝1,即G有一割边,显然这时k(G)＝1,上式成立.(b) 设λ(G)≥2,则必可删去某λ(G)条边,使G不连通,而删去其中λ(G)-1条边,它仍是连通的,且有一条桥e＝(u,v).对λ(G)-1条边中的每一条边都选取一个不同于u,v的端点,把这些端点删去,则必至少删去λ(G)-1条边.若这样产生的图是不连通的,则k(G)≤λ(G)-1＜λ(G),若这样产生的图是连通的,则e仍是桥,此时再删去u或v,就必产生一个不连通图,故 k(G)≤λ(G).由 1) 和 2) 得 k(G)≤λ(G)≤δ(G)
夷元希普： 您好,这是我们数据结构一个作业程序,希望能帮到你.#include <stdio.h>#include<stdlib.h>#define int_max 10000#define inf 9999#define max 20//邻接矩阵定义 typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct ...
榆林市17171531233： 一个有N个顶点和E条边的无向图在其对应的邻接表中所含边结点数为?答案是2E 求解 还有边结点的意思是什么 - ？
夷元希普： 无向图就是不分方向的图 连接表的横列有N项,纵列也是N项 形成的N*N项每项都被称为边结点 每项都有纵横两个坐标,例如点(N,N-1),表示的就是从第N点向第N-1点有无路径. 由于有E条边,自然有E条路径,但是由于无向,=双向,所以要乘以二
榆林市17171531233： c语言求出无向图G的连通分量个数 - ？
夷元希普： 思路是这样的:1、从图中任选一个节点,以此节点进行深度优先搜索并将访问的节点做好标记,连通分量数加一.2、在从图中没有访问的节点集中选一个节点重复1的过程直到所有节点都被标记
榆林市17171531233： 谁能和我说下迪克斯特拉算法,求解最短路径问题 - ？
夷元希普： 迪杰斯特拉算法用于求解一个有向图(也可以是无向图,无向图是有向图的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短路径问题.算法构思很是巧妙(我这么认为),简直达到了“无心插柳柳成荫”的境界.算法本...
榆林市17171531233： 图论割集问题 - ？
夷元希普： 回答楼主,图论大多问题的解决,需要用到遍历算法,判断割集我想不会有其它算法,遍历的算法目前是图论中最基本最重要的算法,当然对一些特殊的图可能会有其它方法.遍历算法的计算复杂度不是很大的,是多项式算法,在计算机上可以实...
榆林市17171531233： 无向图能用Dijkstra算法吗? - ？
夷元希普： 可以的... 设d[i]表示原点到第i个点的最短路径,共n个顶点,p是原点,g[i][j]表示从点i到点j的距离,如果不存在i到j的路径,则g[i][j]=inf 初始d[1....n]=inf,d[p]=0 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(g[i][j]<inf) {d[j]=min(d[i]+g[i][j],d[j]); }不会PASCAL,见谅...
榆林市17171531233： 求代码,建立无向图,输入一个邻接矩阵,1求边的条数2任意两个顶点是否有边相连3.任意一个顶点的度是多少 - ？
夷元希普： 这个其实很好办的,在有向图的基础上,作如下修改.创建有向图的过程中,用一个数来表示是否相连,可以设置weight为1或0.可以在确定一条弧的两个顶点后,locate其位置后将其的权值定为1或0,1表示相连,0表示不相连.这时候赋值的时候写两句,比如说这样: G->arcs[i][j].adj=weight; G->arcs[j][i].adj=weight; 其中i,j分别表示所在的行与列.G是一个图,arcs是一个邻接矩阵,adj就是权值,weight是具体的值,为1或0.这里写了两遍的语句就是实现了无向图的创建.其他的程序就可以依此进行修改,这个还是比较简单的,好好写吧...
榆林市17171531233： 构建邻接矩阵, 已知一组数,V1,V2,V3,V4,V5,知道彼此之间的关系(不一定均相关),求建邻接矩阵 - ？
夷元希普： 已知一个无向图G=(V,E),其中V={V1,V2,V3,V4},其邻接矩阵如下 0 1v2 深度遍历序列:v1 - v2 - v3 - v4 对应的生成...
榆林市17171531233： 离散数学一道证明题 - ？
夷元希普： 若结点v是连通图G=的一个割点,设删去v得到子图G',则G'至少包含2个连通分支.设其为G1=,G2=,任取u∈V1,w∈V2,因为G是连通的,故在G中必有一条连接u和w的路C,但u和w在G'中属于两个不同的连通分支,故u和w必不连通,因此C必须通过v,故u和w之间的任意一条路都通过v 反之,若连接图G中某两个结点的每一条路都通过v,删去v得到子图G',在G'中这两个结点必然不连通,故v是图G的割点.祝你成功!!!!!!!!!!!!!!!!!
榆林市17171531233： 无向图中如何求两顶点之间的所有路径 - ？
夷元希普： #define True 1#define False 0 int visited[MAX_VERTEX_NUM]; void BreadthFirstSearch(Graph g,int v0) {/*广度优先搜索图g中v0所在的连通子图*/ int x,w,m; InitQueue(&Q); EnterQueue(&Q,v0); while(!Empty(Q)) { DeleteQueue(&Q,&x); if(!visited[x]) ...
