Графы и алгоритмы

Важнейшие классы графов

Показывать лекцию целиком

Деревья

Деревом называется связный граф, не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом.

Из теоремы 2 предыдущей лекции следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами, или листьями. В действительности легко доказать, что в каждом дереве не меньше двух листьев, а цепь $$P_{n}$$ - пример дерева, в котором точно два листа.

В следующих двух теоремах устанавливаются некоторые свойства деревьев.

Теорема 1. Граф с $$n$$ вершинами и $$m$$ ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:

  • (1) связен;
  • (2) не имеет циклов;
  • (3) $$m=n-1$$.
    •

    Доказательство.

    Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего.

    (1) и (2) $$\Rightarrow$$ (3). Индукция по числу вершин. При $$n=1$$ утверждение очевидно. При $$n\ge 2$$ в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве $$n-1$$ вершин и, по предположению индукции, $$n-2$$ ребра. Следовательно, в исходном дереве было $$n-1$$ ребро.

    (2) и (3) $$\Rightarrow$$ (1). Пусть в графе, не имеющем циклов, $$n-1$$ ребро, а его компонентами связности являются $$G_{1} ,G_{2}\ldots G_{k}$$, причем $$G_{i}$$ состоит из $$n_{i}$$ вершин, $$i=1\ldots k$$. Каждая компонента является деревом, поэтому, как доказано выше, число ребер в $$G_{i}$$ равно $$n_{i} -1$$, а всего ребер в графе $$\suml_{i=1}^{k}\left(n_{i} -1\right) =n-k=n-1$$. Значит, $$k=1$$ и граф связен.

    (1) и (3) $$\Rightarrow$$ (2). Рассмотрим связный граф с $$n-1$$ ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем $$n-1$$, а это противоречит доказанному выше.

    Теорема 2. Если $$G$$ - дерево, то

  • в $$G$$ любая пара вершин соединена единственным путем;
  • при добавлении к $$G$$ любого нового ребра образуется цикл;
  • при удалении из $$G$$ любого ребра он превращается в несвязный граф.
    •

    Доказательство.

    Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины $$a$$ и $$b$$. Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине $$a$$ ). Пусть $$x$$ - последняя вершина этого совпадающего начала, а после $$x$$ в одном пути следует вершина $$y_{1}$$, а в другом - вершина $$y_{2}$$. Рассмотрим ребро $$\left(x,y_{1}\right)$$. Если его удалить из графа, то в оставшемся подграфе вершины $$y_{1}$$ и $$x$$ будут соединимыми - соединяющий их маршрут можно построить так: взять отрезок первого пути от $$y_{1}$$ до $$a$$ и к нему присоединить отрезок второго от $$x$$ до $$a$$, взятый в обратном порядке. Но это означает, что ребро $$\left(x,y_{1}\right)$$ не является перешейком. Однако из теоремы 4 предыдущей лекции следует, что в дереве каждое ребро является перешейком. Этим доказано утверждение 1). Утверждения 2) и 3) следуют из 1).

    Отметим, что единственный путь, соединяющий две вершины дерева, всегда простой (если путь не является простым, в нем обязательно содержится цикл).

    Центр дерева

    Центр графа может состоять из одной вершины (как, например, в графе $$K_{1,q}$$ ), а может включать все его вершины (полный граф). Для дерева, как мы увидим, имеется гораздо более узкий диапазон возможностей.

    Теорема 3. Центр дерева состоит из одной вершины или из двух смежных вершин.

    Доказательство.

    Допустим, что в некотором дереве имеются две несмежные центральные вершины $$c_{1}$$ и $$c_{2}$$. На пути, соединяющем эти вершины, найдем промежуточную вершину $$a$$ с максимальным эксцентриситетом, и пусть $$b_{1}$$ и $$b_{2}$$ - вершины, соседние с $$a$$ на этом пути (см. рис. 3.1). Пусть $$x$$ - вершина, наиболее удаленная от $$a$$ в дереве, т.е. $$d(a,x)=ecc(a)$$. Путь, соединяющий $$a$$ с $$x$$, не может проходить через обе вершины $$b_{1}$$ и $$b_{2}$$. Допустим, он не проходит через $$b_{1}$$. Тогда единственный путь из $$b_{1}$$ в $$x$$ проходит через $$a$$ и $$d(b_{1},x) \gt d(a,x)$$. Отсюда следует, что $$ecc(b_{1} ) \gt ecc(a)$$, а это противоречит выбору вершины $$a$$, если $$b_{1} \ne c_{1}$$, или тому, что $$c_{1}$$ - центральная вершина, если $$b_{1} =c_{1}$$.

    Следовательно, любые две центральные вершины смежны, а так как в дереве не может быть трех попарно смежных вершин, то в нем не больше двух центральных вершин.

    (рис 3.1)

    Корневые деревья

    Часто в дереве особо выделяется одна вершина, играющая роль своего рода "начала отсчета". Дерево с выделенной вершиной называют корневым деревом, а саму эту вершину - корнем. Из дерева с $$n$$ вершинами можно, таким образом, образовать $$n$$ различных корневых деревьев.

    При графическом изображении корневого дерева обычно придерживаются какого-нибудь стандарта. Один из наиболее распространенных состоит в следующем. Возьмем на плоскости семейство параллельных прямых с равными расстояниями между соседними прямыми. Изобразим корень точкой на одной из этих прямых, смежные с корнем вершины - точками на соседней прямой, вершины, находящиеся на расстоянии 2 от корня, - на следующей, и т.д. Ребра изобразим отрезками прямых. Ясно, что вершины на каждой прямой можно разместить так, чтобы ребра не пересекались. Пример нарисованного таким образом корневого дерева показан на рис. 3.2 (корень обведен кружком). Чаще, впрочем, дерево рисуют корнем вверх, а не вниз.

    (рис 3.2)

    Иногда бывает полезно ребра корневого дерева ориентировать так, чтобы в каждую вершину вел ориентированный путь из корня (для дерева на рис. 3.2 это означает, что каждое ребро ориентируется снизу вверх). Такое ориентированное корневое дерево будем называть исходящим деревом. В исходящем дереве каждая вершина, кроме корня, является концом единственного ребра. Если в исходящем дереве имеется ребро $$xy$$, то вершину $$x$$ называют отцом вершины $$y$$, а вершину $$y$$ - сыном вершины $$x$$. Естественный и для многих целей удобный способ задания корневого дерева состоит в указании для каждой вершины ее отца. При этом иногда считают, что корень приходится отцом самому себе - это равносильно добавлению петли при корне.

    Если в исходящем дереве $$T$$ имеется ориентированный путь из вершины $$x$$ в вершину $$y$$, то говорят, что $$x$$ - предок $$y$$, а $$y$$ - потомок $$x$$. В частности, каждая вершина является предком и потомком самой себя. Множество всех предков вершины $$x$$ порождает ориентированный путь из корня в $$x$$. Множество всех потомков вершины $$x$$ порождает исходящее дерево с корнем в $$x$$, оно называется ветвью дерева $$T$$ в вершине $$x$$.

    Высотой корневого дерева называется эксцентриситет его корня. Если мы хотим превратить некоторое дерево в корневое и притом минимальной высоты, то в качестве корня следует взять центральную вершину.

    Каркасы

    Пусть $$G$$ - обыкновенный граф. Его каркасом называется остовный подграф, в котором нет циклов, а области связности совпадают с областями связности графа $$G$$. Таким образом, каркас связного графа - дерево, а в общем случае - лес.

    У любого графа есть хотя бы один каркас. Действительно, если в $$G$$ нет циклов, то он сам является собственным каркасом. Если же циклы есть, то можно удалить из графа любое ребро, принадлежащее какому-нибудь циклу. Такое ребро не является перешейком, поэтому при его удалении области связности не изменятся. Продолжая действовать таким образом, после удаления некоторого количества ребер получим остовный подграф, в котором циклов уже нет, а области связности - те же, что у исходного графа, то есть этот подграф и будет каркасом. Можно даже точно сказать, сколько ребер необходимо удалить для получения каркаса. Если в графе $$n$$ вершин, $$m$$ ребер и $$k$$ компонент связности, то в каркасе будет тоже $$n$$ вершин и $$k$$ компонент связности. Но в любом лесе с $$n$$ вершинами и $$k$$ компонентами связности имеется ровно $$n-k$$ ребер. Значит, удалено будет $$m-n+k$$ ребер. Это число называется цикломатическим числом графа и обозначается через $$\nu (G)$$.

    Если в графе есть циклы, то у него больше одного каркаса. Определить точное число каркасов связного графа позволяет так называемая матричная теорема Кирхгофа. Приведем ее без доказательства. Для графа $$G$$ определим матрицу $$K(G)$$ - квадратную матрицу порядка $$n$$ с элементами

    $$K_{ij} =\left\{\begin{aligned} -1, \text{если }(i,j)\in EG, \\ 0, \text {если }(i,j)\notin EG \t{ и } i\ne j,\\ \deg (i), \text {если } i=j. \end{aligned} \right}$$

    Иначе говоря, $$K(G)$$ получается из матрицы смежности, если заменить все $$1$$ на $$-1$$, а вместо нулей на главной диагонали поставить степени вершин. Заметим, что матрица $$K(G)$$ - вырожденная, так как сумма элементов каждой строки равна $$0$$, то есть столбцы линейно зависимы.

    Теорема 4 (матричная теорема Кирхгофа). Если $$G$$ - связный граф с не менее чем двумя вершинами, то алгебраические дополнения всех элементов матрицы $$K(G)$$ равны между собой и равны числу каркасов графа $$G$$.

    Двудольные графы

    Граф называется двудольным, если множество его вершин можно так разбить на два подмножества, чтобы концы каждого ребра принадлежали разным подмножествам. Эти подмножества называются долями. Таким образом, каждая из долей порождает пустой подграф. Примером двудольного графа является простая цепь $$P_{n}$$ при любом $$n$$: одна доля порождается вершинами с четными номерами, другая - с нечетными. Граф $$K_{3}$$ - пример графа, не являющегося двудольным: при любом разбиении множества его вершин на два подмножества в одном из этих подмножеств окажутся две смежных вершины.

    Прикладное значение понятия двудольного графа связано с тем, что с помощью таких графов моделируются отношения между объектами двух типов, а такие отношения часто встречаются на практике (например, отношение "продукт $$x$$ используется в производстве изделия $$y$$ " между исходными продуктами и готовыми изделиями, или "работник $$x$$ владеет профессией $$y$$ " между работниками и профессиями). В математике такие отношения тоже нередки, один из наиболее распространенных их видов - отношения инцидентности. Пусть $$A$$ - множество, а $$B$$ - семейство его подмножеств. Элемент $$x\in A$$ и множество $$X\in B$$ инцидентны друг другу, если $$x\in X$$. Отношение инцидентности можно описать с помощью двудольного графа $$G$$, в котором $$VG=A\cup B$$, $$EG=\{(x,X)|{x\in A}, X\in B, x\in X\}$$. На рис. 3.3 показан граф отношения инцидентности для $$A=\{a,b,c\}$$, $$B=\{B_{1},B_{2},B_{3},B_{4}\}$$, где $$B_{1}=\{a\}$$, $$B_{2} =\{a,b,c\}$$, $$B_{3} =\{b,c\}$$, $$B_{4} = \varnothing$$.

    (рис 3.3)

    Вообще говоря, разбиение множества вершин двудольного графа на доли можно осуществить не единственным способом. Так, в графе из только что приведенного примера можно взять в качестве долей множества $$\{a,b,c,B_{4}\}$$ и $$\{B_{1},B_{2},B_{3}\}$$. В то же время в самом определении этого графа уже заложено "естественное" разбиение на доли $$A$$ и $$B$$. Двудольные графы, возникающие в приложениях, нередко бывают заданы именно так - с множеством вершин, изначально состоящим из двух частей, и с множеством ребер, каждое из которых соединяет вершины из разных частей.

    Если разбиение на доли не задано, то может возникнуть вопрос, существует ли оно вообще, т.е. является ли данный граф двудольным? Если в графе $$n$$ вершин, то имеется $$2^{n-1}$$ разбиений множества вершин на два подмножества и непосредственная проверка всех этих разбиений будет очень трудоемким делом. Следующая теорема дает критерий двудольности, а из ее доказательства можно извлечь и эффективный алгоритм проверки двудольности. Подробно такой алгоритм будет описан в следующей лекции.

    Теорема 5. Следующие утверждения для графа $$G$$ равносильны:

  • (1) $$G$$ - двудольный граф;
  • (2) в $$G$$ нет циклов нечетной длины;
  • (3) в $$G$$ нет простых циклов нечетной длины.
    •

    Доказательство.

    Докажем, что из (1) следует (2). Пусть $$G$$ - двудольный граф, в котором выбрано некоторое разбиение на доли, $$C=x_{1},x_{2}\ldots x_{k},x_{1}$$ - цикл длины $$k$$ в графе $$G$$. При любом $$i=1\ldots k-1$$ вершины $$x_{i}$$ и $$x_{i+1}$$ смежны и, следовательно, принадлежат разным долям. Таким образом, одна доля состоит из всех вершин с нечетными индексами, т.е. $$x_{1},x_{3},\ldots$$, другая - из всех вершин с четными индексами. Но вершины $$x_{k}$$ и $$x_{1}$$ тоже смежны и должны принадлежать разным долям. Следовательно, $$k$$ - четное число.

    Очевидно, что из (2) следует (3); остается доказать, что из (3) следует (1). Рассмотрим граф $$G$$, в котором нет простых циклов нечетной длины. Ясно, что граф, в котором каждая компонента связности - двудольный граф, сам двудольный. Поэтому можно считать, что граф $$G$$ связен. Зафиксируем в нем некоторую вершину $$a$$ и докажем, что для любых двух смежных между собой вершин $$x$$ и $$y$$ имеет место равенство $$|d(a,x)-d(a,y)|=1$$. Действительно, допустим сначала, что $$d(a,x)=d(a,y)=t$$. Пусть $$x_{1},x_{2}\ldots x_{t}$$ - кратчайший путь из $$a$$ в $$x, y_{1},y_{2}\ldots y_{t}$$ - кратчайший путь из $$a$$ в $$y$$. Эти пути начинаются в одной вершине: $$x_{1} = y_{1} = a$$, а оканчиваются в разных: $$x_{t}=x$$, $$y_{t} =y$$. Поэтому найдется такое $$k$$, что $$x_{k}=y_{k}$$ и $$x_{i} \ne y_{i}$$ при всех $$i\gt k$$. Но тогда последовательность $$x_{k},x_{k+1} \ldots x_{t},y_{t}\ldots y_{k+1},y_{k}$$ является простым циклом длины $$2(t-k)+1$$. Следовательно, $$d(a,x)\ne d(a,y)$$. Предположим, что $$d(a,x)< d(a,y)$$. Если $$x_{1},x_{2}\ldots x_{t}$$ - кратчайший путь из $$a$$ в $$x$$, то, очевидно, что $$x_{1},x_{2}\ldots x_{t},y$$ - кратчайший путь из $$a$$ в $$y$$, следовательно, $$d(a,y)=d(a,x)+1$$. Итак, расстояния от двух смежных вершин до вершины $$a$$ различаются ровно на единицу. Поэтому, если обозначить через $$A$$ множество всех вершин графа, расстояние от которых до вершины $$a$$ четно, а через $$B$$ множество всех вершин с нечетными расстояниями до $$a$$, то для каждого ребра графа один из его концов принадлежит множеству $$A$$, другой - множеству $$B$$. Следовательно, граф $$G$$ - двудольный.

    Пусть $$C$$ - цикл в графе $$G$$. Множество вершин цикла $$C$$ порождает в $$G$$ подграф, который содержит все ребра этого цикла, но может содержать и ребра, ему не принадлежащие. Такие ребра называют хордами цикла $$C$$. Простой цикл, не имеющий хорд, - это порожденный простой цикл. В графе, изображенном на рис. 3.4, хордами цикла $$4,1,2,6,5,4$$ являются ребра $$(1,5)$$, $$(1,6)$$ и $$(2,5)$$, а цикл $$2,3,7,6,2$$ - порожденный простой цикл. Заметим, что любой цикл длины $$3$$ является порожденным простым циклом.

    (рис 3.5) (рис 3.4)

    Пусть $$C$$ - простой цикл длины $$k$$ в некотором графе, $$(x,y)$$ - хорда этого цикла. Ребро $$(x,y)$$ вместе с ребрами цикла $$C$$ образует два цикла меньшей длины, $$C_{1}$$ и $$C_{2}$$ (см. рис. 3.5), сумма длин которых равна $$k+2$$.

    Значит, если $$C$$ - цикл нечетной длины, то один из циклов $$C_{1}$$, $$C_{2}$$ тоже имеет нечетную длину. Отсюда следует, что в графе, в котором есть цикл нечетной длины, имеется и порожденный простой цикл нечетной длины. Поэтому критерий двудольности справедлив и в следующей формулировке.

    Следствие.Граф является двудольным тогда и только тогда, когда в нем нет порожденных простых циклов нечетной длины.

    Планарные графы

    Геометрический граф - это плоская фигура, состоящая из вершин - точек плоскости и ребер - линий, соединяющих некоторые пары вершин. Всякий граф можно многими способами представить геометрическим графом, и мы уже не раз пользовались этой возможностью. На рис. 3.6 показаны два геометрических графа $$\Gamma_{1}$$ и $$\Gamma _{2}$$, представляющих, как нетрудно проверить, один и тот же обыкновенный граф. Простое устройство этого графа, очевидное на изображении слева, не так легко обнаружить, рассматривая изображение справа. Главная причина этого в том, что в $$\Gamma_{1}$$ ребра не имеют "лишних" пересечений.

    (рис 3.6)

    Геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины, называют плоским графом, а по отношению к представляемому им обыкновенному графу - его плоской укладкой. Не каждый граф допускает плоскую укладку. Граф, для которого существует плоская укладка, называется планарным графом. Кроме удобства визуального анализа, есть немало поводов, в том числе и сугубо практических, для интереса к планарным графам и их плоским укладкам.

    Если плоскость разрезать по ребрам плоского графа, она распадется на связные части, которые называют гранями. Всегда имеется одна неограниченная внешняя грань, все остальные грани называются внутренними. Если в плоском графе нет циклов, то у него имеется только одна грань. Если же циклы есть, то граница каждой грани содержит цикл, но не обязательно является циклом. На рис. 3.7 показан плоский граф с пятью занумерованными гранями. Граница грани с номером 3 состоит из двух циклов, а граница грани с номером 2 кроме цикла длины 5 включает еще дерево из трех ребер.

    (рис 3.7)

    Множества ребер, образующие границы граней, могут быть разными для разных плоских укладок одного и того же графа. На рис. 3.8 показаны две плоские укладки одного графа. В левой укладке есть две грани, границы которых являются простыми циклами длины 5. В правой укладке таких граней нет, но есть грани, ограниченные циклами длины 4 и 6. Однако число граней, как показывает следующая теорема, не зависит от укладки, т.е. является инвариантом планарного графа.

    (рис 3.8)

    Теорема 6 (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего $$n$$ вершин, $$m$$ ребер и $$k$$ компонент связности, равно $$m-n+k+1$$.

    Доказательство.

    Докажем сначала утверждение теоремы при $$k=1$$. Рассмотрим связный плоский граф $$G$$. Если в нем нет циклов, то имеется единственная грань, а $$m=n-1$$, и формула верна. Если же есть хотя бы один цикл, то возьмем какое-нибудь ребро $$e$$, принадлежащее простому циклу $$C$$. Это ребро принадлежит границе двух граней, одна из которых целиком лежит внутри цикла $$C$$, другая - снаружи. Если удалить ребро $$e$$ из графа, эти две грани сольются в одну. Граф $$G_{1}$$, полученный из графа $$G$$ удалением ребра $$e$$, очевидно, будет плоским и связным, в нем на одно ребро и на одну грань меньше, чем в $$G$$, а число вершин осталось прежним. Если в $$G_{1}$$ еще есть циклы, то, удалив еще одно цикловое ребро, получим граф $$G_{2}$$. Будем продолжать удаление цикловых ребер до тех пор, пока не получится связный плоский граф $$G_{r}$$ без циклов, т.е. дерево. У него $$n-1$$ ребро и единственная грань. Значит, всего было удалено $$r=m-n+1$$ ребер, а так как при удалении каждого ребра число граней уменьшалось на единицу, то в исходном графе было $$m-n+2$$ грани. Таким образом, формула верна для любого связного плоского графа. Если граф несвязен, то в компоненте связности, имеющей $$n_{i}$$ вершин и $$m_{i}$$ ребер, как доказано выше, будет $$m_{i}-n_{i}+1$$ внутренняя грань. Суммируя по всем компонентам и прибавляя 1 для учета внешней грани, убеждаемся в справедливости формулы в общем случае.

    Следствие 1. Если в планарном графе $$n$$ вершин, $$n\ge 3$$, и $$m$$ ребер, то $$m\le 3(n-2)$$.

    Доказательство.

    Если в графе нет циклов, то $$m=n-k$$ и неравенство выполняется при $$n\ge 3$$. Рассмотрим плоский граф $$G$$ с $$r$$ гранями, в котором имеются циклы. Занумеруем грани числами от $$1$$ до $$r$$ и обозначим через $$a_{i}$$ количество ребер, принадлежащих грани с номером $$i$$. Так как граница каждой грани содержит цикл, то $$a_{i} \ge 3$$ для каждого $$i$$, следовательно, $$\sum _{i=1}^{r}a_{i} \ge 3r$$. С другой стороны, каждое ребро принадлежит границе не более чем двух граней, поэтому $$\sum_{i=1}^{r}a_{i} \le 2m$$. Из этих двух неравенств следует, что $$3r\le 2m$$. Применяя формулу Эйлера, получаем $$m\le 3n-3k-3\le 3n-6$$.

    Следствие 1 дает необходимое условие планарности, которое в некоторых случаях позволяет установить, что граф не является планарным. Рассмотрим, например, полный граф $$K_{5}$$. У него $$n=5$$, $$m=10$$, и мы видим, что неравенство из следствия 1 не выполняется. Значит, этот граф непланарен. В то же время существуют графы, не являющиеся планарными, для которых неравенство следствия 1 выполняется. Пример - полный двудольный граф $$K_{3,3}$$. У него 6 вершин и 9 ребер. Неравенство выполняется, но мы сейчас установим, что он непланарен. Заметим, что в этом графе нет циклов длины 3 (так как он двудольный, в нем вообще нет циклов нечетной длины). Поэтому граница каждой грани содержит не менее четырех ребер. Повторяя рассуждения из доказательства следствия 1, но используя неравенство $$a_{i} \ge 4$$ вместо $$a_{i} \ge 3$$, получаем следующий результат:

    Следствие 2. Если в планарном графе $$n$$ вершин, $$n\ge 3$$, $$m$$ ребер и нет циклов длины $$3$$, то $$m\le 2(n-2)$$.

    Для графа $$K_{3,3}$$ неравенство следствия 2 не выполняется, и это доказывает, что он непланарен.

    Известно несколько критериев планарности, сформулируем без доказательства два из них. Два графа называют гомеоморфными,если из них с помощью подразбиения ребер можно получить изоморфные графы. На рис. 3.9 изображены гомеоморфные графы.

    (рис 3.9)

    Сформулируем без доказательства два критерия планарности.

    Теорема 7 (критерий Понтрягина-Куратовского). Граф планарен тогда и только тогда, когда у него нет подграфов, гомеоморфных $$K_{5}$$ или $$K_{3,3}$$.

    Граф $$G$$ называется стягиваемым к графу $$H$$, если $$H$$ можно получить из $$G$$ последовательностью операций стягивания ребер.

    Теорема 8 (критерий Вагнера). Граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к $$K_{5}$$ или $$K_{3,3}$$.

    Отметим, что, несмотря на внешнее сходство двух теорем, фигурирующие в них понятия гомеоморфизма и стягиваемости существенно различаются. На рис. 3.10 изображен граф, который называют графом Петерсена. В нем нет подграфа, гомеоморфного $$K_{5}$$, так как в графе $$K_{5}$$ каждая вершина имеет степень $$4$$, а в графе Петерсена степень каждой вершины равна $$3$$. При удалении вершин и ребер и подразбиении ребер степени вершин не увеличиваются. В то же время легко видеть, что граф Петерсена можно превратить в $$K_{5}$$ стягиванием пяти ребер.

    (рис 3.10)
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^