OUC离散数学II实验二(Python+Cpp)

这篇具有很好参考价值的文章主要介绍了OUC离散数学II实验二(Python+Cpp)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实验主题

生成树、环路空间、断集空间的求解

实验目的

1、掌握无向连通图生成树的求解方法;

2、掌握基本回路系统和环路空间的求解方法;

3、掌握基本割集系统和断集空间的求解方法;

4、了解生成树、环路空间和断集空间的实际应用。

实验要求

给定一无向简单连通图的相邻矩阵 (例如:离散数学实验二python,python,算法,开发语言,c++)。

1、输出此图的关联矩阵M

2、求此图所有生成树个数。

3、输出其中任意一棵生成树的相邻矩阵(默认第i行对应顶点vi)和关联矩阵(默认第i行对应顶点vi,第j列对应边ej)。

4、求此生成树对应的基本回路系统(输出形式如:{e1e4e3,e2e5e3})。

5、求此生成树对应的环路空间(输出形式如:{Φ,e1e4e3,e2e5e3,e1e4e5e2})。

6、求此生成树对应的基本割集系统(输出形式如:{{e1,e4},{e2,e5},{e3,e4,e5}})。

7、求此生成树对应的断集空间(输出形式如:{Φ,{e1,e4},{e2,e5},{e3,e4,e5},{e1,e2,e4,e5},{e1,e3,e5},{e2,e3,e4},{e1,e2,e3}})。

实验内容

1. 输出关联矩阵

在相邻矩阵中,如果不为0,则表示这两点之间有边,如果大于1,表示有平行边,可以对相邻矩阵的每一行遍历,找到不为0的元素时,在新矩阵中新增一行,其中两点对应的位置置1,表示一条边,并同时将该元素和其关于主对角线元素-1,最后将矩阵输出即可。

def guanlian_matrix(l: list) -> list:
    length = len(l)
    lc = copy.deepcopy(l)
    m = []
    for i in range(length):
        for j in range(length):
            if lc[i][j] > 0:
                for k in range(lc[i][j]):
                    t = [0] * length
                    t[i], t[j] = 1, 1
                    m.append(t)
                    lc[i][j] -= 1
                    lc[j][i] -= 1
    return m

输出:

print("===>关联矩阵")
g = guanlian_matrix(m)
print("   ", end="")
[print('e' + str(i), end="\t") for i in range(len(g))]
print()
for i in range(len(g[0])):
    print("v" + str(i), end="  ")
    for j in range(len(g)):
        print(g[j][i], end="\t")
    print()

2. 求生成树的个数

方法一:

设D(G)为图的度对角矩阵,A(G)为图的领接矩阵,则C = D ( G ) − A ( G ) 的任意一个余子式的值即为图G的生成树个数。C也成为拉式矩阵。分析得,拉式矩阵的对角线上的元素为相邻矩阵对应行上所有元素的求和,其他为相邻矩阵的相反数。得到拉式矩阵后,再取第一行第一列的余子式,也就是去除第一行和第一列的行列式。

求行列式,可以采用定义法,按第一行展开,得到的n个代数余子式,同样也是求行列式,再按照其第一行展开,一直递归到只剩一行时结束,即可算出行列式。这里使用了numpy中的函数实现。

def cal_tree(l: list) -> int:
    m = []
    for i in range(1, len(l)):
        t = []
        for j in range(1, len(l)):
            if i == j:
                t.append(sum(l[i]))
            else:
                t.append(-l[i][j])
        m.append(t)
    return int(round(np.linalg.det(np.array(m)), 0))

方法二:

可以去除关联矩阵中的任意一行,得到一个n-1行m列的矩阵,再在m条边中选择n-1条,组成一个新矩阵,计算该矩阵是否满秩,即计算行列式是否为0,如果不为0,则包含一个生成树。

def cal_tree(l: list) -> int:
    x = list(itertools.combinations(range(len(l)), len(l[0]) - 1))
    n = 0
    for each in x:
        matrix = [l[i][1:] for i in each]
        if np.linalg.det(matrix) != 0:
            n += 1
    return n

3. 输出一颗树的相邻矩阵和关联矩阵

利用上一题的方法二,取出其中的一个结果,其中从m中选出的n-1列就是选出的树枝。

对于排列组合,可以采用二进制枚举,从1 ~ 2n+1-1判断二进制数中有多少个1,如果符合需要组合的个数,则储存起来,其中1表示被选中,0表示不被选中。这里使用了itertools中的combination函数实现。

def tree(l: list) -> tuple:
    x = list(itertools.combinations(range(len(l)), len(l[0]) - 1))
    rep = []
    for each in x:
        matrix = [l[i][1:] for i in each]
        if np.linalg.det(matrix) != 0:
            rep = each
            break
    xianglin = [[0] * len(l[0]) for _ in range(len(l[0]))]
    guanlian = [l[i] for i in rep]
    # 根据关联矩阵计算相邻矩阵
    for i in guanlian:
        e = [j for j in range(len(i)) if i[j] == 1]
        xianglin[e[0]][e[1]], xianglin[e[1]][e[0]] = 1, 1
    return xianglin, guanlian, rep

输出:

x, y, bian = tree(g)
print("===>生成树的相邻矩阵")
print("   ", end="")
[print('v' + str(i), end="\t") for i in range(len(x))]
print()
for i in range(len(x)):
    print("v" + str(i), end="  ")
    for j in range(len(x)):
        print(x[j][i], end="\t")
    print()

print("===>生成树关联矩阵")
print("   ", end="")
[print('e' + str(i), end=" ") for i in bian]
print()
for i in range(len(y[0])):
    print("v" + str(i), end="  ")
    for j in range(len(y)):
        print(y[j][i], end="  ")
    print()

4. 求生成树对应的基本回路系统

根据生成树的边,可以求出该生成树对应的弦,再根据每根弦的两个顶点,在生成树找到两个顶点的一条通路,加上这条弦,构成一条回路,于是可以求出基本回路系统。寻找通路时,采用了BFS宽度优先搜索,以生成树中的一个顶点为根节点,搜索时保存其子节点,最后再根据保存的字节点,为每个字节点的父节点赋值。根据另一个点,向回找到根节点即为一条回路。

class Node:
    def __init__(self, num, pre=None):
        self.pre = pre
        self.num = num
        self.succed = []


def bfs_loop(matrix: list, start: int, end: int):
    points = [Node(i) for i in range(len(matrix))]
    visited = [False] * len(matrix)
    visited[start] = True
    queue = [start]
    # bfs搜索
    while queue:
        now = queue.pop(0)
        if now == end:
            break
        for i in range(len(matrix)):
            if matrix[now][i] == 1 and visited[i] == False:
                points[now].succed.append(points[i])
                queue.append(i)
                visited[i] = True
    # 为所有字节点的pre赋值,方便找到父节点
    for each in points:
        for i in each.succed:
            i.pre = each
    e = [end]
    # 从端点向回找,找到根节点结束
    while points[end].pre:
        end = points[end].pre.num
        e.insert(0, end)
    return e


def loop(tree: list, guanlian: list, bian: list):
    xian = list(set(range(len(guanlian))) - set(bian))
    loops = []
    # 计算每条弦的回路中的点
    for each in xian:
        e = [i for i in range(len(guanlian[0])) if guanlian[each][i] == 1]
        x = bfs_loop(tree, e[0], e[1])
        x.append(e[0])
        loops.append(x)
    rep = []
    # 根据回路中的点求出对应的边
    for each in loops:
        n = 1
        x = []
        while n < len(each):
            t = [0] * len(guanlian[0])
            t[each[n - 1]], t[each[n]] = 1, 1
            for i in range(len(guanlian)):
                if guanlian[i] == t:
                    x.append('e' + str(i))
                    break
            n += 1
        rep.append(x)
    return rep

5. 求此生成树对应的基本割集系统

可以对每一条树枝,先删除这条树枝,再以此加入弦,如果加入弦之后,图连通,则该弦应该再这条树枝生成的割集中,否则不在。判断连通,可以通过图的相邻矩阵进行bfs搜索,如果全部节点都被访问过的话,则为连通的。也可以使用实验一的方法。

def liantong(matrix: list) -> bool:
    visited = [False] * len(matrix)
    visited[0] = True
    queue = [0]
    # bfs搜索
    while queue:
        now = queue.pop(0)
        for i in range(len(matrix)):
            if matrix[now][i] == 1 and visited[i] == False:
                queue.append(i)
                visited[i] = True
    return all(visited)


def geji(xianglin: list, bian: list, guanlian: list):
    xian = list(set(range(len(guanlian))) - set(bian))
    rep = []

    for i in range(len(bian)):
        xianglin1 = copy.deepcopy(xianglin)
        # 删除树枝
        e = [_ for _ in range(len(guanlian[0])) if guanlian[bian[i]][_] == 1]
        xianglin1[e[0]][e[1]], xianglin1[e[1]][e[0]] = 0, 0
        x = ['e' + str(bian[i])]
        for each in xian:
            # 加上一条弦
            e = [_ for _ in range(len(guanlian[0])) if guanlian[each][_] == 1]
            xianglin1[e[0]][e[1]], xianglin1[e[1]][e[0]] = 1, 1
            if liantong(xianglin1):
                # 如果连通则去除该弦,并加入割集
                x.append('e' + str(each))
                e = [_ for _ in range(len(guanlian[0])) if guanlian[each][_] == 1]
                xianglin1[e[0]][e[1]], xianglin1[e[1]][e[0]] = 0, 0
        rep.append(x)
    return rep

6. 环路空间和断集空间

环路空间只需要对生成树的基本回路系统中取若干个(1~n)做环合运算即可得到结果。环合运算可以取取出的若干个中的第一个回路生成数组A,对于后面的每一个回路,如果其中有边在A中,则在A中删除这条边,如果没有则在A中加入这条边。

取若干个的操作可以使用二进制枚举法,从1~2n-1,1为被选中,0为不被选中,即可枚举出所有选择的情况,这里使用itertools中的combination实现。

割集空间与环路空间同理。

def space(circles: list):
    rep = copy.deepcopy(circles)
    for i in range(2, len(circles) + 1):
        x = itertools.combinations(range(len(circles)), i)
        for e in x:
            t = copy.deepcopy(circles[e[0]])
            for j in e[1:]:
                for each in circles[j]:
                    if each in t:
                        t.remove(each)
                    else:
                        t.append(each)
            if t not in rep:
                rep.append(t)
    return rep

实验测试数据、代码及相关结果分析

离散数学实验二python,python,算法,开发语言,c++

离散数学实验二python,python,算法,开发语言,c++

===>关联矩阵
   e0	e1	e2	e3	e4	e5	e6	
v0  1	1	1	0	0	0	0	
v1  1	0	0	1	1	0	0	
v2  0	1	0	1	0	1	0	
v3  0	0	0	0	0	1	1	
v4  0	0	1	0	1	0	1	
共有24颗树
===>生成树的相邻矩阵
   v0	v1	v2	v3	v4	
v0  0	1	1	0	1	
v1  1	0	0	0	0	
v2  1	0	0	1	0	
v3  0	0	1	0	0	
v4  1	0	0	0	0	
===>生成树关联矩阵
   e0 e1 e2 e5 
v0  1  1  1  0  
v1  1  0  0  0  
v2  0  1  0  1  
v3  0  0  0  1  
v4  0  0  1  0  
===>基本回路系统
{ e0e1e3,e0e2e4,e5e1e2e6  }
===>环路空间
{ Φ, e0e1e3, e0e2e4, e5e1e2e6, e1e3e2e4, e0e3e5e2e6, e0e4e5e1e6, e3e4e5e6 }
===>基本割集系统
{ { e0,e3,e4 }, { e1,e3,e6 }, { e2,e4,e6 }, { e5,e6 } }
===>断集空间
{ Φ, { e0,e3,e4 }, { e1,e3,e6 }, { e2,e4,e6 }, { e5,e6 }, { e0,e4,e1,e6 }, { e0,e3,e2,e6 }, { e0,e3,e4,e5,e6 }, { e1,e3,e2,e4 }, { e1,e3,e5 }, { e2,e4,e5 }, { e0,e1,e2 }, { e0,e4,e1,e5 }, { e0,e3,e2,e5 }, { e1,e3,e2,e4,e5,e6 }, { e0,e1,e2,e5,e6 } }

离散数学实验二python,python,算法,开发语言,c++

离散数学实验二python,python,算法,开发语言,c++文章来源地址https://www.toymoban.com/news/detail-769237.html

实验代码

Python

import numpy as np
import copy
import itertools


def guanlian_matrix(l: list) -> list:
    length = len(l)
    lc = copy.deepcopy(l)
    m = []
    for i in range(length):
        for j in range(length):
            if lc[i][j] > 0:
                for k in range(lc[i][j]):
                    t = [0] * length
                    t[i], t[j] = 1, 1
                    m.append(t)
                    lc[i][j] -= 1
                    lc[j][i] -= 1
    return m


def cal_tree(l: list) -> int:
    m = []
    for i in range(1, len(l)):
        t = []
        for j in range(1, len(l)):
            if i == j:
                t.append(sum(l[i]))
            else:
                t.append(-l[i][j])
        m.append(t)
    return int(round(np.linalg.det(np.array(m)), 0))


# def cal_tree(l: list):
#     x = list(itertools.combinations(range(len(l)), len(l[0]) - 1))
#     n = 0
#     for each in x:
#         matrix = [l[i][1:] for i in each]
#         if np.linalg.det(matrix) != 0:
#             n += 1
#     return n

def tree(l: list) -> tuple:
    x = list(itertools.combinations(range(len(l)), len(l[0]) - 1))
    rep = []
    for each in x:
        matrix = [l[i][1:] for i in each]
        if np.linalg.det(matrix) != 0:
            rep = each
            break
    xianglin = [[0] * len(l[0]) for _ in range(len(l[0]))]
    guanlian = [l[i] for i in rep]
    for i in guanlian:
        e = [j for j in range(len(i)) if i[j] == 1]
        xianglin[e[0]][e[1]], xianglin[e[1]][e[0]] = 1, 1
    return xianglin, guanlian, rep


class Node:
    def __init__(self, num, pre=None):
        self.pre = pre
        self.num = num
        self.succed = []


def bfs_loop(matrix: list, start: int, end: int):
    points = [Node(i) for i in range(len(matrix))]
    visited = [False] * len(matrix)
    visited[start] = True
    queue = [start]
    # bfs搜索
    while queue:
        now = queue.pop(0)
        if now == end:
            break
        for i in range(len(matrix)):
            if matrix[now][i] == 1 and visited[i] == False:
                points[now].succed.append(points[i])
                queue.append(i)
                visited[i] = True
    # 为所有字节点的pre赋值,方便找到父节点
    for each in points:
        for i in each.succed:
            i.pre = each
    e = [end]
    # 从端点向回找,找到根节点结束
    while points[end].pre:
        end = points[end].pre.num
        e.insert(0, end)
    return e


def loop(tree: list, guanlian: list, bian: list):
    xian = list(set(range(len(guanlian))) - set(bian))
    loops = []
    # 计算每条弦的回路中的点
    for each in xian:
        e = [i for i in range(len(guanlian[0])) if guanlian[each][i] == 1]
        x = bfs_loop(tree, e[0], e[1])
        x.append(e[0])
        loops.append(x)
    rep = []
    # 根据回路中的点求出对应的边
    for each in loops:
        n = 1
        x = []
        while n < len(each):
            t = [0] * len(guanlian[0])
            t[each[n - 1]], t[each[n]] = 1, 1
            for i in range(len(guanlian)):
                if guanlian[i] == t:
                    x.append('e' + str(i))
                    break
            n += 1
        rep.append(x)
    return rep


def space(circles: list):
    rep = copy.deepcopy(circles)
    for i in range(2, len(circles) + 1):
        x = itertools.combinations(range(len(circles)), i)
        for e in x:
            t = copy.deepcopy(circles[e[0]])
            for j in e[1:]:
                for each in circles[j]:
                    if each in t:
                        t.remove(each)
                    else:
                        t.append(each)
            if t not in rep:
                rep.append(t)
    return rep


def liantong(matrix: list) -> bool:
    visited = [False] * len(matrix)
    visited[0] = True
    queue = [0]
    # bfs搜索
    while queue:
        now = queue.pop(0)
        for i in range(len(matrix)):
            if matrix[now][i] == 1 and visited[i] == False:
                queue.append(i)
                visited[i] = True
    return all(visited)


def geji(xianglin: list, bian: list, guanlian: list):
    xian = list(set(range(len(guanlian))) - set(bian))
    rep = []

    for i in range(len(bian)):
        xianglin1 = copy.deepcopy(xianglin)
        # 删除树枝
        e = [_ for _ in range(len(guanlian[0])) if guanlian[bian[i]][_] == 1]
        xianglin1[e[0]][e[1]], xianglin1[e[1]][e[0]] = 0, 0
        x = ['e' + str(bian[i])]
        for each in xian:
            # 加上一条弦
            e = [_ for _ in range(len(guanlian[0])) if guanlian[each][_] == 1]
            xianglin1[e[0]][e[1]], xianglin1[e[1]][e[0]] = 1, 1
            if liantong(xianglin1):
                # 如果连通则去除该弦,并加入割集
                x.append('e' + str(each))
                e = [_ for _ in range(len(guanlian[0])) if guanlian[each][_] == 1]
                xianglin1[e[0]][e[1]], xianglin1[e[1]][e[0]] = 0, 0
        rep.append(x)
    return rep


m = []
x = input()
while x:
    m.append(list(map(int, x.split())))
    x = input()

print("===>关联矩阵")
g = guanlian_matrix(m)
print("   ", end="")
[print('e' + str(i), end="\t") for i in range(len(g))]
print()
for i in range(len(g[0])):
    print("v" + str(i), end="  ")
    for j in range(len(g)):
        print(g[j][i], end="\t")
    print()

tree_num = cal_tree(m)
print(f"共有{tree_num}颗树")

x, y, bian = tree(g)
print("===>生成树的相邻矩阵")
print("   ", end="")
[print('v' + str(i), end="\t") for i in range(len(x))]
print()
for i in range(len(x)):
    print("v" + str(i), end="  ")
    for j in range(len(x)):
        print(x[j][i], end="\t")
    print()

print("===>生成树关联矩阵")
print("   ", end="")
[print('e' + str(i), end=" ") for i in bian]
print()
for i in range(len(y[0])):
    print("v" + str(i), end="  ")
    for j in range(len(y)):
        print(y[j][i], end="  ")
    print()

print("===>基本回路系统")
circles = loop(x, g, bian)
print("{ ", end="")
for i in range(len(circles)):
    if i != len(circles) - 1:
        print(''.join(circles[i]), end=",")
    else:
        print(''.join(circles[i]), end=" ")
print(" }")

print("===>环路空间")
print("{ Φ, ", end="")
huanlu = space(circles)
for i in range(len(huanlu)):
    if i != len(huanlu) - 1:
        print(''.join(huanlu[i]), end=", ")
    else:
        print(''.join(huanlu[i]), end="")

print(" }")

print("===>基本割集系统")
gj = geji(x, bian, g)
print("{ ", end="")
for i in range(len(gj)):
    print("{ ", end="")
    if i != len(gj) - 1:
        print(','.join(gj[i]), end=" }, ")
    else:
        print(','.join(gj[i]), end=" }")
print(" }")

print("===>断集空间")
dj = space(gj)
print("{ Φ, ", end="")
for i in range(len(dj)):
    print("{ ", end="")
    if i != len(dj) - 1:
        print(','.join(dj[i]), end=" }, ")
    else:
        print(','.join(dj[i]), end=" }")
print(" }")

CPP

#include "iostream"
#include "vector"
#include "cmath"
#include "queue"
#include "algorithm"

using namespace std;

vector<vector<int>> guanlianMatrix(vector<vector<int>> l) {
    vector<vector<int>> t;
    for (int i = 0; i < l.size(); i++) {
        for (int j = 0; j < l.size(); j++) {
            if (l[i][j] > 0) {
                for (int k = 0; k < l[i][j]; k++) {
                    vector<int> line;
                    line.assign(l.size(), 0);
                    line[i] = 1;
                    line[j] = 1;
                    t.push_back(line);
                    l[i][j]--;
                    l[j][i]--;
                }
            }
        }
    }
    return t;
}

//获得det[i][j]余子式行列式
vector<vector<int> > complementMinor(vector<vector<int>> det, int i, int j) {

    int n = det.size();//n为det的行,m为det的列;
    vector<vector<int>> ans(n - 1);//保存获得的结果
    for (int k = 0; k < n - 1; k++)
        for (int l = 0; l < n - 1; l++) {
            ans[k].push_back(det[k < i ? k : k + 1][l < j ? l : l + 1]);
        }
    return ans;
}

int Det(vector<vector<int>> det) {
    int ans = 0;
    int n = det.size(), m = det[0].size();//n为det的行,m为det的列;
    if (n != m) {
        exit(1);
    }
    if (det.size() == 1)
        return det[0][0];

    for (int i = 0; i < m; i++) {
        ans += det[0][i] * pow(-1, i) * Det(complementMinor(det, 0, i));
    }
    return ans;
}

int treeNum(vector<vector<int>> l) {
    vector<vector<int>> m;
    for (int i = 1; i < l.size(); i++) {
        vector<int> t;
        for (int j = 1; j < l.size(); j++) {
            if (i == j) {
                int sum = 0;
                for (int k: l[j]) {
                    sum += k;
                }
                t.push_back(sum);
            } else {
                t.push_back(-l[i][j]);
            }
        }
        m.push_back(t);
    }
    return Det(m);
}

void
tree(vector<vector<int>> l, vector<vector<int>> &xianglin, vector<vector<int>> &guanlian, vector<unsigned int> &bian) {
    for (int i = 1; i < 1 << l.size(); i++) {
        bian.clear();
        int n = 0;
        unsigned int x = i, place = 0;
        while (x) {
            if (x & 0x1) {
                bian.push_back(place);
                n++;
            }
            x >>= 1;
            place++;
        }
        if (n == l[0].size() - 1) {
            // 去除第一行判断矩阵是否满秩
            vector<vector<int>> matrix;
            for (auto j: bian) {
                vector<int> t;
                for (int k = 1; k < l[j].size(); k++) {
                    t.push_back(l[j][k]);
                }
                matrix.push_back(t);
            }
            if (Det(matrix) != 0) break;
        }
    }
    // 计算关联矩阵
    for (auto x: bian) {
        guanlian.push_back(l[x]);
    }
    for (int i = 0; i < l[0].size(); i++) {
        vector<int> t;
        t.assign(l[0].size(), 0);
        xianglin.push_back(t);
    }
    // 计算相邻矩阵
    for (auto i: guanlian) {
        vector<int> e;
        for (int j = 0; j < i.size(); j++) {
            if (i[j] == 1) e.push_back(j);
            if (e.size() == 2) break;
        }
        xianglin[e[0]][e[1]] = 1;
        xianglin[e[1]][e[0]] = 1;
    }
}

struct Node {
    Node *parent;
    int num;
};

vector<unsigned int> bfs_loop(const vector<vector<int>> &tree, int start, int end) {
    vector<bool> visited;
    visited.assign(tree.size(), false);
    visited[start] = true;
    vector<Node> points;
    for (int i = 0; i < tree.size(); i++) {
        Node t{nullptr, i};
        points.push_back(t);
    }
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < tree.size(); i++) {
            if (tree[now][i] == 1 && !visited[i]) {
                points[i].parent = &points[now];
                q.push(i);
                visited[i] = true;
            }
        }
        if (now == end) break;
    }
    vector<unsigned int> road;
    road.push_back(end);
    while (points[end].parent) {
        end = points[end].parent->num;
        road.insert(road.begin(), end);
    }
    return road;
}

vector<vector<int>> loop(const vector<vector<int>> &xianglin, vector<vector<int>> guanlian, vector<unsigned int> bian) {
    vector<unsigned int> xian;
    for (int i = 0; i < guanlian.size(); i++) {
        if (!count(bian.begin(), bian.end(), i)) {
            xian.push_back(i);
        }
    }
    vector<vector<unsigned int>> points;
    for (auto x: xian) {
        vector<unsigned int> e;
        for (int i = 0; i < guanlian[0].size(); i++) {
            if (guanlian[x][i] == 1) {
                e.push_back(i);
            }
        }
        vector<unsigned int> t = bfs_loop(xianglin, e[0], e[1]);
        t.push_back(e[0]);
        points.push_back(t);
    }
    vector<vector<int>> result;
    for (auto x: points) {
        int n = 1;
        vector<int> t;
        while (n < x.size()) {
            vector<int> m;
            m.assign(guanlian[0].size(), 0);
            m[x[n - 1]] = 1;
            m[x[n]] = 1;
            for (int i = 0; i < guanlian.size(); i++) {
                if (guanlian[i] == m) {
                    t.push_back(i);
                    break;
                }
            }
            n++;
        }
        result.push_back(t);
    }
    return result;
}

bool liantong(vector<vector<int>> matrix) {
    vector<bool> visited;
    visited.assign(matrix.size(), false);
    visited[0] = true;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < matrix.size(); i++) {
            if (matrix[now][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    for (auto x: visited) {
        if (!x) return false;
    }
    return true;
}

vector<vector<int>>
geji(vector<vector<int>> xianglin, vector<vector<int>> guanlian, vector<unsigned int> bian) {
    vector<unsigned int> xian;
    for (int i = 0; i < guanlian.size(); i++) {
        if (!count(bian.begin(), bian.end(), i)) {
            xian.push_back(i);
        }
    }
    vector<vector<int>> result;
    for (auto x: bian) {
        vector<vector<int>> t(xianglin.begin(), xianglin.end());
        vector<int> e;
        for (int i = 0; i < guanlian[0].size(); i++) {
            if (guanlian[x][i] == 1) {
                e.push_back(i);
            }
        }
        t[e[0]][e[1]] = 0;
        t[e[1]][e[0]] = 0;
        vector<int> edge;
        edge.push_back(x);
        for (auto y: xian) {
            // 添加一条弦
            e.clear();
            for (int i = 0; i < guanlian[0].size(); i++) {
                if (guanlian[y][i] == 1) {
                    e.push_back(i);
                }
            }
            t[e[0]][e[1]] = 1;
            t[e[1]][e[0]] = 1;
            if (liantong(t)) {
                edge.push_back(y);
                t[e[0]][e[1]] = 0;
                t[e[1]][e[0]] = 0;
            }
        }
        result.push_back(edge);
    }
    return result;
}

vector<vector<int>> space(const vector<vector<int>> &circles) {
    vector<unsigned int> selected;
    vector<vector<int>> result;
    for (int i = 1; i < 1 << circles.size(); i++) {
        selected.clear();
        unsigned int x = i, place = 0;
        while (x) {
            if (x & 0x1) {
                selected.push_back(place);
            }
            x >>= 1;
            place++;
        }
        vector<int> t(circles[selected[0]].begin(), circles[selected[0]].end());
        selected.erase(selected.begin());
        for (auto e: selected) {
            for (auto each: circles[e]) {
                if (count(t.begin(), t.end(), each)) {
                    for (auto it = t.begin(); it != t.end();) {
                        if (*it == each) {
                            it = t.erase(it);
                        } else {
                            it++;
                        }
                    }
                } else {
                    t.push_back(each);
                }
            }
        }
        result.push_back(t);
    }
    return result;
}

int main() {
    int n, t;
    cout << "请输入点的个数:" << endl;
    cin >> n;
    cout << "请输入矩阵" << endl;
    vector<vector<int>> m;
    for (int i = 0; i < n; i++) {
        vector<int> temp;
        for (int j = 0; j < n; j++) {
            cin >> t;
            temp.push_back(t);
        }
        m.push_back(temp);
    }
    vector<vector<int>> g = guanlianMatrix(m);
    cout << "关联矩阵为:" << endl << "   ";
    for (int i = 0; i < g.size(); i++) {
        cout << "e" << i << "\t";
    }
    cout << endl;
    for (int i = 0; i < g[0].size(); i++) {
        cout << "v" << i << "  ";
        for (auto &j: g) {
            cout << j[i] << "\t";
        }
        cout << endl;
    }
    cout << "共有" << treeNum(m) << "颗树" << endl;
    vector<vector<int>> xianglin, guanlian;
    vector<unsigned int> bian;
    tree(g, xianglin, guanlian, bian);
    cout << "生成树的相邻矩阵为:" << endl << "   ";
    for (int i = 0; i < xianglin.size(); i++) {
        cout << "v" << i << "\t";
    }
    cout << endl;
    for (int i = 0; i < xianglin[0].size(); i++) {
        cout << "v" << i << "  ";
        for (auto &j: xianglin) {
            cout << j[i] << "\t";
        }
        cout << endl;
    }
    cout << "生成树关联矩阵为:" << endl << "   ";
    for (auto x: bian) {
        cout << "e" << x << "\t";
    }
    cout << endl;
    for (int i = 0; i < guanlian[0].size(); i++) {
        cout << "v" << i << "  ";
        for (auto &j: guanlian) {
            cout << j[i] << "\t";
        }
        cout << endl;
    }
    cout << "基本回路系统为:" << endl << "{ ";
    vector<vector<int>> circle = loop(xianglin, g, bian);
    for (int i = 0; i < circle.size(); i++) {
        for (int j = 0; j < circle[i].size(); j++) {
            cout << "e" << circle[i][j];
            if (j == circle[0].size() - 1 && i != circle.size() - 1) cout << ", ";
        }
    }
    cout << " }" << endl;

    vector<vector<int>> huanlu = space(circle);
    cout << "环路空间为:" << endl << "{ Φ ,";
    for (int i = 0; i < huanlu.size(); i++) {
        for (int j = 0; j < huanlu[0].size(); j++) {
            cout << "e" << huanlu[i][j];
            if (j == huanlu[0].size() - 1 && i != huanlu.size() - 1) cout << ", ";
        }
    }
    cout << " }" << endl;

    cout << "基本割集系统为:" << endl << "{ ";
    vector<vector<int>> gj = geji(xianglin, g, bian);
    for (int i = 0; i < gj.size(); i++) {
        cout << "{ ";
        for (int j = 0; j < gj[i].size(); j++) {
            if (j == gj[i].size() - 1) {
                cout << "e" << gj[i][j] << " } ";
                if (i != gj.size() - 1) cout << ",";
            } else {
                cout << "e" << gj[i][j] << ",";
            }
        }
    }
    cout << " }" << endl;

    cout << "断集空间为:" << endl << "{ Φ ,";
    vector<vector<int>> dj = space(gj);
    for (int i = 0; i < dj.size(); i++) {
        cout << "{ ";
        for (int j = 0; j < dj[i].size(); j++) {
            if (j == dj[i].size() - 1) {
                cout << "e" << dj[i][j] << " } ";
                if (i != dj.size() - 1) cout << ",";
            } else {
                cout << "e" << dj[i][j] << ",";
            }
        }
    }
    cout << " }" << endl;
    system("pause");
    return 0;
}

到了这里,关于OUC离散数学II实验二(Python+Cpp)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《离散数学》实验报告HEBUT

    《离散数学》是现代数学的一个重要分支,是计算机科学与技术专业的基础理论课,也是该专业的核心课程和主干课程。“离散数学”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。该课程一方面为后继课程如数据结构、编绎原理、操作

    2024年02月09日
    浏览(65)
  • 离散数学实验三 · 最短路径计算

    一、实验目的 通过本实验的学习理解Dijkstra算法,并且编码实现最短路径问题。 二、实验内容 Dijkstra算法的理解; 算法概念:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,之后每求得一条最

    2024年02月03日
    浏览(36)
  • 离散数学实验----中国邮递员问题

    实验目的和要求 实验目的: 理解什么是欧拉图,熟悉欧拉路和欧拉回路的概念。 掌握Dijkstra算法,求解最短路径 掌握Fleury算法,求解欧拉回路。 了解Edmonds-Johnson算法解决中国邮递员问题的基本思路。 通过程序实现中国邮递员问题,强化其基本思想和实际应用。 实验要求:

    2023年04月12日
    浏览(38)
  • NEFU离散数学实验2-容斥原理

    相关概念  离散数学中的容斥原理是一种使用集合运算的技巧,通常用于计算两个或更多集合的并集或交集的大小。以下是一些与容斥原理相关的常见概念和公式。 概念: 1. 集合:由元素组成的对象,通常用大写字母表示,如A、B、C等。 2. 元素:集合中的单个对象,通常用

    2024年02月07日
    浏览(76)
  • NEFU离散数学实验特别篇1-树和图

    离散数学中,树是一种重要的数据结构,它是一种无向连通图,并且不存在环。下面是树的相关概念和公式: 1. 顶点数为n的树,边数为n-1。 2. 度数为k的树中有k个分支。 3. 一棵树中最多只有两个度数大于1的顶点,这些顶点称为树的端点或叶子,其余顶点称为分支或内部点。

    2024年02月06日
    浏览(40)
  • 南邮|离散数学实验四(图的生成及欧拉(回)路的确定)

    内容:随机生成含指定节点数量 n 的无向连通图,并确定其中有无欧拉 ( 回 ) 路,若有则需要获取至少一条路径并输出。 要求:能随机生成无向连通图并正确判断其是否为 ( 半 ) 欧拉图,若是欧拉图,则还需输出至少一条欧拉 ( 回 ) 路。      

    2024年01月24日
    浏览(39)
  • Python实现离散选择Logit模型(Logit算法)项目实战

    说明:这是一个机器学习实战项目(附带 数据+代码+文档+视频讲解 ),如需 数据+代码+文档+视频讲解 可以直接到文章最后获取。 Logit模型(Logit model,也译作“评定模型”,“分类评定模型”,又作Logistic regression,“逻辑回归”)是离散选择法模型之一,属于多重变量分析

    2024年01月21日
    浏览(34)
  • Python实现离散选择多项式对数模型(MNLogit算法)项目实战

    说明:这是一个机器学习实战项目(附带 数据+代码+文档+视频讲解 ),如需 数据+代码+文档+视频讲解 可以直接到文章最后获取。 多项式对数模型是离散选择模型的一种。 本项目通过MNLogit算法来构建多项式对数模型。   本次建模数据来源于网络(本项目撰写人整理而成),数

    2024年01月23日
    浏览(49)
  • Python实现离散选择负二项式模型(NegativeBinomial算法)项目实战

    说明:这是一个机器学习实战项目(附带 数据+代码+文档+视频讲解 ),如需 数据+代码+文档+视频讲解 可以直接到文章最后获取。 离散选择负二项式模型是一种统计和经济计量模型,它结合了离散选择理论与负二项分布的特点来分析计数型的离散决策变量。在实际应用中,

    2024年01月21日
    浏览(38)
  • 基于改进的离散PSO算法的FJSP的研究(Python代码实现)

    💥 💥 💞 💞 欢迎来到本博客 ❤️ ❤️ 💥 💥 🏆 博主优势: 🌞 🌞 🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳ 座右铭: 行百里者,半于九十。 📋 📋 📋 本文目录如下: 🎁 🎁 🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Python代码实现 文

    2024年02月09日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包