证明如果无向图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是可达的。

相关问题

输入一个无向简单图的邻接矩阵，判定该图是否有欧拉回/通路，若有，给出一条，否则 输出相应提示信息

要判断一个无向简单图是否有欧拉回路（所有顶点恰好访问一次）或欧拉路径（所有顶点恰好访问一次并返回起点），我们需要先了解几个关键点：

1. **欧拉回路**：如果图中恰好有一个偶数个奇度顶点（即度数为奇数的顶点），则存在一个欧拉回路。
2. **欧拉路径**：如果图中没有奇度顶点，则存在一个欧拉路径。

以下是Java代码示例，使用邻接矩阵（二维数组）来实现这一功能：

import java.util.ArrayList;
import java.util.List;

class Graph {
    private int V;
    private int[][] adj;

    // 构造函数
    public Graph(int vertices, int[][] matrix) {
        V = vertices;
        adj = matrix;
    }

    // 检查图中是否存在欧拉回路或路径
    boolean hasEulerCycleOrPath() {
        int oddDegreeCount = 0;
        for (int i = 0; i < V; ++i) {
            oddDegreeCount += adj[i].length - adj[i].length / 2; // 由于是无向图，邻接点计数乘2
        }
        
        if (oddDegreeCount == 0) { // 欧拉路径
            System.out.println("存在欧拉路径");
            List<Integer> path = new ArrayList<>();
            dfsWithEvenDegree(i, path, true); // 假设从第一个奇度顶点开始，i 代表起点
            return true;
        } else if (oddDegreeCount == 2) { // 欧拉回路
            System.out.println("存在欧拉回路");
            dfsWithOddDegree(i, true); // 假设从两个奇度顶点之一开始，i 代表起点
            return true;
        } else {
            return false;
        }
    }

    // 深度优先搜索，找到一个欧拉路径或回路
    private void dfsWithEvenDegree(int start, List<Integer> path, boolean isBacktrack) {
        // ... DFS 实现细节略去，重点是记录路径，并在遇到奇度顶点时改变方向（进入回路）
        // 当前顶点已访问，添加到路径中，并继续查找下一个可达顶点
        // 返回时，根据isBacktrack决定是否回到上一步
    }

    private void dfsWithOddDegree(int start, boolean isCycle) {
        // ... DFS 实现细节略去，重点是在找到第二个奇度顶点时结束，形成回路
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] adjacencyMatrix = {{0, 1, 1}, {1, 0, 1}, {1, 1, 0}}; // 示例邻接矩阵
        Graph graph = new Graph(3, adjacencyMatrix);
        if (graph.hasEulerCycleOrPath()) {
            System.out.println("欧拉路径或回路如下:");
            // 输出路径或回路元素
        } else {
            System.out.println("不存在欧拉路径或回路");
        }
    }
}

这个代码片段首先计算奇度顶点的数量，然后尝试寻找欧拉路径（从偶数个奇度顶点出发）或回路（从两个奇度顶点中一个出发）。具体的深度优先搜索（DFS）实现未在这里列出，你需要根据邻接矩阵来完成这部分。