рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Определение путей и контуров Эйлера

Реферат Курсовая Конспект

Выберите учебное заведение

Определение путей и контуров Эйлера

Определение путей и контуров Эйлера - раздел Образование, Основные операции при работе с деревьями Путь Эйлера Проходит По Каждому Ребру В Графе Только Один Раз...

Путь Эйлера проходит по каждому ребру в графе только один раз. Контур Эйлера проходит каждое ребро в графе тоже один раз, а также начинается и заканчивается в одной и той же вершине (рис. 4). Многие уже знакомы с концепцией следующей простой головоломки — нарисовать какое-то очертание без отрыва ручки от бумаги.

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

Рис. 4. Граф, который имеет путь Эйлера, и сам этот путь.

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

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

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

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

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

На рисунках 5—8 показан пример выполнения такого алгоритма. Работа алгоритма заключается в локализации циклов в графе с использованием похожей на глубинный поиск методики. Эти циклы затем можно скомбинировать для образования одного цикла, который проходит по всем ребрам в графе, — цикла Эйлера. Алгоритм можно описать как последовательность следующих действий:

1. Инициализировать список циклов.

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

3. Объединить пути и циклы вместе для формирования контура Эйлера.

Рис. 5. Исходный граф.

Рассмотрим подробнее этот алгоритм. Глубинный поиск начинается с вершины v0 и на последующих итерациях посещаются вершины v1 и v3. После v3 достигается v0, и полученный цикл считается найденным. Затем цикл v0, v1, v4, v3 и v0 сохраняется.

Рис 6. Ребра графа, по которым проходит

путь 0->1->4->3-> 0 удаляются.

Затем глубинный поиск продолжается с первой вершины, которая имела выходящее из нее ребро. В нашем случае это вершина v,. При глубинном поиске может быть найден цикл v1, v2, v5, v4, v4, v7, v6, v3, v1 который добавляется в список циклов. Рис. 7 демонстрирует граф без второго найденного цикла.

Следующий этап глубинного поиска начинается с вершины v5; при этом обнаруживается цикл v5, v8 v7, v5. Начиная с этого момента, мы больше не найдем непросмотренных ребер. Таким образом, получилось три цикла.

Рис. 7. Граф с удаленными ребрами

по пути 1->2->5->4->7->6->3->1.

Этот же алгоритм с небольшими поправками можно использовать также для поиска пути Эйлера. Разница состоит в результате первого этапа поиска. Любой граф, удовлетворяющий условиям для контура Эйлера, после первого этапа поиска создает цикл. Чтобы найти путь Эйлера, первый поиск надо провести, начиная с одной из двух вершин с нечетными степенями. Результатом такого поиска будет путь от первой вершины с нечетной степенью ко второй. Все последующие этапы поиска дают циклы, которые можно вставить в первый путь таким же образом, как и в случае с контуром Эйлера.

Рис. 8. Найденный контур Эйлера.

Эффективная реализация этого алгоритма может оказаться немного громоздкой. Потенциальную проблему представляют неориентированные графы из-за обычного способа их представления. Хотя в графе ребро является единственным объектом, оно представляется как два ориентированных ребра, одно из которых идет от u к v, а другое — от v к u.

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

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

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Основные операции при работе с деревьями

Основные операции при работе с деревьями... Определение глубины дерева... Обход дерева на заданную глубину включение нового значения в дерево...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Определение путей и контуров Эйлера

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Оптимизация поиска в дереве
Основное свойство дерева соответствует пословице " дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогр

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

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

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

Преобразование лозы в сбалансированное двоичное дерево.
Этот этап алгоритма более содержательный и поэтому менее очевидный. Поэтому сначала будет разобран простой пример, а потом будет дано его обобщение. Пусть есть лоза, котора

Алгоритмы представления графа
При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор представления графа определяется

Файл setgraph.h
#include "graph.h" #include "set.h" // Определение класса для работы с множествами class SetGraph : public Graph { Set **graph; // Массив множеств дуг

Представление графа в виде матрицы смежности
Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе с индексами (i,j) записывается ин

Файл MatrixGraph.cpp
#include "MatrixGraph.h" // Реализация конструктора - заказ и инициализация памяти // под двумерный массив логических значений MatrixGraph::Matr

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

Файл ListGraph.h
#include "graph.h" // Описание родительского класса // Описание шаблона классов для представления // простых однонаправленных списков template &

Файл ListGraph.cpp
#include "ListGraph.h" // Реализация операций над списком. // Добавление нового элемента в список template <class T> void List<

Представление графа в виде списка дуг
Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число дуг существенно меньше NXN, напри

Файл ArcGraph.h
#include "graph.h" // Определение родительского класса // Описание класса для представления A-графа class ArcGraph : public Graph { // Дуга представлена элемент

Файл ArcGraph.cpp
«include "ArcGraph.h" //Реализация операции добавления дуги void ArcGraph::addArc(int from, int to) { // Сначала проверяем правильность задания

Файл convert.срр
#include "SetGraph.h" #include "MatrixGraph.h" #include "ListGraph.h" #include "ArcGraph.h" // Функция пр

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

Поиск кратчайших путей
Путем в графе называют чередующуюся последовательность вершин и дуг v1, e1, v2, e2,... vn-1 en-1, vn, в которой каждый элемент vi— вершина графа, а каждый элемент еi — дуга графа, ведущая из пре

Алгоритм Э. Дейкстры.
Опишем алгоритм нахождения такого пути при условии, что длины всех дуг неотрицательны. Этот алгоритм был предложен и опубликован Э. Дейкстрой (Е. W. Dijkstra), поэтому и носит его имя. Алг

Алгоритм Флойда — Уоршалла
Идея алгоритмом Флойда — Уоршалла, состоит в следующем. Будем рассматривать последовательность матриц смежности. В этой матрице элемент с индексами (i,j) равен +∞, если в графе нет ребра, вед

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

Файл listgraph.h
// Класс ListGraph задает структуру L-графа class ListGraph { // Массив списков дуг List<int> *graph; // Количество вершин графа i

Файл Arc.h
// Структура ребра для алгоритма Крускала: сравнение ребер // происходит по их весам struct Arc { int from, to; double weight; Arc(int f

Файл listgraph.cpp
// Собственно алгоритм Крускала double ListGraph::minSkeleton( // Выходной поток для вывода результирующей информации: std::ostream & out, // Нагрузка на реб

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

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

Пузырьковая сортировка
Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются сле

Быстрая сортировка
Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного

Сортировка слиянием
Рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.

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

Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится

Работа со словарем. Иоиск и вставка. Хеширование.
Довольно часто встречаются ситуации, когда обработке подлежат много маленьких строк — слов, которые надо сохранять в некоторой единой структуре — словаре. Сами слова н

Файл dictionary.h
// Класс, представляющий словарь в виде хеш-таблицы classHashDictionary { private: static const intP = 557;

Файл dictionary.cpp
// Реализация функций intHashDictionary::code(char c) { returnstrchr("abcdefghijklmnopqrstuvwxyz&

Файл "hashtable.h".
// Класс, представляющий хеш-таблицу пар (ключ, значение), причем // ключом является строка, а значением может быть произвольный объект. //В таблице хранятся не са

Алгоритм прямого поиска подстроки в строке
1. Установить i на начало строки S, т.е. i = 0. 2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм