Теория графов

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

4. С421

Решение:

Переведем данное число в двоичную систему счисления:

Тогда матрица смежности графа с 5 вершинами без петель:

Построим данный граф:

Степени вершин равны числу инцидентных данной вершине ребер. Тогда степень вершины 1 равна 2; вершины 2 равна 2; вершины 3 равна 3; вершины 4 равна 2; вершины 5 равна 1.

Цикломатическое число графа – минимальное число ребер, которые нужно удалить, чтобы получить граф без циклов. Очевидно, что в данном примере достаточно удалить ребро между 2 и 3, чтобы получить граф без циклов. Итак, цикломатическое число данного графа равно 1

Хроматическое число графа – минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые 2 вершины соединенные ребром раскрашены в разные цвета. Количество цветом определяется максимальной степенью вершины, т.е. в данном случае это число равно 3:

Матрица инцидентности (число строк равно количеству вершин, а число ребер равно числу столбцов):

.

2) Построить граф своего микрорайона, отметив направление ребер для улиц с односторонним движением. Преобразовать полученный граф в орграф. Можно ли проложить путь между любыми двумя его вершинами, не нарушая установленных направлений движения транспорта и не выезжая за пределы района? На построенном графе приблизительно указать расстояния между смежными вершинами. Найти кратчайшие маршруты, соединяющие интересующие вершины. Существует ли эйлеров цикл для построенного графа, и что он означает? Если для полученного графа существует гамильтонов цикл, найти его.

Решение:

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

Кратчайшее расстояние между вершинами 4 и 1 равно 8+15=23; между 4 и 3 равно 3+8=11.

Эйлеров цикл не существует (он означал бы, что можно пройти по всем дорогам по одному разу) – из вершин 6 и 8 нет дорог внутри микрорайона.

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