Question

Народ все которые на аккаунте даю Неориентированный граф g (v, x) с множеством вершин v=e7 задан списком дуг Х.
X = {(1,2),(2,3),(5,3),(7,1),(7,7),(7,2),(4,4),(2,7),(5,3)};
Укажите вид графа, наличие петель и кратных рёбер степени вершин deg Ui
Постройте
1) геометрическую реализацию графа
2)матрицу инцидентности
3)матрицу смежности

Answer 1

Добрый день! Разберем ваш вопрос по шагам.

1) Вид графа:
Перед нами задан неориентированный граф g (v, x) с множеством вершин v=e7. Это значит, что у нас есть 7 вершин в графе.

2) Наличие петель и кратных ребер степени вершин:
Из списка дуг Х={(1,2),(2,3),(5,3),(7,1),(7,7),(7,2),(4,4),(2,7),(5,3)} видим, что есть петля (7,7), так как вершина 7 связана сама с собой. Кроме того, есть кратные ребра (5,3) встречается дважды. Остальные ребра не являются кратными.

3) Геометрическая реализация графа:
Построим граф с помощью рисунка, где каждая вершина будет обозначаться числом, а ребра - линиями, соединяющими вершины.
```
1 - 2 - 7
| \/
| 3
| |
4 5
```
На рисунке видно, что вершина 1 связана с вершинами 2 и 7, вершина 2 - с вершинами 1, 3 и 7, вершина 3 - с вершинами 2 и 5, вишерина 4 - с собой, вершина 5 - с вершиной 3, вершина 7 - с собой, 1 и 2.

4) Матрица инцидентности:
Матрица инцидентности состоит из вершин и ребер графа. Вершинами будут строки, а ребрами - столбцы. Если вершина i соединена ребром j, то в соответствующей ячейке i-й строки и j-го столбца будет стоять 1, в остальных ячейках - 0.
```
1 2 3 4 5 7
------------------
1 | 1 1 0 0 0 0
2 | 1 1 1 0 0 1
3 | 0 1 1 0 1 0
4 | 0 0 0 1 0 0
5 | 0 0 1 0 1 0
6 | 0 0 0 0 0 0
7 | 1 1 0 0 0 1
```
В этой матрице инцидентности 1 означает, что вершина инцидентна ребру, а 0 - нет. Например, вершина 1 инцидентна ребру 1-2, поэтому в ячейке (1,1) и (1,2) стоят 1.

5) Матрица смежности:
Матрица смежности состоит только из вершин графа. Если вершины i и j соединены, то на пересечении строки и столбца с номерами i и j ставится 1, иначе - 0.
```
1 2 3 4 5 6 7
------------------
1 | 0 1 0 0 0 0 1
2 | 1 0 1 0 0 0 1
3 | 0 1 0 0 1 0 0
4 | 0 0 0 1 0 0 0
5 | 0 0 1 0 0 0 0
6 | 0 0 0 0 0 0 0
7 | 1 1 0 0 0 0 1
```
В этой матрице смежности 1 означает, что вершины соединены, а 0 - нет. Например, вершина 1 соединена с вершинами 2 и 7, поэтому в ячейках (1,2) и (1,7) стоят 1.

Это весь ответ на данный вопрос. Если у вас есть еще вопросы, обращайтесь!