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

(iii)=> (iv). Удаление любого ребра приводит к графу с n вершинами и n -- 2 ребрами, который не может быть связным по теореме 5В.

(iv)=>(v). Так как Т связен, то каждая пара его вершин соединена по крайней мере одной простой цепью. Если же данная пара вершин соединена двумя простыми цепями, то они замыкаются в цикл, а это противоречит тому, что каждое ребро в Т является мостом.

(v)=> (vi). Если Т содержит цикл, то любые две вершины этого цикла соединены по крайней мере двумя простыми цепями. Добавим теперь к графу Т какое-то ребро е; тогда получим цикл, поскольку инцидентные ребру е вершины уже соединены в Т простой цепью. То, что при этом мы получим только один цикл.

(vi)=> (i). Предположим, что Т несвязен; тогда добавление любого ребра, соединяющего вершину одной компоненты с вершиной другой компоненты, не приводит к образованию цикла.

Следствие 9В. Пусть G -- лес с n вершинами и k компонентами, тогда G имеет n -- k ребер.

Доказательство. Применим к каждой компоненте графа G предложение (ii) теоремы 9А. //

Заметим, что по лемме о рукопожатиях сумма степеней всех n вершин дерева равна удвоенному числу его ребер (2n - 2); отсюда следует, что при n ? 2 дерево, имеющее n вершин, всегда содержит не менее двух висячих вершин.

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

В общем случае обозначим через G произвольный граф с n вершинами, m ребрами и k компонентами. Применяя описанную выше процедуру к каждой компоненте G, получим в результате граф, называемый остовным лесом. Число удаленных в этой процедуре ребер называется циклическим рангом (или дипломатическим числом) графа G и обозначается через г(G). Легко видеть, что г(G)= m -- n + k и является неотрицательным целым числом (по теореме 5В). Таким образом, циклический ранг дает меру связности графа: циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице. Удобно также определить коциклический ранг (или ранг разреза) графа G как число ребер в его остовном лесе; коциклический ранг обозначается через х(G) и равен n -- k.

Рис. 2 Рис. 3

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

Теорема 9С. Если Т -- остовный лес графа П, то (i) всякий разрез в G имеет общее ребро с Т; (ii) каждый цикл в G имеет общее ребро с дополнением Т.

Доказательство. (i) Пусть С* -- разрез графа G, удаление которого разбивает одну из компонент G на два подграфа H и K. Поскольку Т -- остовный лес, в нем должно содержаться ребро, соединяющее вершину из H с вершиной из K; это и есть требуемое ребро.

(ii) Пусть С -- цикл в графе G, не имеющий ни одного общего ребра с дополнением Т; тогда С содержится в Т, что невозможно.

С понятием остовного леса Т графа G тесно связано понятие фундаментальной системы циклов, ассоциированной с Т. Оно определяется следующим образом: если добавить к Т любое не содержащееся в нем ребро графа G , то по предложению (vi) теоремы 9А получим единственный цикл; множество всех циклов, получаемых таким способом (т. е. путем добавления по отдельности каждого ребра из G, не содержащегося в Т), называется фундаментальной системой циклов, ассоциированной с T. В том случае, когда нас не интересует, какой остовный лес рассматривается, фундаментальная система циклов графа G. Ясно, что циклы данной фундаментальной системы должны быть различными и что их число должно равняться циклическому рангу графа G. На Рис. 4 показана фундаментальная система циклов графа, изображенного на Рис. 2, ассоциированная с остовным деревом, изображенным на Рис. 3.

Рис. 4

Надеяться, что удастся определить фундаментальную систему разрезов графа С, ассоциированную с данным остовным лесом Т. Покажу, что это действительно можно сделать. По предложению (iv) теоремы 9А удаление любого ребра из Т разбивает множество вершин дерева Т на два непересекающихся подмножества V₁ и V₂. Множество всех, ребер графа G, каждое из которых соединяет вершину из V₁ с вершиной из V₂ является разрезом графа G. Множество всех разрезов, полученных таким способом (т. е. удалением по отдельности каждого ребра из Т), называется фундаментальной системой разрезов, ассоциированной с Т. Ясно, что разрезы данной фундаментальной системы должны быть различными и что их число должно равняться коциклическому рангу графа С. Фундаментальной системой разрезов графа, изображенного на Рис. 2, ассоциированной с остовным деревом, изображенным на Рис. 3, является такая система: {е₁, е₅}, {е₂, е₅, е₇, е₈}, {е₃, е₆, е₇, е₈} и {е₄, е₆, е₈}.

ПРАКТИЧЕСКАЯ ЧАСТЬ

1) Можно ли ходом шахматного коня обойти шахматную доску размером

8 Х8 так, чтобы каждый ход встречался ровно один раз (при этом мы считаем, что ход «встречался», если конь переместился с одной клетки на другую любым из двух возможных способов)? Тот же вопрос для короля и ладьи. Как изменятся ответы для шахматной доски размером 7X7? Изложите свои ответы в терминах теории графов.

Ответ: Для доски 8х8:Что бы каждый ход встречался ровно один раз,должно выполняться условие: конь должен зайти на клетку и сойти с неё т.е перейдя к терминам теории графов ,получим :клетка-вершина графа ,каждая вершина имеет степень равную 2 (есть 2 ребра вход и выход).Значит степень каждой вершины будет чётной => согласно теореме этот граф будет гамильтоновым, а значит существует гамильтонова цепь-путь обхода шахматной доски. Данное утверждение справедливо не только для коня, но для ладьи и короля. Эти соображения не изменяются и для шахматной доски размером 7х7.

2) В графе Петерсена найдите (i) маршрут длины 4; (ii) циклы длины 5, 6, 8 и 9; (iii) разрезы, содержащие 3, 4 и 5 ребер

Ответ:

1) a>b>c>h>l(маршрут длины 4)

2) а)f>h>l>g>k>f (цикл длины 5)

В) a>b>c>d>k>f>a (6)

c) h>l>g>k>f>a>b>c>h (8)

d) d>e>l>g>b>c>h>f>k>d (9)

3) a) {1,2,3} -(разрез,содержащий 3 ребра)

b) {1,2,3,7} (4)

c) {4,5,6,7,8} (5)

3) Докажите, что ребро связного графа является мостом и в том и только в том случае, когда оно не содержится ни в одном из циклов

Ответ: Ребро {a,b} является мостом в том и только в том случае ,если оно не принадлежит ни одному циклу.

Прямая теорема: Если ребро{a,b} не принадлежит ни одному циклу ,при его удалении не остаётся пути, связывающего а и в то есть {a,b} является мостом.

Обратная теорема: Если ребро {a,b} -мост, то {a,b} не принадлежит ни одному циклу. Если бы ребро {a,b} принадлежало циклу, то пути удалении ребра {a,b} остался бы второй путь, связывающий а и в , то есть ребро {a,b} не было бы мостом следовательно {a,b} не принадлежит циклу.

4) В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде?

Ответ:

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

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

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

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

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

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

5) Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?

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

Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.

Заключение

Графы и информация

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

Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

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

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

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

C_nH_2n+2

Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Структурные формулы простейших углеводородов показаны на рисунке 6.1 (а - метан CH₄, б - этан C₂H₆).

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

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

Графы и биология

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

Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и физика

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

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

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

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

Список используемой литературы:

1. Уилсон Р. Введение в теорию графов.- М.:Мир,1977

2. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: ВШ, 1976

3. Березина Л.Ю. Графы и их применения. - М., 1979

4. Новиков Ф.А. Дискретная математика для программистов. - Спб.: Питер, 2003.-304с

5. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.- 2-е изд., перераб. и доп. - М.: Энергоатомиздат,1988.-480с

6. Новиков, Ф.А. Дискретная математика для программистов [Текст]/Ф.А. Новиков. - СПб.: Питер, 2003. - 304 с.

7. Овчинников, В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учебник для вузов [Текст]/В.А. Овчинников. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. - 228 с.

8. Подготовка к ЕГЭ. Информатика и ИКТ.[Текст]:учебное пособие / Под ред. Н. В. Макаровой. -- СПб.: Питер, 2007.-160c.

Размещено на Allbest.ru