Задание 1. Граф G = (V, X) задан множеством вершин, где V = {1, 2, 3, 4, 5, 6, 7} и списком ребер.

Для решения задачи выберем второй вариант списка ребер, так как он задает связный граф для всех вершин (вершина 5 не изолирована): X = {(4, 5), (6, 5), (7, 6), (7, 7), (7, 2), (6, 4), (2, 7), (6, 4)} a) Построение графа: представьте 7 точек на плоскости. Соедините их указанными ребрами. Обратите внимание: (7,7) — это петля на вершине 7. Ребра (6,4) встречаются дважды — это кратные ребра. b) Вид графа: это неориентированный мультиграф с петлями. - Петли: (7, 7). - Изолированные вершины: нет. - Кратные ребра: (6, 4) повторяется дважды. c) Степени вершин $deg(v)$ (количество инцидентных ребер, петля дает 2 к степени): - $deg(1) = 0$ - $deg(2) = 2$ (ребра (7,2), (2,7)) - $deg(3) = 1$ (ребро (4,3)) - $deg(4) = 3$ (ребра (4,5), (6,4), (6,4)) - $deg(5) = 2$ (ребра (4,5), (6,5)) - $deg(6) = 4$ (ребра (7,6), (6,5), (6,4), (6,4)) - $deg(7) = 4$ (ребра (7,6), (7,7) — петля дает +2, (7,2), (2,7)) d) Матрица инцидентности (строки 1-7, столбцы — ребра): Ребра: $e_1(4,5), e_2(6,5), e_3(7,6), e_4(7,7), e_5(7,2), e_6(6,4), e_7(2,7), e_8(6,4)$. | | $e_1$ | $e_2$ | $e_3$ | $e_4$ | $e_5$ | $e_6$ | $e_7$ | $e_8$ | |---|---|---|---|---|---|---|---|---| | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | | 5 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | 6 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | | 7 | 0 | 0 | 1 | 2 | 1 | 0 | 1 | 0 | e) Матрица смежности $A$ ($a_{ij}$ — количество ребер между $i$ и $j$): | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |---|---|---|---|---|---|---|---| | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | | 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | | 4 | 0 | 0 | 1 | 0 | 1 | 2 | 0 | | 5 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | | 6 | 0 | 0 | 0 | 2 | 1 | 0 | 1 | | 7 | 0 | 2 | 0 | 0 | 0 | 1 | 1 |