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

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

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

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

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

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

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

f = m – n + 2,

где n – число вершин, m – число ребер.

11.3. Алгоритм построения плоского изображения графа

Ответ на второй вопрос: – Как получить плоское изображение графа? – дает алгоритм, рассмотренный ниже.

Пусть задана часть G1 = (V1, E1) графа G = (V, E).

Будем называть куском графа G относительно G1:

  1. ребро вместе с его концами, которые принадлежат V1,

  2. а также компоненту связности Gi = (Vi, Ei) подграфа, порожденного подмножеством вершин V\Vl, дополненную всеми ребрами, инцидентными вершинам из V'i, и всеми вершинами этих ребер, принадлежащими V1 , которые называются «контактными точками»;

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

В качестве начального плоского графа выбирают некоторый цикл графа G.

Чтобы перейти от подграфа к , предварительно рассматривают все куски Pj графа G относительно .

Грань fk графа и кусок Рj совместимы, если все его контактные точки принадлежат множеству вершин этой грани.

Для каждого куска определяем грани, которые с ним совместимы. Возможны три случая:

  1. Некоторый кусок не совместим ни с какой гранью графа . Тогда граф не плоский.

  2. Какой–либо кусок совместим с единственной гранью fk графа . Тогда выберем в этом куске цепь такую, что оба ее конца (и только они) принадлежат . Дополняя ребрами и вершинами этой цепи, получаем , проводя внутри грани fk.

  3. Если каждый из кусков Рj совместим, по крайней мере, с двумя гранями графа , то можно выбрать цепь в любом из кусков и действовать как в случае 2.

П
ример.
Проиллюстрируем этот алгоритм на примере графа G(V,E) рис. 11.2.

Рисунок 11.2

Шаг 1. Берем произвольный цикл, например u0 = (1, 2, 6, 5, 1), представляющий плоский граф (рис. 11.3, а).

Грани :

A0 — внешняя грань (1, 2, 6, 5, 1),

В0 — внутренняя грань (1,2,6,5,1).

Куски графа G относительно :

Куски

Вершины куска

Контактные точки

Совместимые грани

P1

{1, 3, 5, 6}

{1, 5, 6}

A0 и B0

Р2

{1, 2, 4, 6}

{1, 2, 6}

A0 и B0

Шаг 2. Определяем . Все куски совместимы с двумя гранями (случай 3). Выбираем, например, цепь (1, 3, 5) из куска Р1 и проводим ее в грани В0. Эта грань в заменяется двумя гранями: В1внутренней к (1, 3, 5, 1) и В2 – внутренней к (1, 2, 6, 5, 3, 1) (рис. 11.3, б).

Куски G относительно :

Куски

Вершины кусков

Контактные точки

Совместимые грани

{3, 6}

{3, 6}

В2

{1, 2, 4, 6}

{1, 2, 6}

A0 и В2

Шаг 3. Определяем . Кусок Р1 совместим лишь с одной гранью В2 (случай 2). Цепь (3, 6) должна быть помещена в грань В2, которую она разобьет на две грани: В3 — внутреннюю к (3, 5, 6, 3) и В4 – внутреннюю к (1, 2, 6, 3, 1) (рис. 11.3, в).

Р
исунок 13.3

Куски G относительно :

Кусок

Вершины куска

Контактные точки

Совместимые грани

{1, 2, 4, 6}

{1, 2, 6}

A0 и В4

Шаг 4. Определяем . Кусок совместим с двумя гранями A0 и B4 (случай 3). Возьмем, например, цепь (1, 4, 2) и поместим ее в грань A0. Получаем две новые грани: A1 – внешнюю к (1, 4, 2, 6, 5, 1) и А2внутреннюю к (1, 4, 2, 1) (рис. 11.3, г).

Куски G относительно :

Кусок

Вершины куска

Контактные точки

Совместимые грани

{4, 6}

{4, 6}

A1

Шаг 5. Определяем . Кусок совместим с одной гранью A1 (случай 2). Помещаем единственную цепь (4, 6) в A1 и получаем новые грани: A3 – внешнюю к (1, 4, 6, 5, 1) и A4 – внутреннюю к (2, 4, 6, 2) (рис. 11.3, д).

Таким образом, получаем плоское изображение графа G.

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

  1. Что такое планарный граф?

  2. Каковы условия планарности для произвольного графа?

  3. Грань плоского графа – Что это такое ? Сколько граней у плоского графа?

  4. Граф K6 плоский? А K7?

  5. Что такое число планарности и толщина графа? Как их определить?

  6. Какова идея алгоритма построения плоского изображения графа?

12. Двудольные графы

Двудольным графом называют такой граф G(X Y,E), что

  1. X Y = ,

Пример двудольного графа и его матрица смежности показаны на рис. 12.1.

Рисунок 12.1

С
войства двудольного графа:

  1. Множество вершин графа состоит из двух непересекающихся подмножеств таких, что внутри каждого подмножества нет смежных вершин.

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

  3. Двудольный граф не имеет простых циклов нечетной длины.

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

Рассмотрим некоторые задачи на двудольных графах.

12.1. Минимальное покрытие двудольного графа

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

Н
апример, для графа рис. 12.2 покрытием будет множество дуг

W = {(x1,y1), (x2,y4), (x3, y2), (x4, y3), (x5, y4), (x5, y5), (x6,y3)}.

Рисунок 12.2

В матрице смежности, показанной на рис. 12.2, дуги множества W выделены полужирным шрифтом.

Анализируя эту матрицу, можно определить покрытие графа как такой набор единиц, что каждая строка и каждый столбец содержат, по крайней мере, по одному элементу из этого набора.

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

12.1.1. Алгоритм с использованием матрицы инцидентности

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

Алгоритм:

  1. Составляем матрицу инцидентности графа, в которой, как известно, число строк равно числу вершин графа, а число столбцов равно числу ребер графа. Каждое ребро инцидентно двум вершинам, поэтому в каждом столбце будет две единицы.

  2. Для определения минимального покрытия вершин графа ребрами необходимо найти такую минимальную совокупность столбцов матрицы инцидентности (ребер), которая содержала хотя бы по одной 1 во всех строках, т.е. могла бы покрыть каждую вершину графа.

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

  1. Для покрытия графа надо покрыть и вершину 1, и вершину 2, и т.д. Поэтому из сумм предыдущего пункта, заменив союз И символом логического умножения, составляем логическое произведение.

  2. полученное логическое произведение сумм преобразуется в дизъюнктивную форму и минимизируется. Терм с минимальным числом букв и будет представлять минимальное покрытие графа.

Пример. Дан граф рис. 12.3.

Найти минимальное подмножество ребер, инцидентных всем вершинам.

Составляем матрицу инцидентности графа (табл. 12.1).

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

Составляем логическое произведение полученных сумм, раскрываем скобки и минимизируем

(a b)(c d)(a c)(b d) =

= (ac ad bc bd)(ab ad bc cd) =

= abc acd abc acd abd ad abcd acd

abc abcd bc bcd abd abd bcd bcd =

= ad bc.

Подмножество ребер ad или bс покрывает все вершины графа.

Таблица 12.1

a

b

c

d

1

1

1

0

0

2

0

0

1

1

3

1

0

1

0

4

0

1

0

1




Рисунок 12.3

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