 无向图G有11条边，4个3度结点，其余结点均为5度结点，则G的结点数为

对于无向图 G，它所有边的数目等于每个顶点的度数之和的一半，即 $|E| = \frac{1}{2}\sum_{v\in V}deg(v)$。因此，有：

$11 = \frac{1}{2}\sum_{v\in V}deg(v)$

对于度数为 3 的结点数为 4，度数为 5 的结点数为 $|V|-4，代入上式得：

$11 = \frac{1}{2}[4\times3 + (|V|-4)\times 5]$

化简后得：

$|V| = 9$

因此，G 的结点数为 9。

相关问题

设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 （ ） 个5 度结点。

设G中有n个5度结点，则有9-n个6度结点。因为每个结点的度数只能是5或6，所以G中总共有 $5n+6(9-n)=54-n$ 条边。根据握手定理，G中边数应该是所有结点的度数之和的一半，即 $\frac{1}{2}\sum_{v\in G} d(v)$。由于每个结点的度数都不是5就是6，所以 $\sum_{v\in G} d(v)$ 必定是偶数。因此，$5n+6(9-n)=54-n$ 必须是偶数，解得 $n\geq 3$。因此，G中至少有3个5度结点。

用java写一段 判断一个有向图和无向图是不是欧拉图和半欧拉图 的代码【实验原理和方法】 （1）用关系矩阵R= 表示图。 （2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。 半欧拉图：有两个点奇数度，其余都是偶数度 （3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。 半欧拉图：有一个点出度比入度多一，另有一个点入度比出度多一，其余点出度等于入度。

下面是用Java实现判断一个有向图和无向图是否为欧拉图和半欧拉图的代码：

import java.util.*;

public class Graph {

    private int V; // 图的顶点数
    private int[][] adjMatrix; // 关系矩阵

    public Graph(int V, int[][] adjMatrix) {
        this.V = V;
        this.adjMatrix = adjMatrix;
    }

    // 判断无向图是否为欧拉图
    public boolean isEulerianUndirected() {
        // 统计每个节点的度数
        int[] degrees = new int[V];
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (adjMatrix[i][j] != 0) {
                    degrees[i]++;
                }
            }
        }
        // 判断是否所有节点的度数都是偶数
        for (int i = 0; i < V; i++) {
            if (degrees[i] % 2 != 0) {
                return false;
            }
        }
        return true;
    }

    // 判断无向图是否为半欧拉图
    public boolean isSemiEulerianUndirected() {
        // 统计奇数度数的节点数量
        int oddDegreesCount = 0;
        for (int i = 0; i < V; i++) {
            int degree = 0;
            for (int j = 0; j < V; j++) {
                if (adjMatrix[i][j] != 0) {
                    degree++;
                }
            }
            if (degree % 2 != 0) {
                oddDegreesCount++;
            }
        }
        // 判断是否恰好有两个节点的度数是奇数
        return oddDegreesCount == 2;
    }

    // 判断有向图是否为欧拉图
    public boolean isEulerianDirected() {
        // 统计每个节点的入度和出度
        int[] inDegrees = new int[V];
        int[] outDegrees = new int[V];
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (adjMatrix[i][j] != 0) {
                    outDegrees[i]++;
                    inDegrees[j]++;
                }
            }
        }
        // 判断是否所有节点的入度等于出度
        for (int i = 0; i < V; i++) {
            if (inDegrees[i] != outDegrees[i]) {
                return false;
            }
        }
        return true;
    }

    // 判断有向图是否为半欧拉图
    public boolean isSemiEulerianDirected() {
        // 统计出度比入度多1的节点数量和入度比出度多1的节点数量
        int outMinusInCount = 0;
        int inMinusOutCount = 0;
        for (int i = 0; i < V; i++) {
            int outDegree = 0;
            int inDegree = 0;
            for (int j = 0; j < V; j++) {
                if (adjMatrix[i][j] != 0) {
                    outDegree++;
                }
                if (adjMatrix[j][i] != 0) {
                    inDegree++;
                }
            }
            if (outDegree - inDegree == 1) {
                outMinusInCount++;
            } else if (inDegree - outDegree == 1) {
                inMinusOutCount++;
            }
        }
        // 判断是否恰好有一个节点出度比入度多1，恰好有一个节点入度比出度多1，其余节点出度等于入度
        return outMinusInCount == 1 && inMinusOutCount == 1 && V - outMinusInCount - inMinusOutCount == 0;
    }

    public static void main(String[] args) {
        // 举例：判断无向图是否为欧拉图
        int[][] adjMatrix = {
                {0, 1, 1, 0},
                {1, 0, 1, 0},
                {1, 1, 0, 1},
                {0, 0, 1, 0}
        };
        Graph graph = new Graph(4, adjMatrix);
        boolean isEulerianUndirected = graph.isEulerianUndirected();
        boolean isSemiEulerianUndirected = graph.isSemiEulerianUndirected();
        System.out.println("是否为欧拉图：" + isEulerianUndirected);
        System.out.println("是否为半欧拉图：" + isSemiEulerianUndirected);

        // 举例：判断有向图是否为欧拉图
        int[][] adjMatrix2 = {
                {0, 1, 0, 0},
                {0, 0, 1, 0},
                {0, 0, 0, 1},
                {1, 0, 0, 0}
        };
        Graph graph2 = new Graph(4, adjMatrix2);
        boolean isEulerianDirected = graph2.isEulerianDirected();
        boolean isSemiEulerianDirected = graph2.isSemiEulerianDirected();
        System.out.println("是否为欧拉图：" + isEulerianDirected);
        System.out.println("是否为半欧拉图：" + isSemiEulerianDirected);
    }
}