精华内容
下载资源
问答
  • g(n)为n个顶点的非联通 则f(n) + g(n) = h(n) = 2^(n * (n - 1) / 2) 其中h(n)是n个顶点的联图的个数 这样计算 先考虑1所在的连通分量包含哪些顶点 假设该连通分量有k个顶点 就有C(n - 1, k - 1)种集合 ...

    设f(n)为所求答案

    g(n)为n个顶点的非联通图

    则f(n) + g(n) = h(n) = 2^(n * (n - 1) / 2)

    其中h(n)是n个顶点的联图的个数


    这样计算

    先考虑1所在的连通分量包含哪些顶点

    假设该连通分量有k个顶点

    就有C(n - 1, k - 1)种集合

    确定点集后,所在的连通分量有f(k)种情况。其他连通分量有 h(n - k)种情况

    因此有递推公式。g(n) = sum{ C(n - 1, k - 1) * f(k) * h(n - k)} 其中k = 1,2...n-1

    注意每次计算出g(n)后立刻算出f(n)


    import java.math.BigInteger;
    import java.util.Scanner;
    
    
    public class Main {
    
    	
    	public static void main(String[] args) {
    		BigInteger two[] = new BigInteger [55];
    		two[0] = BigInteger.ONE;
    		for(int i = 1; i <= 50; i++)
    			two[i] = two[i - 1].multiply(BigInteger.valueOf(2));
    		BigInteger h[] = new BigInteger [55];
    		for(int i = 1; i <= 50; i++){
    			int a = i;
    			int b = i - 1;
    			if(a % 2 == 0) a/= 2;
    			else b /= 2;
    			h[i] = BigInteger.ONE;
    			for(int j = 0; j < a; j++) {
    				h[i] = h[i].multiply(two[b]);
    			}
    		}
    		BigInteger C[][] = new BigInteger[55][55];
    		C[0][0] = BigInteger.ONE;
    		for(int i = 0; i <= 50; i++){
    			C[i][0] = C[i][i] = BigInteger.ONE;
    			for(int j = 1; j < i; j++){
    				C[i][j] = C[i - 1][j].add(C[i - 1][j - 1]);
    			}
    		}
    		BigInteger f[] = new BigInteger[55];
    		BigInteger g[] = new BigInteger[55];
    		f[1] = BigInteger.ONE;
    		for(int i = 2; i <= 50; i++) {
    			g[i] = BigInteger.ZERO;
    			for(int j = 1; j < i; j++) {
    				g[i] = g[i].add(C[i - 1][j - 1].multiply(f[j]).multiply(h[i - j]));
    			}
    			f[i] = h[i].subtract(g[i]);
    		}
    		int n;
    		Scanner cin = new Scanner(System.in);
    		while(cin.hasNext()){
    			n = cin.nextInt();
    			if(n == 0) break;
    			System.out.println(f[n]);
    		}
    	}
    
    }
    


    展开全文
  • 证明每n个顶点连通图都至少有n-1条边 证明:不妨设G是无向连通图(若G为有向图,可忽略边的方向讨论对应的底图)。 设G中顶点为v1, v2, ..., vn。由连通性,必存在与v1相邻的顶点,不妨设其为v2(否则,可...

    Show that every connected graph with n vertices has at least n − 1 edges.
    证明每个有n个顶点的连通图都至少有n-1条边

    证明:不妨设G是无向连通图(若G为有向图,可忽略边的方向讨论对应的底图)。

    设G中顶点为v1, v2, ..., vn。由连通性,必存在与v1相邻的顶点,不妨设其为v2(否则,可重新编号),连接v1与v2得边e1,还是由连通性,在v3, v4, ..., vn中必存在与v1或v2相邻的顶点,不妨设为v3,将其连接得边e2,续行此法,vn必与v1, v2, ..., vn-1中的某顶点相邻,得新边\large e_{(n-1)},由此可见G中至少有n-1条边。

     

    而有关正整数n的命题通常可以用数学归纳法加以证明

    归纳基础:0、1显然成立。

    归纳假设:带有k个顶点的连通图至少具有k-1条边。

    下面我们来证明带有k+1个顶点的连通图至少具有k条边。我们把k+1个顶点分成两部分,一部分含有k个顶点,一部分只有一个顶点,对于k个顶点的连通图我们知道它至少具有k-1条边,我们只需要这样构造:把那个孤立的顶点与k个顶点中的任何一个连接形成一条边,那么显然带有k+1个顶点的连通图至少具有k条边。

    展开全文
  • 无向顶点连通

    千次阅读 2019-09-22 10:04:15
    无向顶点连通度需要用到网络流来求,并且有以下定理; Mengerg定理: 无向顶点连通度K和顶点间的最大独立轨数目之间存在如下关系: ① 当为完全时: k=V-1 (V表示中顶点数) ② 当为非...

      

    无向图的顶点连通度需要用到网络流来求,并且有以下定理;

    Mengerg定理: 无向图的顶点连通度K和顶点间的最大独立轨数目之间存在如下关系:

    ① 当图为完全图时: k=V-1  (V表示图中顶点数)

    ② 当图为非完全图h时: K=min{ P(A, B) | 任意不相邻的顶点AB }

    注意:如果AB相邻的话,那么删除图中所有其他的点后,AB任然连通,故强调不相邻。

     

    独立轨:设A,B是无向图G的两个顶点,从A到B的两条没有公共顶点的路径,互称为独立轨。

    最大独立轨数:A到B独立轨的最大条数,记作P(A,B)。

     

    现在,求无向图G的顶点连通度就相当于求G中任意两点间u最大独立轨数(P(A,B))的最小值。

    求P(A,B)的方法如下:

    (1) 构造一个容量网络。

      ① 原图G中每个顶点v拆分为两个点v1  v2 ,并且v1  v2 之间连一条容量为1的单向弧。

      ② 原图G中每条变e=(u,v)在容量网络中有两条弧e1 =(u1 , v2 ),e2  =(u2 , v1 ),容量均为INF。

      ③ 另设A2 为源点,B1 为汇点。

    (2)求从A2 到B1 的最大流F。

    (3)流处源点的流量之和就是P(A,B),所有具有流量1的弧<v,v>对应的顶点v构成一个割顶集,删除这个割顶集,A,B之间不在连通。

     

    所以,根据以上定理,得出求无向图G的顶点连通度的思路:

    (1) 设K的初始值为INF。

    (2) 分析图中每对不相邻的顶点AB,求出P(A,B)和割顶集。

    (3)  K=min (K, P(A,B)),保存割顶集。

    (4) 重复(2)(3),直到图中所有不相邻顶点分析完为止。

     

     

    给出POJ1966代码:

    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #define _Clr(x, y) memset(x, y, sizeof(x))
    #define INF 0x3f3f3f3f
    #define N 300
    using namespace std;
    
    int map[N][N], flow[N][N];
    int que[N], n, St[N];
    int alpha[N], pre[N];
    
    // 求S到T的最大流
    int MaxFlow(int S, int T)
    {
        int maxf=0, m=2*n;
        _Clr(flow, 0);
        queue<int> Q;
        while(1)
        {
            _Clr(pre, -1);
            _Clr(alpha, 0);
            pre[S] = S;
            alpha[S] = INF;
            Q.push(S);
            while(!Q.empty())
            {
                int u = Q.front(); Q.pop();
                for(int i=0; i<m;  i++)
                {
                    if(pre[i]==-1 && flow[u][i]<map[u][i])
                    {
                        pre[i] = u;
                        alpha[i] = min(alpha[u], (map[u][i]-flow[u][i]));
                        Q.push(i);
                    }
                }
            }
            if(alpha[T] == 0) break;
            
            maxf += alpha[T];
            for(int i=T; i!=S; i=pre[i])
            {
                flow[pre[i]][i] += alpha[T];
                flow[i][pre[i]] -= alpha[T];
            }
        }
        return maxf;
    }
    
    void BuildMap(int m)
    {
        int a, b;
        _Clr(map, 0);
        for(int i=0; i<n; ++i) map[i][i+n] = 1;
        while(m--)
        {
            scanf(" (%d,%d)", &a, &b);
            map[a+n][b] = map[b+n][a] = INF;
        }
    }
    
    int main()
    {
        int m;
        while(~scanf("%d%d", &n, &m))
        {
            BuildMap(m);
            int ans=INF;
            for(int i=1; i<n; i++)
                ans = min(ans, MaxFlow(n, i));
            printf("%d\n", ans==INF?n:ans);
        }
        return 0;
    }
    View Code

     

    转载于:https://www.cnblogs.com/khan724/p/4366514.html

    展开全文
  • N个结点的连通图的边数问题

    千次阅读 2015-09-05 11:13:08
    在数据结构中,N个顶点连通图至少要有(N-1)条边(也就是树)才能保证图为连通图. 对于简单图而言至多有n*(n-1)/2条边,此时即是完全图. 强连通图最多n(n-1)条边,最少n-1条边. 强连通图:任意两个顶点都相互...

    RT:

    在数据结构中,N个顶点的连通图至少要有(N-1)条边(也就是树)才能保证图为连通图.
    对于简单图而言至多有n*(n-1)/2条边,此时即是完全图.

    强连通图最多n(n-1)条边,最少n-1条边.

    强连通图:任意两个顶点都相互连通的图。


    e.g.: 15年腾讯软测的一道选择题


    展开全文
  • 给定n个互不相同的顶点,求它们可以构成的不相同的无向连通图数量 http://poj.org/problem?id=1737 2、算法思路 引文思路描述对我来说有点抽象,这里尝试再说细一些(引文:...
  • 点连通度:一个具有N个点的图G中,在去掉任意k-1个顶点后(1 独立轨:A,B是图G(有向无向均可)的两个顶点,我们称为从A到B的两两无公共内顶点的轨为独立轨,其最大条数记作P(A,B)。 设A和B是无向连通图G两不...
  • POJ 1966 Cable TV Network ... 题意:有线电视网络中,中继器的连接是双向的。如果网络中任何两中继器之间至少有一条路,则中继器网络称为是...具有n 中继器的网络的安全系数f 被定义成: (1) f 为n,如果不管
  • 无向的最大独立轨。 独立轨:设A、B是无向G的两顶点,从A到B的两条没有公共内部顶点的路径互称为独立...关于无向G顶点连通度K(G)与顶点独立轨之间的关系。 Menger定理: K(G) = |V(G)| - 1 当G是完全
  • (1)一个具有 N 个顶点,在去掉任意 k-1 个顶点后 (1<=K<=N) 所得的子图仍连通,  而去掉 K 个顶点后的连通则称 G 是连通的, K 称作 G 的点连通度,记作 K(G) 试设计 (2)相应地如果至少去掉 K 条边使这...
  • 给定一无向和其中的所有边,判断这个图是否所有顶点都是连通的。 输入: 每组数据的第一行是两整数 n 和 m(0<=n<=1000)。n 表示顶点数目,m 表示中边的数目。如果 n 为 0 表示输入结束。随后...
  • 顶点连通度:即最少去掉几点使得不连通 设想两不相邻的点u,v; 从u到v的两条没有公共内部顶点的路径,互称为独立轨,;u到v独立轨最大的条数,记作P(u,v) 所以要想不联通,应该在每条独立轨上都去掉一...
  • 目录题目题解答案2018 无向连通图最少包含多少条边 题目 问题描述 一包含有2019结点的无向连通图,最少包含多少条边?...一n个顶点的无向连通图最多有nn-1)/2条边,最少有n-1条边。 答案 2018 ...
  • PTA上的题目答案绝大多数都是c或者c++的,很少有Java的,这是我和一学C的朋友一起写出来的,分享给大家 先给大家看看结果, 代码如下,我也有些不太理解的地方,欢迎大家留言,一起讨论 import java.io....
  • 有向完全图和强连通图的区别?

    千次阅读 2020-08-14 10:52:27
    相邻关系:两个顶点之间存在一条边,则表示两个顶点具有相邻关系 路径:相邻顶点序偶所构成的序列 路径长度:路径上边的数目 回路:若一条路径中第一个顶点和最后一个顶点相同,则为回路 连通:从顶点Vi到顶点Vj有...
  • 顶点v 构成了一割顶集,在G 中去掉这些顶点后则A 和B 不再连通了。 #include #include #include #include #include #include #include #include #include #define MEM(a,x) memset(a,x,sizeof...
  • Prim算法涉及到的几基础知识生成树: 一个连通图的生成树是它的极小连通子图,在n个顶点的情形下,有n-1条边。生成树是对连通图而言的,是连通图的极小连通子图,包含途中所有顶点,有且仅有n-1条边。非连通图的...
  • 连通图的强连通分支

    千次阅读 2011-09-28 19:28:06
    //双连通分量方法一: //定义一:给定的有向图G=(V,...//互相到达,则称G是强连通图。 //定义二:有向图的极大强连通子图称为强连通分支。 //由定义可2以得知有向图的强连通分支是一最大的顶点集合,在这集合中
  • 判断连通子图

    千次阅读 2019-12-10 18:48:46
    给定一个具有n个顶点、m条边的无向G,假设项点的编号为1-n。基于深度优先搜索算法,编写程序 求无向G连通子图的个数。 输入格式: 第一行两整数n, m,分别表示G的顶点数和边的数量。 下面m行的每-行有两整数a...
  • (3)连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一数值,称为权,权代表着连接两个顶点的代价,称这种连通图叫做连通网 (4)生成树:一个连通图的生成树是指一连通子图,它含有图中全部n个...
  • 什么是连通图 ? 在图论中,连通图基于连通的概念。在一无向图 G 中,若从顶点 i 到顶点 j 有路径相连(当然从 j 到 i 也一定有路径),则称 i 和 j 是连通的。如果 G 是有向图,那么连接 i 和j的路径中所有的边都...
  • 第十一届 蓝桥杯 省 模拟赛 完整题目+题解地址为:第十一届 蓝桥杯 省 模拟赛 ...一包含有2019结点的无向连通图,最少包含多少条边? 答案提交 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为...
  • (3)连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一数值,称为权,权代表着连接两个顶点的代价,称这种连通图叫做连通网 (4)生成树:一个连通图的生成树是指一连通子图,它含有图中全部 n....
  • 正则 正则:regular,有规律的,有规则的。...具有k自由度的顶点的正则被称为k度的k-正则。 此外,奇数程度的正则图形将包含偶数个顶点。 G=(V,E),ifv∈V,deg(v)=r,则称G为r−正则G=(V,E),if v\in V
  • 连通图:最短路径就是形成闭环。 一有向无环图的拓扑序列不是唯一的: 注意: 1)只有有向无环图才存在拓扑序列; 2)对于一DAG(Directed Acyclic Graph,有向无环图),可能存在多拓扑序列; 进行拓扑排序...
  • 权重:当边带有数字标签时,可以将这些数字称为 权重 ,并且说这个图是一 加权 路径:一个顶点到另一个顶点的边的序列连通中的每一个顶点到其他的每一个顶点都有一条路径完全的:从每一...
  • 在一无向连通图中,如果删去某个顶点和与他相关联的边可以使得图不连通,则称该顶点为关节点。关节点的求解tarjan算法: 在无向连通图中,以某个顶点为根节点进行深度优先搜索,则在深度优先搜索树中,每节点都...
  • 连通性问题

    万次阅读 2017-03-21 15:50:25
    果一无向图不是连通图,则称为非连通图(disconnected graph)。对非连通图G,其极大连通子图称为连通分量(connected component,或连通分支),连通分支数记为w(G)。 割顶集与连通度: 设V’是连
  • 最小加权路径:加权有向顶点之间权值之和最小...基于以上事实,如果从源顶点A到目标顶点B1、B2、B3……Bn的最短路径都已知,现在加入一新目标顶点B(n+1),那么从A到B(n+1)的最短路径是[AB1最短路径+B1B(n+1)]、
  • 自由树就是一无回路的连通图(没有确定根)(在自由树中选定一顶点做根,则成为一棵通常的树)。 从根开始,为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序,则它就成为一棵有序树。 在图的应用中,常常...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,466
精华内容 3,386
热门标签
关键字:

具有n个顶点的连通图