Главная » Все файлы » Просмотр файлов из архивов » Документы » Федоров В.Н. - Введение в теорию графов

Федоров В.Н. - Введение в теорию графов, страница 7

2017-07-12СтудИзба

Описание файла

Документ из архива "Федоров В.Н. - Введение в теорию графов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.

Онлайн просмотр документа "Федоров В.Н. - Введение в теорию графов"

Текст 7 страницы из документа "Федоров В.Н. - Введение в теорию графов"

П
олучим

Выбираем строку 4. Записываем

П
реобразуем матрицу

Выбираем строку 1. Записываем

Преобразуем матрицу

П
реобразование матрицы закончено – во всех строках и столбцах только нули.

Формируем произведение

П = С1 С2 С4 = .

После раскрытия скобок и минимизации получаем

П = .

Обозначим

П = K1 K2 K3 K4 .

Дополняющие множества вершин , , , образуют семейство независимых множеств

= , = , = , ={ .

Число внутренней устойчивости графа α(G) = 3.

8.3. Раскраска вершин графа

Раскраской вершин графа называется такое задание цветов вершин, что, если вершины соединены ребром (дугой), то они должны иметь разный цвет.

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

Составим таблицу покрытий вершин графа внутренне устойчивыми множествами (табл. 8.1). Таблица строится следующим образом.

Число строк таблицы равно мощности семейства НМВ, каждая строка обозначается именем соответствующего независимого множества вершин, число столбцов равно числу вершин графа и столбцы обозначаются именами вершин, элемент таблицы ai,j = 1, если вершина xj входит в множество , иначе ai,j = 0 (нули можно не писать).

Таблица 8.1

x1

x2

x3

x4

x5

x6

1

1

1

1

1

1

1

1

1

1

1

1

Из таблицы видно, что для окраски вершины x1 нужна краска множества или , для окраски вершины x2 нужна краска множества , для вершины x3 – нужна краска множества или , или и т.д.

Для окраски всех вершин нужны краски множеств, определяемых выражением

П’ = ( ) ( ) ( )( ).

После раскрытия скобок и минимизации получаем

П’= .

Количество элементов в П’ определяет число красок, необходимых для такой раскраски вершин, при которой смежные вершины имеют разные цвета.

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

Для данного примера (G) = 2. Вершины, входящие в , окрашиваются одной краской, например, красной (к). Вершины, входящие в , другой – белой (б). Раскраска показана на рис. 8.1.

Граф, для раскраски вершин которого достаточно двух красок, называется бихроматическим графом.

Процедура определения хроматического числа оказалась достаточно сложной. В связи с этим возникает вопрос: – А нельзя как–то по проще хотя бы оценить это число?

Ясно, что для полного графа с n вершинами (Kn) = n, так как в полном графе каждая вершина смежна со всеми другими вершинами графа. Очевидно также, что (G) = 1, когда имеем нуль граф, в котором нет связей между вершинами. О хроматическом числе произвольного графа G можно только сказать, что оно лежит в пределах r (G) n, где r – число вершин максимального полного подграфа (такой подграф называется кликой), содержащегося в графе G.

Если известны степени вершин графа, то

(G) = maxdeg(G) + 1, (*)

где maxdeg(G) – максимальная степень вершин графа.

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

(О планарных графах см. Раздел 11.)

Замечание. Если учесть оценку (*), то получается, что у планарного графа максимальная степень вершин не превосходит 4.

8.4. Алгоритм последовательной раскраски вершин графа

В простейшем случае последовательная раскраска вершин производится так:

  1. Произвольной вершине a1 графа G присвоить цвет 1.

  2. Если вершины a1,…, ai раскрашены в цветов, то новой произвольно взятой вершине ai+1 присвоить цвет, не использованный при раскраске ближайших соседей.

Для некоторых классов графов последовательная раскраска минимальна. В общем случае это не так.

Более точная последовательная раскраска производится с помощью приближенного алгоритма поиска МНМВ и сводится к следующему:

  1. С помощью приближенного алгоритма в заданном графе находим МНМВ. Вершины этого множества окрашиваем краской 1.

  2. Удаляем из графа окрашенные вершины и инцидентные им ребра.

  3. В полученном подграфе находим МНМВ и его вершины окрашиваем краской 2.

  4. Удаляем из графа окрашенные вершины и инцидентные им ребра и т.д., пока не окрасим все вершины графа.

8.5. Приближенный алгоритм поиска МНМВ

В этом алгоритме используется функция предпочтения

,

где Гv – множество вершин, смежных с v.

В основу функции предпочтения положены следующие соображения:

  • в МНМВ выгоднее включать вершины с малыми степеням (у них мало смежных вершин);

  • вершины, смежные с включаемыми в МНМВ, должны иметь максимально возможные степени.

Алгоритм поиска МНМВ:

Имеем граф G(V,E).

Обозначим максимальное независимое множество вершин графа через S, множество вершин, смежных с вершинами из S, обозначим через ГS.

  1. Положим S = . Определим для всех вершин графа значения функции предпочтения.

  2. Добавляем к S вершину v, имеющую минимальное значение функции предпочтения (если таких вершин несколько, то любую из них).

  3. Проверяем Если ДА, то КОНЕЦ, иначе повторить п. 2.

Пример. Имеем граф G(6,6) рис. 8.2. Определить МНМВ.

V = {1, 2, 3, 4, 5, 6},

S = .

Определяем значения функции предпочтения:

S = {1},

S = {1, 3},

S = {1, 3, 4},

S = {1, 3, 4, 6}, КОНЕЦ.

Р
исунок 8.2

Множество S = {1, 3, 4, 6} и есть максимальное независимое множество вершин графа.

8.6. Реберная раскраска графа

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

Для реберной раскраски имеется достаточно точная оценка требуемого числа красок в виде

,

где максимальная степень вершин графа G.

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

Для некоторых видов графов хроматический класс определяется достаточно просто, например, для графа в виде цикла с n вершинами 2 или 3 в зависимости от того, четно n или нечетно. Для двудольных полных графов = max(m, n). Для полных графов = n, если n нечетно, и = n – 1, если n четно.

Для раскраски ребер графа рис. 8.2 требуется 3 краски. Раскрасьте граф самостоятельно.

8.7. Контрольные вопросы

  1. Поясните понятие внутренней устойчивости вершин графа.

  2. Число внутренней устойчивости графа – что это такое и как оно обозначается?

  3. Приведите алгоритм определения внутренне устойчивых множеств вершин графа.

  4. Что такое вершинная раскраска графа? Приведите алгоритм определения минимального числа красок для такой раскраски.

  5. Что такое хроматическое число графа и какие оценки существуют для него?

  6. На чем основан приближенный алгоритм нахождения максимального независимого множества вершин графа?

  7. Примените простейший алгоритм последовательной раскраски вершин графа на примере графа C5. Сколько потребовалось красок? Сколько потребуется красок для раскраски графа C6? Какой вывод можно сделать о раскраске графов–циклов?

  8. Что такое хроматический класс графа и какие оценки существуют для него?

9. Связность графов

При исследовании графов возникает два вида задач на связность

  • определение компонент связности графа,

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

Второй вид задач имеет смысл только для орграфов, так как связный неорграф всегда сильно связен. Однако, как будет видно из дальнейшего, алгоритм определения компонент сильной связности орграфа, оказывается пригоден и для решения задач первого вида для неорграфов.

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

Подграф G’ орграфа G(V,E) называется максимальным сильно связным, если не существует сильно связного подграфа G”, строго содержащего G’.

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

Вершины компонент сильной связности образуют множество классов эквивалентности C, |C| = p так, что

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

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

Определим транзитивное замыкание в графе для вершины xi

,

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее