1. 给定无向图的各边所关联的顶点对:

(1) 确定每个顶点的度

(2) 构造这个图的关联矩阵

(3) 若将无向边改为有向边：

构造这个图的邻接矩阵

2.实验代码

(1) 确定每个顶点的度

# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2020/11/13 09:58
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : graph.py
@Version     : Version 1.0.0
@Description : TODO 离散数学实验三
@Created By  : PyCharm
"""
import numpy as np
import re
import pandas as pd


def degree(v_pattern: list, edge_set: str):
    """
    返回各顶点的度
    :param v_pattern: 各顶点的正则模式列表
    :param edge_set:无向图的各边所关联的顶点对
    :return:各顶点的度的矩阵
    """
    degree_matrix = np.zeros(len(v_pattern), dtype=np.int32)
    for index, pattern in enumerate(v_pattern):
        degree_matrix[index] = len(re.findall(pattern, edge_set))
    return degree_matrix

(2) 构造这个图的关联矩阵

def incidence_matrix(v, edge, is_direction=False):
    """
    返回无向图G=<V,E>或者有向图D=<V,E>(不能有环)的关联矩阵
    :param is_direction: 默认是无向图
    :param v: 顶点集
    :param edge: 边集
    :return: 二维标签数组
    """
    matrix = np.zeros((len(v), len(edge)), dtype=np.int32)
    data_frame = pd.DataFrame(matrix, index=v, columns=list(edge.keys()))
    direction = "无向图G"
    if is_direction:
        direction = "有向图D"
        for key, tup in edge.items():
            # e始点记为1，不关联点记为0，终点记为-1
            data_frame.loc[tup[0], key] = 1
            data_frame.loc[tup[1], key] = -1
    else:
        for key, tup in edge.items():
            # 环的关联度为2
            if tup[0] == tup[1]:
                data_frame.loc[tup[0], key] = 2
            else:
                data_frame.loc[tup[0], key] = 1
                data_frame.loc[tup[1], key] = 1
    return direction, data_frame

(3)构造这个图的邻接矩阵

def adjacent_matrix(v, digraph_edge_set):
    """
    返回有向图D=<V,E>邻接矩阵A
    :param v:顶点集
    :param digraph_edge_set:有向边集
    :return:邻接矩阵A
    """
    matrix = np.zeros((len(v), len(v)), dtype=np.int32)
    data_frame = pd.DataFrame(matrix, index=v, columns=v)
    for index, value in digraph_edge_set.items():
        data_frame.loc[index] = value
    return data_frame

3.测试(引入DataFrame数据结构方便理解)

if __name__ == '__main__':
    print("各顶点的度:{}".format(degree(v_pattern=["v1", "v2", "v3", "v4", "v5"],
                                   edge_set="{(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,"
                                            "v5),(v1,v5),(v4,v5)}")))
    V = ["v1", "v2", "v3", "v4", "v5"]
    E = {"e1": ("v1", "v1"), "e2": ("v1", "v2"), "e3": ("v1", "v5"),
         "e4": ("v2", "v5"), "e5": ("v2", "v3"),
         "e6": ("v2", "v3"), "e7": ("v4", "v5")}
    map_matrix = incidence_matrix(V, E)
    print("{}=<V,E>的关联矩阵为:\n{}".format(map_matrix[0], map_matrix[1]))
    E = {"e1": ("v2", "v1"), "e2": ("v1", "v2"), "e3": ("v2", "v4"),
         "e4": ("v3", "v4"), "e5": ("v3", "v4"), }
    map_matrix = incidence_matrix(V, E, is_direction=True)
    print("{}=<V,E>的关联矩阵为:\n{}".format(map_matrix[0], map_matrix[1]))
    e = {("v1", "v1"): 1, ("v1", "v2"): 1, ("v2", "v3"): 2, ("v2", "v5"): 1, ("v1", "v5"): 1, ("v4", "v5"): 1}
    print("邻接矩阵为:\n%s" % adjacent_matrix(V, e))

(1)确定每个顶点的度

(2)构造这个图的关联矩阵

(3)构造这个图的邻接矩阵