Условие задачи
Для заданного графа (рис. 4) найдите:
Рисунок 4 – Исходный граф
а) матрицы смежности вершин, рёбер и инцидентности;
б) вектор степеней и степенное множество;
в) максимальное независимое множество вершин;
г) радиус и диаметр;
д) мосты и точки сочленения;
е) число вершинной и рёберной связности;
ж) колоду;
з) плоское изображение, если граф планарный, или докажите его непланарность;
и) хроматическое число.
Ответ
Нумеруем рёбра (рис. 5)
Рисунок 5 Граф с нумерацией рёбер
а) матрица инциденции:
матрицы смежности вершин и рёбер:
Потяни
