9. G=<V, E>中所有顶点的度数之和等于边数的（ B ）倍。 A. 1 B. 2 C. 3 D. 4

答案是 B. 2。

根据握手定理，无向图中所有顶点的度数之和等于边数的两倍，即：

∑deg(v) = 2|E|

其中，deg(v) 表示顶点 v 的度数，|E| 表示图 G 的边数。

因此，所有顶点的度数之和等于边数的两倍，即：

∑deg(v) = 2|E| = 2 × (|E| / 1) = |E| × 2

所以，所有顶点的度数之和等于边数的 2 倍。答案是 B. 2。

相关问题

证明如果无向图G恰有俩个不同的奇度数的顶点a，b，那么a到b是可达的

首先，我们先证明一个引理：在一个无向图中，度数为奇数的顶点的个数一定是偶数。

证明：对于一个无向图G，设其顶点集为V，任取一条边AB，则A的度数加1，B的度数加1，因此G中所有点的度数之和等于2E（E为边数）。又因为每个点的度数是非负偶数或非负奇数，所以2E是偶数，因此度数为奇数的顶点的个数一定是偶数。

回到原命题，设a和b的奇度数分别为k和m，则k和m为奇数，因此k+m为偶数。由引理可知，G中奇度数顶点的个数为偶数，因此存在一条从a到b的路径，路径上经过的顶点的度数都是偶数，因此a和b的度数必定都是偶数。偶度数顶点有一个重要的性质，即任意一个偶度数顶点都可以通过一系列的边到达其他偶度数顶点。因此，a和b都可以通过一系列的边到达其他偶度数顶点，并最终到达彼此，即a到b是可达的。

所设计的程序能够通过编译，给定包含10个结点且存在哈密尔顿回路的简单图G，顶点集合为{1，2，......，10}，已知边集，判断它是否为平面图。首先输入两个正整数 N 和 M，分别表示图G的顶点数和边数。紧接着的 M行，每行是用空格隔开的两个正整数u 和v ，表示对应图的一条边 (u,v), 输入的数据保证所有边都仅出现一次。输出YES代表是平面图，NO代表不是平面图。

好的，根据您的要求，我可以为您提供一个程序来判断这个图是否为平面图。以下是程序的实现代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15, M = 150;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N][N];  // 用来存储边是否存在
int q[N], cnt[N]; // q存储每个点的度数，cnt表示当前已经加入的点的数量

void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}

bool dfs(int u, int depth)
{
    if (depth == n) return true; // 找到了哈密尔顿回路，说明一定是平面图

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[u][j]) // 如果边(u, j)不存在
        {
            st[u][j] = st[j][u] = true; // 加入边(u, j)
            if (dfs(j, depth + 1)) return true;
            st[u][j] = st[j][u] = false; // 回溯
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h); // 初始化邻接表

    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b); add(b, a); // 无向图添加两条边
    }

    for (int i = 1; i <= n; i ++ ) q[i] = i;

    do
    {
        int tt = 0;
        for (int i = 0; i < n; i ++ ) // 模拟加点的过程
        {
            int t = q[i];
            cnt[tt ++ ] = t;
            for (int j = 0; j < tt - 1; j ++ )
                if (st[t][cnt[j]]) // 如果点t与已经加入的点cnt[j]之间有边
                    goto next; // 不符合条件，直接跳到下一个排列
        }
        memset(st, false, sizeof st); // 重置边的状态
        if (dfs(q[0], 1)) // 从第一个点开始搜索哈密尔顿回路
        {
            cout << "YES" << endl;
            return 0;
        }
        next: ;
    } while (next_permutation(q, q + n)); // 枚举所有排列

    cout << "NO" << endl;

    return 0;
}

程序的大致思路如下：

1. 读入给定的图，使用邻接表存储边的信息。

2. 枚举所有的排列，模拟加点的过程，对于加入的每个点，判断它与已经加入的点之间是否有边，如果有，则跳到下一个排列。

3. 对于每个排列，从第一个点开始搜索哈密尔顿回路，如果找到了，则说明这个图是平面图，输出YES并结束程序。

4. 如果所有排列都枚举完了都没有找到哈密尔顿回路，则说明这个图不是平面图，输出NO并结束程序。

希望这个程序能够满足您的需求，如果有任何疑问，请随时与我联系。