Главная Избранное Популярное Новые добавления Случайная статья Пояснения к доказательству Доказательство Пусть дан (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 элементами другой(Теорема о свадьбах)   Доказательство: Очевидно, что если существует полное паросочетание, то для любого выполнено . У любого подмножества вершин есть по крайней мере столько же соседей (соседи по паросочетанию). В обратную сторону докажем по индукции (будем добавлять в изначально пустое паросочетание по одному ребру и доказывать, что мы можем это сделать, если не полное). Таким образом, в конце получим что — полное паросочетание. База индукции Вершина из соединена хотя бы с одной вершиной из . Следовательно база верна. Индукционный переход Пусть после шагов построено паросочетание . Докажем, что в можно добавить вершину из , не насыщенную паросочетанием . Рассмотрим множество вершин — все вершины, достижимые из , если можно ходить из в только по ребрам из , а из в по любым ребрам из . Тогда в найдется вершина из , не насыщенная паросочетанием , иначе, если рассмотреть вершины (вершины из принадлежащие ), то для них не будет выполнено условие: . Тогда существует путь из в , который будет удлиняющим для паросочетания (т.к из в мы проходили по ребрам паросочетания ). Увеличив паросочетание вдоль этого пути, получаем искомое паросочетание. Следовательно предположение индукции верно.   Пояснения к доказательству Пример Пусть было построено паросочетание размером (синие ребра). Добавляем вершину с номером . Во множество вошли вершины с номерами , , , , , . Ненасыщенная вершина из правой доли всегда найдется (в примере вершина с номером ), т.к иначе получаем противоречие: В входят только насыщенные вершины. В по крайней мере вершин (соседи по паросочетанию для каждой вершины из и ещё одна вершина, которую пытаемся добавить). Цепь является удлиняющей для текущего паросочетания. Увеличив текущее парасочетание вдоль этой цепи, мы насытим вершину с номером .

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

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

Деревья

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

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

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

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

1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
2. Извлечь из начала очереди узел u {\displaystyle u} и пометить его как развёрнутый.
• Если узел u {\displaystyle u} является целевым узлом, то завершить поиск с результатом «успех».
• В противном случае, в конец очереди добавляются все преемники узла 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 Теорема о связи чисел вершинной и рёберной связности

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

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

5.4 Свойства двусвязных графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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