Как представить матрицу инцидентности в алгебраической форме?

Question

К примеру, имеется граф в алгебраической форме: (1,2),(1,3),(2,3). Я написал небольшой код для нахождения матрицы инцидентности для этого графа. Теперь мне бы хотелось сделать все наоборот. Из матрицы инцидентности представить граф в алгебраической форме. Как бы это реализовать?

Вот мой код, который показывает матрицу инцидентности:

if __name__ == '__main__':
    count_reber = int(input('Введите кол-во ребер: '))
    count_vershin = int(input('Введите кол-во вершин: '))

    list_reber = []

    for i in range(count_reber):
        rebro = str(input(f'Введите ребро {i+1}, пример 0,0: ')).split(',')
        list_reber.append([int(rebro[0]),int(rebro[1])])

    for i in range(count_reber):
        print(f'({list_reber[i][0]},{list_reber[i][1]})')

    matrix = [[0] * count_vershin for i in range(count_reber)]

    for i in range(count_reber):
        for j in range(count_vershin):
            # print(type(list_reber[i][0]),type(list_reber[i][1]),type(j))
            if list_reber[i][0] == j+1 or list_reber[i][1] == j+1:
                matrix[i][j] = 1
            else:
                matrix[i][j] = 0

    print(matrix)
    for i in range(count_reber):
        for j in range(count_vershin):
            print(matrix[i][j], end=' ')
        print()

Ввожу так:

Answer 1

Для неориентированного графа. В каждом столбце будет только две единицы или одна в случае петли. Добавляем номера строк +1 в список temp - это будет ребро -> добавляем ребра в общий список рёбер

matrix = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
algForm = []
for i in range(len(matrix[0])):
    temp = []
    for j in range(len(matrix)):
        if matrix[j][i] == 1:
            temp.append(j + 1)
    if len(temp) == 1: # проверка на петлю
        temp.append(temp[0])
    algForm.append(tuple(temp))
print(*algForm)

БЛОГ НА HUSL

Как представить матрицу инцидентности в алгебраической форме?

Ответы (1 шт):