🔎 Как перевести матрицу смежности в матрицу инцидентности на Python

Как перевести матрицу смежности в матрицу инцидентности в Python?

Для того чтобы перевести матрицу смежности в матрицу инцидентности в Python, можно использовать следующий код:

# Предполагаем, что матрица смежности уже определена
matrix = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

# Определяем количество вершин и ребер
num_vertices = len(matrix)
num_edges = sum(sum(row) for row in matrix) // 2

# Инициализируем матрицу инцидентности
inc_matrix = [[0] * num_edges for _ in range(num_vertices)]

# Заполняем матрицу инцидентности
edge_counter = 0
for i in range(num_vertices):
    for j in range(i+1, num_vertices):
        if matrix[i][j] == 1:
            inc_matrix[i][edge_counter] = 1
            inc_matrix[j][edge_counter] = 1
            edge_counter += 1
  
# Выводим матрицу инцидентности
for row in inc_matrix:
    print(row)

Как вы видите, мы сначала определяем количество вершин и ребер в матрице смежности. Затем инициализируем матрицу инцидентности, которая будет иметь размерность "количество вершин x количество ребер". Затем мы перебираем пары вершин и проверяем, есть ли между ними ребро. Если да, мы помечаем соответствующие элементы в матрице инцидентности. В конце выводим полученную матрицу инцидентности.

Как перевести матрицу смежности в матрицу инцидентности в Python

Матрица смежности и матрица инцидентности - это два важных представления графов, которые можно использовать для анализа связей между вершинами. Если у вас есть матрица смежности графа и вы хотите перевести ее в матрицу инцидентности, вам потребуется немного программирования на Python. Давайте рассмотрим, как это можно сделать.

Предположим, у нас есть следующая матрица смежности:

adjacency_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]
]

Наша цель - создать матрицу инцидентности, которая будет представлять все ребра графа. Мы можем начать создавать пустую матрицу инцидентности с нулевыми значениями:

num_vertices = len(adjacency_matrix)
num_edges = sum(sum(row) for row in adjacency_matrix) // 2

incidence_matrix = [[0] * num_edges for _ in range(num_vertices)]

Мы используем двойной список с размером, равным количеству вершин в матрице смежности и количеству ребер в графе. Значения матрицы инцидентности устанавливаются в ноль для начала.

Теперь мы можем начать заполнять матрицу инцидентности, исходя из матрицы смежности. Мы будем использовать циклы для обхода каждой вершины и каждого ребра и устанавливать значения в матрице инцидентности в зависимости от наличия ребер между вершинами.

edge_index = 0

for i in range(num_vertices):
    for j in range(i + 1, num_vertices):
        if adjacency_matrix[i][j] == 1:
            incidence_matrix[i][edge_index] = 1
            incidence_matrix[j][edge_index] = 1
            edge_index += 1

Мы используем два цикла для перебора каждой пары вершин. Если есть ребро между вершинами, мы устанавливаем значения в матрице инцидентности в единицу для соответствующих вершин и ребра.

После выполнения этого кода, у нас будет матрица инцидентности, представляющая граф, исходя из матрицы смежности. Вы можете распечатать это, чтобы убедиться:

for row in incidence_matrix:
    print(row)

Вот полный код:

adjacency_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]
]

num_vertices = len(adjacency_matrix)
num_edges = sum(sum(row) for row in adjacency_matrix) // 2

incidence_matrix = [[0] * num_edges for _ in range(num_vertices)]

edge_index = 0
for i in range(num_vertices):
    for j in range(i + 1, num_vertices):
        if adjacency_matrix[i][j] == 1:
            incidence_matrix[i][edge_index] = 1
            incidence_matrix[j][edge_index] = 1
            edge_index += 1

for row in incidence_matrix:
    print(row)

Теперь вы знаете, как перевести матрицу смежности в матрицу инцидентности с помощью Python. Это полезный способ представления графов и может быть использован в различных алгоритмах и задачах анализа сетей.