[数据结构与算法]离散数学实验三

实验题目：平面图对偶图的求解

实验目的：

1、掌握平面图的定义；
2、掌握平面图对偶图的求解方法；
3、掌握平面图与其对偶图之间顶点数、边数和面数的关系。

实验要求：

1、给定一平面图的面矩阵R和连通分支数p

2、输出此平面图的顶点数n、边数m和面数r。
3、输出此平面图的对偶图的顶点数n*、边数m和面数r。
4、输出此平面图的对偶图的相邻矩阵（注意：面Ri中放置顶点vi，相邻矩阵第i行对应顶点vi，）。

知识回顾

1、平面图的欧拉定理：n - m + r = 1 + p; 其中n、m、r、p分别是顶点数、边数、面数、连通分支数；
2、对偶图的顶点数、边数、面数与原平面图的关系：

实现代码

/*
实验要求：
1、给定一平面图的面矩阵R和连通分支数p
2、输出此平面图的顶点数n、边数m和面数r。
3、输出此平面图的对偶图的顶点数n*、边数m*和面数r*。
4、输出此平面图的对偶图的相邻矩阵（注意：面Ri中放置顶点vi，相邻矩阵第i行对应顶点vi，）。
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int p = 0; // 连通分支数
    vector<vector<int> > R;
    int r = 0; // 面矩阵的行数，即平面图的面数
    int m = 0; // 面矩阵的列数，即平面图的边数
    printf("输入面矩阵的行数和列数：\n");
    scanf("%d %d", &r, &m);
    for (int i = 0; i < r; ++i) {
        vector<int> temp;
        int t = 0;
        for (int j = 0; j < m; ++j) {
            scanf("%d", &t);
            temp.push_back(t);
        }
        R.push_back(temp);
    }
    printf("输入平面图的连通分支数：\n");
    scanf("%d", &p);
    // 欧拉公式: n - m + r = 1 + p
    int n = 0; // 平面图的顶点数
    n = 1 + p + m - r;
    printf("该平面图的顶点数n、边数m和面数r分别为：%d %d %d\n", n, m, r);
    int n1 = r; // 对偶图的顶点数
    int m1 = m; // 对偶图的边数
    int r1 = n - p + 1; // 对偶图的面数
    printf("该平面图的顶点数n、边数m和面数r分别为：%d %d %d\n", n1, m1, r1);
    // 输出此平面图的相邻矩阵
    // 发现原平面图的面矩阵就是对偶图的关联矩阵，可以根据此性质得到相邻矩阵
    // 如果平面图有桥，则对偶图有环
    vector<vector<int> > A(r, vector<int>(r, 0));
    for (int j = 0; j < m; ++j) {
        int t1 = -1; // 边关联的两个顶点，可以是同一个点
        int t2 = -1;
        for (int i = 0; i < r; ++i) {
            if (R[i][j] != 0) {
                if (t1 == -1) {
                    t1 = i;
                }
                else if (t2 == -1) {
                    t2 = i;
                }
                else {
                    printf("出错了，一条边最多只能关联2个顶点！\n");
                    return 0;
                }
            }
        }
        if (t2 == -1) { // 说明有环
            t2 = t1;
        }
        A[t1][t2] += 1;
        A[t2][t1] += 1;

    }
    printf("输出该平面图的对偶图的相邻矩阵A：\n");
    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < n1; ++j) {
            if (i == j) {
                A[i][j] >>= 1;
            }
            printf("%d ", A[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

测试数据

/*
测试数据：
3 5
1 1 0 1 1
0 1 1 0 1
1 0 1 1 0
1

输入面矩阵的行数和列数：
3 5
1 1 0 1 1
0 1 1 0 1
1 0 1 1 0
输入平面图的连通分支数：
1
该平面图的顶点数n、边数m和面数r分别为：4 5 3
该平面图的顶点数n、边数m和面数r分别为：3 5 4
输出该平面图的对偶图的相邻矩阵A：
0 2 2
2 0 1
2 1 0
/
/
3 8
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0
1 1 1 1 1 1 1 1
3
输入面矩阵的行数和列数：
3 8
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0
1 1 1 1 1 1 1 1
输入平面图的连通分支数：
3
该平面图的顶点数n、边数m和面数r分别为：9 8 3
该平面图的顶点数n、边数m和面数r分别为：3 8 7
输出该平面图的对偶图的相邻矩阵A：
0 0 4
0 0 3
4 3 2
/
/
3 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
1 1 1 1 0 1 1 1 1 1
3
输入面矩阵的行数和列数：
3 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
1 1 1 1 0 1 1 1 1 1
输入平面图的连通分支数：
3
该平面图的顶点数n、边数m和面数r分别为：11 10 3
该平面图的顶点数n、边数m和面数r分别为：3 10 9
输出该平面图的对偶图的相邻矩阵A：
1 0 4
0 0 3
4 3 2
/
/
输入面矩阵的行数和列数：
3 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
1 1 1 1 0 1 1 1 1 1
输入平面图的连通分支数：
4
该平面图的顶点数n、边数m和面数r分别为：12 10 3
该平面图的顶点数n、边数m和面数r分别为：3 10 9
输出该平面图的对偶图的相邻矩阵A：
1 0 4
0 0 3
4 3 2
*/