Формула Эйлера
Воспользуемся методом математической индукции по количеству граней графа.
База индукции:
[math]F = 2[/math] . Граф [math]G[/math] представляет собой многоугольник с [math]n[/math] вершинами (рис. 1). Тогда [math]V = E = n[/math] , значит, равенство [math]V — E + F = 2[/math] выполняется.
Индукционный переход:
Пусть [math]G[/math] связный планарный обыкновенный граф с [math]V[/math] вершинами ( [math]V \geqslant 3[/math] ), [math]E[/math] ребрами и [math]F[/math] гранями. Тогда [math]E \leqslant 3V — 6[/math]
Трехмерный случай
Покажем, что в трехмерном случае так же имеет место формула Эйлера.
Для любого выпуклого многогранника имеет место равенство [math]V — E + F = 2[/math] , где [math]V[/math] — число вершин, [math]E[/math] — число ребер и [math]F[/math] — число граней данного многогранника.
Пример невыпуклого многоугольника для которого [math]V — E + F = 0[/math] . Многоугольник получен путем вырезания куба внутри куба.
Для доказательства соотношения Эйлера представим поверхность выпуклого многогранника сделанной из эластичного материала. Удалим (вырежем) одну из его граней и оставшуюся поверхность растянем на плоскости. Получим планарный граф, содержащий [math]F’ = F — 1[/math] внутренних граней, [math]V[/math] вершин и [math]E[/math] ребер.
Тогда справедливо уже доказанное соотношение: [math]V — E + F ‘ = 1 [/math] .
В любом выпуклом многограннике имеется или треугольная грань, или трехгранный угол. Более того, число треугольных граней плюс число трехгранных углов больше или равно восьми.
Обозначим через [math]V_[/math] число вершин выпуклого многогранника, в которых сходится [math]i[/math] ребер. Тогда для общего числа вершин [math]V[/math] имеет место равенство [math]V = V_ + V_ + V_ + \dots[/math]
Аналогично, обозначим через [math]F_[/math] число граней выпуклого многогранника, у которых имеется [math]i[/math] ребер. Тогда для общего числа граней [math]F[/math] имеет место равенство [math]F = F_ + F_ + F_ + \dots[/math]
Посчитаем число ребер [math]E[/math] многогранника. Имеем: [math]3V_ + 4V_ + 5V_ + \dots = 2E[/math] , [math]3F_ + 4F_ + 5F_ + \dots = 2E[/math] .
По теореме Эйлера выполняется равенство [math]4V — 4E + 4F = 8[/math] . Подставляя вместо [math]V[/math] , [math]E[/math] и [math]F[/math] их выражения, получим:
[math]4V_ + 4V_ + 4V_ + \dots — (3V_ + 4V_ + 5V_ + \dots) — (3F_ + 4F_ + 5F_ + \dots) + 4F_ + 4F_ + 4F_ + \dots = 8[/math] .
Источники информации
- Асанов М,, Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы (стр. 104-107)
- О.Оре — Графы и их применение (стр. 131-135)
- Википедия — Теорема Эйлера для многоугольников
- Выпуклые многогранники
- Алгоритмы и структуры данных
- Укладки графов
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в соиальных сетях учстились случаи педложения помощи в написании прогамм от лиц, прикрвающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в псторонних группах ВК. Для связи с нами используйте исключительно эти контакт: vscoderu@yandex.ru, https://vk.com/vscode
Поиск элементарных цепей в графе
В этой статье речь пойдет об алгоритме поиска всех элементарных цепей в неориентированном графе. Будет приведено описание алгоритма и его реализация на языке программирования C#.
Цепью в графе называется последовательность ребер , когда каждое предыдущее ребро соприкасается одним из своих концов со следующим ребром . Цепь обозначается последовательностью вершин, которые она содержит (2-5-3-6).
Цепь называется элементарной, если все вершины, входящие в нее, различны.
Приведем пример. Пусть дан граф, как на рисунке ниже:
Все элементарные цепи в нем: 1-2, 1-3-2, 1-2-3, 1-3, 1-2-3-4, 1-3-4, 2-1-3, 2-3, 2-1-3-4, 2-3-4, 3-4.
Пусть граф задан, как G = (V, E), где V — множество вершин графа, а E — множество его ребер. Вершины и ребра можно представить объектами следующих классов:
Терминология теории графов
Граф (или неориентированный граф) — упорядоченная пара [math](V, E)[/math] из непустого множества [math]V[/math] вершин и множества [math]E \subseteq V^[/math] рёбер, где через [math]V^[/math] обозначается множество всех двухэлементных подмножеств (2-сочетаний) множества [math]V[/math] .
Граф называется пустым (или нуль-графом), если его множество рёбер пусто. Граф называется полным, если он содержит все возможные рёбра.
Множество вершин графа [math]G[/math] обозначается через [math]V(G)[/math] или [math]VG[/math] , множество рёбер — через [math]E(G)[/math] или [math]EG[/math] . Число [math]|V(G)|[/math] вершин графа [math]G[/math] называется его порядком и обозначается через [math]|G|[/math] .
Граф порядка [math]n[/math] называется помеченным, если его вершинам присвоены некоторые метки, например, номера [math]1, 2, \ldots, n[/math] .
Мультиграф — упорядоченная пара [math](V, E)[/math] из непустого множества [math]V[/math] вершин и семейства (мультимножества) [math]E \subseteq V^[/math] рёбер. Одинаковые рёбра мультиграфа называются кратными. Другими словами, мультиграф — это обобщение графа на случай кратных рёбер.
Псевдограф — упорядоченная пара [math](V, E)[/math] из непустого множества [math]V[/math] вершин и семейства [math]E[/math] неупорядоченных пар (2-сочетаний с повторениями) вершин. Термин псевдограф обобщает понятие мультиграфа, допуская наличие петель — рёбер, соединяющих вершину саму с собой.
Ориентированный граф (или орграф) — упорядоченная пара [math](V, A)[/math] из непустого множества [math]V[/math] вершин и множества [math]A \subseteq V^2[/math] ориентированных рёбер (или дуг), где через [math]V^2[/math] обозначается множество всех упорядоченных пар (2-размещений), состоящих из двух различных элементов [math]V[/math] .
Множество дуг орграфа [math]G[/math] обозначается через [math]A(G)[/math] или [math]AG[/math] . Аналогично определяются ориентированный мультиграф, с той лишь разницей, что совпадающие дуги ориентированного мультиграфа называются параллельными.
Основание орграфа [math]G[/math] — неориентированный мультиграф, получающийся в результате снятия ориентации с дуг орграфа [math]G[/math] .
Смешанный граф — граф, в котором могут быть как дуги, так и неориентированные рёбра.
Термин граф может использоваться вместо любого из обобщений этого понятия, если из контекста ясно, о каком определении идёт речь. Поэтому чтобы отличать граф в исходном определении от других, используется понятие простого графа — неориентированного графа без петель и кратных рёбер.
Деревья
Дерево — связный граф, не содержащий циклов. [1]
Ориентированный граф [math]D = (V, A)[/math] называется ориентированным деревом с корнем [math]r \in V[/math] , если каждая его вершина достижима из [math]r[/math] и основание [math]D_b[/math] графа [math]D[/math] является деревом.
Лес (или ациклический граф) — граф без циклов. Каждая компонента леса является деревом. Заметим, что речь здесь идёт только о неориентированном простом графе.
Ациклический орграф — орграф без циклов. Стоит отметить, что основание ациклического орграфа может не являться ациклическим графом (лесом).
Подграфы
Граф [math]H[/math] называется подграфом (или частью) графа [math]G[/math] , если [math]V(H) \subseteq V(G)[/math] и [math]E(H) \subseteq E(G)[/math] .
Остовный подграф (или фактор) — подграф, содержащий все вершины исходного графа.
Остов (или каркас) графа [math]G[/math] — максимальный по включению лес, являющийся подграфом графа [math]G[/math] . Другими словами, остов — это подграф графа [math]G[/math] , состоящий из одного остовного дерева для каждой компоненты связности графа [math]G[/math] . Стоит отметить, что не всякий остовный лес является остовом, поскольку, к примеру, пустой остовный подграф является лесом, но не является остовом, если граф содержит хотя бы одно ребро.
Если множество вершин подграфа [math]H[/math] графа [math]G[/math] есть [math]S[/math] , а сам подграф [math]H[/math] максимальный (по включению) среди всех таких подграфов, то подграфа [math]H[/math] называется подграфом, порождённым множеством [math]S[/math] , или просто порождённым подграфом. Другими словами, подграф [math]H[/math] графа [math]G[/math] называется порождённым, если он содержит все возможные (для своего множества вершин) рёбра графа [math]G[/math] .
Цепи, циклы, пути
В неориентированном графе
Маршрут — чередующаяся последовательность [math]v_0, e_1, v_1, e_2, \ldots, e_, v_ \tag[/math] вершин и рёбер, в которой [math]e_i = \, v_i\,\>\label[/math] ( [math]i = \overline[/math] ). Вершины [math]v_0[/math] и [math]v_[/math] называются крайними, а все остальные — промежуточными (или внутренними). Маршрут, содержащий вершины [math]v_0[/math] и [math]v_[/math] в качестве крайних, называется [math](v_0, v_)[/math] -маршрутом.
Если в графе нет кратных рёбер, то маршрут можно однозначно задать последовательностью вершин.
Цепь — маршрут, все рёбра которого попарно различны.
Простая цепь — цепь, все вершины которой, кроме, возможно, крайних, попарно различны.
Цепь в графе также можно рассматривать как подграф этого графа. Тем не менее подграф, соответствующий цепи, однозначно (с точностью до направления) задаёт эту цепь, если и только если она является простой.
Циклический маршрут — маршрут, крайние вершины которого совпадают.
Цикл (или циклическая цепь) — циклический маршрут, являющийся цепью.
Простой цикл — простая циклическая цепь.
Гамильтонов цикл — простой цикл, содержащий все вершины графа.
Эйлеров цикл — цикл, содержащий все рёбра графа.
В ориентированном графе
Ориентированный маршрут (или просто маршрут) — последовательность вида (1) для ориентированного графа, в которой [math]e_i = (v_, v_i)[/math] . Понятия цепи, циклического маршрута и цикла переносятся на случай ориентированного графа без изменений.
Путь — ориентированный маршрут, все вершины которого, кроме, возможно, крайних, различны.
Контур — циклический путь.
Полумаршрут — последовательность вида (1), в которой [math]e_i = (v_, v_i)[/math] или [math]e_i = (v_i, v_)[/math] . Аналогично определяются полуцепь, полупуть и полуконтур.
Если в орграфе существует [math](u, v)[/math] -маршрут, то говорят, что вершина [math]v[/math] достижима из вершины [math]u[/math] . Любая вершина считается достижимой из самой себя.
Связность
В неориентированном графе
Связный граф — граф, любые две несовпадающие вершины которого соединены маршрутом.
Связная компонента (или компонента связности, или просто компонента) графа [math]G[/math] — максимальный (по включению) связный подграф графа [math]G[/math] .
Область связности графа — множество всех вершин одной компоненты связности этого графа.
Точкой сочленения называется вершина, при удалении которой число компонент графа увеличивается.
Связный граф, не содержащий точек сочленения, называется двусвязным или вершинно двусвязным.
Мостом называется ребро, при удалении которого число компонент графа увеличивается.
Связный граф, не содержащий мостов, называется рёберно двусвязным.
В ориентированном графе
Орграф называется сильным (или сильносвязным), если любые две его вершины достижимы друг из друга.
Орграф называется односторонним (или односторонне связным), если для любой пары его вершин по меньшей мере одна достижима из другой.
Орграф называется слабым (или слабосвязным, или просто связным), если любые две его вершины соединены полупутём.
Сильная и слабая компоненты определяются аналогично компоненте в неориентированном графе.
Замечания
- ↑ Существуют альтернативные эквивалентные определения.
Существует ли быстрый алгоритм поиска максимальной цепи в графе?
Здравствуйте. Задача: есть взвешенный ориентированный граф (полно циклов, у каждой вершины 5-20 связей), в нем нужно найти такой путь через все вершины, что бы сумма весов пройденных ребер была максимальной, а каждая вершина встречалась только один раз. Не сложно догадаться до полного перебора, но меня интересуют графы, в которых около сотни вершин. Существует ли алгоритм, который может найти такой путь? Если совсем нет, существует ли быстрый алгоритм, позволяющий найти хоть какой-нибудь путь в графе, проходящий через все вершины только один раз?
Отслеживать
задан 29 янв 2018 в 21:10
1,536 1 1 золотой знак 11 11 серебряных знаков 27 27 бронзовых знаков
Это у Вас в чистом виде задача коммивояжера, соответственно, смотрите алгоритмы ее решения. Быстрый (полиномиальный) точный алгоритм неизвестен, и более того, неизвестно, существует ли он вообще. Так что, смотрите в сторону приближенных алгоритмов.
29 янв 2018 в 21:48
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Предлагаю такой алгоритм.
Перебор всех вариантов с двумя поправками.
- Для последующих вариантов убираем те вершины через которые прошли (то есть они уже не будут участвовать в расчёте).
- Сначала идём не в ширину а в глубину. При переборе может быть разный порядок вычислений, в данном случае мы по очереди просматриваем не варианты разных выходов из одной вершины, а сначала идём вглубь переходя к следующей вершине, и уже если там не прошло то идём в ширь.
Алгоритм должен достаточно быстро найти первый путь, хотя сумма и не будет максимальной, но проходя дальше и ища дополнительные пути, можно будет уже выбирать более быстрые. Даже не обязательно все варианты в результате перебирать, можно какой-то процент обработать, и настолько уже можно будет найти более хороший путь.
Далее есть идеи как можно после нахождения первого пути, достаточно быстро без полного перебора находить более быстрые пути.
Найдя первый рабочий путь, смотрим варианты какие вершины можно в порядке прохождения поменять местами, и какие рёбра, если это ускоряет путь, значит нашли более быстрый (Метод улучшения пути).
Если нужна ещё большая оптимизация то ищем N первых рабочих путей, используя случайные варианты. И уже каждый из путей оптимизируем алгоритмом (Метод улучшения пути). Находим из них лучшее решение.