Где рассказывать гипер-,мультиграфы? Где Гамильтоновы графы?


Скачать 65.18 Kb.
НазваниеГде рассказывать гипер-,мультиграфы? Где Гамильтоновы графы?
Дата07.11.2012
Размер65.18 Kb.
ТипРассказ

ü http://nosorog.jino-net.ru › mailto: gaga-gaga@bk.ru

Примечание: Все утверждения, помеченные * не доказываются и не обосновываются сознательно… они не сложны… если все - таки не ICE, то все на

ICQ:411-928-384 или e-mail:crazyzez@mail.ru


FAQ (составлен по Пашкиным вопросам)


  1. Изоморфизм

Скорее всего, тут нужно говорить именно о изоморфизме и о его инвариантах.

Два графа G = (V, E) и G’ = (V’, E’) называются изоморфными, если существует изоморфизм φ и справедливо:

(a,b) есть в E, тогда и только тогда, когда (φ(a), φ(b)) есть в E’.

Примечание: у меня в тетради это определение написано только в одну сторону. Если у кого то также – это НЕ ВЕРНО. Должно быть тогда и только тогда. Ибо иначе пустой граф изоморфен ЛЮБОМУ другому.

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

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

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

  • Набор степеней вершин (степени идущие в неубывающем порядке)

  • Число компонент связности

  • Число вершин и ребер

И несколько более извращенных:

  • Число циклов в графе

  • Наличие в нем Эйлерова или Гамильтонова цикла




  1. Гиперграфы и мультиграфы

Кратные ребра = «одинаковые» ребра.

Мультиграфом называется граф с кратными ребрами.

Пример мультиграфа (неориентированного): G = (V, E) V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 2), (4, 2), (4, 2)}

Гиперграфом называется граф G = (V, E), где V – конечное множество, а E подмножество 2v (булеан или как говориться по простому – множество всех подмножеств множества V). У меня дальше идут какие то несуразые определения смежности и инцидентности… пока воздержусь от их изложения… я их че то не догоню да и их справедливость подозрительна…


  1. Лемма о рукопожатиях

Лемма о рукопожатиях: Количество рукопожатий всегда четно.

Доказать самому… ибо это очевидно (я серьезно)

В формулировке теории графов: Сумма степеней вершин четна (АБСОЛЮТНО та же теорема, но в иной формулировке)


  1. Где рассказывать гипер-,мультиграфы? Где Гамильтоновы графы?

Думаю, что в первом билете… больше «сунуть», кажется, и не куда.


  1. Где Лемма о рукопожатии? Где т. О листьях?

Судя по всему это просто не вошло в билеты… потому что они тупы до беспределия…)))


  1. Что в билете №9: матричное задание написал, а ещё?

Мне кажется, тут нужно упомянуть способы:

    • Матрица смежности

    • Матрица инцидентности

    • Список ребер

    • Изображение на плоскости




  1. Что в билете №13: это теорема с цикломатическим числом?

Теорема: ню(G) определяет количество ребер, которые нужно удалить, чтобы получить остов


  1. По Т. Эйлера: Что означает остановку и что из неё следует, если в графе из которого

мы удалили цикл чего то нет? (оч. интересная формулировка… в оригинале…))))

Теоремка: Если степень каждой вершины не меньше 2х, то в графе имеется цикл.

Следствие: Если в графе степени всех вершин четны, то он либо пуст, либо в нем есть цикл.

(Этого в тетради нет… написал, чтобы было понятно, на что же мы опираемся в т. Эйлера. Доказательство, думаю, тут не требуется, оно не сложное.)


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

Достаточность*

Необходимость:

Замечание к теореме: Из условия вытекает, что степень каждой вершины не менее 2х *.

Теорема доказывается по шагам. Общий смысл доказательства следующий:

По следствию из теоремки вытекает, что в графе есть цикл с1 (ведь он не пуст по условию)… возьмем его и удалим из графа. Заметим: Когда из графа удаляется цикл, то степени всех вершин по прежнему остаются четными*. НО: Они уменьшаются…

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

Отсюда можно сделать вывод: алгоритм конечен. Теперь у нас имеется множество циклов. Причем: их объединение дает нам исходный граф. Так вот мы берем и объединяем их в один большой - Эйлеров.

Как объединить 2 цикла (за общую вершинку):





  1. Т. Кёнига

Примечание: Это очень простая теорема, но понять то доказательство, что писал Прилуцкий… в общем, я думаю, понятно че я о нем хочу сказать… Здесь предлагаю свое доказательство этой теоремы. В конце концов, ЕГО доказательства у меня просто нет… я его не писал…

Т. Кенига (критерий двудольности графа):

Для двудольности необходимо и достаточно отсутствие циклов нечетной длины.


Более привычная формулировка (для меня), если кому интересно: Граф двудолен тогда и только тогда, когда все циклы имеют четную длину.


Достаточность:

Граф двудолен. Рассмотрим произвольный цикл, и зафиксируем в нем какую-нить вершину А.

Пойдем из этой вершины по ребрам цикла и сделаем такое замечание: Из того, что граф двудолен следует, что при переходе через ребро мы ОБЯЗАТЕЛЬНО будем менять ту долю, в который мы находимся. Значит для того чтобы вернуться обратно в вершину A необходимо сколько то раз сходить во 2ю долю и СТОЛЬКО же обратно. Отсюда и имеем, что наш цикл – имеет четную длину.

Примечание: надеюсь, не смотря на корявость моего объяснения, идея ясна… ибо такие простые вещи излагать сложнее всего…


Необходимость:

Граф имеет циклы только четной длины (если вообще их имеет). Докажем, что он – двудольный.

Пусть d(u, v) – кратчайшее расстояние между u и v (длина кратчайшего пути)

Для каждой его компоненты связности делаем следующее:

  • Фиксируем произвольную вершину v и помещаем ее в первую долю.

    • Все вершины ui, достижимые из v (т.е. из той же компоненты связности, что и v) мы помещаем в первую долю, если d(ui, v) – четно и во вторую, в противном случае.

Из данного алгоритма (п.2) следует, что 2 вершины из одной компоненты связности лежат в одной доле тогда и только тогда, когда длина кратчайшего пути между ними четна (хотя бы 2). Отсюда имеем, что между вершинами одной доли ребер нет (иначе пусть между ними равен 1). Следовательно, граф двудольный.


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


  1. 1 – приближенный алгоритм.

- что такое Т2?

Т2 – граф, полученный удвоением всех ребер в графе – остове T0 (было ребро – сделали 2)

Как следствие, он имеет в себе Эйлеров цикл из которого строится Гамильтонов.

- В доказательстве получаем формулу: Wц)<=W(Эц)=2W(Т0). Как?

Во первых, посмотрим, как строится Гамильтонов цикл.

Замечание: Эйлеров цикл проходит по всем вершинам.

Пусть Эйлеров цикл имеет вид:

(i1, i2)…(in, i1). Гамильтонов строим следующим образом:

Идем по вершинам, начиная с самого начала этого цикла и если с помощью следующего ребра мы попадаем

туда, куда нас еще «не заносило», то идем, иначе вершину игнорируем и идем в следующую по цепочке. т.к. в Эйлеровом графе есть все вершины, то мы пройдемся по всем, т.е. получим Гамильтонов цикл.

Из неравенства треугольника следует, что если мы вдруг неожиданно игнорируем одну из вершин и идем в следующую, то путь от этого может только улучшиться. Отсюда имеем: W(Гц) <= W(Эц), ну а то что

W(Гц) = 2W(Эц) думаю понятно… (ведь одно из другого получено простым удвоением ребер)

Дальнейшие выкладки опускаются…*

  1. Т. Краскала:

- Есть такое место: Т’ = T+ei-e

- что за ребро е?

- потом выведем, что W(ei)=W(e) и W(T')=W(T) отсюда какое то противоречие вытекает. Какое и

почему оно доказывает теорему?

Тn-1 – построенный остов

Т – остов минимального веса

ei – ребра добавляемые в Tn-1 по нашему алгоритму.

Так вот, пусть ei – ребро с наименьшим i, такое, что оно есть в построенном остове, но нет его в минимальном.

Тогда добавляем его в T. Оно создаст там цикл, удалим из него ребро e (оно тяжелее ei по построению, т.е. W(ei)<=W(e)), чтобы убрать этот лишний цикл.

W(T’) = W(T)+W(ei)-W(e), но W(T’)>=W(T), следовательно W(ei)>=W(e). Но тогда из этого следует:

W(ei) = W(e) (Это никак не значит, что ребра совпадают!). Имеем: W(T’) = W(T), т.е T’ – минимальный остов.

Если T’ <> Tn-1, то выполняем эту процедуру опять. В конце концов получаем Tn-1 = T’, что означает, что искомой минимальный по условию остов T мы смогли преобразовать в построенный Tn-1 без увеличения веса, т.е. построили остов минимального веса.

Примечание: можно, конечно, свести и к противоречию, но оно мне там каким то очень нехорошим показалось…


Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница