Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7) задан списком дуг ((1, 2), (1, 4), (1, 5), (2, 4), (3, 2), (3, 4), (3, 4), (4, 2), (4, 5), (5, 5).(5, 7), (7,…
Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7) задан списком дуг ((1, 2), (1, 4), (1, 5), (2, 4), (3, 2), (3, 4), (3, 4), (4, 2), (4, 5), (5, 5).(5, 7), (7, 1)), Построить реализацию графа, матрицу инцидентности и матрицы соседства вершин ориентированного и соответственного ему неориентированного графов. Го
Чтобы решить задачу, начнем с построения графа G, заданного списком дуг, и дальше перейдем к созданию матрицы инцидентности и матрицы соседства как для ориентированного, так и для неориентированного графов.
Шаг 1: Построение графа
Наш ориентированный граф G задан следующим образом:
- Вершины: \( V = \{1, 2, 3, 4, 5, 6, 7\} \)
- Дуги:
- \( (1, 2) \)
- \( (1, 4) \)
- \( (1, 5) \)
- \( (2, 4) \)
- \( (3, 2) \)
- \( (3, 4) \)
- \( (4, 2) \)
- \( (4, 5) \)
- \( (5, 5) \)
- \( (5, 7) \)
- \( (7, 1) \)
На основе этого мы можем визуально изобразить граф, но для наших целей важнее составить матрицы.
Шаг 2: Матрица инцидентности
Матрица инцидентности \( M \) имеет строки, представляющие вершины, и столбцы, представляющие дуги. Если вершина инцидентна дуге, то в соответствующей ячейке будет стоять \( 1 \), в противном случае — \( 0 \).
Сначала определим количество дуг, которое равно \( 11 \) (по количеству указанных пар):
| (1,2) | (1,4) | (1,5) | (2,4) | (3,2) | (3,4) | (4,2) | (4,5) | (5,5) | (5,7) | (7,1) | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 5 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Шаг 3: Матрица соседства
Матрица соседства \( A \) имеет строки и столбцы, принадлежащие вершинам. Если существует дуга от вершины \( i \) к вершине \( j \), то \( A[i][j] = 1 \), в противном случае — \( 0 \).
Матрица соседства будет выглядеть так:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Шаг 4: Неориентированный граф
Чтобы получить неориентированный граф, просто удаляем направление. Мы представим неориентированный граф, добавляя дуги в обе стороны. Так, мы получим следующий список ребер:
- \( (1, 2) \)
- \( (1, 4) \)
- \( (1, 5) \)
- \( (2, 4) \)
- \( (3, 2) \)
- \( (3, 4) \)
- \( (4, 2) \)
- \( (4, 5) \)
- \( (5, 5) \)
- \( (5, 7) \)
- \( (7, 1) \)
Новые пары не изменятся, но в матрицах инцидентности и соседства будут все рёбра дублироваться.
Матрица инцидентности для неориентированного графа
Так как в неориентированном графе каждая сторона дублируется, мы получим следующую матрицу инцидентности:
(Здесь просто добавим столбцы для обратных рёбер)
Матрица соседства для неориентированного графа
Матрица соседства также будет, как и раньше, но обе стороны будут учитываться:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 5 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
Таким образом, мы построили и представили требуемые матрицы как для ориентированного, так и неориентированного графов. Если у вас есть дальнейшие вопросы или требуется дополнительное пояснение, пожалуйста, дайте знать!
