23.03 - ДМ - Эйлеровы пути и циклы, произвольно вычерчиваемые графы

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

• Доказывается, что граф, содержащий эйлеров цикл, также содержит эйлеров путь.  

• Доказывается, что если в графе есть эйлеров цикл, то все вершины имеют четную степень.  

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

• Доказывается, что если все вершины имеют четную степень, то все множество ребер можно разбить на циклы.  

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

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

• Если взять максимальный подграф, удовлетворяющий условиям три, то он будет содержать все ребра, разбивающиеся на циклы.  

• В идеальном мире, где все ребра разбиваются на циклы, граф ж один равен графу ж.  

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

• Удаление ребер из графа ж один приводит к противоречию с утверждением о четности степеней вершин.  

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

• Добавление этого цикла в аш приводит к противоречию с утверждением о максимальности графа ж один.  

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

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

• Далее, рассматривается вопрос о том, как связаны циклы между собой.  

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

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

• Это приводит к утверждению, что в графе с двумя нечетными степенями можно покрыть все ребра простыми путями.  

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

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

• В видео доказывается, что для покрытия всех ребер графа достаточно ребер на простых путях.  

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

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

• Сначала проверяется наличие путей или циклов в графе, затем начинается рекурсия от вершины с нечетной степенью.  

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

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

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

• Это важно для фиксации ребер, которые были использованы в процессе поиска.  

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

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

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

• Это удобно для планирования выставок, где посетитель может посетить все залы, не беспокоясь о том, что он что-то пропустил.  

• В видео приводятся примеры произвольно вычерчиваемых графов и обсуждаются их ограничения.  

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

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

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

• Если все вершины четной степени, то граф является эйлеровым.  

• Если есть вершины нечетной степени, то они образуют компоненту, которая может быть эйлеровой или неэйлеровой.  

• Если есть цикл, который не пересекается с вершиной "в", то можно доказать, что все компоненты, кроме "аш ноль", являются одноэлементными.  

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

• Это приводит к противоречию, так как утверждалось, что любой путь может быть продолжен до эйлерова цикла.  

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

• Для этого нужно взять вершину "в", которая будет являться вершиной, с которой будет произвольно вычерчиваться граф, и представить остальные вершины в виде произвольных лесов.  

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

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

• Если вершина имеет четную степень, то можно добавить любое количество четных ребер, а если нечетную степень - любое количество нечетных ребер.  

• Главное, чтобы соблюдалась соответствующая четность с вершиной "в", из которой добавляются ребра.  

• Если вершина имеет степень 0, то можно оставить ее без связи с вершиной "в".