В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Это число связано с проблемой четырех красок (см. 3 59). В определенном смысле двойственной к операции стягивания ребра является операция расщепления вершины. Пусть о — одна из вершин графа С. Разобьем ее 2 г 1 1 5 Рис. 3.5 окружение произвольным образом на две части М и У и выполним следующее преобразование графа С: удалим вершияу и вместе с инцидентными ей ребрами, добавим новые вершины и и ш и соединяющее их ребро ииг, вер- 21 шину и соединим ребром с каждой вергаиной из множества М, а вершину и — с каждой вершиной из множества Х Полученный в результате граф обозначим символом с .

Будем говорить, что с получается из графа О расщеплением вершины о (рис. 3.5). й 4. Цепи, циклы, компоненты Чередующаяся последовательность О„Е1, Ог, ЕМ, е1, Шт1 (1) вершин и ребер графа, такая что е, = шо,ь1 (1=1, 1), называется маршрутом, соединяющим вершины и1 и и, (или (с1, и„.1)-маршрутом).

Очевидно, что маршрут (17 можно задать последовательностью О1, Ог ° ° ° ~ ОИ-1 (2) его вершин, а также последовательностью Е1, Ег, °, Е, ребер. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если и1 = щь1. Циклическая цепь называт 2 ется циклом, а циклическая простая цепь — простым циклом. Число 1 ребер н в маршруте (1) называется его длиной. Простой цикл длины 1 называетсн Рциклом, 3-цикл часто называют треугольником. Длина всякого цикла нн 7 менее трех, если речь идет о простом Рис.

4.1 графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом. Очевидно, что любую цепь графа можно рассматривать как его подграф. Пусть Р— некоторая цепь вида '(2) в графе С, щ и щ — входящие в нее вершины, 1(.15 Очевидно, что часть и„и;„1, ..., щ цепи Р, начинающаяся в вершине о, и заканчивающаяся в иг, сама является цепью графа С. Эта цепь называется (о„щ)-подцепью цепи Р. Обратимся, например, к графу, изображенному на рис.

4.1. В нем (1, 2) н (1, 2, 4, 7) являются простыми цепями; (1, 2, 4, 7, 8, 4) — цепь, не являющаяся простой; (1, 2, 4, 7, 8, 4, 2) — маршрут, не являющийся цепью; (1, 2, 4, 1) — простой цикл. Обхват этого графа равен 3. 22 гг« ми„=их л 'Для ориентированного графа вводится понятие ориентированного маршрута — это последовательность вида (1), в которой е, =(ог, оо»г). Аналогом цепи в этой ситуации слугкит путь (ориентироеанная цепь).

Вершина о называется достижилгой иг еерипгньг и, если :существует (и, о)-путь. Поскольку при иФ тз о пропзвольньги (и, о)-маршрут, пе являю- а„, щийся простой цепью, превращается в про:етую (и, о)-цепь после иа устранения «лишних Р . 4.2 вс. кусков», то верно У т в е р ж д е н и е 4.1. Ври и г- о всякий (и, о)-маршрут содержит простую (и, «а)-цепь. Аналогично получается У т в е р ж д е н и е 4.2.

Всякий цикл содержит ггростой цикл. Ниже окажутся полезными следующие утверждения 4.3 и 4.4. Утверждение 4.3. Объедггггение двух несоепадающих простых (и, о)-цепей содержит простой шгкл. С. Пусть Р =(иг, ..., и,) и гг =(ог, ..., о,) — несовпадающие простые цепи, иг = — ог = и, и,= о,= о, и и в„— первые, считая от и, из несовпадающих вершин этих цепей, и, и о,— первые нз совпадающих вершин, следующих после и„и о . Тогда а) 1 и объедиггеггие (и„г, .и„)-подцепи цепи Р и (о„ г, о,)-подцепи цепи гг' является простым циклом и„г, и,... и„о, г,..., о,и (рпс.

4.2). 0 Утверждение 4.4. Если С и Р— деа несоепадающих простых цикла, имеющих общее ребро е, то граф (С 0 Р) — е также содерхсит простой цикл. > Если е= ив, то С вЂ” е и Р— е — несогпадающие простые (и, о)-цепи. Поэтому нугг«псе следует из предыдущего утверждения. г Граф называется сеягныч, если любые две его несовпадающие вершины соединены маршрутом. Учитывая утверждение 4.1, можно в этом определении заменить маршрут цепью или простой цепью.

2$ Очевидно следующее Утверждение 4.5. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины и и каждой другой вершины и существовал (и, о)-маршрут. Всякий максимальный связный подграф графа С называется связной компонентой (или просто компонентой) графа С. Слово вмаксимальпыйз означает максимальный относительно включения, т.

е. пе содержащийся в связном подграфе с болыпим числом элементов. Множество вершин связной компоненты называется областью связности графа. Т е о р е и а 4.8, Каждый граф представляется в виде дпгъюнктного объединения своих связных колтонент. Разложение графа на связные компоненты определено однозначно. Пусть С вЂ” произвольный граф. На множестве т'С определим бинарное отношение —, положив и — о длявершип и и о, если и =- и илн в графе С существует. (и, и)-маршрут. Очевидно, что это отношение есть эквивалентность.

Следовательно, мы получим разбиопие множества УС на классы, отнеся в оди~ класс все вершины, эквивалентные друг другу. Пусть )'С = () Уь— такое разбиение. Очевидно, что порожденные подграфы С; = 6()т;) и только опи являются компонентами графа С и С= ()Сг — дизыопктпое объединение. <1 Полезно следующее Утверждение 47. Для любого графа либо он сам, либо его дополнение является связным. ~> Пусть С вЂ” несвязный граф, А — одна из его областей связности, В = )гС~А.

Тогда для любых а из А и Ь из В в дополнительном графе 6 есть реоро аЬ. Следовательно, произвольная вершина нз В соединена с а маршрутом длины 1, а произвольная вершина из А (отличная от а) соединеяа с а маршрутом длины не более чем 2. Теперь из утверждения 4.5 вытекает, что связен. <3 С помощью предыдущего утверждения некоторые проблемы (например, проблема изоморфизма) сводятся.

к случаю связных графов. Полезна также и следующая Лемма 4.8. Пусть С вЂ” связный граф, е аз ЕС. Тогда:. 1) если ребро е принадлежит какому-либо циклу графа С, то граф С вЂ” е свявен; 24 2) если ребро е не входит ни в какой цикл, то граф С вЂ” е имеет ровно две компонентьь 1) Пусть ребро е=ио принадлежит циклу С графа 6. Заменив в каждой (х, у)-цепи, содержапьей е, подцепь (и, е, о) (и, о)-цепью С вЂ” е, получим (х, у)-маршрут, не содержащий ребра е. Следовательно, в графе 6 любые две несовпадающие верьпины соединены маршрутом, не проходящим через е. Но тогда и граф 6 — е связеьь.

2) Пусть ребро е=ио не входит ни в какой цикл графа С. Тогда, очевидно, вершины и и о принадлежат разным компонентам, например, 6 и соответственно С„, графа 6 — е. Для произвольной вершины хчь и в 6 существует (х, и)-маршрут. Если ребро е в этот маршрут не входит, х ш 6„. В противном случае х ~ 6„. З Ниже число ребер и число компонент графа 6 обозначаются через пь(6) и й(6) соответственно. Очевидно, что число ребер в произвольном графе по/охх рядка и не больше числа ребер в К„, равного ( ) Но сколько ребер может быть в графе порядка и с фиксированным числом й компонент? На этот вопрос отвечает следующая Т е о р е м а 4.9. Если й(С) = й для и-вершинного графа С, то и — й < т(6) ~ (п — й) (и — й + 1) ь2, (З) причем обе гти оценки для т(6) достихсььмы. > Вначале рассмотрим верхнюю оценку. Пусть 6— граф порядка и с к компонентами и максимальным для таких графов числом ребер.

Тогда каждая его компонента ивляется полным графом. Пусть, далее, К, и К,— две компоненты, р ) д ) 1, о — вершина из второй компоненты. Удалив из графа все ребра, инцидентные вершипе о, и соединив о ребром с каждой вершиной из первой компоненты, получим новый граф порядка п с тем же числом компонент и большим числом ребер. Последнее невозможно, стало быть, только одна из компонент может иметь порядок, болыпий 1. Он равен и — й+1, и потому (и — ьь+ 1'ь (о — /ь) (и — л+ ь) 2 ! 2 Справедливость верхней оценки (3) и ее достижимость доказаны. 25 Перейдем к доказательству неравенства т(6) > и — кх Опо очевидно при п»(6)= О, так как тогда й = и. Воспользуемся индукцией по тп(6).

Пусть т(С)> О и пуст для графов с меньшим, чем кп(6), числом робер соответствующее неравенство верно. Рассмотрим граф С— — е, где е е ЕС. Согласно лемме 4.8 число компопентэтого графа равно й или у+ 1. Число ребер в нем равно тп(6) — 1. По индуктивному предположению в обоих случаях т(6) — 1 > и — й — 1. Следовательно, т(6)> и — й, Нужное неравенство доказано. Дизъюпктное объединение С = О, 1 0 К,,»1 реализует равенство т(С) = и — й.

Характеристики

Список файлов лекций