Пояснения к доказательству





Доказательство

Пусть дан (n,m)-граф G. Предположим противное: все его вершины имеют разную степень.

Максимальная степень вершины в графе порядка n может быть равна (n-1), тогда вершины должны иметь степени (n-1), (n-2), …, 2, 1, 0. Но вершина степени (n-1) соединена со всеми оставшимися вершинами, в том числе и с изолированной, что невозможно. Пришли к противоречию, поэтому в любом графе обязательно найдутся две вершины, имеющие одинаковую степень. максимальная степень вершины может быть на единицу меньше количества вершин!!!!!!

1.3 Теорема о вершинах степени 0 или n-1

Пусть натуральные числа n и d ,среди которых есть чётное удовлетворяют неравенствам 0<=d<=n-1 .Тогда существует регулярный граф порядка n и степени d

1.4 Изоморфизм графов

Пусть G=(VG ,EG) и H=(VH,EH) графы ,где отображение a: VG ->VH биекция

.Если для любых вершин u и v графа G их образы а(u) и а(v) смежны в Н тогда и только тогда когда u и v смежны в G ,то графы G и H изоморфны

1.5 Матричное представление графов .

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных рёбер) является бинарной матрицей и содержит нули на главной диагонали.

Проще говоря это симметрическая матрица с нулями на диагонали(если отсутствуют петли) число едениц в строке равно числу рёбер инцедентных соответствующей вершине. Теорема графы изоморфны тогда и только тогда ,когда их матрицы смежности получаются друг из друга перестановками строк и столбцов следующим образом : Одновременно с перестановкой i-й и j-й строк переставляются i-й j-й столбцы. Из этой теоремы следует ,что ранги матриц смежности изоморфных графов равны.

Определение. Матрицей инцедентностипомеченного (n,m) – графа G=(VG ,EG), где VG ={v1,v2 ,…..vn} ,EG ={e1,e2,…..en }называется NXM матрица ,такая, что aij=1 ,если вершина vi и ребро ej инцедентны и aij=0 если вершина vi и ребро ej неинцедентны .В Каждом столбце матрицы инцедентности ровно две еденицы ,равных столбцов нет. Теорема графы изоморфны тогда и только тогда когда их матрицы инцедентности получаются друг из друга произвольными перестановками строк и столбцов .

Операции с графами

2.1 Удаление рёбер и вершин ,добавление рёбер и вершин ,отождествление вершин, расщипление вершин

ОпределениеГраф H=(VH,EH) называется подграфом графа G=(VG ,EG)

,если VH включено VG и EH включено EG

2.2 Объединение ,пересечение ,произведение графов

Гомеоморфизм графов ответ находится выше.

2.4 n-Мерные кубы как особый класс графов ,Коды ГРЕЯ

Первое фото выше ,второе фото.

Маршруты, цепи ,циклы.

3.3 Теорема о связности дополнения графа

Для любого графа либо он сам, либо его дополнение – связный граф.

Доказательство

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

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

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

3.4 Теорема о простом цикле.

Всякий цыкл содержит простой цикл .

Доказательство

Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число [1]). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.

 

3.5 Признаки двудольности графа

1) Теорема Кёнига для того чтобы граф был двудольным необходимо и достаточно ,чтобы он не содержал циклов нечётной длины. Следствие для двудольности графа необходимо и достаточно чтобы он не содержал простых циклов нечётной длины.

2) Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые k элементов одной из долей связаны по крайней мере с k элементами другой(Теорема о свадьбах)

 

Доказательство:
Очевидно, что если существует полное паросочетание, то для любого выполнено . У любого подмножества вершин есть по крайней мере столько же соседей (соседи по паросочетанию). В обратную сторону докажем по индукции (будем добавлять в изначально пустое паросочетание по одному ребру и доказывать, что мы можем это сделать, если не полное). Таким образом, в конце получим что — полное паросочетание. База индукции Вершина из соединена хотя бы с одной вершиной из . Следовательно база верна. Индукционный переход Пусть после шагов построено паросочетание . Докажем, что в можно добавить вершину из , не насыщенную паросочетанием . Рассмотрим множество вершин — все вершины, достижимые из , если можно ходить из в только по ребрам из , а из в по любым ребрам из . Тогда в найдется вершина из , не насыщенная паросочетанием , иначе, если рассмотреть вершины (вершины из принадлежащие ), то для них не будет выполнено условие: . Тогда существует путь из в , который будет удлиняющим для паросочетания (т.к из в мы проходили по ребрам паросочетания ). Увеличив паросочетание вдоль этого пути, получаем искомое паросочетание. Следовательно предположение индукции верно.

 

Пояснения к доказательству

Пример

Пусть было построено паросочетание размером (синие ребра).

Добавляем вершину с номером .

Во множество вошли вершины с номерами , , , , , .

Ненасыщенная вершина из правой доли всегда найдется (в примере вершина с номером ), т.к иначе получаем противоречие:

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

Цепь является удлиняющей для текущего паросочетания.

Увеличив текущее парасочетание вдоль этой цепи, мы насытим вершину с номером .

 

3) Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем; то есть его хроматическое число равняется двум.

3.6 Распознование двудуульности поиском в ширину.

 

Деревья

4.1 Признаки дерева.

1) Отсутствие циклов

2) Любые две вершины соединяет простая цепь.(единственная)

4.2) Три способа построения остова .Алгоритм построения остова обходом графа в ширину

  1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
  2. Извлечь из начала очереди узел u {\displaystyle u} и пометить его как развёрнутый.
  3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
  4. Вернуться к п. 2.

4.3 Три способа построения остова, обход графа в глубину.

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1].

4.4 Фундаментальные циклы.

Фундаментальным циклом графа G=(V,E) c остовным деревом Т=(V,E’) называется простой цикл ,получаемый в результате добавления в Т одного из рёбер G не принадлежащего Е’.

4.5 Теорема о центре дерева.

Теорема

:

Каждое

дерево

имеет

центр

,

состоящи

й

из

одной

вершины

или

из

двух

смежных

вершин

.

Доказательство

:

Утверждение

очевидно

для

деревьев

с

одной

и

двумя

вершинами

.

Покажем

,

что

у

любого

другого

дерева

T

те

же

центральные

вершины

,

что

и

у

дерева

T’

,

полученного

из

T

удалением

всех

его

висячих

вершин

.

Расстояние

от

данной

вершины

дерева

u

до

любой

другой

вершины

v

достигает

наибольш

его

значения

,

когда

v

висячая

вершина

.

Таким

образом

,

эксцентриситет

каждой

вершины

дерева

T’

точно

на

единицу

меньше

эксцентриситета

этой

же

вершины

в

дереве

T

,

следовательно

,

центры

этих

деревьев

совпадают

.

Продолжим

процесс

удаления

и

получим

требуемое

.

 

4.6 Теорема Кирхгофа о числе остовов

4.7 Теорема Кэли о числе помеченных деревьев доказательство ,алгоритм перевода дерева в последовательность и обратно с примерами.

4.9 Поиск Остова минимального веса. Алгоритм Краскала

4.10 Поиск Остова минимального веса Алгоритм Прима

4.11 Матричный Алгоритм Прима. Приведён выше J

Связность

5.1 Числа рёберной и вершинной связности ,теорема о точках сочленения .

Теорема о точках сочленения.

5.3 Теорема о связи чисел вершинной и рёберной связности

Для любого графа справедливо следующее неравенство: где последнее это есть минимальная степень вершины графа

  1. Проверим второе неравенство. Если в графе нет ребер, то . Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае .
  2. Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.
    1. Если - несвязный или тривиальный граф, то .
    2. Если связен и имеет мост , то . В последнем случае , поскольку или граф имеет точку сочленения, инцидентную ребру , или же .
    3. Наконец, предположим, что граф содержит множество из ребер, удаление которых делает его несвязным. Ясно, что удаляя ребер из этого множества получаем граф, имеющий мост . Для каждого из этих ребер выберем какую-либо инцидентную с ним вершину отличную от и . Удаление выбранных вершин приводит к удалению (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то ; если же он связен, то в нем есть мост , и поэтому удаление вершины или приводит либо к несвязному, либо к тривиальному графу. В любом случае .
 
5.4 Свойства двусвязных графов      

5.5 Теоремы о блоках графа

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

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

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

 

Планарные Графы .

6.1 Теорема Эйлера о связи чисел, вершин, рёбер и граней.

Для любого связного ,плоского графа справедливо неравенство

n-m+f=2 где n,m,f число вершин рёбер и граней данного графа .

6.2 Непланарность графов К5 К3,3

6.3 Критерий планарности графа .

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

 

Доказательство:
 

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

Докажем неоходимость. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных или . Пусть — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.

6.4 Триангуляция графа ,Теорема ФАРИ

Теорема Фари Для любого планарного графа существует плоское представление в котором все рёбра прямолинейные отрезки.

Доказательство:
Докажем теорему для плоской триангуляции графа . Ее можно достичь, добавив в необходимое количество ребер. Применим индукцию по числу вершин . База индукции, когда , выполняется тривиальным образом. Предположим, что графы с любым числом вершин меньше , мы можем нарисовать требуемым образом. Рассмотрим ребро , инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда — граница двух граней и . Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин и может быть только два общих соседа и . Пусть и — обход по часовой стрелке ребер, исходящих соостветсвенно из и . Пусть — граф, полученный из стягиванием ребра в вершину . Заменим пары параллельных ребер и на и на . Получим вершину , из которой исходят ребра — по часовой стрелке. Мы получили граф , с меньшим числом вершин равным , то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер, инцидентных ). Для любого обозначим — круг радиуса , с вершиной в центре. Для каждого соседа вершины в графе обозначим объединение всех отрезков, проведённых из в . Возьмем равным минимуму из всех расстояний от вершины до инцидентных ей вершин и до отрезков, проходящих мимо нее. Тогда получим, что все соседи вершины находятся снаружи и только ребра , инцидентные , могут пересекать . Проведем линию через вершину так, чтобы вершина лежала с одной ее стороны, а — с другой (такая линия существует, иначе рёбра и накладывались бы друг на друга) и никакое из ребер и не лежало на . Ребра и разбивают на две дуги: первая пересекает ребра , а вторая — ребра . пересекает в двух точках. Расположим и в этих точках: на дуге, пересекающей , а с другой стороны. Удалим и инцидентные ей ребра, нарисуем прямые ребра , инцидентные и . Получим, что лежит на . Так как и лежат с разных сторон , ребра, инцидентные и , не пересекаются. По выбору , ребра, инцидентные и , не пересекают и другие ребра . Таким образом желаемая укладка графа достигнута. Теперь мы можем удалить добавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.

6.5 Гамма Алгоритм укладки графа на плоскости

Обходы в Графах

7.1 Уникурсальные графы. Теорема Эйлера

Уникурсальный граф-граф по каждому ребру которого можно пройти единожды .или проще говоря граф у которого все степени вершин чётны. Связный граф является Эйлеровым тогда и только тогда когда степени всех его вершин чётные.

7.2 Алгоритм Флёри построения Эйлерового цыкла.

7.3 Эйлеров Путь в графе.

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





Читайте также:
Отчет по производственной практике по экономической безопасности: К основным функциональным целям на предприятии ООО «ХХХХ» относятся...
Зачем изучать экономику?: Большинство людей работают, чтобы заработать себе на жизнь...
Развитие понятия о числе: В программе математики школьного курса теория чисел вводится на примерах...
Тест Тулуз-Пьерон (корректурная проба): получение информации о более общих характеристиках работоспособности, таких как...

Рекомендуемые страницы:



Вам нужно быстро и легко написать вашу работу? Тогда вам сюда...

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-13 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.106 с.