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

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

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

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

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

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

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

1a32c34f33d31e24h26i25k47m48l45 и 8j16g13b12.

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

  1. Приведите алгоритм построения эйлеровой цепи в графе? Какому условию должен удовлетворять граф?

  2. Приведите алгоритм построения эйлерового цикла в графе. Какому условию должен удовлетворять граф?

  3. В чем заключается модификация алгоритмов построения эйлеровой цепи и эйлерового цикла?

  4. Как можно превратить произвольный граф в эйлеров граф?

  5. Приведите алгоритм покрытия графа непересекающимися по ребрам цепями.

7. Внешне устойчивые множества вершин и вершинная база графа

7.1. Внешне устойчивые множества вершин графа

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

Если это множество не содержит подмножеств с таким же свойством, то оно минимально.

Мощность минимального ДМВ обозначается β(G) и называется числом внешней устойчивости графа.

Для нахождения ДМВ образуем матрицу

A’ = E v A,

где Е – единичная матрица, А – матрица смежности.

Матрица Е вводится для учета изолированных вершин.

Найдем в матрице A’ минимальное множество строк, единицы в которых покрывают все столбцы. Множество вершин, соответствующее этому множеству строк, и есть ДМВ.

Пример. Для графа, показанного на рис. 7.1, получаем

A’ = E v A = v = .

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

Анализируя матрицу A’, замечаем, что

  • для покрытия столбца 1 нужна строка 1 (v1),

  • для покрытия столбца 2 нужна строка 1 (v1), или строка 2 (v2), или строка 3 (v3), что можно записать так (v1 v2 v3),

  • для покрытия столбца 3 нужна строка 3 (v3),

  • для покрытия столбца 4 нужна строка 2 (v2) или строка 4 (v4), что можно записать (v2 v4).

Поскольку нам необходимо покрыть строками и столбец 1, и столбец 2, и столбец 3, и столбец 4, то для покрытия всех столбцов, заменив союз И символом конъюнкции, можно записать

v1 (v1 v2 v3) v3 (v2 v4).

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

v1 v2 v3 v1 v3 v4.

Каждое из множеств {v1,v2,v3} и {v1,v3,v4} является доминирующим множеством вершин.

число внешней устойчивости данного графа β(G) равно 3.

7.2. Алгоритм определения внешне устойчивых множеств вершин

Используя полученные результаты, алгоритм нахождения всех доминирующих множеств вершин графа можно сформулировать следующим образом:

      1. Получить матрицу A’ = E v A.

      2. Обозначить вершины графа логическими переменными, например, x1, x2, x3,…, xn, где xi = 1, если вершина принадлежит какому либо внешне устойчивому множеству, и xi = 0 в противном случае.

      3. Для каждой вершины графа, используя матрицу A’, записать выражение

где – xi вершина, соответствующая выбранной строке,

xk, xl,…, xq – вершины, смежные ей.

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

  1. Сформировать логическое выражение в виде произведения полученных сумм

П = Ci Cj Ck .

  1. Провести преобразования логического выражения П для получения минимальной дизъюнктивной нормальной формы (МДНФ).

  2. Каждая конъюнкция полученной МДНФ будет являться доминирующим множеством вершин графа, а количество переменных в минимальной из них будет числом внешней устойчивости данного графа β(G). В совокупности получим семейство из всех внешне устойчивых множеств графа.

7.3. Вершинная база

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

Для нахождения вершинной базы необходимо сформировать матрицу

A” = E v A v…v An-1,

где Е – единичная матрица размера n n, А,…, An–1 – степени матрицы смежности графа, от 1 до n–1.

Затем надо найти в матрице A” множество строк, единицы в которых покрывают все столбцы, – множество вершин, соответствующее этому множеству строк, и есть вершинная база.

В качестве примера найдем вершинную базу графа, показанного на рис. 7.1.

Составим матрицу смежности графа

A = .

Определим необходимые степени матрицы смежности

A2= * = ,

A3= * = .

Определим матрицу A”

A”= E v A v A2 v A3 = .

Для определения вершинной базы необходимо найти вершины, строки которых покрывают все столбцы матрицы A”.

Анализируя матрицу A”, замечаем, что

  • для покрытия столбца 1 нужна строка 1 (v1),

  • для покрытия столбца 2 нужна строка 1 (v1), или строка 2 (v2), или строка 3 (v3), что можно записать так (v1 v2 v3),

  • для покрытия столбца 3 нужна строка 3 (v3),

  • для покрытия столбца 4 нужна или строка 1 (v1), или строка 2 (v2), или строка 3 (v3), или строка 4 (v4), что можно записать так

(v1 v2 v3 v4).

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

v1 (v1 v2 v3) v3 (v1 v2 v3 v4).

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

v1 v3.

Множество вершин {v1, v3} и есть вершинная база графа.

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

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

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

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

    4. Поясните понятие вершинной базы графа. Чем это понятие похоже и чем отличается от внешней устойчивости графа?

    5. Приведите алгоритм определения вершинной базы графа.

    6. Как определяется множество строк матриц A’ и A”, покрывающих единицами все столбцы этих матриц?

8. Внутренняя устойчивость и раскраска графа

8.1. Внутренне устойчивые множества вершин графа

Множество вершин графа, среди которых нет смежных, называется независимым множеством вершин (НМВ) или внутренне устойчивым множеством вершин.

Если такое множество не является подмножеством другого множества с таким свойством, то оно максимально.

Мощность максимального независимого множества вершин (МНМВ) α(G) – называется числом внутренней устойчивости графа.

С помощью приведенного ниже алгоритма можно выделить семейство всех независимых множеств вершин произвольного графа.

8.2. Алгоритм определения внутренне устойчивых множеств вершин

  1. Составить матрицу смежности графа.

  2. Обозначить вершины графа логическими переменными, например, x1, x2, x3,…, xn, где xi = 0, если вершина принадлежит какому либо внутренне устойчивому множеству, и xi = 1 в противном случае.

Обратите внимание на отличие значений xi от значений этой переменной в алгоритме определения внешне устойчивых множеств вершин графа.

  1. В матрице смежности выбрать строку с максимальным числом ненулевых элементов. Если таких строк несколько, то берется любая из них.

  2. Для выбранной строки записывается выражение

где xi – вершина, соответствующая выбранной строке, xk, xl,…, xq – вершины, смежные ей.

Трактовать это выражение можно так – во внутренне устойчивое множество вершин графа не должна входить вершина xi или ни одна из вершин, смежных с ней.

  1. После этого в строке и столбце матрицы смежности с индексом i единицы заменить нулями (строку и столбец с индексом i можно удалить).

  2. В полученной матрице смежности снова выбрать строку с наибольшим числом ненулевых элементов (например, строку j) и записать выражение

  1. Строка и столбец с индексом j обнуляются.

  2. Процесс повторяется, пока все строки матрицы смежности не станут пустыми (одни нули).

В строках изолированных и тупиковых вершин первоначальной матрицы смежности стоят только 0, поэтому для них не будут составлены выражения Ci. Изолированные вершины обязательно войдут в любое из внутренне устойчивых множеств и будут учтены в п. 10 алгоритма. поэтому их можно сразу исключить из матрицы смежности, упростив тем самым решение задачи. Тупиковые вершины будут учтены в выражениях для вершин, смежных с ними.

  1. Из полученных выражений Ci, Cj, , Ck составить произведение

П = Ci Cj Ck,

в котором раскрыть скобки и провести минимизацию.

  1. После минимизации для каждой конъюнкции найти не вошедшие в нее вершины графа, которые и образуют независимое множество.

В совокупности получим семейство из всех независимых множеств.

  1. Число внутренней устойчивости графа α(G) будет равно количеству вершин, вошедших в максимальное независимое множество вершин.

Пример. Дан граф G(6,6) рис. 8.1.

Определить внутренне устойчивые множества графа.

С
оставляем матрицу смежности графа

Рисунок 8.1

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

Обнуляем строку и столбец с индексом 2.

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