Что такое поток в графе
Химия. Максимальный поток
Вместо предисловия
Привет, Хабр! Недавно потратил кучу времени в попытках решить данную задачку. Алгоритм и реализация в ней оказались несложными, но связь между постановкой вопроса и использованием потоков, на мой взгляд, не очевидная, и я, потратив какое-то время в поисках каких-то объяснений или намеков на решение в гугле, смог найти только следующую статейку с довольно куцым объяснением. Потому пишу данный пост, в надежде на то, что кому-нибудь он поможет.
Постановка задачи
Вася и Сережа играют в следующую игру. В некоторых клетках клетчатого листка Сережа рисует один из символов ‘ H ‘, ‘ O ‘, ‘ N ‘ или ‘ C ‘, после чего Вася должен провести между некоторыми находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение химической молекулы. К сожалению, Сережа любит рисовать много символов, и Вася не может сразу определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу, которая даст ответ на этот вопрос.
В этой задаче проведенные между символами химических элементов линии будем считать корректным изображением молекулы, если они удовлетворяют следующим условиям:
каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках,
между каждой парой символов проведено не более одной линии,
от каждого элемента отходит ровно столько линий, какова валентность этого элемента (1 для H, 2 для O, 3 для N, 4 для C),
пустые клетки ни с чем не соединены, и
хотя бы в одной клетке нарисован какой-то символ.
Входные данные
Выходные данные
В выходной файл выведите одно слово « Valid », если линии провести требуемым образом можно, и « Invalid », если нельзя.
При чем здесь поток?
Но как определить, что и куда будет вытекать? Определим для себя сами. Для этого используем следующее замечание: граф, который, согласно условию, представляет собой множество клеток прямоугольника в качестве вершин и множество сторон клеток в качестве ребер, при детальном рассмотрении оказывается двудольным. Почему?
Раскраска входных данных из первого примера
Решение
От воды к графам
Чтобы разлить из большой бочки-истока в каждую «темную» бочку воды ровно столько, сколько в нее поместится, необходимо пропускную способность трубки, ведущую в данную бочку, установить равной литражу данной бочки. Аналогично поступаем и со стоками.
А теперь то же в понятиях графов. К двудольному графу, в котором ребра представляют собой связи между соседними клетками, добавим фиктивную вершину-исток и фиктивную вершину-сток. Из вершины стока проведем ребра в каждую вершину левого множества, установив вес ребра равным валентности атома в этой вершине, а из правого множества по тому же принципу в вершину-сток. Между вершинами, играющими роль атомов, проведем все возможные по условию связи.
Граф для первого примера
Получаем слоистую сеть, в которой ребра ориентированы по увеличению длины пути от истока. Подсчитывая максимальный поток, будем использовать, к примеру, алгоритм Форда-Фалкерсона, пытаясь найти увеличивающий путь, пока пути из истока в сток вообще имеются. С практической точки зрения, мы будем пытаться задействовать связи между атомами так, чтобы реализовать все валентности (использовать трубки так, чтобы перелить из бочек как можно больше воды).
Когда максимальный поток будет найден, остается проверить, не осталось ли воды в изначально полных бочках, и все ли пустые бочки теперь заполнены. Если мы полностью опустошили или наполнили бочку объемом V литров, то через трубку, соединяющую её с истоком или стоком, должно пройти ровно V литров воды. С точки зрения графов нужно проверить, нет ли среди инцидентных истоку или стоку ребер ненасыщенных, т.е. таких, чья пропускная способность использована не по максимуму.
Для этого при составлении графа будем суммировать валентности вершин каждого множества. Если обе суммы равны найденному максимальному потоку, значит, все ребра в этих множествах насыщены, и необходимая комбинация связей нашлась. В противном случае расставить связи никак не получится.
Краткий итог
Красим вершины в шахматном порядке.
Вес ребер, инцидентных стоку или истоку, устанавливаем равным валентности соответствующих вершин-атомов, для белых и черных вершин отдельно считаем сумму валентностей.
Соединяем соседние по условию вершины-атомы ребрами веса 1, направляя из черных в белые.
Реализация
В качестве примера приведу свою реализацию решения задачи на С++.
Алгоритм Форда-Фалкерсона
Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.
При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.
Постановка задачи
Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истока
в сток
.
Исходный граф
Как работает сам алгоритм?
Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:
Отправлять определенное количество потока из текущей вершины в соседние.
Возвращать определенное количество потока из соседних вершин в текущую.
В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.
Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.
Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.
Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.
А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.
Возвращаемся обратно к нахождению пути в остаточной сети после модификации.
Разбор конкретного примера
Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.
Допустим наш алгоритм нашел следующий путь из вершины
в
нашей остаточной сети, которая на момент начала, совпадает с исходным графом.
Сколько потока можем провести по этому пути.
— Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:
Остаточная сеть после 1-ой итерации
Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.
Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из 
в 
.
Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:
Остаточная сеть после 1-ой итерации
Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:
Остаточная сеть после 2-ой итерации
На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:
Остаточная сеть после 2-ой итеации
Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
Остаточная сеть после 3-ей итерации
На 4-ой итерации находим следующий путь в остаточной сети:
Остаточная сеть после 3-ей итерации
Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
Итоговая остаточная сеть
На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.
Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!
Потоки в сетях
Мы увидим, что с этими задачами и приложениями можно справиться с помощью нескольких естественных моделей, сводимых одна к другой. Существует несколько различных, хотя технически эквивалентных, способов формулирования базовых задач. Для реализации алгоритмов решения любых этих задач мы выберем две конкретные задачи, разработаем эффективные алгоритмы их решения, а затем разработаем алгоритмы для решения других задач с помощью сведения их к уже известным задачам.
В реальной жизни мы не всегда располагаем свободой выбора, как в этом идеализированном сценарии, поскольку сводимость одной задачи к другой доказана не для каждой пары задач и поскольку известно немного оптимальных алгоритмов решения любой из этих задач. Бывает, что еще не найдено прямое решение заданной задачи, и бывает, что еще не найдено эффективное сведение для заданной пары задач. Формулировка задачи о сетевых потоках, которой мы займемся в данной главе, имеет успех не только потому, что к ней легко сводятся многие практические задачи, но и потому, что было разработано множество эффективных алгоритмов решения базовых задач о потоках в сетях.
Приведенные ниже примеры демонстрируют диапазон задач, которые можно решить с помощью моделей сетевых потоков, алгоритмов и реализаций. Их можно разбить на общие категории, известные как задачи распределения ( distribution ), сопоставления ( matching ) и сечения ( cut ); и мы поочередно рассмотрим каждую из них. Мы не будем заострять внимание на конкретных деталях этих примеров, а выделим несколько различных взаимосвязанных задач. Ниже в этой главе, когда мы дойдем до разработки и реализации алгоритмов, будут даны строгие формулировки многих из упомянутых здесь задач.
Распределение товаров. У компании имеются фабрики, где производятся товары, оптовые базы для временного хранения товаров и розничные торговые точки, в которых товары продаются. Компания должна регулярно поставлять товары с фабрик в розничные торговые точки через оптовые базы, используя каналы распределения, которые обладают различными пропускными способностями и различными стоимостями доставки. Можно ли так организовать доставку товаров со складов в розничные торговые точки, чтобы везде удовлетворить спрос? Как определить маршрут наименьшей стоимости? Пример задачи распределения приведен на рис. 22.1.
Транспортные потоки. Городское управление должно разработать план аварийной эвакуации людей из города. Каково минимальное время для эвакуации города, если мы можем регулировать для этого транспортные потоки? Ответственные за планирование дорожного движения могут ставить подобные вопросы, обумывая решение, какие новые дороги, мосты или туннели могут смягчить проблему уличного движения в часы пик или в выходные дни.
В задаче сопоставления сеть представляет возможные способы соединения пар вершин. Необходимо выбрать такие возможные соединения (в соответствии с указанным критерием), чтобы не выбрать ни одну из вершин дважды. Другими словами, выбранное множество ребер определяет способ попарного соединения вершин. Можно сопоставлять колледжи и студентов, вакантные рабочие места и соискателей, предметы и свободные часы в школе или членов Конгресса США (Государственной Думы России, Верховной Рады Украины) и различные комитеты. В каждой из таких ситуаций возможны самые разнообразные критерии, определяющие характер выбора.
Задача о трудоустройстве. Служба трудоустройства организует интервью для группы студентов с некоторым количеством компаний, в результате чего появляется ряд предложений работы. Если считать, что интервью с последующим предложением работы представляет взаимную заинтересованность студента и компании, то для обеих сторон выгодно добиваться максимального трудоустройства. Из примера на рис. 22.3 видно, что эта задача может оказаться весьма сложной.
В этом примере задачи распределения имеются три вершины предложения (от 0 до 2), четыре распределительных пункта (от 3 до 6), три вершины потребления (от 7 до 9) и двенадцать каналов. У каждой вершины предложения своя скорость производства, у каждой вершины потребления своя скорость потребления, а у каждого канала своя максимальная пропускная способность и стоимость доставки единицы продукции. Нужно так минимизировать стоимость доставки по каналам (без превышения пропускной способности каналов), чтобы общая скорость извлечения материалов из каждой вершины предложения была равна скорости производства; чтобы общая скорость поставки в вершины потребления была равна скорости его потребления; и чтобы общая скорость поступления в каждый распределительный пункт была равна скорости вывоза.
Транспортная задача похожа на задачу распределения, только в ней нет ограничений на пропускные способности каналов и распределительных пунктов. В данном примере имеются пять вершин снабжения (от 0 до 4), пять вершин потребления (от 5 до 9) и двенадцать каналов. Нужно найти самый дешевый способ распределения материала по каналам, чтобы предложения соответствовали спросу.
В частности, нужно присвоить каналам такие веса (скорость распределения), чтобы сумма весов исходящих ребер была равна поставкам в каждую снабжающую вершину; сумма весов входящих ребер равна суммарной потребности каждой потребляющей вершины; а общая стоимость (сумма произведений веса на стоимость для всех ребер) должна быть минимальной при всех таких вариантах присваивания.
Здесь представлена система дорог, соединяющих базу снабжения армии (верху) с войсками (внизу). Черные точки означают план бомбовых ударов противника, которые должны отделить войска от снабжения. Противник стремится минимизировать стоимость бомбардировок (возможно, исходя из предположения, что стоимость отсечения ребра пропорциональна его ширине), а армия стремится разработать такую сеть дорог, чтобы максимизировать минимальную стоимость бомбардировок. Эта же модель полезна для повышения надежности сетей связи и во множестве других приложений.
Надежность сети. Телефонную сеть можно представить в виде некоторого множества кабелей, которые соединяют телефонные аппараты с помощью коммутаторов так, что возможен коммутируемый путь через междугородные линии связи, соединяющий любые два заданных телефона. Каково максимальное количество междугородных линий, которые можно отключить без нарушения связи между любой парой телефонных коммутаторов?
На первый взгляд может показаться, что многие из этих задач не имеют ничего общего с задачами о потоках в сетях. Выявление связи с известными задачами часто является наиболее важным шагом при разработке решения задачи. Более того, этот шаг часто важен еще и потому, что перед разработкой реализаций необходимо (как обычно в случае алгоритмов на графах) определить тонкую грань, которая отделяет тривиальные задачи от трудноразрешимых. Внутренняя структура задач и взаимосвязь между задачами, которые мы рассмотрим в этой главе, обеспечивают удобный контекст для ответов на подобные вопросы.
С другой стороны, известно, что некоторые задачи, которые сводятся к задачам о сетевых потоках, более эффективно решаются с помощью специализированных алгоритмов. В принципе, мы могли бы заняться реализацией и совершенствованием таких особых алгоритмов. В отдельных случаях такой поход вполне удобен, однако эффективные алгоритмы решения множества других задач (отличных от сведения к сетевым потокам) не существуют. Но даже в тех случаях, когда известны специализированные алгоритмы, разработка реализаций, способных превзойти удачные программы обработки сетевых потоков, может оказаться очень сложной. А кроме того, исследователи постоянно со-вершенствовуют алгоритмы обработки сетевых потоков, и они вполне могут превзойти известные специальные методы решения конкретной практической задачи.
С другой стороны, задачи о сетевых потоках представляют собой специальные случаи еще более общих задач линейного программирования (LP), о которых речь пойдет в части VIII. Для решения задач о сетевых потоках в сетях можно воспользоваться алгоритмом решения LP-задач (и многие так и делают), но все же рассматриваемые ниже алгоритмы обработки сетевых потоков намного проще и эффективнее, чем построенные на решении LP-задач. Однако исследователи продолжают совершенствовать программы решения LP-задач, и не исключена возможность того, что качественный алгоритм решения LP-задачи, будучи использованным для решения задач о сетевых потоках, сможет оказаться эффективнее алгоритмов, которые мы рассматриваем в данной главе.
Классические решения задач о сетевых потоках тесно связаны с другими, уже изученными нами, алгоритмами на графах, и мы можем написать на удивление компактные программы их решения, воспользовавшись разработанными ранее алгоритмическими инструментами. Как мы уже не раз видели, качественные алгоритмы и структуры данных могут существенно снизить время выполнения программ. Поиск методов разработки более совершенных реализаций классических обобщенных алгоритмов продолжается, и время от времени появляются новые подходы.
Теория графов. Основные понятия и виды графов
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
