1. Введение
2. Рстория возникновения теории графов
3. Основные определения теории графов
4. Основные теоремы теории графов
5. Задачи на применение теории графов
Возможно вы искали - Реферат: Теория игр и принятие решений
6. Применение теории графов в школьном курсе математики
7. Приложение теории графов в различных областях науки и техники
8. Последние достижения теории графов
9. Вывод
В§1. РРЎРўРћР РРЇ Р’РћР—РќРКНОВЕНРРЇ ТЕОРРРГРАФОВ.
Родоначальником теории графов принято считать математика Леонарда Рйлера (1707-1783). Рсторию возникновения этой теории можно проследить РїРѕ переписке великого ученого. Р’РѕС‚ перевод латинского текста, который РІР·СЏС‚ РёР· РїРёСЃСЊРјР° Рйлера Рє итальянскому математику Рё инженеру Маринони, отправленного РёР· Петербурга 13 марта 1736 РіРѕРґР° [СЃРј. [5]стр. 41-42]:
Похожий материал - Реферат: Теория информации
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. Ртут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B , C иD – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a , b , c , d , e , f , g ".
(Р РРЎРЈРќРћРљ 1.1)
РџРѕ РїРѕРІРѕРґСѓ обнаруженного РёРј СЃРїРѕСЃРѕР±Р° решать задачи РїРѕРґРѕР±РЅРѕРіРѕ СЂРѕРґР° Рйлер писал [СЃРј. [5]стр. 102-104]:
"Рто решение РїРѕ своему характеру, РїРѕ-РІРёРґРёРјРѕРјСѓ, имеет мало отношения Рє математике, Рё РјРЅРµ непонятно, почему следует скорее РѕС‚ математика ожидать этого решения, нежели РѕС‚ какого-РЅРёР±СѓРґСЊ РґСЂСѓРіРѕРіРѕ человека, РёР±Рѕ это решение подкрепляется РѕРґРЅРёРј только рассуждением, Рё нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Ртак, СЏ РЅРµ знаю, каким образом получается, что РІРѕРїСЂРѕСЃС‹, имеющие совсем мало отношения Рє математике, скорее разрешается математиками, чем РґСЂСѓРіРёРјРё".
Так можно ли обойти Кенигсбергские мосты, РїСЂРѕС…РѕРґСЏ только РѕРґРёРЅ раз через каждый РёР· этих мостов? Чтобы найти ответ, продолжим РїРёСЃСЊРјРѕ Рйлера Рє Маринони:
Очень интересно - Реферат: Теория случайных функций
"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти РІ РїРёСЃСЊРјРµ Р›. Рйлера Рє своему РґСЂСѓРіСѓ Рлеру РѕС‚ 3 апреля того же РіРѕРґР°. РњС‹ перескажем ниже отрывок РёР· этого РїРёСЃСЊРјР°.
Математик писал, что переход возможен, если РЅР° участке разветвления реки имеется РЅРµ более РґРІСѓС… областей, РІ которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать РЅР° СЂРёСЃСѓРЅРєРµ уже пройденные мосты. Легко проверить, что если РјС‹ начнем двигаться РІ соответствии СЃ правилами Рйлера, пересечем РѕРґРёРЅ РјРѕСЃС‚ Рё сотрем его, то РЅР° СЂРёСЃСѓРЅРєРµ будет изображен участок, РіРґРµ опять имеется РЅРµ более РґРІСѓС… областей, РІ которые ведет нечетное число мостов, Р° РїСЂРё наличии областей СЃ нечетным числом мостов РјС‹ будем располагаться РІ РѕРґРЅРѕР№ РёР· РЅРёС…. Продолжая двигаться так далее, пройдем через РІСЃРµ мосты РїРѕ РѕРґРЅРѕРјСѓ разу.
Рстория СЃ мостами РіРѕСЂРѕРґР° Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник РїРѕ математике РїРѕРґ редакцией Рќ.РЇ. Виленкина для шестого класса. Р’ нем РЅР° странице 98 РІ СЂСѓР±СЂРёРєРµ развития внимательности Рё сообразительности РјС‹ найдем задачу, имеющую непосредственное отношение Рє той, которую РєРѕРіРґР°-то решал Рйлер.
Задача № 569 . На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A ?
Вам будет интересно - Курсовая работа: Рстория статистики
(Р РРЎРЈРќРћРљ 1.2)
Решение. Поскольку эта задача РїРѕРґРѕР±РЅР° задаче Рѕ Кенигсбергских мостах, то РїСЂРё ее решении РјС‹ также воспользуемся правилом Рйлера. Р’ результате получим следующий ответ: катер должен доставить путешественников РЅР° остров E или F , чтобы РѕРЅРё смогли пройти РїРѕ каждому мосту РѕРґРёРЅ раз. РР· того же правила Рйлера следует невозможность требуемого РѕР±С…РѕРґР°, если РѕРЅ начнется СЃ острова A .
Р’ заключение отметим, что задача Рѕ Кенигсбергских мостах Рё подобные ей задачи вместе СЃ совокупностью методов РёС… исследования составляют очень важный РІ практическом отношении раздел математики, называемый теорией графов. Первая работа Рѕ графах принадлежала Р›. Рйлеру Рё появилась РІ 1736 РіРѕРґСѓ. Р’ дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), РёР· современных математиков – Рљ. Берж, Рћ. РћСЂРµ, Рђ. Зыков.
В§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРРРГРАФОВ
Теория графов, как было сказано выше, – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает РІ себя Рё необходимые строгие определения. Ртак, приступим Рє организованному введению основных понятий этой теории.
Определение 2.01. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
Похожий материал - Реферат: Теория управления
Рто определение можно сформулировать иначе: графом называется непустое множество точек (вершин ) Рё отрезков (ребер ), РѕР±Р° конца которых принадлежат заданному множеству точек (СЃРј. СЂРёСЃ. 2.1).
(Р РРЎРЈРќРћРљ 2.1)
Р’ дальнейшем вершины графа РјС‹ будем обозначать латинскими буквами A , B ,C ,D . РРЅРѕРіРґР° граф РІ целом будем обозначать РѕРґРЅРѕР№ заглавной Р±СѓРєРІРѕР№.
Определение 2.02. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными .
cwetochki.ru
Содержание
Краткий перечень основных понятий теории графов ……………….. 4
Понятия смежности, инцидентности, степени ……………………….. 7
Маршруты и пути ………………………………………………………. 7
Матрицы смежности и инцидентности…..……………………………. 7
Связность. Компоненты связности …………………………………….. 8
Матрицы достижимости и связности ………….………………………. 9
Расстояния в графе …………………………..…………….……………. 9
Образ и прообраз вершины и множества вершин …………..……….. 10
Нагруженные графы ………………..………………………………….. 11
Деревья и циклы …………………………………….………….……… 12
Решение контрольных задач по теме «Теория графов»……………………………………………...…………………... 13
Задание 1. Компоненты сильной связности ориентированного графа.……………………………………………………………………. 13
Задание 2. Расстояния в ориентированном графе..………………...... 16
Задание 3. Минимальный путь в нагруженном ориентированном графе...……...…………………………………………………………... 20
Задание 4. Рйлеровы циклы Рё цепи ……..………………………….… 23
Задание 5. Минимальное основное дерево...………...…………...…… 25
Задание 6. Задача о коммивояжёре...………...…………...…………… 27
Задания для самостоятельного решения ………….………......……… 34
Список литературы…………………………………………………..…. 37
Краткий перечень основных понятий теории графов.
Теория графов как теоретическая дисциплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы не будут вводиться в рассмотрение) с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы. Например, графом, изображенным на рис. 1, в котором точки − вершины графа − города, линии, соединяющие вершины − ребра − дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного города - пункта в другой).
Р РёСЃ. 1.
Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения V×V, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V, X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V.
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
Р РёСЃ.2.
Например, кратность ребра {v1, v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3, v4} − трем.
Псевдограф − граф, в котором есть петли и/или кратные ребра.
Мультиграф − псевдограф без петель.
Граф − мультиграф, в котором ни одна пара не встречается более одного раза.
Граф называется ориентированным, если пары (v, w) являются упорядоченными.
Ребра ориентированного графа называются дугами.
Ртак, используемые далее обозначения:
V – множество вершин;
X – множество ребер или дуг;
V (или vi)– вершина или номер вершины;
G, G0 - неориентированный граф;
D, D0 – ориентированный;
{v, w} − ребра неориентированного графа;
{v, v} – обозначение петли;
(v, w) − дуги в ориентированном графе;
V, w - вершины, x, y,z – дуги и ребра;
N(G), n(D) количество вершин графа;
M(G) - количество ребер, m(D) - количество дуг.
Примеры
1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},
X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.
Р РёСЃ. 3.
2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},
X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.
Р РёСЃ. 4.
Понятия смежности, инцидентности, степени
Если x={v, w} - ребро, то v и w − концы ребра x.
Если x=(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.
Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).
Вершины v, w называются смежными, если {v, w}ÎX.
Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.
Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.
Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).
Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).
Маршруты и пути
Последовательность v1x1v2x2v3...xkvk+1, (где k³1, viÎV, i=1,...,k+1, xiÎX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj, vj+1} (для ориентированного графа (vj, vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).
Пример
В графе, изображенном на рис.4, v1x1v2x2v3x4v4x3v2 - маршрут, v2x2v3x4v4 – подмаршрут;
Маршрут можно восстановить и по такой записи x1x2x4x3 ;
Если кратности ребер (дуг) равны 1, можно записать и так v1v2v3v4v2 .
Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.
Цикл − замкнутая цепь (в неориентированном графе).
referatbox.com
Муниципальное общеобразовательное учреждение «Средняя общеобразовательная школа № 6»
Реферат на тему: «Теория графов»
Подготовила: Майорова Екатерина, 8Г класс Учитель: Малова Татьяна Алексеевна
Содержание:
I. Введение
II. Основная часть. 1.Рстория возникновения теории графов.
2.Некоторые задачи теории графов. 2.1 Логические задачи 2.2 Задачи РЅР° связность. 2.3 Задачи РїРѕ теореме Рйлера Рѕ нечетных вершинах
3.Применение теории графов в различных сферах деятельности. 3.1.Графы и информация 3.2.Графы и химия. 3.3.Графы и биология 3.4.Графы и физика
III. Заключение.
IV. Список литературы.
I. Введение.
Я выбрала эту тему, потому что она была и остается актуальной в наше время.
Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике - при построении электрических схем, в химии и биологии - при изучении молекул и их цепочек, в географии – при составлении карт, в истории – при составлении родословной, в геометрии – в чертежах многоугольников, многогранников, пространственных фигур, в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог).
Графами являются блок-схемы программ для РР’Рњ, сетевые графики строительства. РЎ помощью графов решается задача Рѕ назначении РЅР° должности. Рђ именно: если имеется несколько вакантных должностей Рё РіСЂСѓРїРїС‹ лиц, желающих РёС… занять, причем каждый РёР· претендентов имеет квалификацию для нескольких должностей, то РїСЂРё каких условиях каждый РёР· претендентов сможет получить работу РїРѕ РѕРґРЅРѕР№ РёР· СЃРІРѕРёС… специальностей? Теория графов РІ школьной программе РЅРµ изучается, РЅРѕ широко применяется РїСЂРё решении математических олимпиадных задач.
II. 1. Рстория возникновения теории графов
Рзучив информацию Рнтернет-ресурсов, СЏ для себя открыла следующие интересные факты РѕР± истории теории графов. Родоначальником теории графов принято считать математика Леонарда Рйлера. Рсторию возникновения этой теории можно проследить РїРѕ переписке великого ученого. Р’ ней РѕРЅ сообщал, что ему была предложена задача Рѕ семи мостах Кенигсберга. Спрашивалось, может ли кто-РЅРёР±СѓРґСЊ непрерывно обойти РёС…, РїСЂРѕС…РѕРґСЏ только однажды через каждый РјРѕСЃС‚. Рему сразу же было сообщено, что никто еще РґРѕ СЃРёС… РїРѕСЂ РЅРµ РјРѕРі это проделать, РЅРѕ никто Рё РЅРµ доказал, что это невозможно. Р’РѕРїСЂРѕСЃ этот показался ему достойным внимания тем, что «…Для его решения недостаточны РЅРё геометрия, РЅРё алгебра, РЅРё комбинаторное искусство...В». После долгих размышлений РѕРЅ нашел легкое правило, основанное РЅР° вполне убедительном доказательстве, СЃ помощью которого можно РІРѕ всех задачах такого СЂРѕРґР° определить, может ли быть совершен такой РѕР±С…РѕРґ через какое СѓРіРѕРґРЅРѕ число Рё как СѓРіРѕРґРЅРѕ расположенных мостов или РЅРµ может. Кенигсбергские же мосты расположены так, что РёС… можно представить РЅР° СЂРёСЃСѓРЅРєРµ, РЅР° котором Рђ обозначает остров, Р° Р’, РЎ Рё D - части континента, отделенные РґСЂСѓРі РѕС‚ РґСЂСѓРіР° рукавами реки. Семь мостов обозначены буквами Р°, b, СЃ, d, Рµ, f, g. Кенигсбергские мосты.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов.
Для того чтобы проще представить себе это, будем стирать РЅР° СЂРёСЃСѓРЅРєРµ уже пройденные мосты. Легко проверить, что если начать двигаться РІ соответствии СЃ правилами Рйлера, пересечь РѕРґРёРЅ РјРѕСЃС‚ Рё стереть его, то РЅР° СЂРёСЃСѓРЅРєРµ будет изображен участок, РіРґРµ опять имеется РЅРµ более РґРІСѓС… областей, РІ которые ведет нечетное число мостов. Рђ РїСЂРё наличии областей СЃ нечетным числом мостов РјС‹ будем располагаться РІ РѕРґРЅРѕР№ РёР· РЅРёС…. Продолжая двигаться так далее, пройдем через РІСЃРµ мосты РїРѕ РѕРґРЅРѕРјСѓ разу. В В Рстория СЃ мостами РіРѕСЂРѕРґР° Кенигсберга имеет современное продолжение. Р’ некоторых учебниках математики или РІ дополнительных материалах (приложениях) учебника можно встретить задачи, чьё решение основано именно РЅР° предложенном Рйлером СЃРїРѕСЃРѕР±Рµ. РЇ поняла, что РІ С…РѕРґРµ рассуждений Рйлер пришёл Рє следующим выводам:
docus.me
Федеральное агентство по образованию РФ
ГОУ Р’РџРћ «УГТУ-РЈРџРВ»
Курсовая работа
по теории информационных систем №
(Р”РРЎР¦РРџР›РРќРђ)
на тему: Теория графов и их применение
Преподаватель Александров О.Е
(Р¤РРћ)
Студент РіСЂ. в„– РС‚44010РґРё Риасс Рђ.Р’.
(Р¤РРћ)
номер зачетной книжки 17436537
Екатеринбург
2008
Курсовая работа по _____ теории информационных систем
(Р”РРЎР¦РРџР›РРќРђ)
№ записи в книге регистрации дата регистрации 200 8 г.
Преподаватель ___Александров О.Е.________________________________
(Р¤РРћ)
Студент Риасс Рђ.Р’. РіСЂСѓРїРїР° в„– РС‚44010РґРё
(Р¤РРћ)
Деканат ФДО
Содержание:
1. Рстория возникновения графов……………………………………………………………3
2. Начальные понятия теории графов………………………………………………………5
3. Определения графа…………………………………………………………………………………5
4. Графы и бинарные отношения……………………………………………………………….7
5. Откуда берутся графы…………………………………………………………………………….7
6. Число графов……………………………………………………………………………………………8
7. Смежность, инцидентность, степени……………………………………………………..8
11. Рзоморфизм…………………………………………………………………………………………..11
16. Деревья……………………………………………………………………………………………………15
20. РџР РМЕНЕНРР• ТЕОРРРГРАФОВ Р’ ТЕОРРР РНФОРМАЦРР………………….23
1. РРЎРўРћР РРЇ Р’РћР—РќРКНОВЕНРРЇ ТЕОРРРГРАФОВ.
Родоначальником теории графов принято считать математика Леонарда Рйлера (1707-1783). Рсторию возникновения этой теории можно проследить РїРѕ переписке великого ученого. Р’РѕС‚ перевод латинского текста, который РІР·СЏС‚ РёР· РїРёСЃСЊРјР° Рйлера Рє итальянскому математику Рё инженеру Маринони, отправленного РёР· Петербурга 13 марта 1736 РіРѕРґР° [СЃРј. [5]стр. 41-42]:
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. Ртут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".
(Р РРЎРЈРќРћРљ 1.1)
РџРѕ РїРѕРІРѕРґСѓ обнаруженного РёРј СЃРїРѕСЃРѕР±Р° решать задачи РїРѕРґРѕР±РЅРѕРіРѕ СЂРѕРґР° Рйлер писал [СЃРј. [5]стр. 102-104]:
"Рто решение РїРѕ своему характеру, РїРѕ-РІРёРґРёРјРѕРјСѓ, имеет мало отношения Рє математике, Рё РјРЅРµ непонятно, почему следует скорее РѕС‚ математика ожидать этого решения, нежели РѕС‚ какого-РЅРёР±СѓРґСЊ РґСЂСѓРіРѕРіРѕ человека, РёР±Рѕ это решение подкрепляется РѕРґРЅРёРј только рассуждением, Рё нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Ртак, СЏ РЅРµ знаю, каким образом получается, что РІРѕРїСЂРѕСЃС‹, имеющие совсем мало отношения Рє математике, скорее разрешается математиками, чем РґСЂСѓРіРёРјРё".
Так можно ли обойти Кенигсбергские мосты, РїСЂРѕС…РѕРґСЏ только РѕРґРёРЅ раз через каждый РёР· этих мостов? Чтобы найти ответ, продолжим РїРёСЃСЊРјРѕ Рйлера Рє Маринони:
"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти РІ РїРёСЃСЊРјРµ Р›. Рйлера Рє своему РґСЂСѓРіСѓ Рлеру РѕС‚ 3 апреля того же РіРѕРґР°. РњС‹ перескажем ниже отрывок РёР· этого РїРёСЃСЊРјР°.
Математик писал, что переход возможен, если РЅР° участке разветвления реки имеется РЅРµ более РґРІСѓС… областей, РІ которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать РЅР° СЂРёСЃСѓРЅРєРµ уже пройденные мосты. Легко проверить, что если РјС‹ начнем двигаться РІ соответствии СЃ правилами Рйлера, пересечем РѕРґРёРЅ РјРѕСЃС‚ Рё сотрем его, то РЅР° СЂРёСЃСѓРЅРєРµ будет изображен участок, РіРґРµ опять имеется РЅРµ более РґРІСѓС… областей, РІ которые ведет нечетное число мостов, Р° РїСЂРё наличии областей СЃ нечетным числом мостов РјС‹ будем располагаться РІ РѕРґРЅРѕР№ РёР· РЅРёС…. Продолжая двигаться так далее, пройдем через РІСЃРµ мосты РїРѕ РѕРґРЅРѕРјСѓ разу.
Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами, например задачи, в которых требуется выяснить какие-либо особенности устройства графа, или найти в графе часть, удовлетворяющую некоторым требованиям, или построить граф с заданными свойствами.
Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками, прямоугольниками и т.д.), а связи между ними - линиями или стрелками, соединяющими элементы. При этом получаются диаграммы вроде тех, что показаны на рис. 1.1.
Р РёСЃ. 1.1.В
На таких диаграммах часто ни способ изображения элементов, ни форма или длина линий не имеют значения - важно лишь, какие именно пары элементов соединены линиями. Если посмотреть внимательно, то можно заметить, что рисунки 1.1а и 1.1 б изображают одну и ту же структуру связей между элементами ,
,
,
,
,
. Рту же структуру можно описать, РЅРµ прибегая Рє графическому изображению, Р° просто перечислив пары связанных между СЃРѕР±РѕР№ элементов:
,
,
,
,
,
,
. Таким образом, РєРѕРіРґР° РјС‹ отвлекаемся РѕС‚ всех несущественных подробностей, Сѓ нас остаются РґРІР° СЃРїРёСЃРєР°: СЃРїРёСЃРѕРє элементов Рё СЃРїРёСЃРѕРє пар элементов. Вместе РѕРЅРё составляют то, что математики называют графом. РР· этого примера РІРёРґРЅРѕ, что понятие графа само РїРѕ себе РЅРµ связано напрямую СЃ геометрией или графикой. Тем РЅРµ менее, возможность нарисовать граф - РѕРґРЅР° РёР· привлекательных черт этого математического объекта.
Термин "граф" неоднозначен, это легко заметить, сравнивая приводимые в разных книгах определения. Однако во всех этих определениях есть кое-что общее. В любом случае граф состоит из двух множеств - множества вершин и множества ребер, причем для каждого ребра указана пара вершин, которые это ребро соединяет. Вершины и ребра называются элементами графа. Здесь будут рассматриваться только конечные графы, то есть такие, у которых оба множества конечны. Чтобы получить законченное определение графа того или иного типа, необходимо уточнить еще три момента.
Ориентированный или неориентированный?
Прежде всего, нужно договориться, считаем ли мы пары и
различными. Если да, то говорят, что рассматриваются упорядоченные пары (порядок элементов в паре важен), если нет - неупорядоченные. Если ребро
соединяет вершину
с вершиной
и пара
считается упорядоченной, то это ребро называется ориентированным, вершина
- его началом, вершина
- концом. Если же эта пара считается неупорядоченной, то ребро называется неориентированным, а обе вершины - его концами. Чаще всего рассматривают графы, в которых все ребра имеют один тип - либо ориентированные, либо неориентированные. Соответственно и весь граф называют ориентированным или неориентированным. На рисунках ориентацию ребра (направление от начала к концу) указывают стрелкой. На рис. 1.1 показаны неориентированные графы, а на рис. 1.2 - ориентированные.
Кратные ребра.
Следующий пункт, требующий уточнения, - могут ли разные ребра иметь одинаковые начала и концы? Если да, то говорят, что в графе допускаются кратные ребра. Граф с кратными ребрами называют также мультиграфом. На рис. 1.2 изображены два графа, левый является ориентированным мультиграфом, а правый - ориентированным графом без кратных ребер.
Петли.
Ребро, которому поставлена в соответствие пара вида , то есть ребро, соединяющее вершину
с нею же самой, называется петлей. Если такие ребра не допускаются, то говорят, что рассматриваются графы без петель.
Р РёСЃ. 1.2.В
РљРѕРјР±РёРЅРёСЂСѓСЏ эти три признака, можно получить разные варианты определения понятия графа. Особенно часто встречаются неориентированные графы без петель Рё кратных ребер. Такие графы называют обыкновенными. Если РІ графе нет кратных ребер, то можно просто отождествить ребра СЃ соответствующими парами вершин - считать, что ребро это Рё есть пара вершин. Чтобы исключить петли, достаточно оговорить, что вершины, образующие ребро, должны быть различны. Рто РїСЂРёРІРѕРґРёС‚ Рє следующему определению обыкновенного графа.
Определение. Обыкновенным графом называется пара , где
- конечное множество,
- множество неупорядоченных пар различных элементов из
. Рлементы множества
называются вершинами графа, элементы множества
- его ребрами.
Слегка модифицируя это определение, можно получить определения других типов графов без кратных ребер: если заменить слово "неупорядоченных" словом "упорядоченных", получится определение ориентированного графа без петель, если убрать слово "различных", получится определение графа с петлями. Ориентированный граф часто называют орграфом.
В дальнейшем термин "граф" мы будем употреблять в смысле "обыкновенный граф", а рассматривая другие типы графов, будем специально это оговаривать.
Множество вершин графа будем обозначать через
, множество ребер -
, число вершин -
, число ребер -
.
РР· определения РІРёРґРЅРѕ, что для задания обыкновенного графа достаточно перечислить его вершины Рё ребра, причем каждое ребро должно быть парой вершин. Положим, например, ,
. Тем самым задан граф
СЃ
,
. Если граф не слишком велик, то более наглядно представить его можно с помощью рисунка, на котором вершины изображаются кружками или иными значками, а ребра - линиями, соединяющими вершины. Заданный выше граф
показан на рисунке 1.3. Мы будем часто пользоваться именно этим способом представления графа, при этом обозначения вершин иногда будут помещаться внутри кружков, изображающих вершины, иногда рядом с ними, а иногда, когда имена вершин несущественны, и вовсе опускаться.
Р РёСЃ. 1.3.В
Напомним, что бинарным отношением на множестве называется любое подмножество
множества
, состоящего из всевозможных упорядоченных пар элементов множества
. Каждому такому отношению можно поставить в соответствие граф отношения
. Сравнивая с тем, что говорилось выше об определениях различных типов графов, видим, что понятие бинарного отношения эквивалентно понятию ориентированного графа с петлями. Другие типы графов без кратных ребер - это частные виды бинарных отношений. Отношение
называется рефлексивным, если для любого
пара
принадлежит
, и антирефлексивным, если ни одна такая пара не принадлежит
. Отношение называется симметричным, если из
следует, что
. В графе антирефлексивного и симметричного отношения нет петель и для каждой пары вершин либо нет ни одного, либо есть два ребра, соединяющих эти вершины. Если в таком графе каждую пару ориентированных ребер, соединяющих одни и те же две вершины, заменить одним неориентированным ребром, то получится обыкновенный граф.
Легко найти примеры графов РІ самых разных областях науки Рё практики. Сеть РґРѕСЂРѕРі, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы - РІ этих случаях графы возникают естественно Рё РІРёРґРЅС‹ "невооруженным глазом". РџСЂРё желании графы можно обнаружить практически РіРґРµ СѓРіРѕРґРЅРѕ. Рто наглядно показано РІ РєРЅРёРіРµ Р”.Кнута [D.E.Knuth, "The Stanford GraphBase"] - графы извлекаются РёР· романа "РђРЅРЅР° Каренина", РёР· картины Леонардо РґР° Винчи, РёР· материалов Бюро Ркономического Анализа РЎРЁРђ Рё РёР· РґСЂСѓРіРёС… источников.
Немало поводов для появления графов и в самой математике. Наиболее очевидный пример - любой многогранник в трехмерном пространстве. Вершины и ребра многогранника можно рассматривать как вершины и ребра графа. При этом мы отвлекаемся от того, как расположены элементы многогранника в пространстве, оставляя лишь информацию о том, какие вершины соединены ребрами. На рис. 1.4 показаны три способа изобразить один и тот же граф трехмерного куба.
Р РёСЃ. 1.4.В
Еще один способ образования графов из геометрических объектов иллюстрирует рис. 1.5. Слева показаны шесть кругов на плоскости, а справа - граф, в котором каждая вершина соответствует одному из этих кругов и две вершины соединены ребром в том и только том случае, когда соответствующие круги пересекаются. Такие графы называют графами пересечений. Можно построить граф пересечений семейства интервалов на прямой, или дуг окружности, или параллелепипедов. Вообще, для любого семейства множеств можно построить граф пересечений с множеством вершин
, в котором ребро
имеется тогда и только тогда, когда
Рё
. Рзвестно, что любой граф можно представить как граф пересечений некоторого семейства множеств.
Р РёСЃ. 1.5.В
Возьмем какое-нибудь множество , состоящее из
элементов, и будем рассматривать всевозможные (обыкновенные!) графы с множеством вершин
. Обозначим число таких графов через
. Рти графы различаются только множествами ребер, Р° каждое ребро - это неупорядоченная пара различных элементов РёР·
. В комбинаторике такие пары называются сочетаниями из
по 2, их число равно
Каждая пара может быть включена или не включена в множество ребер графа. Применяя правило произведения, приходим к следующему результату:
Теорема 1. .
Если в графе имеется ребро , то говорят, что вершины
Рё
смежны в этом графе, ребро
инцидентно каждой из вершин
,
, а каждая из них инцидентна этому ребру.
Множество всех вершин графа, смежных с данной вершиной , называется окрестностью этой вершины и обозначается через
.
РќР° практике удобным Рё эффективным РїСЂРё решении РјРЅРѕРіРёС… задач СЃРїРѕСЃРѕР±РѕРј задания графа являются так называемые СЃРїРёСЃРєРё смежности. Рти СЃРїРёСЃРєРё РјРѕРіСѓС‚ быть реализованы различными способами РІ РІРёРґРµ конкретных структур данных, РЅРѕ РІ любом случае речь идет Рѕ том, что для каждой вершины перечисляются РІСЃРµ смежные СЃ ней вершины, С‚.Рµ. элементы множества
. Такой способ задания дает возможность быстрого просмотра окрестности вершины.
Число вершин, смежных с вершиной , называется степенью вершины
и обозначается через
.
Если сложить степени всех вершин некоторого графа, то каждое ребро внесет в эту сумму вклад, равный 2, поэтому справедливо следующее утверждение:
Теорема 2. .
Рто равенство известно как "лемма Рѕ рукопожатиях". РР· него следует, что число вершин нечетной степени РІ любом графе четно.
Вершину степени называют изолированной.
Граф называют регулярным степени , если степень каждой его вершины равна
.
Набор степеней графа - это последовательность степеней его вершин, выписанных в неубывающем порядке.
Рассмотрим некоторые особенно часто встречающиеся графы.
Пустой граф - граф, не содержащий ни одного ребра. Пустой граф с множеством вершин обозначается через
.
Полный граф - граф, в котором каждые две вершины смежны. Полный граф с множеством вершин обозначается через
.
Граф , в частности, имеет одну вершину и ни одного ребра. Очевидно,
. Будем считать также, что существует граф
, у которого
.
Цепь(путь) - граф с множеством вершин
и множеством ребер
.
Цикл - граф, который получается из графа
добавлением ребра
.
Все эти графы при показаны на рис. 1.6
Р РёСЃ. 1.6.В
Пусть - граф с
вершинами, причем
. Построим квадратную матрицу
РїРѕСЂСЏРґРєР°
, в которой элемент
, стоящий на пересечении строки с номером
и столбца с номером
, определяется следующим образом:
Она называется матрицей смежности графа. Матрицу смежности можно построить и для ориентированного графа, и для неориентированного, и для графа с петлями. Для обыкновенного графа она обладает двумя особенностями: из-за отсутствия петель на главной диагонали стоят нули, а так как граф неориентированный, то матрица симметрична относительно главной диагонали. Обратно, каждой квадратной матрице порядка , составленной из нулей и единиц и обладающей двумя указанными свойствами, соответствует обыкновенный граф с множеством вершин
.
Другая матрица, ассоциированная с графом - это матрица инцидентности. Для ее построения занумеруем вершины графа числами от 1 до , а ребра - числами от 1 до
. Матрица инцидентности
имеет
строк и
столбцов, а ее элемент
равен 1, если вершина с номером
инцидентна ребру с номером
, в противном случае он равен нулю. На рис. 1.7 показан граф с занумерованными вершинами и ребрами и его матрицы смежности и инцидентности.
Р РёСЃ. 1.7.В
Для ориентированного графа матрица инцидентности определяется несколько иначе: ее элемент равен 1, если вершина
является началом ребра
, и равен
, если она является концом этого ребра, и он равен
, если эта вершина и это ребро не инцидентны друг другу.
Часто, особенно когда графы используются для моделирования реальных систем, их вершинам, или ребрам, или и тем, и другим приписываются некоторые числа. Природа этих чисел может быть самая разнообразная. Например, если граф представляет собой модель железнодорожной сети, то число, приписанное ребру, может указывать длину перегона между двумя станциями, или наибольший вес состава, который допустим для этого участка пути, или среднее число поездов, проходящих через этот участок в течение суток и т.п. Что бы ни означали эти числа, сложилась традиция называть их весами, а граф с заданными весами вершин и или ребер - взвешенным графом.
На рис. 1.8 изображены два графа с одним и тем же множеством вершин . При внимательном рассмотрении можно обнаружить, что это разные графы - в левом имеется ребро
, в правом же такого нет. В то же время, если не обращать внимания на наименования вершин, то эти графы явно одинаково устроены: каждый из них - цикл из четырех вершин. Во многих случаях при исследовании строения графов имена или номера вершин не играют роли, и такие графы, один из которых получается из другого переименованием вершин, удобнее было бы считать одинаковыми. Для того чтобы это можно было делать "на законном основании", вводится понятие изоморфизма графов.
Р РёСЃ. 1.8.В
Определение. Графы и
называются изоморфными, если существует такая биекция
множества
на множество
, что
тогда и только тогда, когда
. Отображение
в этом случае называется изоморфизмом графа
на граф
.
Тот факт, что графы и
изоморфны, записывается так:
.
Для графов, изображенных на рис. 1.8, изоморфизмом является, например, отображение, задаваемое следующей таблицей:
Заметим, что в этом примере есть и другие изоморфизмы первого графа на второй.
Сформулированное определение изоморфизма годится и для ориентированных графов, нужно только обе упоминаемые в нем пары вершин считать упорядоченными.
Рзоморфизм - бинарное отношение РЅР° множестве графов. Очевидно, что это отношение рефлексивно, симметрично Рё транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. РљРѕРіРґР° РіРѕРІРѕСЂСЏС‚, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, Сѓ которого стерты имена (пометки) вершин, поэтому абстрактные графы РёРЅРѕРіРґР° называют также непомеченными графами.
Для получения новых графов можно использовать разнообразные операции над графами. Здесь мы рассмотрим два вида операций - локальные, при которых заменяются, удаляются или добавляются отдельные элементы графа, и алгебраические, когда новый граф строится по определенным правилам из нескольких имеющихся.
Простейшая операция - удаление ребра. При удалении ребра сохраняются все вершины графа и все его ребра, кроме удаляемого. Обратная операция - добавление ребра.
При удалении вершины вместе с вершиной удаляются и все инцидентные ей ребра. Граф, получаемый из графа удалением вершины
, обозначают
. При добавлении вершины к графу добавляется новая изолированная вершина. С помощью операций добавления вершин и ребер можно "из ничего", то есть из графа
, построить любой граф.
Операция стягивания ребра определяется следующим образом. Вершины
Рё
удаляются из графа, к нему добавляется новая вершина
и она соединяется ребром с каждой вершиной, с которой была смежна хотя бы одна из вершин
.
Операция подразбиения ребра действует следующим образом. РР· графа удаляется это ребро, Рє нему добавляется новая вершина
и два новых ребра
Рё
. На рис. 1.10 изображены исходный граф
, граф
, полученный из него стягиванием ребра
Рё
, полученный подразбиением того же ребра. В обоих случаях вновь добавленная вершина обозначена цифрой
.
Р РёСЃ. 1.10.В
Граф называется подграфом графа
, если
,
. Всякий подграф может быть получен из графа удалением некоторых вершин и ребер. На рис. 1.11 изображены граф
и его подграфы
,
,
,
.
Р РёСЃ. 1.11.В
Подграф графа
называется остовным, если
. Остовный подграф может быть получен из графа удалением некоторых ребер, вершины же остаются в неприкосновенности. На рис. 1.11
- остовный подграф графа
, Р°
,
Рё
не являются остовными подграфами.
Другая важная разновидность подграфов - порожденные подграфы. Пусть задан граф и в нем выбрано множество вершин
. Рассмотрим подграф
, РіРґРµ
состоит из всех тех ребер графа
, у которых оба конца принадлежат
. Говорят, что этот подграф порожден множеством вершин
. Он обозначается через
. Порожденный подграф может быть получен из графа удалением "лишних" вершин, т.е. вершин, не принадлежащих
.
Можно определить также подграф, порожденный множеством ребер . Рто подграф
, РіРґРµ
состоит из всех вершин, инцидентных ребрам из
.
На рис. 1.11 - подграф графа
, порожденный множеством вершин
, С‚.Рµ.
, он же порождается множеством ребер
; подграф
не порождается множеством вершин, но порождается множеством ребер
; подграф
не является ни остовным, ни порожденным в каком-либо смысле.
Поскольку граф состоит из двух множеств (вершины и ребра), то различные операции над множествами естественным образом порождают соответствующие операции над графами. Например, объединение двух графов и
определяется как граф
, у которого
,
, а пересечение - как граф
, у которого
,
. Обе операции иллюстрирует рис. 1.12.
Р РёСЃ. 1.12.В
Дополнением (дополнительным графом) к графу называется граф
, у которого множество вершин то же, что у
, а множество ребер является дополнением множества
РґРѕ множества всех неупорядоченных пар вершин. Рначе РіРѕРІРѕСЂСЏ, РґРІРµ различные вершины смежны РІ графе
тогда и только тогда, когда они несмежны в графе
. Например,
. Другой пример показан на рис. 1.13. Очевидно, что всегда
.
Р РёСЃ. 1.13.В
Под суммой двух абстрактных графов понимают объединение графов с непересекающимися множествами вершин. Точнее говоря, имеется в виду следующее. Сначала вершинам графов-слагаемых присваиваются имена (пометки, номера) так, чтобы множества вершин не пересекались, затем полученные графы объединяются. Операция сложения ассоциативна, то есть
для любых трех графов. Поэтому можно образовывать сумму любого числа графов, не указывая порядка действий с помощью скобок. Если складываются
экземпляров одного и того же графа
, то полученный граф обозначается через
. Например,
. На рис. 1.14 изображен граф
.
Р РёСЃ. 1.14.В
Р РёСЃ. 1.15.В
Соединением двух графов и
называется граф, получаемый из их суммы добавлением всех ребер, соединяющих вершины первого слагаемого с вершинами второго. Будем записывать эту операцию как
. На рис. 1.15 представлен граф
. Легко видеть, что операции сложения и соединения графов связаны друг с другом следующими простыми соотношениями:
Введем еще два типа специальных графов, которые легко описываются с помощью операции соединения. Первый - полный двудольный граф . В этом графе множество вершин разбито на два подмножества (доли), в одном из которых
вершин, в другом
, и две вершины в нем смежны тогда и только тогда, если они принадлежат разным подмножествам. Второй - колесо
. На рис. 1.16 показаны графы
Рё
.
Р РёСЃ. 1.16.В
Произведение графов
Рё
определяется следующим образом. Множеством вершин графа
является декартово произведение множеств
Рё
, то есть вершины этого графа - упорядоченные пары
, РіРґРµ
- вершина первого сомножителя,
- вершина второго. Вершины
Рё
РІ
смежны тогда и только тогда, если
Рё
смежна с
в графе
, или
Рё
смежна с
в графе
. С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух цепей дает прямоугольную решетку (см. рис. 1.17). Если один из сомножителей превратить в цикл, добавив одно ребро, то прямоугольная решетка превратится в цилиндрическую, а если и второй сомножитель превратить в цикл, то получится тороидальная решетка.
Р РёСЃ. 1.17.В
Другой пример - - мерный куб
, определяемый следующим образом. Вершинами его являются всевозможные упорядоченные двоичные наборы длины
. Всего, таким образом, в этом графе
вершин. Вершины
Рё
смежны в нем тогда и только тогда, когда наборы
Рё
различаются точно в одной координате. С помощью операции произведения граф
можно определить рекурсивно:
На рис. 1.18 показано, как получается из
.
Р РёСЃ. 1.18.В
Деревом называется связный граф, не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом.
РР· теоремы 2 предыдущей лекции следует, что РІРѕ РІСЃСЏРєРѕРј дереве, РІ котором РЅРµ меньше РґРІСѓС… вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами, или листьями. Р’ действительности легко доказать, что РІ каждом дереве РЅРµ меньше РґРІСѓС… листьев, Р° цепь - пример дерева, РІ котором точно РґРІР° листа.
В следующих двух теоремах устанавливаются некоторые свойства деревьев.
Теорема 1. Граф с вершинами и
ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:
Доказательство.
Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего.
(1) Рё (2) (3). Рндукция РїРѕ числу вершин. РџСЂРё
утверждение очевидно. При
в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве
вершин и, по предположению индукции,
ребра. Следовательно, в исходном дереве было
ребро.
(2) и (3) (1). Пусть в графе, не имеющем циклов,
ребро, а его компонентами связности являются
, причем
состоит из
вершин,
. Каждая компонента является деревом, поэтому, как доказано выше, число ребер в
равно
, а всего ребер в графе
. Значит,
и граф связен.
(1) и (3) (2). Рассмотрим связный граф с
ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем
, а это противоречит доказанному выше.
Теорема 2. Если - дерево, то
в любая пара вершин соединена единственным путем;
при добавлении к любого нового ребра образуется цикл;
при удалении из любого ребра он превращается в несвязный граф.
Доказательство.
Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины и
. Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине
). Пусть
- последняя вершина этого совпадающего начала, а после
в одном пути следует вершина
, а в другом - вершина
. Рассмотрим ребро
. Если его удалить из графа, то в оставшемся подграфе вершины
Рё
будут соединимыми - соединяющий их маршрут можно построить так: взять отрезок первого пути от
РґРѕ
и к нему присоединить отрезок второго от
РґРѕ
, взятый в обратном порядке. Но это означает, что ребро
РЅРµ является перешейком. Однако РёР· теоремы 4 предыдущей лекции следует, что РІ дереве каждое ребро является перешейком. Ртим доказано утверждение 1). Утверждения 2) Рё 3) следуют РёР· 1).
Отметим, что единственный путь, соединяющий две вершины дерева, всегда простой (если путь не является простым, в нем обязательно содержится цикл).
Геометрический граф - это плоская фигура, состоящая из вершин - точек плоскости и ребер - линий, соединяющих некоторые пары вершин. Всякий граф можно многими способами представить геометрическим графом, и мы уже не раз пользовались этой возможностью. На рис. 3.6 показаны два геометрических графа и
, представляющих, как нетрудно проверить, один и тот же обыкновенный граф. Простое устройство этого графа, очевидное на изображении слева, не так легко обнаружить, рассматривая изображение справа. Главная причина этого в том, что в
ребра не имеют "лишних" пересечений.
Р РёСЃ. 3.6.В
Геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины, называют плоским графом, а по отношению к представляемому им обыкновенному графу - его плоской укладкой. Не каждый граф допускает плоскую укладку. Граф, для которого существует плоская укладка, называется планарным графом. Кроме удобства визуального анализа, есть немало поводов, в том числе и сугубо практических, для интереса к планарным графам и их плоским укладкам.
Если плоскость разрезать по ребрам плоского графа, она распадется на связные части, которые называют гранями. Всегда имеется одна неограниченная внешняя грань, все остальные грани называются внутренними. Если в плоском графе нет циклов, то у него имеется только одна грань. Если же циклы есть, то граница каждой грани содержит цикл, но не обязательно является циклом. На рис. 3.7 показан плоский граф с пятью занумерованными гранями. Граница грани с номером 3 состоит из двух циклов, а граница грани с номером 2 кроме цикла длины 5 включает еще дерево из трех ребер.
Р РёСЃ. 3.7.В
Множества ребер, образующие границы граней, могут быть разными для разных плоских укладок одного и того же графа. На рис. 3.8 показаны две плоские укладки одного графа. В левой укладке есть две грани, границы которых являются простыми циклами длины 5. В правой укладке таких граней нет, но есть грани, ограниченные циклами длины 4 и 6. Однако число граней, как показывает следующая теорема, не зависит от укладки, т.е. является инвариантом планарного графа.
Р РёСЃ. 3.8.В
Теорема 6 (формула Рйлера). Количество граней РІ любой плоской укладке планарного графа, имеющего вершин,
ребер и
компонент связности, равно
.
Доказательство.
Докажем сначала утверждение теоремы при . Рассмотрим связный плоский граф
. Если в нем нет циклов, то имеется единственная грань, а
, и формула верна. Если же есть хотя бы один цикл, то возьмем какое-нибудь ребро
, принадлежащее простому циклу
. Рто ребро принадлежит границе РґРІСѓС… граней, РѕРґРЅР° РёР· которых целиком лежит внутри цикла
, другая - снаружи. Если удалить ребро
из графа, эти две грани сольются в одну. Граф
, полученный из графа
удалением ребра
, очевидно, будет плоским и связным, в нем на одно ребро и на одну грань меньше, чем в
, а число вершин осталось прежним. Если в
еще есть циклы, то, удалив еще одно цикловое ребро, получим граф
. Будем продолжать удаление цикловых ребер до тех пор, пока не получится связный плоский граф
без циклов, т.е. дерево. У него
ребро и единственная грань. Значит, всего было удалено
ребер, а так как при удалении каждого ребра число граней уменьшалось на единицу, то в исходном графе было
грани. Таким образом, формула верна для любого связного плоского графа. Если граф несвязен, то в компоненте связности, имеющей
вершин и
ребер, как доказано выше, будет
внутренняя грань. Суммируя по всем компонентам и прибавляя 1 для учета внешней грани, убеждаемся в справедливости формулы в общем случае.
Следствие 1. Если в планарном графе вершин,
, Рё
ребер, то
.
Доказательство.
Если в графе нет циклов, то и неравенство выполняется при
. Рассмотрим плоский граф
СЃ
гранями, в котором имеются циклы. Занумеруем грани числами от
РґРѕ
и обозначим через
количество ребер, принадлежащих грани с номером
. Так как граница каждой грани содержит цикл, то
для каждого
, следовательно,
. С другой стороны, каждое ребро принадлежит границе не более чем двух граней, поэтому
. РР· этих РґРІСѓС… неравенств следует, что
. Применяя формулу Рйлера, получаем
.
Следствие 1 дает необходимое условие планарности, которое в некоторых случаях позволяет установить, что граф не является планарным. Рассмотрим, например, полный граф . У него
,
, и мы видим, что неравенство из следствия 1 не выполняется. Значит, этот граф непланарен. В то же время существуют графы, не являющиеся планарными, для которых неравенство следствия 1 выполняется. Пример - полный двудольный граф
. У него 6 вершин и 9 ребер. Неравенство выполняется, но мы сейчас установим, что он непланарен. Заметим, что в этом графе нет циклов длины 3 (так как он двудольный, в нем вообще нет циклов нечетной длины). Поэтому граница каждой грани содержит не менее четырех ребер. Повторяя рассуждения из доказательства следствия 1, но используя неравенство
вместо
, получаем следующий результат:
Следствие 2. Если в планарном графе вершин,
,
ребер и нет циклов длины
, то
.
Для графа неравенство следствия 2 не выполняется, и это доказывает, что он непланарен.
Рзвестно несколько критериев планарности, сформулируем без доказательства РґРІР° РёР· РЅРёС…. Два графа называют гомеоморфными,если РёР· РЅРёС… СЃ помощью подразбиения ребер можно получить изоморфные графы. РќР° СЂРёСЃ. 3.9 изображены гомеоморфные графы.
Р РёСЃ. 3.9.В
Сформулируем без доказательства два критерия планарности.
Теорема 7 (критерий Понтрягина-Куратовского). Граф планарен тогда и только тогда, когда у него нет подграфов, гомеоморфных или
.
Граф называется стягиваемым к графу
, если
можно получить из
последовательностью операций стягивания ребер.
Теорема 8 (критерий Вагнера). Граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к или
.
Отметим, что, несмотря на внешнее сходство двух теорем, фигурирующие в них понятия гомеоморфизма и стягиваемости существенно различаются. На рис. 3.10 изображен граф, который называют графом Петерсена. В нем нет подграфа, гомеоморфного , так как в графе
каждая вершина имеет степень
, а в графе Петерсена степень каждой вершины равна
. При удалении вершин и ребер и подразбиении ребер степени вершин не увеличиваются. В то же время легко видеть, что граф Петерсена можно превратить в
стягиванием пяти ребер.
РџРѕРёСЃРє РІ глубину - вероятно, наиболее важная РІРІРёРґСѓ многочисленности приложений стратегия РѕР±С…РѕРґР° графа. Рдея этого метода - идти вперед РІ неисследованную область, РїРѕРєР° это возможно, если же РІРѕРєСЂСѓРі РІСЃРµ исследовано, отступить РЅР° шаг назад Рё искать новые возможности для продвижения вперед. Метод РїРѕРёСЃРєР° РІ глубину известен РїРѕРґ разными названиями, например, "бэктрекинг", "РїРѕРёСЃРє СЃ возвращением".
Понятия новой, открытой, закрытой и активной вершин для поиска в глубину имеют такой же смысл, как и для поиска в ширину. Отметим, что всегда имеется не более чем одна активная вершина.
Обход начинается с посещения заданной стартовой вершины , которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине
ребро
и посещается вершина
. Она становится открытой и активной. Заметим, что при поиске в ширину вершина
оставалась активной до тех пор, пока не были исследованы все инцидентные ей ребра. В дальнейшем, как и при поиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине
, уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер
, это ребро исследуется. Если вершина
новая, то она посещается и превращается в открытую.
Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной выбирается последняя вершина. Схематически это показано на рис. 5.1.
Р РёСЃ. 5.1.В
Обозначим стек для открытых вершин через , остальные обозначения сохраняют тот же смысл, что и в предыдущем разделе. Через
обозначается верхний элемент стека (т.е. последний элемент, добавленный к стеку). Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной
может быть записана следующим образом (DFS - Depth First Search).
Procedure DFS(a)
посетить вершину
while do
if имеется неисследованное ребро
then исследовать ребро
if вершина новая
then посетить вершину
else удалить из
Еще раз обратим внимание на основное отличие этой процедуры от аналогичной процедуры поиска в ширину. При поиске в ширину вершина, став активной, остается ею, пока не будет полностью исследована ее окрестность, после чего она становится закрытой. При поиске в глубину, если в окрестности активной вершины обнаруживается новая вершина
, то
помещается в стек и при следующем повторении цикла while станет активной. При этом
остается РІ стеке Рё через какое-то время СЃРЅРѕРІР° станет активной. Рначе РіРѕРІРѕСЂСЏ, ребра, инцидентные вершине
, будут исследованы не подряд, а с перерывами.
Алгоритм обхода всего графа - тот же, что и в случае поиска в ширину только нужно очередь заменить стеком, а процедуру BFS - процедурой DFS.
Свойства 1 и 2 поиска в ширину, отмеченные в предыдущем разделе, сохраняются и для поиска в глубину. Остается верной и оценка трудоемкости , но ее доказательство требует несколько иных рассуждений, так как каждая вершина теперь может становиться активной несколько раз. Однако каждое ребро рассматривается только два раза (один раз для каждой инцидентной ему вершины), поэтому в операторе if в строке 5 ветвь then (строки 6-9) повторяется
раз. В этом же операторе ветвь else (строка 10) повторяется
раз, так как каждая вершина может быть удалена из стека только один раз. В целом получается
, причем остаются справедливыми сделанные в предыдущей лекции замечания об условиях, при которых имеет место эта оценка.
Работа всякого алгоритма обхода состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра - зависит от конкретной задачи, для решения которой производится обход. В любом случае, однако, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую.
Рдея РїРѕРёСЃРєР° РІ ширину состоит РІ том, чтобы посещать вершины РІ РїРѕСЂСЏРґРєРµ РёС… удаленности РѕС‚ некоторой заранее выбранной или указанной стартовой вершины . Рначе РіРѕРІРѕСЂСЏ, сначала посещается сама вершина
, затем все вершины, смежные с
, то есть находящиеся от нее на расстоянии
, затем вершины, находящиеся от
на расстоянии
, Рё С‚.Рґ.
Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной . Вначале все вершины помечаются как новые. Первой посещается вершина
, она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины
. Рта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину
с новой вершиной
, то вершина
посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.
Основная особенность РїРѕРёСЃРєР° РІ ширину, отличающая его РѕС‚ РґСЂСѓРіРёС… СЃРїРѕСЃРѕР±РѕРІ РѕР±С…РѕРґР° графов, состоит РІ том, что РІ качестве активной вершины выбирается та РёР· открытых, которая была посещена раньше РґСЂСѓРіРёС…. Рменно этим обеспечивается главное свойство РїРѕРёСЃРєР° РІ ширину: чем ближе вершина Рє старту, тем раньше РѕРЅР° будет посещена. Для реализации такого правила выбора активной вершины СѓРґРѕР±РЅРѕ использовать для хранения множества открытых вершин очередь - РєРѕРіРґР° новая вершина становится открытой, РѕРЅР° добавляется РІ конец очереди, Р° активная выбирается РІ ее начале. Схематически процесс изменения статуса вершин изображен РЅР° СЂРёСЃ. 4.1. Черным кружком обозначена активная вершина.
Р РёСЃ. 4.1.В
Опишем процедуру поиска в ширину (BFS - от английского названия этого алгоритма - Breadth First Search) из заданной стартовой вершины . В этом описании
обозначает множество всех вершин, смежных с вершиной
,
- очередь открытых вершин. Предполагается, что при посещении вершины она помечается как посещенная и эта пометка означает, что вершина уже не является новой.
Procedure BFS(a)
посетить вершину
while do
for do
исследовать ребро
if вершина новая
then посетить вершину
Отметим некоторые свойства процедуры BFS.
Процедура BFS заканчивает работу после конечного числа шагов.
Действительно, при каждом повторении цикла while из очереди удаляется одна вершина. Вершина добавляется к очереди только тогда, когда она посещается. Каждая вершина может быть посещена не более одного раза, так как посещаются только новые вершины, а в результате посещения вершина перестает быть новой. Таким образом, число повторений цикла while не превосходит числа вершин.
В результате выполнения процедуры BFS будут посещены все вершины из компоненты связности, содержащей вершину a, и только они.
Очевидно, что вершина может быть посещена только в том случае, когда существует путь, соединяющий ее с вершиной (так как посещается всегда вершина, смежная с уже посещенной). То, что каждая такая вершина будет посещена, легко доказывается индукцией по расстоянию от данной вершины до вершины
.
Время работы процедуры BFS есть , где
- число ребер в компоненте связности, содержащей вершину
.
РР· предыдущих рассуждений РІРёРґРЅРѕ, что каждая вершина РёР· этой компоненты становится активной точно РѕРґРёРЅ раз. Внутренний цикл for для активной вершины выполняется
раз. Следовательно, общее число повторений внутреннего цикла будет равно
.
Ртак, процедура BFS() РїСЂРѕРёР·РІРѕРґРёС‚ РѕР±С…РѕРґ компоненты связности, содержащей вершину
. Чтобы перейти к другой компоненте, достаточно выбрать какую-нибудь новую вершину (если такие вершины еще имеются), в качестве стартовой. Пусть
- множество вершин графа. Следующий алгоритм осуществляет полный обход графа методом поиска в ширину.
Алгоритм 1. Поиск в ширину.
пометить все вершины как новые
создать пустую очередь
for do if
новая then BFS(
)
Учитывая, что цикл for в строке повторяется
раз, где
- число вершин графа, получаем общую оценку трудоемкости
. Необходимо отметить, что эта оценка справедлива РІ предположении, что время, требуемое для просмотра окрестности вершины, пропорционально степени этой вершины. Рто имеет место, например, если граф задан списками смежности. Если же граф задан матрицей смежности, то для просмотра окрестности любой вершины будет затрачиваться время, пропорциональное
. В этом случае общее время работы алгоритма будет оцениваться как
. Наибольшее значение величины
при данном
равно
, т.е. имеет порядок
. Таким образом, трудоемкость алгоритма поиска в ширину при задании графа списками смежности не выше, чем при задании матрицей смежности. В целом же первый способ задания предпочтительнее, так как дает выигрыш для графов с небольшим числом ребер.
В качестве простейшего примера применения поиска в ширину для графа рассмотрим задачу выявления компонент связности. Допустим, мы хотим получить ответ в виде таблицы, в которой для каждой вершины указан номер
компоненты, которой принадлежит эта вершина. Компоненты будут получать номера в процессе обхода. Для решения этой задачи достаточно ввести переменную
со значением, равным текущему номеру компоненты, и каждый раз при посещении новой вершины
полагать
. Значение
первоначально устанавливается равным
и модифицируется при каждом вызове процедуры BFS.
. РџР РМЕНЕНРР• ТЕОРРРГРАФОВ Р’ ТЕОРРР РНФОРМАЦРР.
Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
refdb.ru