Числовые характеристики графов

Размещено на http://www.allbest.ru/

Числовые характеристики графов

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Раскраска графа

Раскраска вершин графа 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-раскрашиваем.

3. Раскраска карт

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

Проблема четырех красок

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

Стивен Барр предложил логическую игру для двух игроков, названную "Четыре краски". По словам Мартина Гарднера - "Я не знаю лучшего способа понять трудности, которые встречаются на пути решения проблемы четырёх красок, чем просто поиграть в эту любопытную игру".

Квадрат разбит на несколько квадратов (в основном 4x4), и его стороны окрашены каждая в один из четырёх различных цветов. Первым ходом закрашивается квадрат прилегающий к стороне, каждый последующий ход можно закрашивать тот квадрат, который прилегает к одному из закрашенных квадратов. Нельзя закрашивать квадрат теми цветами, которыми закрашен один из прилегающих к нему квадратов (в том числе и по диагонали) или прилегающая к квадрату сторона. Выигрывает игрок, делающий последний ход.

Гипотеза о том, что всякую карту можно раскрасить четырьмя красками, была сформулирована Фрэнсисом Гутри (англ.) в 1852 году, однако доказать ее долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок.

Теорема о четырёх красках, подтвердившая верность гипотезы Гутри, была доказана только в 1976 году Кеннетом Аппелем (англ.) и Вольфгангом Хакеном (англ.) из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера.

Число внутренней устойчивости, или число независимости, есть наибольшее число попарно несмежных вершин графа G (при этом попарно несмежные вершины графа G образуют внутренне устойчивое множество).

Для графов, изображенных на рисунке, имеем следующие числа внутренней устойчивости. (G1)=1, т.к. любая пара вершин G1 является смежной. Граф G2 имеет два внутренне устойчивых множества S1={x1,x3}, S2={x4,x2}. Так как, |S1|=|S2|=2, то, следовательно, (G2)=2. Граф G3 содержит внутренне устойчивые множества S1={x1,x5}, S2={x1,x3}, S3={x1,x4}, S4={x2,x5},S5={x2,x4}.

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

4. Нахождение множеств внутренней устойчивости

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

Классический пример, задача о восьми ферзях: Как расставить на шахматной доске восемь ферзей, чтобы они не били друг друга. То есть построить граф с 64 вершинами (клеточками), где каждая клеточка соединена с клеточками, которые находятся под боем.

Максимальные множества несмежных вершин и дают решение этой задачи.

Долго эта задача была классическим полигоном для систем искусственного интеллекта, как творческая задача, использующая нестрогие (эвристические) методы.

Последние годы ситуация изменилась.

Для нахождения таких множеств появился замечательный алгоритм Магу, который,

Фактически дает аналитическое (!) решение этой задачи.

5. Алгоритм Магу

Рассмотрим граф, заданный матрицей смежности:

1. По единицам матрицы строим парные дизъюнкты.

(а b)(a c)(b e)(c f)(d b)(d e)(e c)(f b)(f d)(f e)

2. Преобразуем в ДНФ, выполнив все возможные поглощения и операции идемпотентности.

Получим:

bcde bcef adef afeb fbdc

3. Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.

{ a, f }, { a, d }, { a, e }, { b, c }, { c, d }

Максимальное из таких множеств дает число внутренней устойчивости (здесь оно равно 2).

Пример: 1) Составим матрицу смежности:

2) Составим парные дизъюнкты (a b)(a c)(a e)(b d)(d e)

3) Преобразуем полученное выражение (a bce)(d be) ad abe bcde bcead abe bce.

4) Выпишем множества внутренней устойчивости: {b, c, e}, {c, d}, {a, d}.

5) Получаем число внутренней устойчивости графа (G) =|{b, c, e} | =3.

Примеры множеств внутренней устойчивости:

· задача непоражающего размещения 8 ферзей на шахматной доске (симметричный граф с 64 вершинами; 92 решения - 76 были найдены Гауссом),

· задача о 15 девушках, которых можно водить на прогулку тройками, в которые каждая пара попадает не более одного раза, - (G) = 35 при C315 = 455 тройках

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

Определим число внешней устойчивости для данных графов. Любая пара вершин графа G1 образует внешне устойчивое множество, но любая его вершина не является внешне устойчивым множеством, следовательно, b(G1)=2. Граф G2 содержит два внешне устойчивых множества T1={x1,x3}, T2={x2,x4} с минимальным числом элементов, т.е. b(G2)=2. Для графа G3 внешне устойчивым множеством минимальной мощности является T={x2,x5}, т.е. b(G3)=2.

Примеры чисел внешней устойчивости:

· сколько можно поставить ферзей или других фигур, чтобы все поля доски были под ударом (5 ферзей, 8 ладей или слонов, 12 коней).

· сколько наблюдателей поставить на пересечениях улиц, чтобы все перекрестки были под присмотром.

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

Нужно выяснить, каково минимальное число часовых, необходимых для наблюдения за всеми объектами.

Граф, изображенный на рисунке, соответствует следующей задаче: 9 вершин графа - охраняемые объекты (n=9), ребра характеризуют возможность просматривания объектов часовыми. Так, например, часовой у объекта X1 может одновременно наблюдать за объектами X2,X3,X4,X6,X9, часовой у объекта X2 - за объектами X1,X3,X7,X8 и т.д. Для данного графа число внешней устойчивости равно 2. Внешне устойчивое множество образуют вершины X4,X8. Достаточно двух часовых, расположенных в точках X4 и X8, для охраны всех объектов.

6. Алгоритм Магу поиска внешне устойчивых множеств

1) Составим матрицу смежности графа, дополнив ее единицами на главной диагонали:

2) По единицам таблицы составим дизъюнкты:

3) Полученные конъюнкции и составят множества внешней устойчивости:

4) Мощность минимального из них и дает число внешней устойчивости: ?(G)=2

Размещено на Allbest.ru