 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Эйлеровы графы
Задача о Кенигсбергских мостах (Эйлер, 1736 год). На рисунке 4.1 слева изображена часть реки Прейгель, находящейся в Кенигсберге (ныне Калининграде). Буква Л обозначает левый берег, П – правый, А и Б – острова.
Требуется найти маршрут пешехода, проходящий через все мосты, через каждый мост пешеход должен пройти ровно один раз. Эйлер доказал, что эта задача не имеет решений.
Сначала напомним определение простого графа, приведенное в пп. 1.5. Для произвольного множества V обозначим через P2(V) множество, состоящее из подмножеств { v1,v2 }Í V, каждое из которых состоит из двух не равных между собой элементов.
Определение 1. Простым (неориентированным) графом G=(V,E) называется пара, состоящая из множества V и произвольного подмножества E Í P2(V). Элементы из V называются вершинами, а из E – ребрами.
Вершины простого графа изображаются как точки или круги, а ребра – как отрезки.
Рис. 4.1. Схема мостов и соответствующий ей граф
Обобщим определение простого графа.
Определение 2. Графом называется тройка (V, E, a), состоящая из множеств V, E и функции a: E ®P2(V), сопоставляющей каждому eÎE неупорядоченную пару {u,v}. Элементы из E называются ребрами, элементы из V – вершинами.
Если a(e)={u,v}, то вершины u и v называются концами ребра e. В этом случае u и v называются смежными вершинами и инцидентными ребру e. Если концы ребра e равны (a(e) состоит из единственного элемента), то ребро e называется петлей.
Степенью вершины v называется число инцидентных ей ребер. Ребро, являющееся петлей, учитывается два раза. В частности, петля дает степень 2. Для графа, соответствующего схеме Кенигсбергских мостов, степени вершин равны 3, 3, 3 и 5. Путем в графе называется последовательность вершин и ребер v0g1v1g2v2 ∙∙∙ vn-1gnvn, таких что vi и vi+1 инцидентны ребрам gi+1, для всех i Î{1,2, ∙ ∙ ∙, n }. Граф, допускающий путь, не содержащий кратных ребер и содержащий все ребра, называется эйлеровым. Такой путь тоже называется эйлеровым.
На рис. 4.1 справа изображен граф, ребра которого соответствуют мостам, а вершины – частям суши. Задача о Кенигсбергских мостах имеет решение тогда и только тогда, когда этот граф является эйлеровым.
Поиск по сайту: