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

По формуле суммы степеней для графа ,

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

Свойство (?!):

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью.^[2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

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

15. Алгоритм нахождения наименьшего остова.

(https://ru.wikipedia.org/wiki/Алгоритм_Краскала)

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

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

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

17. Необходимое и достаточное условия существования эйлеровой цепи. (вики)

Определение: Эйлерова цепь в графе – это цепь, содержащая все ребра графа, причем через каждое ребро проходим ровно один раз.

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

Замечание: Если в графе G эйлерова цепь существует, то она цепь соединяет вершины нечетной степени.

18. Доказательство непланарности и .

Граф имеет 5 вершин и 10 ребер. Если он планарен, то по следствию из формулы Эйлера получаем . Что невозможно.

(т. Эйлера: Пусть связный планарный обыкновенный граф с вершинами (), ребрами и гранями. Тогда )

Граф содержит , и граней. Пусть граф планарен. Тогда по формуле Эйлера . Пусть, двигаясь вдоль -й грани мы пройдем ребер. Очевидно, что . Поскольку граф двудольный, все его циклы имеют четную длину. Значит . Получаем , то есть . То есть , что невозможно.   20. Алгоритм поиска кратчайших путей в графах.   Алгоритм Дейкстры: Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены. Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые. Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовём соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещённую и повторим шаг алгоритма. 21. Поиск гамильтонова цикла в графе. Эвристические оптимизации При прямом переборе вариантов вершин возможно значительное увеличение средней сложности поиска гамильтонова пути на случайных графах (если гарантируется наличие гамильтонова пути в графе). Для улучшения данного способа можно на каждом шаге перебора при некоторой построенной части цепи проверять, образуют ли оставшиеся вершины связный граф (если не образуют, то цепь не может являться началом гамильтоновой цепи); на каждом шаге перебора при выборе следующей вершины пробовать сначала вершины с наименьшей остаточной степенью (количеством рёбер, ведущих в ещё не посещённые вершины). Кроме того, если это дерево является цепью, то гамильтонов цикл в нём возможен. Иначе (если в дереве есть вершины степенью не меньше, чем 3) построение гамильтонова цикла невозможно.   22. Задача коммивояжера. https://ru.wikipedia.org/wiki/Задача_коммивояжёра   23. Задача о максимальном потоке. Алгоритм Форда-Фалкерсона. В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такогопотока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна. Дана транспортная сеть с источником , стоком и пропускными способностями . Определение: Величиной потока (value of flow) называется сумма потоков из источника . В статье «Транспортная сеть» доказано, что она равна сумме потоков в сток . Задача о максимальном потоке заключается в нахождении потока такого, что величина потока максимальна. Решение: (https://ru.wikipedia.org/wiki/Алгоритм_Форда-Фалкерсона) Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех . Затем величина потокаитеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. Дан граф с пропускной способностью и потоком для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков: · . Поток из в не превосходит пропускной способности. · . · для всех узлов , кроме и . Поток не изменяется при прохождении через узел. Остаточная сеть — сеть с пропускной способностью и без потока. Вход Граф с пропускной способностью , источник и сток Выход Максимальный поток из в 1. для всех ребер 2. Пока есть путь из в в , такой что для всех ребер : 1. Найти 2. Для каждого ребра 1. 2. Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса — Карпа) или поиском в глубину в .

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