Свойства эйлеровых графов

ВВЕДЕНИЕ

Граф представляет собой отображение отношений внутри некоторого множества объектов, представляемых вершинами графа: наличие или отсутствие связей между ними (в первом случае они соединены друг с другом ребрами; во втором случае ребра отсутствуют), а также количественно выраженная направленность и интенсивность связей.
Универсальность такого представления структуры позволяет описывать и давать количественную оценку широкого класса задач в технических, технологических, экономических и многих других приложениях.
Например, в виде графа отображают последовательность выполняемых работ при строительстве объектов, начиная от изыскательских работ и заканчивая обустройством прилегающих территорий, маршруты транспортировок материалов, взаимосвязи этапов работ, потоки ресурсов различного рода (материальных, финансовых, трудовых, энергетических), системы учета и управления проектами в соответствии с каждым из этапов и т.д.
Несмотря на различную природу описываемых отношений, графы обладают многими общими свойствами, что позволяет использовать методы дискретной математики и, в частности, теории графов для количественного описания их общих свойств, независимо от реальных объектов, которые они представляют.
Графы используют во всех областях науки и техники, в частности при принятии решении и в задачах оптимизации, когда в пространстве всех возможных состояний системы необходимо выбрать наилучшее с позиций поставленных цели и критериев.
Графовые модели систем открывают широкие возможности для анализа и синтеза систем с помощью методов теории графов и прикладной теории графов, что во многих случаях упрощает анализ, делая его наглядным и поддающимся содержательной интерпретации. Сложность системы, будучи ключевым понятием системологии, должна быть глубоко и интенсивно исследована и ориентирована на развитие подходов к анализу сходства систем.
Можно утверждать, что структурная сложность систем наименее изучена, хотя теория сложности структурированных объектов (графов, гиперграфов, семантических сетей) наиболее востребована в таких областях, как системы искусственного интеллекта, принятия решений, информационного поиска структурной информации, системы автоматизированного проектирования регулярных топологий вычислительных сетей и сред, химическая информатика, структурное распознавание образов, структурный анализ систем автоматического управления и др [1].
Цель этой работы— изучить граф Эйлера и его различные аспекты в реальном мире. В настоящее время граф Эйлера используется во многих ситуациях, которые встречаются в компьютерных науках, физических науках, науках о коммуникации, экономике и многих других областях. Графы касаются взаимоотношений с линиями и точками (узлами). Граф Эйлера может быть использован для представления практически любой проблемы, связанной с дискретным расположением объектов, где интерес представляют не внутренние свойства этих объектов, а взаимоотношения между ними. Для достижения цели следует изучить основные понятия теории графов, и исследовать методы, которые используются для нахождения пути Эйлера и цикла Эйлера. 

1.Основные определения и понятия теории графов

1.1. Задача о мостах Кенигсберга как начало теории графов

Река Прегель (Pregel) протекает через город Кенигсберг (Калининград), разделяющий город на четыре сухопутных региона, два из которых являются берегами реки, а два — островами или дельтовыми образованиями. Четыре сухопутных региона были соединены 7 мостами (рис. 1). Для жителей Кенигсберга было занимательное и интересное упражнение: начать с любого сухопутного региона и вернуться в исходную точку, перейдя каждый из семи мостов ровно один раз, не повторяя один и тот же путь [2].



Рисунок 1. Схема мостов Кенигсберга

В начале XVIII века жители Кёнигсберга проводили дни, прогуливаясь по сложной системе мостов через воды реки Прегель, которая окружала два центральных массива суши, соединенных мостом. Кроме того, первый массив суши (остров) был соединен двумя мостами с нижним берегом Прегеля, а также двумя мостами с верхним берегом, в то время как другой массив суши (который разделял Прегель на два рукава) был соединен с нижним берегом одним мостом и с верхним берегом одним мостом, всего семь мостов. Согласно фольклору, возник вопрос, может ли гражданин прогуляться по городу таким образом, чтобы каждый мост был пересечён ровно один раз.
В 1735 году швейцарский математик Леонард Эйлер представил решение этой задачи, заключив, что такая прогулка невозможна. Чтобы подтвердить это, предположим, что такая прогулка возможна [3]. При одной встрече с определенным массивом суши, кроме начального или конечного, необходимо учитывать два разных моста: один для входа на массив суши и один для выхода с него. Таким образом, каждый такой массив суши должен служить конечной точкой числа мостов, равного удвоенному числу раз, когда он встречается во время прогулки. Следовательно, каждый массив суши, за возможным исключением начального и конечного, если они не идентичны, должен служить конечной точкой четного числа мостов. Однако для массивов суши Кенигсберга A (рис. 2) является конечной точкой пяти мостов, а B, C и D являются конечными точками трех мостов. Поэтому прогулка невозможна.
Прошло почти 150 лет, прежде чем математики изобразили задачу о мостах Кенигсберга как граф, состоящий из узлов (вершин), представляющих массивы суши, и дуг (ребер), представляющих мосты. Степень вершины графа определяет количество ребер, инцидентных ей. В современной теории графов эйлеров путь проходит по каждому ребру графа один и только один раз. Таким образом, утверждение Эйлера о том, что граф, обладающий таким путем, имеет не более двух вершин нечетной степени, было первой теоремой в теории графов.




Рисунок 2. Задача о мостах Кенигсберга

Теория графов и топология, обе рожденные в работах Эйлера, в настоящее время являются основными областями математических исследований.
Эйлер предположил и далее объяснил, что это невозможно сделать, используя терминологию точек (представляющих сухопутные регионы) и линий (представляющих мосты). Поэтому он назвал свою работу «Решения задачи, связанной с геометрией положений». С помощью этого объяснения он заложил основу для теории графов. Теория графов началась с этой проблемы.
Он абстрагировал случай Кенигсберга, исключив все ненужные особенности. Он нарисовал картинку, состоящую из «точек», которые представляли собой массивы суши, и отрезков линий, представляющих мосты, которые соединяли эти массивы суши.
 

1.2. Основные определения и понятия теории графов

Наиболее общим подходом к исследованию графов и их свойств является теория множеств и многие определения в теории графов можно дать с этих позиций [4, 5, 6].
Граф G – это совокупность двух множеств: V и E:
G = (V, E),
где V – основное множество вершин (от англ. Vertex – вершина), а E (от англ. Edge – ребро) – множество двухэлементных подмножеств множества V, называемых ребрами.

Множество V
Множество V множество е1

Элементы множества V Элементы множества E
Рисунок 3. Граф G(V, E) и его множества V и E

Число вершин графа G обозначим р, а число рёбер — q.
Если нужно явно упомянуть числовые характеристики графа, то говорят, (р, q)-граф.
Пусть v1,v2— вершины, е = (v1, v2) — соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, ребро е и вершина v2также инцидентны