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

Для примера выполним все задания для графа под номером 1. 1. Самостоятельно назвать вершины и рёбра. * Вершины: A, B, C, D * Рёбра: AB, BC, CD, DA, AC 2. Записать матрицу инцидентности. Матрица инцидентности показывает связь между вершинами и рёбрами. Строки соответствуют вершинам, столбцы - рёбрам. Если вершина инцидентна ребру, ставим 1, иначе 0. | | AB | BC | CD | DA | AC | |---|----|----|----|----|----| | A | 1 | 0 | 0 | 1 | 1 | | B | 1 | 1 | 0 | 0 | 0 | | C | 0 | 1 | 1 | 0 | 1 | | D | 0 | 0 | 1 | 1 | 0 | 3. Записать матрицу смежности. Матрица смежности показывает связь между вершинами. Строки и столбцы соответствуют вершинам. Если вершины соединены ребром, ставим 1, иначе 0. | | A | B | C | D | |---|---|- ---|---|---| | A | 0 | 1 | 1 | 1 | | B | 1 | 0 | 1 | 0 | | C | 1 | 1 | 0 | 1 | | D | 1 | 0 | 1 | 0 | 4. Задать граф с помощью списка ребер и вершин. * Вершины: {A, B, C, D} * Рёбра: {(A, B), (B, C), (C, D), (D, A), (A, C)} 5. Определить вид графа. Граф является неориентированным, связным и несвязным (есть петли или кратные ребра - нет). Это простой граф. 6. Найти наибольшую степень вершины графа. Степень вершины - это количество рёбер, инцидентных данной вершине. * Степень вершины A: 3 * Степень вершины B: 2 * Степень вершины C: 3 * Степень вершины D: 2 Наибольшая степень вершины графа: 3 7. Перерисовать заданный граф, произвольно расставить направления, чтобы получить ориентированный граф. Теперь каждое ребро будет иметь направление (стрелку). Предположим, направления будут следующими: A→B, B→C, C→D, D→A, A→C. 8. Для полученного ориентированного графа записать матрицу инцидентности и матрицу смежности. Матрица инцидентности (для ориентированного графа): | | AB | BC | CD | DA | AC | |---|----|----|----|----|----| | A | 1 | 0 | 0 | -1 | 1 | | B | -1 | 1 | 0 | 0 | 0 | | C | 0 | -1 | 1 | 0 | -1 | | D | 0 | 0 | -1 | 1 | 0 | (1 - ребро выходит из вершины, -1 - ребро входит в вершину, 0 - вершина не инцидентна ребру) Матрица смежности (для ориентированного графа): | | A | B | C | D | |---|---|---|---|---| | A | 0 | 1 | 1 | 0 | | B | 0 | 0 | 1 | 0 | | C | 0 | 0 | 0 | 1 | | D | 1 | 0 | 0 | 0 |