2 Тема

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

2. Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом (см. Словарь терминов теории графов).

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

4. Плоский граф — граф, уложенный на плоскость.Теорема Жордана - Плоский граф разрезает плоскость на совокупность D(G) неперекрывающихся многоугольных областей.

5. Существуют различные способы представления графов.

• Матрица инцидентности. Это прямоугольная матрица размерности n ч m, где n – количество вершин, а m – количество ребер.

• Матрица смежности. Это квадратная матрица размерности n ч n, где n – количество вершин.

• Список смежности (инцидентности). Представляет собой структуру данных, которая для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.

• Список списков. Представляет собой древовидную структуру данных, в которой одна ветвь содержит списки вершин, смежных для каждой.

6. Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных выборов даёт глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме: Сначала доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не хуже первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

7. Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

8. Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенногоориентированного графаПусть вершины графа пронумерованы от 1 дои введено обозначениедля длины кратчайшего пути отдо, который кроме самих вершинпроходит только через вершины. Очевидно, что— длина (вес) ребра, если таковое существует (в противном случае его длина может быть обозначена как). Существует два варианта значения: Кратчайший путь междуне проходит через вершину, тогдаСуществует более короткий путь между, проходящий через, тогда он сначала идёт отдо, а потом отдо. В этом случае, очевидно,Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.Тогдарекуррентная формула для имеет вид:— длина ребраАлгоритм Флойда-Уоршелла последовательно вычисляет все значениядляот 1 до. Полученные значенияявляются длинами кратчайших путей между вершинами

9. Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех. Затем величина потокаитеративноувеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .Для каждого ребра на найденном пути увеличиваем поток на, а в противоположном ему — уменьшаем на.Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.Возвращаемся на шаг 2.Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению.

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

11. Представление деревьев на смежной памяти (одномерный массив) предполагает неявное присутствие ребер, переход по которым выполняется посредством арифметических операций над индексами элементов массива — смежной памяти. Формирование таких деревьев с помощью адресной арифметики можно осуществлять двумя способами. Идея первого способа применима при любом постоянном количестве ребер, выходящих из вершин (регулярное дерево). Рассмотрим данный способ формирования на примере двоичного (бинарного) дерева. Пусть имеется одномерный массив смежных элементов Неявная структура двоичного дерева определяется как на рисунке 14. По дереву на рис.14 легко перемещаться в обоих направлениях. Переход вниз на один уровень из вершины а [к] можно выполнить, удвоив индекс к (индекс левого поддерева) или удвоив и прибавив 1 (индекс правого поддерева). Переход вверх на один уровень из вершины а[m] можно выполнить, разделив m пополам и отбросив дробную часть. Рассмотренная структура применима к любому дереву с постоянным количеством ребер, выходящих из вершин.

12. Мозаикой называют правильный бесконечный граф. Существует три вида мозаик: на основе треугольника, на основе четырехугольника, шестиугольника.

13. Двойственный граф кпланарному графу — это граф, в котором вершины соответствуют граням графа; эти вершины соединены ребром, только если соответствующие им грани графаимеют общее ребро. Например, двойственны друг к другу графыкуба и октаэдра.

Двойственный граф является псевдографом: в нём могут быть петли и кратные рёбра.

В зависимости от укладки, к одному и тому же графу могут существовать несколько двойственных.

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

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

15. Граф без циклов называется лесом. Вершины степени 1 в дереве называются листьями.

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки. Пусть задан граф , где— множество вершин графа,— множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены вбелый цвет. Выполним следующие действия:

• Из множества всех белых вершин выберем любую вершину, обозначим её .

• Выполняем для неё процедуру DFS().

• Перекрашиваем её в чёрный цвет.

• Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина )

• Перекрашиваем вершину вчерный цвет.

• Для всякой вершины ,смежной с вершиной u, выполняем следующие два шага:

  • Если вершина окрашена в белый цвет, выполняем процедуруDFS(w).

  • Окрашиваем вчёрный цвет.

16. K-хроматический граф — граф, хроматическое число которого равно . То есть вершины графа можно раскраситьцветами так, что у любого ребра концы будут разного цвета, но так раскраситьцветами — уже нельзя. Правильной раскраской графа называется такое отображениеиз множества вершинв множество красок, что для любых двух смежных вершинивыполняется. Так же её называютt-раскраской. Раскраской графа чаще всего называют именно правильную раскраску.

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

Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.

Формулируется следующим образом:

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

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (lower bound algorithm).

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

19. Связная компонента графа(Connected component of a graph) - всякий максимальный связный подграф графа; множество вершин связной компоненты называется областью связности графа.

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

Идея алгоритма

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

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

• Передадим её статус всем вершинам соединенным с ней ребром.

• Алгоритм

• Присвоим всем вершинам статус 1.

• Присвоим ИСХОДНОЙ вершине статус 2.

• Пока есть вершины имеющие статус = 2 выполнить

• Выберем любую вершину имеющую статус 2 назовем её ТЕКУЩЕЙ

• Для всех вершин инцидентных ТЕКУЩЕЙ выполнить

• Если вершина имеет статус 1 то её статус = 2

• Статус ТЕКУЩЕЙ вершины = 3

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

20. Пра́вильный многоуго́льник — это выпуклый многоугольник, у которого все стороны между собой равны и все углы между собой равны.