В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 31
Текст из файла (страница 31)
Двойственность и планарпость Целью этого параграфа является получение еще одного критерия планарности графа, основанного на понятии двойственности. Условимся, что всюду в этом параграфе слово «граф» означает «псевдограф». Кроме того, видоизменим здесь использованную выше (см.
4 3) операцию стягивания ребра е = изшЕ6, под которой теперь будем понимать удаление ребра е н отождествление вершин и и и в новую вершину, ипцидентную тем ребрам графа 6, которые были пнцидентны вершинам и н о, за исключением ребра е (рис. 40.1). Том самым теперь появляющиеся при стягивании ребра кратные ребра не отождествляются, как ранее. Для плоского графа 6 построим новый плоский граф 6*, который назовем геометрически двойственным к 6.
Для этого внутри каждой грани Г, графа 6 выберем по одной точке ь,'. Эти точки — вершины будущего графа 6*. Далее, каждому ребру е ш Е6 поставим в соответствие жордапову кривую е*, которая перосекает лишь одно реоро е графа 6 н соединяет вершины о;, лозкащие в гра- 169 нях, границы которых содернсат ребро е (таких граней молсет быть две или одна). Кривые е* — ребра графа 6*. Очевидно, что ребра графа 6* можно провести так, чтобы они не керосекалпсь. На рвс. 40.2 сплошной линией изображон граф 6, а пунктирной — граф 6~. Заметим, что потлсо в 6г порождает всякий мост в 6, а кратные Рвс. 40Л ребра появлясотся в 6* тогда и только тогда, когда две грани графа 6 имеют более одного общего ребра. Из этого построения очевидно, что граф 6г, геометрически двойственный к плоскому графу 6, определяется однозначно с точностью до изоморфизма, причем граф 6* Рис.
40.2 всегда связеп. Последнее утверждение летке доказать индукцией по числу вершин графа 6* (т. е, по чссслу граней графа 6) путем стягивания ребра ег графа 6*, что, очевидно, соответствует удаленисо ребра е в графе 6. При этом, если ребро е — граница двух граней, то упомянутые операции приводят к уменьшению числа вершин графа 6г (числа граней графа 6) на единицу.
Применяя формулу Эйлера, легко получить Утверждение 40.1. Ьели 6 — плоский связный (и, т)-граф с 1 гранями, а 6* — (и", т")-граф, геометрически двойетеессссый к ссему, е )* граиялси, то и* = ~, т* = и, 1* = и. Поскольку граф 6* — плосшш, то можно построить граф, геометрически двойствопный к 6*, который естест- 170 ванно обозначить через С**. Связь между графами С и С*в устанавливает следующая теорема. Теорема 40.2. Нели С вЂ” плоский связный зраф, то граф С** изоморфен графу С, > Из утвернсдепия 40.1 следует, что и**= )з=п, где и** = 16**!.
Следовательно, каждая грань графа Се содерлсит одну вершину графа С (С*а). 1(оэтому построение, при помощи которого граф С* получен из С, можно обратить, т, о. получить С из Се. <1 Граф, двойственный к плапарпому графу, определяется следующим образом: рассмотрим любусо укладку этого графа п построим геометрически двойственный граф. Здесь уместно отметить, что планарный граф, допускающий песколько укладок на плоскости, может иметь по изоморфпые двойственные графы (см. упр. 25). Т е о р е и а 40.3.
Пусть С вЂ” планарный граф, С*— граф, гео»сетрически двойетвесшый к С. Под»шоэсество ребер из С образует простой цикл в С тогда и только тогда, когда соответствующее мпоаеество ребер из Сь образует разрез в Сь. Дли доказательства этой теоремы потребуется одна очевидная лемма. Д е и м а 40.4.
Пусть Н вЂ” связный граф, мнозкество Ь'Н вершин которого разбито на два под»снолсества Ус и Уг, Мноокеетво ребер ЛХ((тн Иг)=(е= огпг сн ЕН: о1~ (тн о»ж т'г) является разрезом тогда и только говда, ковда графы ХХЯ1) и Н((тг) связны. ~> Доказательство теоремы 403. Не исключая общности, будем считать, что С вЂ” плоский граф. Пусть С вЂ” простой цикл в С. Тогда оп ограничивает одну или несколько внутренних граней графа С, т. е. ограничивает часть плоскости, содержащую непустое множество Ит вершин графа 6*. Поэтому ребра из Сг, пересекающие ребра цикла С, образуют мполсество М в С"', удаление которого разделяет связный граф С* па два подграфа с мпоисествами вершин И" п т'С*'сИ' (рис.
40.3). Ипдукцией по числу вершин легко доказать связность каждого нз этих подграфов. Следовательно, па осповапии леммы 40.4 ЛХ вЂ” разрез в графе Се. Путем обращения приведенного вьппе рассуждения доказывается обратное утверждение о том, что разрезу в Се соответствует простой цикл в С. с 171 Теорема 40.3 естественным образом приводит к следующему комбипаторному определению двойственности графов, котороо обобщает геометрическую двойственность и позволяет сформулировать еще одпп критерий пчапарпостя графов. Граф Св называется абстрактно двойственным к графу С, если между множествами ЕС и КСв существует биекцпя, обладающая тем свойством, что подмножество ребер из С образует простой цикл в С тогда и только тогда, когда соответствующео ~:т ему подмножество ребер из Св об— разует разрез в С".
На рнс. 40.4 изображены граф и абстрактно двойственный к нему граф. Соответствующие ребра обозначены одной и той же буквой. Другой пример графов 6 и С* приведен па рпс. 40.5. Попятив абстрактной двойственности обобщает попятие геометрической двойственности, так как согласно теореме 40.3 справедливо Утверждение 40.5. Граф, геометрически двойственный к плоскому графу, является абстрактно двойственным к нел1у. Непосредственно из определения вытекает следующее утверждение. Утвернгдеппе 40.6.
Граф ХХ является абстрактно двойственным к графу С тогда и только тогда, когда ма- Рвс. 40.4 троид ЛХ(6) циклов графа С изоморфен матроиду ЛХ"(Е1) разрезов графа ХХ. Теорема 40.7. Если граф Св — абстрактно двойственный к С, то С вЂ” граф, абстракжго двойственпый к С". Отметим, что здесь, в отличие от теоремы 40.2, пе требуется связность графа С. 172 > На основании утверждения 40.6 матроид М(6) изоморфеп матроиду Мв(6*). Поэтому в силу следствия 20.2 матроиды М*(6) и М**(6*) также изоморфпы. Но М**(6*) = М(6*). Следовательно, матроид М(6*) циклов графа Се изоморфен матроиду М*(6) разрезов гра- ев ег Рис, 40.5 фа 6, т. е.
на основании утверждения 40.6 граф С является абстрактно двойственным к С*. < Таким образом, учитывая теорему 40.7, графы С и 6* можно называть двойственными. На вопрос о том, каждый ли подграф графа, имеющего двойствешгый граф, обладает двойственным графом, отвечает Теорема 40.8. Пусть С и 6* — двойственные графы, е = стивен ЕС, е* = огог — соответствующее реоро графа 6*.
Если Н вЂ” граф, полученный ив графа 6 удалением ребра е, а Р— граф, полученный стягиванием ребра ев в 6*, то Н и Р— двойственные графы, причем биекуия между множествами ЕН и ЕР остается такой лсе, как и мелсду ЕС и ЕС". с' Любой простой цикл С графа Н= 6 — е является простым циклом и в графе С. Поэтому соответствующее мпон<ество ребер Св — разрез в 6*, разделяющий мнов в жество веРшин 1'С на два множества Рг и Уг. По- з в скольку е ФС~, то вершины о„н о, находятся одновременно либо в У„либо в У,.
Поэтому С* — разрез н в Р. Итак, каждому простому циклу графа Н соответствует разрез графа Р. Пусть теперь С* — разрез в Р, Так как в*ФСв, го Св — разрез и в 6*. Поэтому С вЂ” простой цикл графа С. Поскольку еФС, то С вЂ” простой цикл и в П. Следовательно, всякому разрезу в Р соответствует простой цикл в Н. 'э Принимая во внимание, что всякий подграф Н графа 6 можно получить иэ 6 удалением ребер, не принадлежащих подграфу Н, из теоремы 40.8 выводим 173 Следствие 40.9, Если граф имеет абстрактно двойственньчй граф, то всякий его подграф также имеет абстрактно двойственный граф.
Поскольку на основании теоремы 40.7 двум ребрам графа С, ипцндептпым всрп>ине степени 2 (т. е. разрезу, отделяющему эту вершину), соответствуют два кратных ребра (2-ци>чл) графа С*, то получаем еще одно следствие теоремы 40.8. Следствие 40ЛО. Если граф С имеет абстракпчо двойственный граф, то л>обой граф, голчеолсорфччый графу С, таклсе имеет абстрактно двойственный. Т е о р е и а 40.11, Всякий плапарпый граф ил<ест абстракт>>о двойственный к себе граф, 3> Для доказательства достаточно рассмотреть любую плоскую укладку С исходного плапарпого графа и граф С*, геометрически двойственный к 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
