Понятие числовых характеристик графов

Числовые характеристики графов — функции, заданные на множестве графов и принимающие значения из некоторого множества чисел.

Наиболее простыми числовыми характеристиками графов являются число вершин n и число ребер m графа G.

1. Цикломатическим числом графа G называется наименьшее число ребер m, удаление которых приводит к графу без циклов;

где k — число компонент связности графа G.

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

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

Пример: Найти число компонент связности графа.

Деревом графа G называется ациклический связный подграф этого графа.

Остов графа G — дерево графа, содержащее все его вершины.

2. Плотность есть наибольшее число вершин в полном подграфе графа G.

Примеры: Найти плотность графов.

3. Хроматическое число.

Раскраска графа

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

Наименьшее значение K, для которого существует правильная K-раскраска графа G, называется Хроматическим числом графа G и обозначается ?(G).

Примеры:

• · Для простой цепи Рn хроматическое число равно 2.
• · Хроматическое число простого цикла Сn в случае четного N также равно 2, а для нечетных N — равно 3.
• · В полном графе Кn, очевидно, окраска вершин будет правильной только в случае, если все вершины раскрашены в разные цвета. Поэтому ?(Кn) = n.
• · Хроматическое число двудольного графа равно 2

К поиску правильной окраски графа и его хроматического числа сводится решение многих классических задач.

· Задача распределения оборудования Пусть V — множество работ, которые необходимо выполнить. Предположим, что для выполнения каждой работы требуется одинаковое время t и некоторые механизмы из множества механизмов М Никакие механизмы не могут быть использованы одновременно для выполнения двух и более работ.

Требуется распределить механизмы так, чтобы выполнить все работы и чтобы затраченное на это время T было минимальным.

Построим граф, соответствующий данной задаче, выбрав в качестве множества вершин V — множество работ. Если какие-то две работы требуют для их выполнения один и тот же механизм или механизмы, то соответствующие им вершины, соединим ребром, в противном случае — нет. Найдем какую-нибудь правильную раскраску полученного графа G. Тогда видно, что работы «раскрашенные в один и тот же цвет» могут выполняться одновременно. Значит минимальное время выполнения всех работ.

T = t ?(G).

Рассмотрим пример. На предприятии планируется выполнить 8 работ v1, v2,…, v8.

Для выполнения этих работ необходимы механизмы a1, a2,…, a6.

Использование механизмов для каждой из работ определяется следующей таблицей:

Ни один из механизмов не может быть использован одновременно на двух работах. Выполнение каждой работы занимает 1 час. Как распределить механизмы, чтобы суммарное время выполнения всех работ было минимальным и каково это время?

Решение.

Рассмотрим граф G, вершинами которого являются планируемые работы v1, v2, …, v8, а ребра соединяют работы, в которых участвует хотя бы один общий механизм (и которые, по этой причине, нельзя проводить одновременно). Этот граф изображен на рисунке. Вершины v1, v2, v4, v5 порождают подграф K4 графа G. Следовательно,.

?(G)4.

Цифры в скобках на рисунке указывают правильную раскраску графа G в 4 краски. Следовательно, ?(G) =4.

Таким образом, все работы можно выполнить за 4 часа. Для этого, в соответствии с найденной раскраской графа G, надо в 1-й час выполнять работы v1 и v6, во 2-й — работы v2 и v3, в 3-й — работы v4 и v8, в 4-й — работы v5 и v7.

граф число раскраска карта.

· Задача о составлении расписания формулируется и интерпретируется аналогичным образом.

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

Переведем эту задачу на язык графов. Построим граф G, в котором вершины соответствуют лекциям и две различные вершины смежны тогда и только тогда, когда соответствующие лекции не могут читаться одновременно. Очевидно, что любая правильная раскраска графа G определяет допустимое расписание (если при этой раскраске использовано k цветов, то для всякого i=1,2, …, k вершины, раскрашенные i-м цветом, дают список лекций, которые надо читать на i-й паре). И наоборот, любое допустимое расписание определяет правильную раскраску графа G.

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

Пример В студенческих группах КС-203 и КС-204 надо провести занятия по логике, математическому аппарату построения КС, и информационным технологиям (по одному занятию по каждому предмету). Занятия по каждому предмету проводятся с каждой группой отдельно. Занятия по логике и по математическому аппарату ведет преподаватель Евстифеева Г. В., по метрологии — преподаватель Петрова Л. Н., по информационным технологиям — преподаватель Блинков И. А. Найти минимальное число пар, в которые можно уложить все занятия, и составить соответствующее расписание.

Решение.

Построим граф с вершинами Л3, Л4, МА3, МА4, М3, М4, ИТ3 и ИТ4 (буква соответствует предмету, а цифра номеру группы).

Вершины Л3, Л4, МА3 и МА4 этого графа порождают в нем подграф K4. Следовательно, хроматическое число нашего графа не меньше 4. На рисунке справа указана правильная раскраска нашего графа в 4 краски. Следовательно, хроматическое число графа равно 4, т. е. все занятия можно провести за 4 пары.

Соответствующее расписание указано в таблице.

Для оценки хроматических чисел графов доказаны Теорема. Если наибольшая из степеней вершин графа равна ?, то этот граф (?+1)-раскрашиваем.

Теорема Греча. Любой не содержащий треугольников планарный граф.

3-раскрашиваем.