Материал: ПОДГОТОВКА К ЭКЗАМЕНУ ДИСКРЕТНАЯ МАТЕМАТИКА

Порядок графа - это число вершин в графе, |V|.

Размер графа - это число его рёбер, |E|

Концевые вершины графа - это вершины, соединяющие данное множество ребер.

Две концевые вершины одного и того же ребра называются соседними.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги.

Смешанный - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой (V, E, A).

Изоморфный граф - это некоторый граф G, для которого существует биекция f из множества вершин графа G в множество вершин другого графа H, которому он изоморфен, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот - если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины f^{-1}(A) в вершину f^{-1}(B). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Элементарный путь - это простой путь в графе, вершины в котором не повторяются.

Петля - это элементарный цикл.

Компонента графа, связная компонента графа - это всякий максимальный связный подграф графа. Слово "максимальный" означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.

Мост - это ребро графа, удаление которого увеличивает число компонент графа, такое ребро не содержится ни в одном цикле.

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

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

Дерево - это связный граф, не содержащий простых циклов.

Полный граф - это граф, в котором любые его две вершины соединены ребром.

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

k-дольный граф - это граф, в котором вершины можно разбить на k непересекающихся подмножества V_1, V_2, :, V_k так, что не будет рёбер, соединяющих вершины одного и того же подмножества.

Полный двудольный граф - это граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.

Планарный граф -  граф, который может быть изображён на плоскости без пересечения рёбер. 

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

22. Маршрут в графе — это чередующаяся последовательность вершин и рёбер {\displaystyle v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}} v0,e1,v1,e2, v2…, e_n, v_n, в которой любые два соседних элемента инцидентны. Если {\displaystyle v_{0}=v_{k}} v0 = v_n, то маршрут замкнут, иначе открыт.

Число n называется длиной маршрута.

Цепь - маршрут, в котором все ребра различны

Цикл - замкнутый маршрут, являющийся цепью.

Простая цепь - маршрут, в котором все вершины различны.

Простой цикл - цикл, в котором все вершины, кроме первой и последней, различны.

Две вершины называются связными, если существует маршрут между ними.

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

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

22. Дерево – связный граф без циклов.

Лес – граф, все компоненты связности которого являются деревьями.

Граф полный, если каждые две его вершины соединены только одним ребром.

Граф плоский (планарный), если его можно изобразить на плоскости так, что все пересечения его ребер являются вершинами графа.

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

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

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

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

Самодополнительный граф — это граф, изоморфный своему дополнению.

22. Общая постановка экстремальной задачи на графе. Примеры экстремальных задач.

Дан граф G = (V, E), |V| = n, в котором ребра взвешены числами e ∈ E -> w (e) > 0.

Также указаны условия и свойства, которые должен удовлетворять дополнительный частичный граф x = (V_x, E_x), V_x ⊂ V, E_x ⊂ E. Обычно допустимое решение X определяет решение задачи.

Примеры: задача об остовном дереве, нахождение кратчайшего пути, задача коммивояжера.

22. Задача об остовном дереве: Дан связный, неориентированный граф с весами на ребрах.

Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

Так как T связен и не содержит циклов, он является деревом и называется остовным. Остовное дерево T, у которого суммарный вес его ребер w(T) = ∑_(u,v)∈T w(u,v) минимален, называется минимальным остовным.

Алгоритм Краскала

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

Алгоритм Прима.

Сначала берется произвольная вершина и выбирается ребро, инцидентное данной вершине и с наименьшим весом. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются ребра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости, которое не образует цикл. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

29. Алгоритм Дейкстры

1. Первой вершине присваивается метка 0, а остальным вершинам - метка бесконечности.

2. Выбираем вершину V, которая имеет минимальную метку

3. рассматриваем все вершины смежные вершине V

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

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

6. Повтор пунктов 3-5, пока текущей вершиной не окажется конечная, в итоге получим путь, и его длина будет весом текущей вершины.

30. Гамильтоновы циклы и контуры. Необходимые и достаточные условия существования гамильтонова цикла в графе. Алгоритм «иди в ближайший».

 Гамильтонов граф – граф, который содержит гамильтонов цикл.

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

Гамильтонов цикл - такой цикл, который проходит через каждую вершину данного графа по одному разу.

Необходимое условие: Неориентированный граф содержит гамильтонов цикл тогда, когда в нём не существует ни одной вершины со степенью < 2.

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

Условие Дирака: если степень каждой вершины не меньше, чем половина к-ва вершин в графе, то граф называется графом Дирака. Граф Дирака — гамильтонов.

Условие Оре: если в графе степени любых двух несмежных вершин не меньше числа всех вершин в графе, то граф называется графом Оре. Граф Оре — гамильтонов.

Алгоритм «иди в ближайший»

1. Выбор произвольной вершины

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

3. Алгоритм закончит работу на шаге, когда уже будет построена гамильтонова цепь. Остается замкнуть ее в цикл.

31. Метод ветвей и границ для решения задачи коммивояжера.

Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

1. Построение матрицы с исходными данными.

2. Нахождение минимума по строкам.

3. Редукция строк.

4. Нахождение минимума по столбцам.

5. Редукция столбцов.

6. Вычисление оценок нулевых клеток.

7. Редукция матрицы.

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута.

32. Эйлеровы маршруты на графах. Теорема Эйлера.

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

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

Эйлеров граф — граф, содержащий эйлеров цикл.

Полуэйлеров граф — граф, содержащий эйлеров путь.

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

33. Алгоритм Флери и алгоритм элементарных циклов нахождения эйлерова маршрута на графе.

Алгоритм Флери:

Пусть задан эйлеров граф{\displaystyle G=(V,E)}. Начинаем с произвольной вершины{\displaystyle p\in V} и вычеркиваем каждое пройденное ребро, если оно не является мостом. Проходим по мосту, если других путей нет. Число шагов алгоритма совпадет с к-вом ввершин в графе.

Алгоритм элементарных циклов нахождения эйлерова маршрута на графе.

1. найти все элементарные циклы

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

повтор этого до тех пор пока все ребра графа не окажутся окрашенными

в р-те имеем последовательность элементарных циклов

2. начинать движение по первому циклу вдоль его ребер до пересечения с каким-то другим циклом

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

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

34. Алгоритм построения оптимального эйлерова мультиграфа.

Эйлеров мультиграф – мультиграф, содержащий эйлеров цикл.

1. на данном не эйлеровом графе выделяют вершины нечетной степени V’ ∈ V.

Их к-во |V’| = n’ и строится соответсвующий єтим вершинам n’-вершинный граф K _n’

2. ребра полученного полного графа взвешиваются весами равными длине кратчайшего пути между парой вершин V₁ , V₂ инцидентных соотвутсвующему ребру (V₁ , V₂ ) в полном графе K _n’

3. в полном графе K _n’ ищется совершенное паросочетание минимального веса.

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

35. Паросочетания. Задача о нахождении оптимального совершенного паросочетания в графе.

В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

Максимальное паросочетание — это такое паросочетание в графе, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.

Наибольшее паросочетание (или максимальное по размеру паросочетание)— это такое паросочетание, которое содержит максимальное количество рёбер.

Совершенным паросочетанием - -паросочетание, в котором участвуют все вершины графа.

36.    Сеть - связный орграф без петель.

          Поток в сети - некоторая функция, которая ставит в соответствие дуге некоторое число - вес дуги.

Поток полный, если в нём любой путь полный.

Алгоритм форда фалкерсона:

а) ищем любую цепь из истока графа в сток;

б) каждой дуге приписываем возможный больший поток из истока в сток (записываем его через дробь с весом дуги; при этом поток не может превысить вес дуги, но может быть ему равен);

в) если поток становится равен весу дуги, то эта дуга является насыщенной, то есть через нее нельзя пройти при рассмотрении цепей в графе;

г) так перебираем все возможные цепи, пока станет невозможно попасть из истока в сток;

д) поток в сети будет равен сумме потоков всех дуг, инцидентных стоку графа (следует заметить, что сумма потоков всех дуг, инцидентных стоку графа равна сумме потоков всех дуг, инцидентных истоку графа).

37. Алгоритм плоской укладки графа

1. Инициализация. Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G′; сформируем сегменты S_i; если множество сегментов пусто, то перейти к п. 3. В противном случае перейти к п.2.

2. Общий шаг:

a. Для каждого сегмента S найти множество Г(S).

Если существует сегмент S, для которого |Г(S)| = 0, то граф не планарный, конец.

b. Выбираем один из сегментов с минимальным числом, вмещающих его граней.

c. Выбираем одну из подходящих граней для выбранного сегмента.

d. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов, и если множество образовавшихся сегментов не пусто, перейдем к п. a).

В противном случае перейдем к п.3.

3. Завершение. Построена плоская укладка G′ исходного графа G, конец.