Содержание
Введение
I. Основные понятия
1.Эйлеровы графы.
2. Кротчайшие пути.
3. Деревья.
II.Задача коммивояжера.
1.Общие описание.
2.Методы решенияЗК.
а. Жадный алгоритм.
б. Деревянный алгоритм.
в. Метод ветвей и границ.
III. Выводы.
Литература.
Введение.
ТЕОРИЯГРАФОВ — это областьдискретной математики, особенностью которойявляется геометрический подход к изучению объектов. Теория графов находится сейчас всамом расцвете. Обычно её относят к топологии (потому что во многих случаяхрассматриваются лишь топологические свойства графов), однако она пересекаетсясо многими разделами теории множеств, комбинаторной математики, алгебры,геометрии, теории матриц, теории игр, математической логики и многих других математическихдисциплин. Основной объект теории графов-граф и егообобщения.
Первыезадачи теории графов были связаны с решением математических развлекательныхзадач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей нашахматной доске, задачи о перевозках, задача о кругосветномпутешествии и другие). Однимиз первых результатов в теории графов явился критерий существования обхода всехребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Вот пересказотрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача обострове, расположенном в городе Кенигсберге и окруженном рекой, через которуюперекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их,проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог этопроделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя ибанальный, показался мне, однако, достойным внимания тем, что для его решениянедостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгихразмышлений я нашел лёгкое правило, основанное на вполне убедительномдоказательстве, с помощью которого можно во всех задачах такого рода тотчас жеопределить, может ли быть совершен такой обход через какое угодно число и какугодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так.
Существует ещеодин вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь,проходящий через все вершины, причем не более одного раза через каждую. Цикл,проходящий через каждую вершину один и только один раз, носит названиегамильтоновой линии( в честь Уильяма РоуэнаГамильтона, знаменитого ирландского математика прошлого века, который первымначал изучать такие линии). К сожалению, пока еще не найден общий критерий, спомощью которого можно было бы решить, является ли данный граф гамильтоновым, иесли да, то найти на нём все гамильтоновы линии.
Сформулированная в середине 19 в. проблемачетырех красок также выглядит как развлекательнаязадача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое иприкладное значение. Проблема четырех красок формулируется так: ”Можно лиобласть любой плоской карты раскрасить четырьмя цветами так, чтобы любые двесоседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответутвердительный, была сформулирована в середине 19в. В 1890 году было доказаноболее слабое утверждение, а именно, что любая плоская карта раскрашивается впять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф,получают эквивалентную формулировку задачи в терминах графов: Верно ли, чтохроматическое число любого плоского графа меньше либо равно четырёх?Многочисленные попытки решения задачи оказали влияние на развитие ряданаправлений теории графов. В 1976 году анонсировано положительное решениезадачи с использованием ЭВМ.
I. Основные понятия теории графов.
1. Граф G(V,E) — комбинаторный объект,состоящий из двух конечных множеств: V — называемого множествомвершин и множества пар элементов из V, т.е. Е VxV, называемого множеством ребер, если парынеупорядочены, и множеством дуг, если парыупорядочены. В первом случае граф G(V,E) называется неориентированным, вовтором ориентированным. Если е = (v1,v2).
eЕ, то говорят, что ребро е соединяет вершиныv1,v2,если v1=v2, торебро е называется петлей. Две вершины v1,v2 называютсясмежными, если существует соединяющее их ребро. Аналогично, два различных ребра смежны, если они имеют общую вершину.
Степеньювершины vназывается число ребер d(v), инцидентных ей, при этомпетля учитывается дважды. В случае ориентированного графа различаютстепень d0(v) повыходящим дугам и d1(v) — по входящим.
Путь — это последовательностьребер e1, е2,…, еm,такая, что ei, ei+1имеют общую вершину. Число ребер называется длиной пути. Если ни однаиз вершин не появляется более одного раза, то путь называется простым. Ясно,что в простом пути ни одно ребро не используется дважды.
Путь называется циклом,если его начальная вершина совпадает с конечной, простым циклом, если это не выполняетсядля других вершин.
В случае ориентированного графа, еслипуть проходит в направлении дуг, он называется ориентированным. Аналогичноопределяется ориентированный цикл.
Граф называется связным,если для любых двух вершин существует путь, их соединяющий.Ориентированный граф называется сильно связным, если для любых двух вершинсуществует ориентированный путь, их соединяющий. Для ориентированного графаопределяем скелетный граф, как неориентированный граф, полученный снятием ориентации исходного графа.
3. Двудольные графы.Это графы, у которых множествовершин можно
разбить на два множества V1,иV2 , и так что каждое ребро графасоединяет только некоторую
вершину из V1с некоторой вершиной изV2.
4. Граф единичного n-мерного куба Вn. Вершины графа — n-мерные двоичные наборы.Ребра соединяют вершины, отличающиеся одной координатой.
Факт 1.Любой графсодержит четное число вершин нечетной степени. ♦ Если граф Gимеет xiвершин степени i, то
X1+2×2+…+kxk=2E (1)
поскольку мы подсчитываем число концевых вершин ребер, акаждое ребро имеет точно две концевые вершины. Отсюда получаем, что x1+ x3+… + x2s+1- четное число. Число ребер в графе существенновлияет на его связность. Заметим, что любой граф можно разбить на связные части- компоненты связности, задав следующее отношение эквивалентности на множестве его вершин: две вершины эквивалентны, еслисуществует путь из одной вершины в другую. Таким образом, связный графсостоит из одной компоненты.
Факт 2.Пусть G — граф с nвершинами и kкомпонентами. Тогда число mего ребер удовлетворяетнеравенствам:
Нижнююоценку доказывают индукцией по числу ребер в G. Если множество
ребер пусто, то утверждение очевидно. Если в графе Gчисло ребер минимально (скажем m0),удаление любого ребра приводит к увеличению числа компонент на единицу. Значит,в графе k+1 компонента иm0-1 ребро. По предположению индукции, m0-1n-(k+1)откуда m0> n — к. Для доказательства верхней оценки считаем каждую компоненту графа Gполным графом. Если Ciи Cj — две компоненты с niи njвершинами (ni> nj> 1), то заменяяих на полные графы с ni+ 1 и nj-1 вершинами, мы, не меняя
числа вершин,увеличиваем число ребер. Действительно,
Значит, максимальное число ребер имеет граф G, у которого k-1 изолированных вершин и компонента из полного графа на n — к + 1 вершинах. Отсюда и следуетверхняя оценка.
Следствие.Любойграф с nвершинами, имеющий более, чем
ребер, связан.
Действительно, если граф имеет kкомпонент, то по предыдущему, число егоребер не превышает
Нонеравенство:
справедливо только при к = 1.
Убедимся теперь втом, что степени вершин существенно влияют на наличие циклов в графе.
Факт 3.Если степень каждой вершины графа G(V,E) не меньше двух, то Gсодержитцикл.
Пусть v — произвольная вершина из V.Строим последовательность ребер
(v,v1), (v1,v2), …, выбирая v1смежной с v,…, Vi+1 — смежной с v1, и отличной от vi-1. По условиювершина Vi+1 существует. В силу конечности Vна некотором шаге будет выбранавершина, уже встретившаяся раньше. Пусть это vk. Тогда часть последовательности ребер между вхождениями vkобразует цикл.
2.Пусть G — связный граф, u, v — произвольные вершины. Определим d(u, v) — расстояние между uи vкак длину кратчайшего пути из uв v. При этом полагаем d(u, v) = 0 при u= v.
Ясно, что введенноетаким образом расстояние удовлетворяет аксиомам метрики:
1. d(u,v)
2. d(u, v) = 0
3. d(u,v) = d(v,u)
4. d(u, v)+d(v, w) d(u, w) (неравенство треугольника)
Для связного графа Gдиаметр d(G) определяется как`
d(G) = maxd(u,v)
3.Графы G1(V1, E1) и G2(V2, E2) называются изоморфными,если существует биекция f: V1V2, такая, что выполнено
(v1, v2)(f(v1), f(v2)2
При этом fназывается изоморфизмом графов G1и G2.Изоморфизм графа Gна себя называется автоморфизмом.
Пример 1. Следующие графыимеют только тождественные автоморфмы
Пример2. Следующий граф имеет, кроме тождественного, автоморфизмы (1,3), (2,4),(13)(24).
Широкоизвестна так называемая проблема изоморфизма графов, в которой для любых двух графов требуется установить, изоморфныони или нет. Для знакомства с результатами по данной проблеме следуетобратиться к приведенному списку литературы.
4. Поскольку графы можно рассматриватькак частные случаи бинарных отношений, то для них могутбыть определены аналогичные операции. Укажем некоторые из них.
Пусть G1+ (V1, E1), G2=(V2, E2) — два графа.
Объединение графов G1и G2есть граф, у которого V= V1 V2,
Е = E1 Е2.
Соединение графов G1+G2есть граф, у которого
V= V1 V2, Е = E1 Е2 {(v1, v2)}для всех v1V1, v2V2
Прямое произведение графовесть граф, у которого V= V1V2,
((c1,v2),(v1,v2))(v1,v1)и (v2,v2)E2
Пример.Пустьданы графы отображений f1V1Vi, f2: V2V2.Тогда пря
мое произведение соответствует отображению
f1 f2: V V2 V1 V2гдеf1 f2(v1,v2) =(f1,(v1), f2(v2))
Пусть f1 и f2 имеют и начальных вершин соответственно. Тогда f1 f2 будет
иметь
Некоторые классы графов допускаютхарактеристическое описание. В качестве примера приведем критерий двудольностиграфа (Кёниг, 1936 г.)
Теорема.Длядвудольности графа необходимо и достаточно, чтобы онне содержал циклов нечетной длины.
Пусть G= (V, Е) — двудольный граф, С — один из его циклов длины k.Фиксируем вершину v1 и проходим цикл,начиная с v1.Пусть это вершины v1, v2,…,vk. Поскольку концы каждого ребралежат в разных долях, то k — четное число.
Пусть G= (V, Е)- связный и все его циклы четной длины. Определим разбиение V= V1V2следующим образом: Фиксируем произвольную вершину v1Vивключаем ее в V1. Теперь включаем u1 d(u, v1) — четное число.Остальные вершины включаем в V2.
Покажем, что граф Gдвудольный. Пусть, напротив, существуетребро (v’, v”), где v’, v” V1. Следовательно, d(v1, v’), d(v1, v”) — четны. Ребро (v’, v”) дает цикл нечетной длины, содержащийпуть от v1к v’, ребро (v’, v”),путь от v” к v1. Аналогично показываем, что нет ребер (v’, v”), v’, v” V2.
1. Эйлеровы графы.
Эйлеровымпутемграфа G(V,E) называется путь e1,e2,…, etтакой, что каждое ребро появляется ровно 1 раз, т.е. t= | Е |. Граф G(V,E) называется эйлеровым,если он имеет замкнутый эйлеровый путь, и полуэйлеровым, если существует эйлеров путь,не являющийся замкнутым.
Теорема 1.Связный граф Gявляется эйлеровым тогда и только тогда, когда каждая вершина Gимеет четную степень.
Предположим, что Р является эйлеровым циклом в графе G. Тогда при всяком прохождении цикла черезлюбую вершину графа используется одно ребро для входа и одно ребро для выхода.Поскольку каждое ребро используется один раз, то каждая вершина должна иметьчетную степень. Обратное утверждение доказываем индукцией по числу ребер вграфе G. Пусть граф Gсвязен и степень каждойвершины четна. На основании Факта 3 граф содержит цикл C.Если Cсодержит каждое ребро, то все доказано. Если женет, то удаляем из графа Gвсе ребра, принадлежащиециклу C. Получаем новыйграф G1,возможно несвязный. Число ребер в G1меньше чем в G, и каждая вершина имеет четную степень. Поиндуктивному предположению в каждой компоненте графа dимеется эйлеров цикл. В силу связностиграфа Gкаждая компонента графа G1имеет общие вершины с циклом С. Теперь проходим, ребра графа Gследующим образом: идем по ребрам цикла С допервой неизолированной вершины графа G1. Затем проходим эйлеровцикл в компоненте графа G1, затем снова двигаемсяпо циклу С до следующей неизолированной вершины графа G1. Ясно, что процессзаканчивается в исходной вершине, что и показывает существование эйлерова цикла.
Аналогичным образом доказывается
Теорема 2.Связный граф Gявляется полуэйлеровым тогда и только тогда, когда внем существует точно две вершины нечетной степени. Аналогичное определение можносделать для ориентированных графов. Ориентированный эйлеров путь это ориентированный путь,содержащий каждую дугу точно один раз. Ориентированный граф называется эйлеровым, если в нем существует ориентированный эйлеровпуть.
Аналогично теореме 1 можно доказать следующее утверждение.
Теорема 3.Ориентированный граф G(V,E), у которого связан соответствующийскелетный граф, является Эйлеровым тогда и толькотогда, когда либо для всех вершин v, di(v) = d0(v), либо существуют точно двевершины v1и v2такие, что d0(v1) = di(v1) +1,
d0(v2) +1 = di(v2), адля остальных вершин
dI(v) = d0(v). (3)
В первом случае любой эйлеров путь является ориентированнымциклом, во втором –
начинается в вершине v1заканчивается в вершине v2
Теорема 4.Пусть G — связный граф, имеющийточно 2s> 0 вершин нечетной степени. Тогда существует sи не существует меньшего числа путей P1,…, Ps,которые в совокупностисодержат все ребра графа Gточно по одному разу.При этом каждый из путей P1,…, Psначинается в одной нечетной вершине и кончается в другой.
Согласно факта 1 вграфе Gимеется четное число 2sвершин нечетной степени. Разобьем эти вершины на sпар (v1, w1), …, (vs, ws). Образуем теперь новыйграф G1,= добавив каждой паре (vi, wi), i=1,sребро. Тогда G — связный граф, у котороговсе вершины четны. Согласно теореме 1 в графе G1существует эйлеровцикл С, проходящий по всем ребрам точно по одному разу. Удалим из цикла С добавленныеребра и получим sпутейP1,…, Ps,проходящих каждое ребро точно один раз. Ясно, что каждый путь начинается и кончается внечетной вершине. Пусть теперь имеется tпутей t
Приведем теперь алгоритм построенияэйлерового пути в данном эйлеровом графе.
Теорема 5.Пусть G — эйлеров граф. Тогда следующая процедура всегда возможна и приводит кпостроению эйлеровой цепи графа G.
Выходя из произвольнойвершины, идем по ребрам графа произвольным образом, соблюдая следующие правила:
1) стираем ребра по мере их прохождения (вместес изолированными вершинами, которые при этом образуются);
2) накаждом этапе идем по ребру, удаление которого нарушает связность, только в том случае, когданет других возможностей.
Убедимся сначала, что указанная процедураможет быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v u. Удалив ребра пути из vв u, видим,
что оставшийсяграф G1связен и содержит ровно две нечетных вершины
vи u. Согласно теореме 2 граф G1имеет эйлеров путь Р из vви. Поскольку удаление первого ребра инцидентного uпути Pлибо не нарушает связности G1,либо происходитудаление вершины uи оставшийся граф G2связен с двумя нечетнымивер-
шинами, то отсюда получаем, что описанноевыше построение всегда возможно на каждом шаге. (Если v= и, то доказательство не меняется,если имеются ребра, инцидентные u). Покажем, что даннаяпроцедура приводит к эйлерову пути. Действительно, в Gне может быть ребер, оставшихся непройденными послеиспользования последнего ребра, инцидентного u, поскольку в противномслучае удаление ребра, смежному одному из оставшихся, привело бы к несвязномуграфу, что противоречит 2). ♦
Вкачестве одного из применений эйлеровых графов приведем следующее.
Пусть А = {0, 1, …, m-1} — алфавит из mбукв. Ясно, что имеется
mn, различных слов длины nв алфавите А.Последовательностью де Брейна называется циклическое слово a0 a1…aL-1 в алфавите А, такое, что подпоследовательности вида aiai+1…ai+n-1 i= 0, …, L-1состоят из всех возможных L= mnслов длины n.Наиболее важный случай для приложений m= 2. Последовательностиде Брейна производятся полноцикловыми регистрами сдвига. Покажем существованиепоследовательностей де Брейна.
Пример.
Определим ориентированныйграф Gm,n(V,E) следующим образом
1) Vявляется множеством всех mn-1слов длины n-1 над A
2) Е является множествомвсех mnслов длины nнад A
3) дуга (a1, a2… ,an) имеет начальной вершиной (a1, … ,an-1) и конечной (an, … ,an).
Приведем граф G2,3:
Ясно, что последовательности де Брейна соответствуетзамкнутый путь в графе Gm,nсодержащий каждую дугуточно один раз. Обратно, ориентированный цикл в Gm,n, содержащийкаж