Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
| Тема 7.4 Двудольные и изоморфные графы. Графы, которые отличаются только нумерацией вершин, называются изоморфными. У изоморфных графов матрицы совпадают при применении к ним элементарных алгебраических операций. На графах изоморфизм возможно представить как функцию: пусть G1(V1 E1 ) и G2(V2 E2) изоморфные графы, тогда существует функция Н-биекция, сохраняющая смежность H: V1V2 и e1=(vi vj)E1 e2=(h(vi ) h(vj))E2 e2=(vi vj)E2 e1=(h-1 (vi ) h-1(vj))E1 Теорема: изоморфизм графов есть отношение эквивалентности. Доказательство: 1. рефлексивность- h тождественная функция 2. симметричность- т.к. h: V1V2-биекция, то h-1 :V2V1 тоже биекция 3. транзитивность- h: G1G2 & f: G2G3hf: G1G3 Числовая характеристика, сохраняющаяся при изоморфизме, называется инвариат. У изоморфных графов все инварианты совпадают, но это не является признаком изоморфизма графов, т.е. при совпадении всех инвариантов мы не можем утверждать об изоморфности данных графов. Для определения изоморфизма между орграфами G  и Gможно предложить следующий алгоритм.Шаг 1. Если число вершин и число дуг, соответственно, совпадают для орграфов, то переходим к шагу 2. Иначе орграфы не изоморфны. Шаг 2. Для каждой вершины орграфов определяем пары чисел, равные полустепеням захода и исхода. Если каждой такой паре орграфа G найдется аналогичная пара орграфа G, то переходим к шагу 3. Иначе орграфы не изоморфны.Шаг 3. Если каждой рассмотренной паре чисел для орграфа G соответствует единственная аналогичная пара орграфа G, то есть единственное соответствие между вершинами орграфов из которого можно легко установить соответствие между дугами орграфов, т.е. они будут изоморфными. Если некоторой паре орграфа G соответствует не одна аналогичная пара орграфа G, то этой вершине орграфа G ставим в соответствие поочередно вершины орграфа G с аналогичной парой чисел. Из этих сопоставлений находим подстановки для дуг, инцидентным этим вершинам. Для вершин G имеющих только одну аналогичную пару чисел для G, так же находим подстановку для дуг, инцидентным им. Если из всех, не противоречащих друг другу, полученных подстановок удастся получить полную подстановку для всех дуг орграфов, то они будут изоморфными. Иначе нет. По подстановкам дуг, вошедшим в полную подстановку дуг, получим подстановку для вершин орграфов. Двудольным графом называется граф, у которого множество вершин можно разбить на два непересекающихся подмножества так, что ребра соединяют вершины из разных подмножеств. Паросочетанием в двудольном графе называется любое множество попарно несмежных ребер (у них нет общих вершин). Паросочетание называется максимальным для данного графа, если оно содержит наибольшее число ребер для всех возможных паросочетаний. Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c. Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S. Теорема Холла. Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)]. Венгерский алгоритм нахождения максимального паросочетания. Дан двудольный граф. Все определения для графа справедливы. Полным паросочетанием называется паросочетание (ПС), к которому нельзя добавить ни одного ребра графа, не нарушив условие несмежности ребер. Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание. Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими. Вершины, которые соединены толстыми ребрами – насыщенные. Остальные – ненасыщенные. Чередующейся цепью называется цепь, в которой тонкие и толстые ребра чередуются. Тонкой чередующейся цепью называется чередующаяся цепь, соединяющая 2 ненасыщенные вершины (В ней тонких ребер на 1 больше, чем толстых).
Количество ребер в новом паросочетании увеличится на 1. Максимальное паросочетание (МПС) найдено. Совершенное ПС – МПС обязательно. Матрицы смежности двудольных графов. A(M,N) [V] = M [W] = N Aij = 1, если есть ребро ViWj Если его нет, то Aij = 0. Чтобы найти полное паросочетание, нужно найти единицы, которые находятся в разных строках и разных столбцах. Алгоритм – тот же самый. При поисках мы можем двигаться по строкам и на углы в 90 градусов. Лабораторная работа № 4. Наибольшее паросочетание Цель работы:
Литература:
Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задание: Имеется m мужчин и n женщин. Каждый мужчина указывает несколько (может, нуль; может, одну; может, много) женщин, на которых он согласен жениться. Мнение женщин не спрашивают. Заключить наибольшее количество моногамных браков. Можно поставить эту задачу в терминах теории графов: Дан двудольный граф Bm,n. Найти наибольшее паросочетание. Краткие теоретические сведения: Двудольным графом называется граф Г( , ), в котором множество вершин такое, что каждое ребро ( ) соединяет вершину  с вершиной  .Паросочетанием называется множество ребер, не имеющих общих вершин. На рис. а) показан пример паросочетания, а на рис. б) - пример наибольшего паросочетания. 1 2 3 4 5 a) 1` 2` 3` 4` 5` 1 2 3 4 5 б) 1` 2` 3` 4` 5` Для решения задачи о наибольшем паросочетании применяется метод чередующихся цепей. Пусть М -паросочетание в двудольном графе. Цепь, в которую поочередно входят ребра из М (жирные) и из пе-М (тонкие) назовем чередующейся относительно М. Например, на рис. а) цепь (1, 1`, 2, 3`) -чередующаяся. Вершины, инцидентные ребрам, из М назовем насыщенными, прочие - ненасыщенными. Очевидно, что если в графе существует чередующаяся относительно М цепь с ненасыщенными концевыми вершинами (т.е. тонкими концевыми ребрами), то в ней тонких ребер на одно больше, чем жирных. Если цепь "перекрасить", т.е. сделать все жирные ребра тонкими, а тонкие - жирными, то число жирных ребер, а, следовательно, и паросочетание увеличатся на одно ребро. Чередующаяся относительно М цепь с ненасыщенными концевыми вершинами называется увеличивающей относительно М цепью. Теорема: Паросочетание М является наибольшим тогда и только тогда, когда нет увеличивающих относительно М цепей. Данная теорема служит основой для алгоритма нахождения наибольшего паросочетания. Содержание отчета:
Контрольные вопросы:
Тема 7.5 Эйлеровы и гамильтоновы графы. Классической в теории графов является следующая задача. В городе Кенигсберге имеется два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рисунке.  Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя по одному разу по каждому мосту, вернуться обратно. Решение этой задачи сводится к нахождению некоторого специального маршрута в графе. Пусть G – псевдограф. Цепь (цикл) в G называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро псевдографа G. Поставим в соответствие схеме мультиграф G, изображенный на рисунке,  в котором каждой части суши соответствует вершина, а каждому мосту – ребро, соединяющее соответствующие вершины. На языке теории графов задача звучит следующим образом: найти эйлеров цикл в мультиграфе G. Граф является эйлеровым, если он содержит эйлеров цикл. Теорема. Связный граф является эйлеровым тогда и только тогда, когда каждая вершина имеет четную локальную степень. Теорема. Связный граф содержит эйлерову цепь тогда и только тогда, когда ровно две вершины имеют нечетную локальную степень. Рассмотрим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри. Теорема. Пусть G – эйлеров граф; тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:
Любой простой полный граф с нечетным количеством вершин является эйлеровым. Любой циклический граф является эйлеровым. Граф, являющийся колесом, не является эйлеровым. Критерий эйлеровости: Для того, чтобы граф являлся эйлеровым необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень. Цепь (цикл) в G называется гамильтоновой (гамильтоновыми), если она (он) проходит по одному разу через каждую вершину псевдографа G. Граф является гамильтоновым, если он содержит гамильтонов цикл. С понятием гамильтоновых циклов тесно связана так называемая задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины (иными словами, коммерсант должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, и при этом стоимость такой поездки должна быть минимальной). Приведем теорему Дирака, которая отвечает на вопрос: существует ли в графе гамильтонов цикл. Теорема. Если в простом графе с n ( 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым. Любой простой полный граф является гамильтоновым. Любой циклический граф является гамильтоновым. Граф, являющийся колесом, является гамильтоновым. Критерии гамильтоновости:
Лабораторная работа № 5 Эйлеровы графы Цель работы;
Литература:
Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задание: Заданы графы: 1) 4) 2) 3) 5) Краткие теоретические сведения: Граф называется полным, если каждые две его вершины соединены одним и только одним ребром. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Е Степ. А=1 Степ. В=2 Степ. С=2 Степ. D=l Степ. Е=0 Вершина называется нечетной, если её степень - число нечетное. Вершина называется четной, если её степень - число четное. Степень каждой вершины полного графа на единицу меньше числа его вершин. Теорема о сумме степеней графа: В графе Г - сумма степеней всех его вершин, есть число четное, равное удвоенному числу его ребер, т.е.  где р - число ребер графа, п- число вершин. Содержание отчета:
Контрольные вопросы:
|
