Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6} задан списком дуг {(1, 6), (2, 1), (2, 5), (3, 1), (3, 3), (3, 5), (3, 2), (3, 6), (5, 1), (5, 6), (6, 4), (6,…

Для реализации ориентированного графа, заданного множеством вершин \( V = \{1, 2, 3, 4, 5, 6\} \) и списком дуг \( \{(1, 6), (2, 1), (2, 5), (3, 1), (3, 3), (3, 5), (3, 2), (3, 6), (5, 1), (5, 6), (6, 4), (6, 5)\} \), можно использовать структуру данных, например, список смежности или матрицу смежности.

1. Список смежности

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

# Реализация графа с помощью списка смежности
graph = {
    1: [6],
    2: [1, 5],
    3: [1, 3, 5, 2, 6],
    4: [],
    5: [1, 6],
    6: [4, 5]
}

# Вывод графа
for vertex, edges in graph.items():
    print(f'Вершина {vertex}: {" -> ".join(map(str, edges))}')

2. Матрица смежности

Для матрицы смежности мы создадим двумерный массив, где строки и столбцы будут представлять вершины, а ячейки, содержащие 1, будут указывать на наличие ребра. Так как у нас 6 вершин, матрица будет размером \( 6 \times 6 \).

# Реализация графа с помощью матрицы смежности
num_vertices = 6
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

edges = [(1, 6), (2, 1), (2, 5), (3, 1), (3, 3), (3, 5), (3, 2), (3, 6), (5, 1), (5, 6), (6, 4), (6, 5)]

# Заполняем матрицу смежности
for (u, v) in edges:
    adj_matrix[u - 1][v - 1] = 1  # уменьшаем на 1 для индексации с 0

# Вывод матрицы смежности
for row in adj_matrix:
    print(row)

Пояснения:

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

Выберите подходящий метод для реализации вашего графа в зависимости от ваших нужд!