精华内容
下载资源
问答
  • 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条边。

    展开全文
  • 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年腾讯软测的一道选择题


    展开全文
  • 无向顶点连通

    千次阅读 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

    展开全文
  • 22个顶点连通图中边的条数至少为() 正确答案: C 你的答案: 空 (错误) 18 20 21 ...n个顶点连通图至少有n-1条边(树); n个顶点的简单图(完全图)至少有n*(n-1)/2条边。 所以选C
  • 给定n个互不相同的顶点,求它们可以构成的不相同的无向连通图数量 http://poj.org/problem?id=1737 2、算法思路 引文思路描述我来说有点抽象,这里尝试再说细一些(引文:...
  • n个顶点,m条边的全连通图,至少去掉____边才能构成一棵树? 正确答案: C n-1 m-1 m-n+1 m-n-1 添加笔记 收藏 纠错 Google面试题,n个顶点的树一定有n-1条边...
  • 思想:图G是不带权的无向连通图,一条边的长度为1,因此,求距离顶点v的最远的顶点,即求距离顶点v的边数最多的顶点。利用广度优先遍历算法,从v出发进行广度遍历,类似于从顶点v出发一层层地向外扩展,到达j, …,...
  • 顶点连通度和边连通度

    千次阅读 2016-03-18 15:59:42
    思路:从网上找了一下大牛对于这类问题的总结:连通度问题是指:在中删去部分元素(点或边),使得中指定的两点s和t不连通 (不存在从s到t的路径),求至少要删去几元素。  连通度分为点连通度...
  • 连通图: 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。 强连通和弱连通的概念只...如果一有向图的基图是连通图,则有向图是弱连通图。 ...
  • (二)什么是连通图,(强)连通图详解

    万次阅读 多人点赞 2019-03-18 11:37:24
    前面讲过,图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。...无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。例如,图 2 中的无向图就是一连...
  • POJ 1966 Cable TV Network ... 题意:有线电视网络中,中继器的连接是双向的。...一空的网络、以及只有一中继器的网络被认为是连通的。具有n 中继器的网络的安全系数f 被定义成: (1) f 为n,如果不管
  • 题意:一无向n个点,m条边,求此顶点连通度。 思路:顶点连通度,即最小割点集里的割点数目,一般求无向图顶点连通度的方法是转化为网络流的最小割。 建图: (1)原点i拆点,拆为i‘和i’...
  • 连通图与简单图

    千次阅读 2016-12-02 10:52:22
    n个顶点连通图至少有n-1条边(树); n个顶点的简单图(完全图)至少有n*(n-1)/2条边。
  • 如果有向图G的每两个顶点都强连通,称G是一连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一强连通分量,因为
  • 判断一图是否为强连通图、单向连通图、弱连通图。输入为有向图的邻接矩阵。 输入 输入有若干行 第一行为正整数N(0 接下来N行,每行有N个数据,每数据以空格分隔,代表邻接矩阵。 注意:输入的都是连通图。 输出...
  • 问:n节点的连通图的个数有多少?(节点不同) 大约1月前,下到ltc的做男人不容易系列就看到了这题目。但是讲解soso的简单,我说实在话也想不出来。 今天发现是pku1337的题目,又看到了别人的思路,才想通,...
  • 无向的最大独立轨。 独立轨:设A、B是无向G的两顶点,从A到B的两条没有公共内部顶点的路径互称为独立...关于无向G顶点连通度K(G)与顶点独立轨之间的关系。 Menger定理: K(G) = |V(G)| - 1 当G是完全
  • 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使图G中每条边的两个顶点有不同的颜色? 问题分析 这问题是图的m可着色判定问题。 若一图最少需要m种...
  • 连通图

    2020-05-20 16:45:16
    给定一无向和其中的所有边,判断这个图是否所有顶点都是连通的。 输入描述: 每组数据的第一行是两整数 n 和 m(0<=n<=1000)。n 表示顶点数目,m 表示中边的数目。随后有 m 行数据,每行有两值 ...
  • ①无向的非递归深度优先搜索需借用一堆栈保存被访问过的顶点,以便回溯查找已被访问结点的被访问过的邻接点。 ②访问起始顶点v0,visited[v0]标记1,v0入栈,指针p指向v0对应的边表首结点; ③从左到右扫描p所指的...
  • 数据结构_图_定义/分类/顶点与边之间的关系/连通图/存储结构/基本操作
  • dfs判断一无向图是不是连通图

    千次阅读 2020-01-20 10:05:17
    n个顶点,编号为1~n,用dfs遍历一遍邻接矩阵,若遍历到的顶点个数等于n,则证明改无向图是一个连通图 #include<bits/stdc++.h> using namespace std; const int maxn=1005; bool vis[maxn]; vector<int...
  • 九度OJ——1109连通图

    2017-10-13 18:41:25
    给定一无向和其中的所有边,判断这个图是否所有顶点都是连通的。 输入: 每组数据的第一行是两整数 n 和 m(0<=n)。n 表示顶点数目,m 表示中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据...
  • (1)一具有 N 个顶点,在去掉任意 k-1 个顶点后 (1<=K<=N) 所得的子图仍连通,  而去掉 K 个顶点后的连通则称 G 是连通的, K 称作 G 的点连通度,记作 K(G) 试设计 (2)相应地如果至少去掉 K 条边使这...
  • 题目:求一个连通图的割点,割点的定义是,如果除去此节点和与其相关的边,图不再连通,描述算法。 分析: 1. 最简单也是最直接的算法是,删除一点然后判断连通性,如果删除此点,图不再连通,则此点是割点...
  • ​ 设 G=(V,E) 是一无向图 ,V的子集S称为分离图G,如果G-S是不连通的,图G的顶点连通度κ=κ(G)\mathrm{\kappa=\kappa (G)}κ=κ(G) 是为了产生一连通图或平凡图所需要从G中去掉的最少顶点的数目 ​ 图G 的 ...
  • 连通图总结及例题

    千次阅读 2018-01-20 17:29:56
    在一无向图 G 中,若从顶点i到顶点j有路径相连(当然从j到i也一定有路径),则称i和j是连通的。如果 G 是有向图,那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果...
  • 顶点连通度:即最少去掉几点使得不连通 设想两不相邻的点u,v; 从u到v的两条没有公共内部顶点的路径,互称为独立轨,;u到v独立轨最大的条数,记作P(u,v) 所以要想不联通,应该在每条独立轨上都去掉一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,821
精华内容 12,328
关键字:

对n个顶点的连通图