• 所有问题

    • 离散证明:一个图包含2n个结点，每个结点的度数大于等于n的简单图是连通的

    如题所述

    举报该问题
    其他回答
    第1个回答  2019-09-02
    假设不连通。有如下两种情况：
    1.最小连通分量有n个结点：此时共两个连通分量，每个分量n个结点。对于任一点，它的度至多是n-1,矛盾。
    2.最小连通分量小于n个结点：该分量中任一点的度不超过n，矛盾。
    第2个回答  2020-04-22
    假设g不是连通的
    则g至少有两个连通分支g1和g2，有
    |g1|+|g2|
    ≤
    |g|
    =
    n
    任取g1中一点v1，g2中一点v2
    则d(v1)≤|g1|-1，d(v2)≤|g2|-1
    d(v1)+d(v2)
    ≤
    |g1|+|g2|-2
    ≤
    n-2，与条件矛盾
    相似回答
    若无向简单图G有2n个顶点,每个顶点的度数至少为n证明此图是连通图。答：【答案】：[证明]用反证法，设图G不是连通图，不妨设图G有两个连通分支G1和G2构成，其中G1含有k个顶点(1≤k＜n)，G2含有2n-k个顶点。在连通分支G1中任取一点v1，在连通分支G2中任取一点v2。由于图G是简单图，所以G1和G2也是简单图，于是有deg(v1)≤k-1deg(v2)≤2n-k-1由此可得de...
    证明:在两个或两个以上结点的简单图中,至少有两个结点的度数相同。答：在n阶简单图中，点的度数在必然在0～n-1之间，共n个不同的度数。假设: 没有两个点度数相同，即:0～n-1这n个度数必然对应n个点。证明:1.若最小度为0，则说明有一个点为孤立点，此时在剩下n-1个点中，最大的度数只能为n-1-1=n-2，0～n-2只对应n-1个点，故，与假设矛盾。2.若最...
    大家正在搜
    链表每个结点中都恰好包含一个指针链表中每个节点都包含一个指针每个节点包含两个域包含节点abc的树有几个链式存储结构中的节点包含设置包含根节点的二叉树高度为0建立有n个节点的单链表设有n个节点的无向图设有n个节点的完全二叉树