Граф g задан списком ребер (каждый элемент списка – это тройка чисел:
номера двух смежных вершин и вес ребра их соединяющего): (1,4,8), (1,5,4),
(1,6,6), (1,8,3), (2,3,1), (2,6,5), (3,8,7), (4,5,9), (4,7,2), (6,7,5), (7,8,1). требуется
6) нарисовать граф g;
7) найти степенную последовательность графа g. укажите четные и
нечетные вершины;
8) найти матрицу смежности графа g;
9) найти в графе одну простую цепь наибольшей длины;
10) постройте дополнение заданного графа;

Хорошо, давайте разберемся с каждым пунктом вопроса по порядку.

6) Нарисовать граф g:
Для этого нам нужно нарисовать вершины графа и ребра, соединяющие их. Вершины обозначаются числами, а ребра - линиями. По данным вопроса, у нас имеется следующий список ребер: (1,4,8), (1,5,4), (1,6,6), (1,8,3), (2,3,1), (2,6,5), (3,8,7), (4,5,9), (4,7,2), (6,7,5), (7,8,1).

8
/ \
4/ 2 9\ 6
/ \
4__ 5 1 __ _7__
|
3

7) Найти степенную последовательность графа g:
Степенью вершины называется количество ребер, соединяющих данную вершину с другими. Для каждой вершины графа посчитаем степень:
Вершина 1 имеет степень 4 (имеет 4 смежные вершины)
Вершина 2 имеет степень 2
Вершина 3 имеет степень 2
Вершина 4 имеет степень 3
Вершина 5 имеет степень 2
Вершина 6 имеет степень 3
Вершина 7 имеет степень 3
Вершина 8 имеет степень 4

Теперь разделим все вершины на четные и нечетные. Вершина считается четной, если ее степень является четным числом, в противном случае она считается нечетной.
Четные вершины: 2, 4, 6, 8
Нечетные вершины: 1, 3, 5, 7

8) Найти матрицу смежности графа g:
Матрица смежности - это квадратная матрица, в которой указываются значения ребер между вершинами графа. Если вершины соединены, то в матрице указывается вес ребра, иначе ставится 0.
Нумерацию вершин начнем с 1.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---------------------------------------
1 | 0 | 0 | 0 | 8 | 4 | 6 | 0 | 3 |
---------------------------------------
2 | 0 | 0 | 1 | 0 | 0 | 5 | 0 | 0 |
---------------------------------------
3 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 7 |
---------------------------------------
4 | 8 | 0 | 0 | 0 | 9 | 0 | 2 | 0 |
---------------------------------------
5 | 4 | 0 | 0 | 9 | 0 | 0 | 0 | 0 |
---------------------------------------
6 | 6 | 5 | 0 | 0 | 0 | 0 | 5 | 0 |
---------------------------------------
7 | 0 | 0 | 0 | 2 | 0 | 5 | 0 | 1 |
---------------------------------------
8 | 3 | 0 | 7 | 0 | 0 | 0 | 1 | 0 |

9) Найти в графе одну простую цепь наибольшей длины:
Простая цепь - это последовательность вершин, в которой каждая вершина соединена с предыдущей и следующей вершинами.

Для решения этого задания нужно воспользоваться алгоритмом поиска в глубину или поиска в ширину.

10) Построить дополнение заданного графа:
Дополнение графа - это граф, в котором каждое ребро отсутствует, если оно присутствовало в исходном графе, и наоборот.

Для построения дополнения заданного графа нужно создать новый граф, в котором каждая вершины из исходного графа станет вершиной дополнительного графа, а для каждой пары вершин из исходного графа, не соединенной ребром, нужно добавить ребро в дополнение графа.

Давайте я предоставлю вам изображение исходного графа, матрицу смежности и опишу алгоритм для поиска одной простой цепи наибольшей длины. Пожалуйста, если у вас есть еще вопросы, не стесняйтесь задавать.