Question

Ориентированный граф G c множеством вершин 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)}. Построить реализацию графа.

Answer 1

Чтобы построить реализацию графа G, нужно представить его в виде матрицы смежности. Матрица смежности - это квадратная матрица, в которой на пересечении i-й строки и j-го столбца находится 1, если есть дуга из вершины i в вершину j, и 0, если дуги нет.

Для начала, создадим пустую матрицу смежности размером 6x6:
М = [[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]]

Теперь, посмотрим на каждую дугу из списка дуг и заполним матрицу смежности соответствующим образом:

- Дуга (1, 6) указывает на то, что есть дуга из вершины 1 в вершину 6. Запишем 1 в матрицу M на пересечении 1-й строки и 6-го столбца:
M[1-1][6-1] = 1
M[0][5] = 1

- Дуга (2, 1) указывает на то, что есть дуга из вершины 2 в вершину 1. Запишем 1 в матрицу M на пересечении 2-й строки и 1-го столбца:
M[2-1][1-1] = 1
M[1][0] = 1

- Дуга (2, 5) указывает на то, что есть дуга из вершины 2 в вершину 5. Запишем 1 в матрицу M на пересечении 2-й строки и 5-го столбца:
M[2-1][5-1] = 1
M[1][4] = 1

- Дуга (3, 1) указывает на то, что есть дуга из вершины 3 в вершину 1. Запишем 1 в матрицу M на пересечении 3-й строки и 1-го столбца:
M[3-1][1-1] = 1
M[2][0] = 1

- Дуга (3, 3) указывает на то, что есть дуга из вершины 3 в вершину 3. Запишем 1 в матрицу M на пересечении 3-й строки и 3-го столбца:
M[3-1][3-1] = 1
M[2][2] = 1

- Дуга (3, 5) указывает на то, что есть дуга из вершины 3 в вершину 5. Запишем 1 в матрицу M на пересечении 3-й строки и 5-го столбца:
M[3-1][5-1] = 1
M[2][4] = 1

- Дуга (3, 2) указывает на то, что есть дуга из вершины 3 в вершину 2. Запишем 1 в матрицу M на пересечении 3-й строки и 2-го столбца:
M[3-1][2-1] = 1
M[2][1] = 1

- Дуга (3, 6) указывает на то, что есть дуга из вершины 3 в вершину 6. Запишем 1 в матрицу M на пересечении 3-й строки и 6-го столбца:
M[3-1][6-1] = 1
M[2][5] = 1

- Дуга (5, 1) указывает на то, что есть дуга из вершины 5 в вершину 1. Запишем 1 в матрицу M на пересечении 5-й строки и 1-го столбца:
M[5-1][1-1] = 1
M[4][0] = 1

- Дуга (5, 6) указывает на то, что есть дуга из вершины 5 в вершину 6. Запишем 1 в матрицу M на пересечении 5-й строки и 6-го столбца:
M[5-1][6-1] = 1
M[4][5] = 1

- Дуга (6, 4) указывает на то, что есть дуга из вершины 6 в вершину 4. Запишем 1 в матрицу M на пересечении 6-й строки и 4-го столбца:
M[6-1][4-1] = 1
M[5][3] = 1

- Дуга (6, 5) указывает на то, что есть дуга из вершины 6 в вершину 5. Запишем 1 в матрицу M на пересечении 6-й строки и 5-го столбца:
M[6-1][5-1] = 1
M[5][4] = 1

Таким образом, после обработки всех дуг из списка дуг, наша матрица смежности будет выглядеть следующим образом:
М = [[0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0],
[1, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 0, 1],
[0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0]]

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