用张铭编写的《数据结构与算法》证明： 只要适当地排列顶点的次序， 就能使有向无环图的邻接矩阵中主对角线以下的元 素全部为 0

假设有向无环图的顶点集为 {v1, v2, ..., vn}，我们可以通过对顶点集进行拓扑排序来得到一个顶点序列 {vi1, vi2, ..., vin}，使得对于任意的 i < j，不存在从 vij 指向 vii 的边。这样的顶点序列可以通过 Kahn 算法或 DFS 实现。

接下来，我们根据拓扑序列来构造邻接矩阵。设 A 为邻接矩阵，其中 A[i][j] 表示从 vi 到 vj 是否存在一条边。由于拓扑排序的性质，对于任意的 i < j，vj 不可能指向 vi，因此 A[j][i] 必然为 0。

由于有向无环图中不存在环，因此不存在从一个顶点出发经过若干个顶点后回到该顶点的情况。因此，对于任意的 i，vj 不可能指向 vi，也就是说 A[i][i+1] 至 A[i][n-1] 都必须为 0。因此，邻接矩阵 A 中主对角线以下的元素全部为 0。

综上所述，只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为 0。

相关问题

用张铭编写的《数据结构与算法》证明： 对于一个无向图 G=<V, E>，若 G 中各顶点度数都大于等于 2，则 G 中必有回路。

首先，我们需要明确一个概念，回路（Cycle）是指在图中存在至少一条边，能够从某个顶点出发，经过若干个不同的顶点后，再回到这个出发点。

接下来，我们使用反证法证明原命题。

假设 G 中不存在回路，即 G 是无环图。

由于 G 中各顶点度数都大于等于 2，那么对于任意一个顶点 v∈V，它至少有两条出边，连接着不同的顶点。我们从这个顶点 v 出发，依次沿着其中一条出边走到下一个顶点，然后再沿着其中一条出边走到下一个顶点，一直走下去，直到无法继续走下去为止，这时我们会停在一个度数为 1 的顶点 u 上。

由于 G 是无环图，我们不能再从顶点 u 出发继续往下走，因为如果我们能够继续往下走，那么我们就会形成一个回路，与假设矛盾。因此，顶点 u 只有一条入边与之相连，否则它的度数就大于等于 2。

现在我们考虑从顶点 u 出发，继续按照上述方法往下走，走到下一个度数为 1 的顶点 v 上。同样地，顶点 v 也只有一条入边与之相连。

继续往下走，我们会发现如果 G 是无环图，那么我们最终一定会走到某个度数为 1 的顶点 w 上，且顶点 w 的入边与顶点 v 的出边相同。如下图所示：

    v ----> w
    ^       |
    |       |
    +-------+

现在我们将这条边从图中删除，再将顶点 w 也从图中删除，得到新的图 G'。由于顶点 w 的入边和顶点 v 的出边相同，所以删除这条边对 G 的连通性没有影响。此时，顶点 v 的度数减少了 1，但仍然大于等于 1。同样地，对于顶点 u 和它的出边也是如此。因此，我们可以重复上述过程，每次都删除某个度数为 1 的顶点及其相连的边，直到剩余的图 G'' 中只剩下一个度数不为 0 的连通分量。

最终得到的图 G'' 中，所有顶点的度数都为 0，这是因为每次删除顶点和边时，总度数减少 2，而初始时总度数为偶数（因为每条边都被算了两次），因此经过若干次删除后，剩余的总度数为偶数，而每个顶点的度数又都是偶数，所以剩余的图中顶点的度数都为偶数，与总度数为偶数矛盾。

因此，假设不成立，原命题得证。即，对于一个无向图 G=<V, E>，若 G 中各顶点度数都大于等于 2，则 G 中必有回路。

给定正整数 n ，输出所有数字1和2相邻的1~n的全排列，用c++递归实现。无其他头文件无其他函数无数组无std::string超级简单入门级萌新也能懂适合初学者理解

以下是使用 C++ 递归实现输出所有数字 1 和 2 相邻的 1~n 的全排列的代码示例：

#include <iostream>

// 递归函数，参数分别为当前数字、目标数字 n、当前排列
void generatePermutations(int currNum, int n, std::string currPermutation) {
    // 如果当前数字大于目标数字，表示已完成一次排列，输出结果
    if (currNum > n) {
        std::cout << currPermutation << std::endl;
        return;
    }

    // 在当前排列的基础上加上 1，继续递归
    generatePermutations(currNum + 1, n, currPermutation + "1");

    // 在当前排列的基础上加上 2，继续递归
    generatePermutations(currNum + 1, n, currPermutation + "2");
}

int main() {
    int n;
    std::cout << "请输入一个正整数 n：" << std::endl;
    std::cin >> n;
  
    std::cout << "所有数字 1 和 2 相邻的 1~" << n << " 的全排列如下：" << std::endl;
  
    generatePermutations(1, n, "");

    return 0;
}

这段代码通过递归生成所有数字 1 和 2 相邻的 1~n 的全排列。首先，我们定义了一个递归函数 `generatePermutations`，它接受三个参数：当前数字 `currNum`，目标数字 `n`，当前排列 `currPermutation`。在递归函数中，我们首先判断当前数字是否大于目标数字，如果是，则表示已经生成完一次排列，输出结果并返回。如果不是，我们分别在当前排列的基础上加上 1 和 2，并分别调用递归函数继续生成下一个数字的排列。

在主函数中，我们首先读取用户输入的正整数 n，然后调用递归函数生成并输出所有数字 1 和 2 相邻的 1~n 的全排列。

希望这个代码示例对你有所帮助，如果有任何疑问，请随时提问。