Задание №1. Задан неориентированный граф. Для получившегося графа: 1. Самостоятельно назвать вершины и рёбра. 2. Записать матрицу инцидентности. 3. Записать матрицу смежности. 4. Задать граф с помощью списка ребер и вершин. 5. Определить вид графа. 6. Найти наибольшую степень вершины графа. 7. Перерисовать заданный граф, произвольно расставить направления, чтобы получить ориентированный граф. Для полученного ориентированного графа записать матрицу инцидентности и матрицу смежности.

Разберем задачу по пунктам:

1. Самостоятельно назвать вершины и рёбра.

   Обозначим вершины графа латинскими буквами: A, B, C, D. Обозначим ребра цифрами: 1, 2, 3, 4, 5.

2. Записать матрицу инцидентности.

   Матрица инцидентности показывает связь между вершинами и ребрами. Строки соответствуют вершинам, столбцы - ребрам. Если ребро инцидентно вершине, ставим 1, иначе 0.

   	1	2	3	4	5
   A	1	1	0	0	0
   B	1	0	1	0	0
   C	0	1	0	1	1
   D	0	0	1	1	0

3. Записать матрицу смежности.

   Матрица смежности показывает связь между вершинами. Строки и столбцы соответствуют вершинам. Если между вершинами есть ребро, ставим 1, иначе 0. Для неориентированного графа матрица симметрична.

   	A	B	C	D
   A	0	1	1	0
   B	1	0	0	1
   C	1	0	0	1
   D	0	1	1	0

4. Задать граф с помощью списка ребер и вершин.

   Вершины: A, B, C, D

   Ребра: 1(A, B), 2(A, C), 3(B, D), 4(C, D), 5(C,C)

5. Определить вид графа.

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

6. Найти наибольшую степень вершины графа.

   Степень вершины - количество инцидентных ей ребер. Вершина C имеет степень 4 (ребра 2, 4, 5 и петля считается дважды), вершина А имеет степень 2, вершина B имеет степень 2, вершина D имеет степень 2.

   Наибольшая степень вершины графа: 4 (вершина C).

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

   Предположим, что мы задали следующие направления ребрам: 1(A -> B), 2(C -> A), 3(B -> D), 4(C -> D), 5(C->C)

   Матрица инцидентности для ориентированного графа:

   	1	2	3	4	5
   A	-1	1	0	0	0
   B	1	-1	-1	0	0
   C	0	-1	0	-1	1
   D	0	0	1	1	0

   Матрица смежности для ориентированного графа:

   	A	B	C	D
   A	0	1	0	0
   B	0	0	0	1
   C	1	0	1	1
   D	0	0	0	0