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

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

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

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

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

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

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

Если к дереву T добавить произвольную хорду hi, то образуется точно один цикл Ci. Этот цикл состоит из хорды hi и некоторых ветвей остова, образующих простую цепь и соединяющих вершины хорды hi.

Цикл Ci называется фундаментальным циклом графа G относительно хорды hi остова T (в общем случае остовов в графе может быть много). Таким образом, фундаментальный цикл содержит точно одну хорду остова графа.

Множество всех фундаментальных циклов {C1, C2, …, Ci, …, Cmn+1} относительно хорд остова T называется фундаментальным множеством циклов графа G. Мощность этого множества равна цикломатическому числу (G) = mn +1 или рангу графа G.

фундаментальное множество циклов графа можно задать с помощью матрицы, строки которой имеют вид

h1, h2, …, hmn+1, b1, b2, …, bn1,

где hi, bj – хорды и ветви соответственно.

В каждом цикле имеется одна хорда hi и некоторое множество ветвей остова T. Этой хорде hi и ветвям, входящим в цикл Ci, присвоим значение 1, остальным ребрам графа присвоим значение 0. Повторяя процедуру для всех хорд, получим матрицу строк из 0 и 1.

Пример. для графа G и его остова T, показанных на рис. 10.1, матрица фундаментальных циклов будет такой

,

где 1, 2, 3 – хорды, 4, 5, 6, 7, 8 – ветви остова T, E – единичная матрица порядка (G) = mn + 1, B – матрица остова T.

Р
исунок 10.1

10.4. Фундаментальные разрезы

Разрезом неорграфа G(V,E) по разбиению множества вершин V на два подмножества V1 и V2 называется множество ребер, соединяющих вершины из подмножества V1 с вершинами подмножества V2. В связном графе любой разрез не пуст.

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

В связном неорграфе остов T имеет по крайней мере одно общее ребро с любым разрезом графа.

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

Пусть имеем связный неорграф G с остовом T. И пусть b1, b2, …, bi,…, bn1 – ветви остова T.

Удаляя произвольную ветвь bi из T, получаем лес с двумя компонентами, т. е. каждое ребро bi есть разрез T по некоторому разбиению вершин V1, V2.

В графе могут найтись еще какие–то ребра hi1, hi2,…, hij, которые соединяют V1 и V2.

Множество ребер Ki = {bi, hi1, …, hij} образует разрез G относительно ветви bi, который называют фундаментальным разрезом относительно bi остова T. Таким образом, фундаментальный разрез содержит точно одну ветвь остова графа.

Множество {K1, K2, …, Kn1} всех фундаментальных разрезов графа G называется фундаментальным множеством разрезов графа G относительно остова T.

Мощность этого множества равна *(G) = n–1. (В общем случае n , где число компонент связности графа.)

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

(ai1, ai2, …, aim),

где

Из этих векторов можно составить матрицу фундаментальных разрезов.

Поскольку каждый фундаментальный разрез содержит точно одну ветвь T, то матрица K имеет вид

hi,j – хорды

bi – ветви T

K1

h1,1

.

h1,V*

1

0

0

.

0

K =

.

h2,1

.

h2,V*

0

1

0

.

0

.

.

.

.

.

.

.

.

.

KV*

hV*,1

.

hV*,V*

0

0

0

.

1

где v* это *(G) = n – 1.

Таким образом ,

где H – матрица хорд графа, E – единичная матрица порядка *(G).

Матрицы фундаментальных циклов C и фундаментальных разрезов K взаимосвязаны.

Если , то ,

где – транспонированная матрица B.

Следовательно, для анализа графа достаточно найти одну матрицу (C или K), а другую можно определить транспонированием.

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

.

Р
исунок 10.2

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

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

  2. Что такое фундаментальный цикл? Сколько таких циклов в графе? Как называется их количество?

  3. Что такое фундаментальный разрез? Сколько таких разрезов в графе? Как называется их количество?

  4. Что такое ранг графа? А коранг? Как их определить?

  5. Какая связь существует между матрицами фундаментальных циклов и фундаментальных разрезов в графе?

11. Планарные графы

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

Изображение графа на плоскости с соблюдением этого условия называется плоским графом.

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

  • граф планарен?

  • Как получить планарное изображение графа?

Если граф не планарен, то приходится удалять (переносить на другой слой, на другую плоскость) отдельные ребра.

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

(Kn) = (n–3)(n–4)/2.

Из формулы следует, что при n = 4 (K4) = 0. Для K5 (K5) = 1, следовательно, чтобы граф K5 стал плоским, из него надо удалить одно ребро.

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

Минимальное число плоскостей, при котором граф разбивается на плоские части, называется толщиной графа и обозначается t(G).

Толщина произвольного графа удовлетворяет неравенству

t(G) .

Здесь [x] – целая часть x.

Толщина полных графов удовлетворяет неравенству

t(Kn) .

Например, для K5 t(K5) = 2.

11.1. Условия планарности

Ответ на первый вопрос: – Граф планарен? – можно получить, если воспользоваться условиями планарности.

У связного плоского графа с n 3 число ребер m удовлетворяет условию

У связного плоского двудольного графа

П
ример.
Полный граф K4 (рис. 11.1, а) – планарен?

В этом графе n = 4, m = 6.

Рисунок 11.1

Подставим эти значения в условие планарности

Условие выполняется. Следовательно, граф планарен. Действительно, граф K4 можно представить так, как показано на рис. 11.1, б.

Из рисунка ясно, что граф K4 планарен.

Пример. Полный граф K5 (рис. 11.1, в) – планарен?

В этом графе n = 5, m = 10.

Подставим эти значения в условие планарности

Условие не выполняется. Следовательно, граф не планарен.

Пример. Двудольный полный граф К3,3 (рис. 11.1, г) – планарен?

В этом графе n = 6, m = 9.

Подставим эти значения в условие планарности

Условие не выполняется. Следовательно, граф не планарен.

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

Доказательство простое.

Расположим все вершины на одной прямой рис. 11.2.

Р
исунок 11.2

Построим m плоскостей на этой прямой, т. е. для каждого ребра свою плоскость.

Проведем ребра на своих плоскостях. Ребра не пересекаются (кроме как на своих вершинах).

Непланарность графов K5 и К3,3 используется для оценки планарности “больших графов”: граф не планарен, если он содержит подграфы вида K5 или К3,3, или сводимые к ним.

11.2. Грани плоского графа

У плоского графа кроме вершин и ребер можно выделить еще один геометрический образ – грань.

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

Внешняя неограниченная грань называется бесконечной гранью.

Например, граф на рис. 11.1, б обладает четырьмя гранями: f1, f2, f3, f4, где f4 бесконечная грань.

У графа без циклов ровно одна грань – бесконечная. Не следует думать, что она какая–то исключительная. При укладке графа на сферу эта грань ничем не будет отличаться от других.

Число граней f в связном плоском графе определяется из соотношения

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