下列关于无向连通图特征的叙述中，正确的是： 所有顶点的度之和为偶数 边数大于顶点个数减1 至少有一个顶点的度为1 A. 只有1 B. 只有2 C. 1和2 D. 1和3

正确的选项是C，即1和2。

1. 所有顶点的度之和为偶数是无向图的欧拉定理，对于任何无向图都成立。

2. 边数大于顶点个数减1是无向图连通性的一个必要条件，也就是说如果这个条件不成立，则该图必定不连通。

3. 至少有一个顶点的度为1是树的特征，而不是无向连通图的特征。而且即使是树也可能不存在度为1的顶点，比如只有一个顶点的树。

相关问题

无向连通图所有顶点的度数之和为偶数

证：

设无向连通图 $G=(V,E)$ 中有 $n$ 个顶点，$m$ 条边。则 $G$ 的所有顶点的度数之和为：

$$
\sum_{v\in V} \deg(v) = 2m
$$

其中 $\deg(v)$ 表示顶点 $v$ 的度数。

我们知道，每条边都会贡献 $2$ 到度数之和中，因为每条边连接了 $2$ 个顶点，每个顶点的度数都会加 $1$。因此，上式中的 $2m$ 就是所有顶点度数之和的总和。

而一个数能够被 $2$ 整除，当且仅当它的最低位为 $0$。因此，如果所有顶点的度数之和为偶数，那么它的二进制表示的最低位为 $0$，也就是说，每个顶点的度数都是偶数。

因为 $G$ 是一个无向图，所以每个顶点的度数就是它所连接的边数。如果所有顶点的度数都是偶数，那么每条边的两个端点的度数均为偶数。因此，每条边贡献 $2$ 到所有顶点度数之和中，也就是说，所有顶点度数之和为偶数。

综上所述，无向连通图所有顶点的度数之和为偶数。

欧拉图判断: 先判断图是否连通，非连通图则是非欧拉图。 对无向连通图而言，若所有结点的度都是偶数，则该图为欧拉图。 对无向连通图而言，若只有两个结点的度数是奇数，其余结点度数为偶数，则该图为半欧拉图。 判断一个图是否欧拉图 若是欧拉图，则输出"a is euler”； 若是半欧拉图，则输出"a is semi-euler”； 若不是欧拉图，则输出“a is not euler”。 注意：该输出前后无空格，行尾回车。 输入格式: 第一行输入结点数n（n<=10），第二行输入无向图关系矩阵的上三角元素为1的一对结点编号，结点编号之间以空格分隔；第三行输入无向图关系矩阵的下三角元素为1的一对结点编号，结点之间以空格分隔。输入 -1 -1则结束输入。 输出格式: 输出a是否欧拉图、半欧拉图或者不是欧拉图。 输入样例: 在这里给出一组输入(上图的关系矩阵)。例如： 9 0 1 1 2 0 3 1 3 1 4 3 4 2 5 4 5 3 6 4 7 5 7 5 8 6 7 7 8 1 0 2 1 3 0 3 1 4 1 4 3 5 2 5 4 6 3 7 4 7 5 8 5 7 6 8 7 -1 -1 输出样例: 在这里给出相应的输出。例如： a is euler

以下是使用C++实现的代码：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 15;
int g[N][N];
int n;
int deg[N];

int bfs(int u)
{
    queue<int> q;
    q.push(u);
    bool st[N];
    memset(st, 0, sizeof st);
    st[u] = true;

    int cnt = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        cnt ++;

        for (int i = 0; i < n; i ++ )
            if (g[t][i] && !st[i])
            {
                st[i] = true;
                q.push(i);
            }
    }

    return cnt;
}

int main()
{
    memset(deg, 0, sizeof deg);

    int a, b;
    cin >> n;
    while (cin >> a >> b, a != -1 && b != -1)
        g[a][b] = g[b][a] = 1, deg[a] ++ , deg[b] ++;

    int cnt = bfs(0);
    bool flag = true;
    for (int i = 0; i < n; i ++ )
        if (!deg[i])
        {
            flag = false;
            break;
        }

    if (!flag || cnt < n) puts("a is not euler");
    else if (cnt == n) puts("a is euler");
    else
    {
        int odd = 0;
        for (int i = 0; i < n; i ++ )
            if (deg[i] & 1)
                odd ++;

        if (odd == 2) puts("a is semi-euler");
        else puts("a is not euler");
    }

    return 0;
}

该程序首先读入图的顶点数n和图的边。然后使用邻接矩阵表示图，并计算每个顶点的度数。接下来，使用BFS遍历图，并记录遍历到的节点数cnt。然后，遍历每个顶点的度数，如果有顶点的度数为0，则该图不是连通图，输出“a is not euler”。如果遍历到的节点数cnt小于n，则该图不是连通图，输出“a is not euler”。否则，如果每个顶点的度数都是偶数，则输出“a is euler”。如果只有两个顶点的度数是奇数，则输出“a is semi-euler”，否则输出“a is not euler”。