离散数学无向图和有向图

离散数学中，图可以分为有向图和无向图两种类型。

无向图：由一组顶点和一组边组成，每条边连接两个顶点，没有方向。在无向图中，每个顶点的度数是与之相连的边的数量，而一个无向图的总度数等于其边数的两倍。无向图中的边可以看作是没有方向的，因此从一个顶点到另一个顶点的路径是可以沿着任意一条边走的，因此无向图中的路径是没有方向的。

有向图：由一组顶点和一组有向边组成，每条边连接两个顶点，有方向。在有向图中，每个顶点的入度是指指向该顶点的边的数量，而出度是指从该顶点出发的边的数量。一个有向图的总入度等于总出度。有向图中的边是有方向的，因此从一个顶点到另一个顶点的路径必须沿着边的方向走，因此有向图中的路径是有方向的。

相关问题

离散数学非平凡无向图

离散数学中的非平凡无向图是指那些至少包含两个顶点和一条边的无向图，它区别于平凡无向图（也叫单点图或无边图），后者仅包含一个顶点没有边。非平凡无向图通常具有以下特点：

1. **至少两个顶点**：非平凡图至少包含两个不同节点，这些节点可以通过边相连。

2. **至少一条边**：图中存在至少一条连接两个顶点的边，这使得图不再是孤立的点集。

3. **无向性**：边是双向的，即如果有边连接节点A到节点B，那么从B到A也有一条边，不存在方向性。

4. **不规则性**：非平凡图可以是简单图（无自环、无多重边）或复杂图（允许自环和/或多条边）。

在图论中，研究非平凡无向图的重要内容包括但不限于顶点着色、连通性、路径、环、树、平面图等概念。理解这些概念对于理解和应用图算法（如深度优先搜索、广度优先搜索、最短路径算法等）至关重要。

离散数学输入两个无向图或有向图的邻接矩阵判断同构的c++程序

以下是一个简单的 C++ 程序，可用于判断两个无向图或有向图的邻接矩阵是否同构：

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

using namespace std;

const int MAXN = 100;

int n, m; // n 表示图中的节点数，m 表示图中的边数
int a[MAXN][MAXN]; // 存储第一个图的邻接矩阵
int b[MAXN][MAXN]; // 存储第二个图的邻接矩阵
bool vis[MAXN]; // 标记数组，用于深度优先搜索

// 判断两个邻接矩阵是否同构
bool isomorphic() {
    vector<int> va, vb; // 存储节点度数的数组
    int da[MAXN], db[MAXN]; // 存储节点度数的数组
    memset(da, 0, sizeof(da));
    memset(db, 0, sizeof(db));
    for (int i = 0; i < n; i++) {
        int d = 0;
        for (int j = 0; j < n; j++) {
            if (a[i][j]) d++;
        }
        da[d]++;
        va.push_back(d);
    }
    for (int i = 0; i < n; i++) {
        int d = 0;
        for (int j = 0; j < n; j++) {
            if (b[i][j]) d++;
        }
        db[d]++;
        vb.push_back(d);
    }
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
    for (int i = 0; i < n; i++) {
        if (da[i] != db[i]) return false;
    }
    for (int i = 0; i < n; i++) {
        if (va[i] != vb[i]) return false;
    }
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vector<int> v1, v2;
            for (int j = 0; j < n; j++) {
                if (a[i][j]) v1.push_back(j);
                if (b[i][j]) v2.push_back(j);
            }
            sort(v1.begin(), v1.end());
            sort(v2.begin(), v2.end());
            if (v1 != v2) return false;
            for (int j = 0; j < v1.size(); j++) {
                vis[v1[j]] = true;
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        a[u][v] = a[v][u] = 1;
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        b[u][v] = b[v][u] = 1;
    }
    if (isomorphic()) {
        cout << "两个图同构" << endl;
    } else {
        cout << "两个图不同构" << endl;
    }
    return 0;
}

程序的基本思路是先计算每个节点的度数，然后将它们按照度数从小到大排序，最后分别比较两个邻接矩阵中每个节点的邻居是否相同。如果两个邻接矩阵同构，则它们具有相同的节点度数序列，并且每个节点的邻居集合也相同。