1) 分析并回答下列问题 图中顶点的度之和与边数之和的关系? 有向图中顶点的入度之和与出度之和的关系?具有n个顶点的无向图，至少应有多少条边才能确保是个连通图?若采用邻接矩阵表示，则该矩阵的大小是多 少? G具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的?为什么?

1. 图中顶点的度之和与边数之和的关系为：顶点的度之和等于边数之和的两倍，即∑deg(v) = 2|E|。这是因为每条边都会贡献两个度数，一个度数给与边相连的起点，另一个度数给与边相连的终点。

2. 对于有向图，顶点的入度之和等于出度之和，即∑indeg(v) = ∑outdeg(v)。这是因为每条弧都会贡献一个入度和一个出度，一个入度给与弧指向该顶点的终点，一个出度给与弧起点所在的顶点。

3. 至少应有n-1条边才能确保是个连通图。这是因为n个顶点的无向图的最小边数为n-1条，当且仅当图为树时达到最小值。如果图不是树，那么再添加边就会形成环，即会出现多余的边。因此，至少需要n-1条边才能保证图的连通性。

4. 如果采用邻接矩阵表示，则该矩阵的大小为n*n。因为邻接矩阵是一个n*n的矩阵，其中第i行第j列的元素表示顶点i和顶点j是否相邻，因此需要n行n列的矩阵来表示。

5. 对于有向图，至少应有n条弧才能确保是强连通图。这是因为强连通图是指从任意一个顶点出发都可以到达图中的任意一个顶点，因此每个顶点都需要至少一条出弧和一条入弧。因此，每个顶点至少需要2条弧，所以n个顶点的有向图至少需要n条弧。

相关问题

对n个顶点的有向图G，采用邻接表存储，请回答下列有关问题： （1）如何求图中的边数？ （2）如何判断顶点i到顶点j是否有边相连？ （3）如何求任意一个顶点i的入度？

对于一个有向图G采用邻接表存储，每个顶点的邻接列表会包含与其相连的所有顶点及其对应的边的信息。

（1）求图中的边数：只需遍历所有的邻接表，每条边都会被计数一次。对于每个顶点，检查其邻接表中的边的数量，然后累加即可。例如，可以用一个变量sum初始化为0，然后对每个顶点的邻接表进行迭代，每次增加sum的值。

edges_count = sum(len(adj_list[vertex]) for vertex in G.vertices)

（2）判断顶点i到顶点j是否有边相连：对于邻接表来说，可以直接查找顶点i的邻接表中是否包含顶点j。如果找到，则说明存在一条从i到j的边；如果没有，则不存在。

if j in adj_list[i]:
    has_edge = True
else:
    has_edge = False

（3）求任意一个顶点i的入度：入度是指指向该顶点的边的数量。同样地，在顶点i的邻接列表中计算直接指向它的边的数量。

in_degree_i = len(adj_list[i])

用DEV C++写一个程序对有向无环图，按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。 输入有向图的相关信息，若图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。 因拓扑有序序列不唯一，故要求如下： （1）使用邻接表存储图。邻接表的每个链表中，要求按顶点的序号从大到小排列； （2）使用栈辅助操作。初始时，入度为0的顶点入栈时，也按顶点的序号从大到小的顺序入栈。 输入说明： 输入有向图的顶点数、边数、各顶点的值，各边的信息。 输出说明： 若有向图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。 拓扑有序序列的每个顶点数据后有一个空格。

以下是用C++语言编写的程序，可实现对有向无环图进行拓扑排序：

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 10005;

struct Edge {
    int to, next;
};

Edge edges[MAXN];
int head[MAXN], inDegree[MAXN];
int N, M, cnt;

void addEdge(int from, int to) {
    edges[++cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt;
    inDegree[to]++;
}

bool topSort() {
    stack<int> st;
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) st.push(i);
    }
    vector<int> ans;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        ans.push_back(u);
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            inDegree[v]--;
            if (inDegree[v] == 0) st.push(v);
        }
    }
    if (ans.size() != N) return false;
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    return true;
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int from, to;
        cin >> from >> to;
        addEdge(from, to);
    }
    if (!topSort()) cout << "此有向图不是有向无环图";
    return 0;
}

使用邻接表存储图，并使用一个 stack 存储入度为 0 的节点，在每次取出一个节点后更新其相邻节点的入度，并将入度为 0 的节点压入栈中。最终，如果所有节点都被排列，则说明拓扑排序成功，输出拓扑有序序列；否则，输出“此有向图不是有向无环图”。