Метрические характеристики графов. Деревья. Планарность графов

Метрические характеристики графа
В этом параграфе G - связный граф.
1. Пусть и и v - две несовпадающие вершины графа G. Длина кратчайшего (u,v) - маршрута называется расстоянием между вершинами и и v и обозначается через d(u,v). Положим также d(u,u) = 0.
Теорема 1. Расстояние d(u, v) удовлетворяет аксиомам метрики:
а) d(u,v) ≥ 0;
б) d(u, v) = 0 тогда и только тогда, когда и = v;
в)d(u,v) = d(v,u);
г) d(u,v) + d(v,w) ≥ d(u, w)
для любых вершин и, и, w графа G.
Понятие расстояния между вершинами позволяет определить k-ю степень графа G. Граф Gk имеет то же множество вершин, что и G и несовпадающие вершины u и v смежны в графе Gk в том и только том случае, если d(u,v) ≤ k. Диаметром d(G) графа G называется наибольшее из расстояний. Ясно, что d(G) ≤ |G|.
Теорема 2. Если k ≥ d(G), то Gk - полный граф.
Теорема 3. Для любого связного графа G имеет место неравенство: d(G) ≤ rankG.
2. Критерий двудольности графа.
Теорема 3 (Кениг, 1936 г.). Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.
Деревья
Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим или лесом. Следующая теорема характеризует и дает эквивалентные определения дереву.
Теорема 1. Для (п, т)-графа G следующие условия эквивалентны:
а) G - дерево;
б) G - связный граф и т = п - 1;
в) G - ациклический граф и т = п - 1;
г) любые две несовпадающие вершины графа G соединяет единственная простая цепь.
Следствие. В любом дереве порядка п ≥ 2 имеется не менее двух концевых вершин.
Пусть Н - остовной подграф произвольного графа G. Если на каждой области связности графа G графом H порождается дерево, то Н называется остовом или каркасом графа G. Очевидно, что в любом графе существует остов: разрушая в каждой компоненте циклы, т.е. удаляя лишние ребра, придем к остову.
Теорема 2. Число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m(G) - |G| + k(G), где m(G) и k(G) - число ребер и число компонент графа G соответственно.
Планарность
Встречаются ситуации (например в радиоэлектронике при проектировании путей коммуникаций), когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Таким образом возникает понятие плоского графа. Плоским графом назовем граф, вершины которого являются точками плоскости, а ребра - непрерывными плоскими линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Любой граф, изоморфный плоскому графу, будем называть планарным. О планарных графах говорят, что они укладываются на плоскости. Имеет смысл рассматривать укладки и на других поверхностях (например, сфере, торе, сфере с п ручками), а также в пространстве.
Теорема 1. Для любого графа найдется натуральное число п такое, что данный граф укладывается на сфере с п ручками. Тем более любой граф укладывается в пространстве.
Наименьшее натуральное число п со свойством, указанным в теореме 1, называется родом графа G и обозначается γ(G). В случае γ(G) = 1 говорят о тороидальных графах. Что касается взаимоотношений планарности и возможности укладки на сфере, то ответ дается в следующей теореме.
Теорема 2. Граф укладывается на сфере тогда и только тогда, когда он планарен, что в свою очередь эквивалентно равенству γ(G) = 0.
Доказательство легко получается с помощью стереографической проекции. Южный полюс сферы помещаем на плоскость и проектиру ем из северного полюса. При этом, если граф уложен на сфере, считаем, что северный полюс не принадлежит ни одному ребру графа, а если граф уложен на плоскости, то южный полюс обладает таким же свойством (очевидно, что даже малым сдвигом графа можно обеспечить соблюдение этого условия)
Существуют ли непланарные графы? Да, существуют, граф K3,3 не является планарным, как мы увидим позже. Более того, почти все графы непланарны в том смысле, что предел отношения

количество непланарных графов порядка n
количество всех графов порядка п
равен единице при п → .
Гранью плоского графа называется максимальное по включению множество точек плоскости, каждая пара которых может быть соединена непрерывной кривой, не пересекающей ребра графа. Границей грани будем считать множество вершин и ребер, принадлежащих этой грани. Далее будем пользоваться следующими обозначениями: n, m, f -соответственно число вершин, ребер и граней плоского графа.
Теорема 3 (Эйлер, 1758 г.). Для всякого связного плоского графа верно равенство (формула Эйлера) п - т + f = 2.
Именно с помощью формулы Эйлера доказывается непланарность некоторых графов.
Предложение. Графы К5 и К3,3 непланарны.
Особая роль непланарных графов К5, К3,3 заключается в том, что эти графы являются минимальными непланарными графами и играют важную роль во многих критериях планарности. Имеется несколько критериев планарности графа. Мы рассмотрим только один.
Теорема 4 (Понтрягина - Куратовского). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомоморфных К5 или К3,3.

Powered by Drupal - Design by artinet