Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 21
Текст из файла (страница 21)
В дальнейшем (см. 5 4.4) в связи с проблемой изоморфизма графов будет дано другое определение произведения графов, точнее, их квадратов. Прямые произведения графов. Пусть даны графы 61 и 6з с множествами вершин )г, и )гз. У прямого произведения этих графов с=6,Х6з множеством вершин является прямое произведение )1=)г,)()гз. Ребра произведения могут быть определены различными способами. 104 При одном из определений в произведении Е графов 6, и 6з ребро (о,', о',), (а<', о,") имеется тогда, когда в графе 6< есть ребро (оь о>) или в графе 6з — (и>, оз), В другом определении для этого требуется существование обоих этих ребер.
В первом случае элементы матрицы смежности определяются формулой б«„<,><;,л,> = бпь '/ б<,<„во втором б«„,<,>ц,,>ч>=б<н, б<,>, Таким образом, в обоих случаях матрица смежности произведения является кронеккеровским произведением матриц смежности сомножителей, но в первом случае произведение элементов матрицы понимается как логическая сумма </ (или), а во втором — как логическое (и обычное) произведение (и). Чаще всего используется третье определение, согласно которому ребро (о'„о,'), (о>', в.",) существует в тех и только тех случаях, когда в графах 6, и 6, есть соответственно ребра (о,, о,) и (о„ о>) или о,=о>, а в графе 6, есть ребро (о,, о>) или, наконец, в графе 6, есть ребро (о„ о>), а о," = и",.
Пусть Л'=Е<</Л, где Š— единичная матрица, а Л вЂ” матрица смежности рассматриваемого графа: б' = (бы и Тогда матрица смежности прямого произведения графов 6> и 6з при таком определении равна Л<"> = Л <щ>х Х Л <в'> — Е<а'> >< Е<в'> б;, б,', <<+1< или <, чь уз; ню » (Ыз> 0, >>=1< и Аналогично определяются прямые произведения любого множества графов. Задача о кенигсбергских мостах. Постановка и решение этой задачи Эйлером знаменует начало разработки теории графов. Расположение мостов в г. Кенигсберге в его время приведено на рис.
4.10, а. Требуется пройти каждый мост по одному разу и вернуться в исходную часть города. Можно построить граф задачи, в котором каждой части города соответствует вершина, а каждому мосту — ребро, инцидентное вершинам, относящимся к соединяемым им частям (этот граф изображен на рис. 4.10, б). Попробуем каким-либо способом обойти мосты. После того как мы пройдем какой-нибудь из них, нужно будет ид- 105 4 3 г а а! в Риа вид стали называть эйлеровыми, а графы, имеющие эйлеровы циклы, — эйлеровылш графами. Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы — это такие графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и кончается в одной и той же точке.
Условия, при которых граф эйлеров. Теорема 4.1 (Эйлера), Конечный неориентированный граф 6 эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны. Необходимость этих условий доказать легко, В несвязном графе каждый цикл принадлежит какой-либо его связной части, т, е. не проходит через все его ребра (кроме случая, когда все компоненты связности графа, кроме одной, — изолированные вершины). Кроме того, каждый раз, когда эйлеров цикл приходит в какую-нибудь вершину, он должен выйти из нее по другому ребру, т. е.
инцидентные вершинам ребра можно разбить на пары соседних в эйлеровом цикле. Исключением являются ребра, инцидентные началу эйлерова цикла, совпадающему с его концом. Сначала цикл выходит из этой вершины по какому-либо ребру. Затем он, возможно, несколько раз возвращается в эту 106 ти по мосту, связывающему часть города, в которую мы попали, с некоторой другой частью, Следовательно, обходу мостов соответствует последовательность ребер графа задачи, в которой два соседних ребра имеют общую вершину, т. е.
маршрут. Так как в конце обхода нужно вернуться в исходную часть города и па каждом мосту нужно побывать по одному разу, этот маршрут является простым циклом, содержащим все ребра графа. В дальнейшем такие циклы с вершину, каждый раз входя по новому ребру и выходя также по новому, но другому ребру. В конце концов он возвращается в исходную вершину по не затронутому ранее ребру. Таким образом, и в этом случае инцидентные этой вершине ребра также распадаются на пары соседних в эйлеровом цикле, но одна из этих пар состоит из ребра, проходимого в начале процесса, и другого, замыкающего этот процесс. Теперь нужно доказать достаточность этих условий.
Пусть 6 — конечный связный неориентированный граф с четными степенями всех вершин, Начнем построение эйлерова цикла с произвольной вершины о графа 6. Каждый раз, когда мы добавляем к маршруту новое ребро и приходим в новую вершину, число свободных ребер в этой вершине изменяется на единицу. Если до этого оно было четным, то теперь оно становится нечетным и не может оказаться нулем После ухода из этой вершины число свободных инцидентных ей ребер уменьшается еще на единицу и вновь становится четным.
Исключением является исходная вершина, у которой после начала процесса число свободных ребер нечетно и остается нечетным после каждого возвращения в эту вершину и ухода из нее. Описанный ранее процесс построения цикла может закончиться лишь в той вершине, откуда он начинался, но при этом не обязательно, чтобы он проходил через все ребра графа. Принадлежащие ему ребра порождают связную часть Р графа 6, в которой степени всех вершин четны.
Значит, они четны и для разности 6',Р. Так как граф 6 связен, в дополнении 6' Р существует хотя бы одна вершина о', принадлежащая также части Р. Начиная с этой вершины, можно провести, как и ранее, построение цикла Р в 6',Р, кончающегося также в вершине о'. Эта вершина, кроме того, разбивает цикл Р на два участка: Р, с началом э и концом о' и Р, с началом о' н концом п. Тогда РйР'ЦР~ — также цикл, начинающийся и кончающийся в вершине э, но имеющий большее число ребер. Если и этот цикл не проходит через все ребра, этот процесс расширения цикла можно повторить. Каждый раз число ребер в цикле увеличивается не менее чем на два, значит, в конце концов эйлеров цикл будет построен.
П В графе задачи о Кенигсбергских мостах (рис. 4.10) все вершины имеют нечетную степень, Следовательно, ее решение невозможно. Эйлеровы цепи. Так называется цепь, включающая все ребра данного конечного неориентированного графа 6, но 107 имеющая различные начало и' и конец с". Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность степеней всех вершин, кроме начальной и' и конечной и". Последние две вершины должны иметь нечетные степени: из и' мы лишний раз выходим, а в о" лишний раз входим.
Эти условия достаточны для существования эйлеровой цепи, Доказательство — то же самое, как и для условий, достаточных для существования эйлерова цикла. Можно искать наименьшее число не пересекающихся по ребрам цепей, покрывающих конечный связный граф 6. Пусть 6 не является эйлеровым графом, л — число его вершин нечетной степени.
Ранее было доказано, что й— четно. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих цепей. Следовательно, число последних не меньше, чем А/2. Но ограничиться А/2 цепями не так трудно. Соединим вершины нечетной степени попарно й/2 ребрами произвольным образом. Тогда степень каждой из этих вершин увеличится на единицу и станет четной.
Получится эйлеров граф, в котором существует эйлеров цикл. Выбросим теперь обратно присоединенные ребра. При выбрасывании первого ребра эйлеров цикл превратится в эйлерову цепь, а при выбрасывании каждой следующей цепи одна из возникших к этому моменту цепей разобьется на две части. Таким образом, общее число этих цепей станет равно А/2, (Заметим, что при построении никогда не выбрасываются соседние по эйлерову циклу ребра.) Случай конечного ориентированного графа. Чтобы в конечном ориентированном графе б существовал эйлеров цикл, необходимо и достаточно равенство степеней вершин этого графа по входящим и выходящим ребрам: у вен б (р, (и) = рз (о) ) .
Доказательство буквально тоже, что и для неориентированного графа, только вместо определения четности числа оставшихся свободных ребер показывается, что в процессе построения эйлерова цикла для всех вершин, кроме исходной для построения очередного подцикла, сохраняется баланс между количествами свободнь|х (еще не пройденных) входящих и выходящих ребер. Так как любому неориентированному графу канонически соответствует ориентированный, в котором каждое ребро заменено двумя ребрами, инцидентными тем же вершинам и идущими в противоположном направлении (причем у этого графа для каждой вершины степени по входящим и выходящим вершинам равны степени этой вершины 108 в исходном неориентированном графе, а значит, и между собой), то отсюда следует справедливость утверждения: в конечном связном графе всегда можно построить ориентированньчй цикл, проходящий через каждое ребро по одному разу в каждом из двух направлений.
Такой цикл иногда называют способом обхода всех ребер графа. Он используется во многих прикладных задачах, связанных с графами. Гамильтоновым циклом называется простой цикл, проходящий через все вершины рассматриваемого графа. Такой цикл существует да- в леко не во всяком графе. Более того, через любые две вершины рассматриваемого графа может А ь" проходить простой цикл а) 41 (в этом случае граф Ст называется циклически связным), а гамильтонов цикл при этом может отсутствовать. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
