2014-02-12
837
Изоморфизмы и реализации
Очевидно, что геометрический граф есть частный случай графа, в котором вершины и ребра являются соответственно точками и простыми кривыми в пространстве Rn, а выражение F(e)=(v&w) означает, что v и w являются граничными точками кривой e или что v - единственная вершина, содержащаяся в замкнутой кривой e, если v=w.
Ранее было отмечено, что любой граф в абстрактном смысле идентичен, или, используя более принятый термин, изоморфен некоторому геометрическому графу. Изоморфизм графов формально определяется следующим образом: говорят, что графы G=(V,E) и G¢=(V¢,E¢) изоморфны друг другу, если существует взаимно однозначное соотношение между V и V¢ и между E и E¢, сохраняющее отношения инцидентности. Иначе говоря, ребро e инцидентно вершине v графа G тогда и только тогда, когда инцидентны соответствующие элементы e¢ и v¢ в графе G¢. Если граф G изоморфен геометрическому графу G¢, тогда G¢ называется геометрической реализацией графа G. (В частности, геометрический граф можно рассматривать как геометрическую реализацию самого себя.)
Граф называется плоским тогда и только тогда, когда он имеет геометрическую реализацию в пространстве R 2. Например, граф G, изображенный на рис. 6.2, а, плоский, т. к. он изоморфен графу, изображенному на рис. 6.2, б.
| а) б) Рис.6.2 – Пример плоского графа | Рис.6.3 – Пример не плоского графа |
На рис. 6.3 показан не плоский граф, т. е. граф, не имеющий геометрической реализации в пространстве R 2. Граф иллюстрирует одну из двух фундаментальных конфигураций, которые характеризуют все неплоские конечные графы. Этот результат, следующий из важной теоремы, принадлежащей Куратовскому. Если в пространстве R 2 только ограниченный класс конечных графов имеет геометрическую реализацию, то для пространства R 3 справедливо следующее утверждение.
Теорема. Любой конечный граф G имеет геометрическую реализацию в R 3.
Чтобы получить возможность четкого описания различных структурных свойств графов, полезно ввести ряд дополнительных понятий, которые особенно наглядно иллюстрируются на примере геометрических графов.
Если e~(v& w), то будем называть v и w граничными точками e независимо от того, является граф геометрическим или нет. Если v=w, тогда v - единственная граничная точка e, а e называется петлей. Если e1~(v& w) и e2~(v& w), тогда e1 и e2 называются параллельными ребрами. В частности, две петли, инцидентные одной и той же вершине, являются параллельными. Говорят, что вершины v и w смежные, если существует, по крайней мере, одно ребро e такое, что e~(v& w). В частности, вершина v смежна сама с собой, если существует петля, инцидентная v; в противном случае, v не может быть смежной сама с собой. Аналогично ребра e1 и e2 называются смежными, если они имеют, по крайней мере, одну общую граничную точку. Заметим, что смежность является отношением между двумя подобными элементами (между вершинами или между ребрами), тогда как инцидентность есть отношение между разнородными элементами.
Число ребер, инцидентных вершине v (петля учитывается дважды), называется степенью вершины v и обозначается d(v). Говорят, что вершина v изолирована, если d(v)=0. В частности, вырожденным графом называется граф, у которого все вершины изолированы.
Пусть S - любое конечное множество. Обозначим через | S| число элементов в множестве S. Таким образом, | V| и | E| - число вершин и ребер конечного графа G=(V, E) соответственно. Учитывая, что появление каждого нового ребра добавляет по единице к степеням двух вершин (или в случае петли два к степени одной вершины), имеем
.
Если V 0 и V 1 - множества вершин, имеющих четные и нечетные степени соответственно, то очевидно, четно, т. к. это конечная сумма четных чисел. Отсюда следует, что
также обязательно четно, что доказывает следующую теорему.
Теорема. В конечном графе число вершин нечетной степени четно.
| Рис.6.5 – Определение степеней вершин | Для лучшего усвоения введенной выше терминологии проиллюстрируем ее на примере графа, изображенного на рис. 6.5. Граничными точками ребра e1 являются вершины v3 и v2. Петля e4 имеет единственную граничную точку v1. Ребро e2 смежно ребру e1 и параллельно ребру e3. (Заметим, что параллельные ребра являются также и смежными.) Вершина v1 смежна с v4 и сама с собой, однако v4 с собой не смежна. Вершина v5 является изолированной вершиной. Четыре вершины, а именно, v1, v2, v3 и v4, имеют четную степень. |
Пусть задан граф G(V, E, F ). Систему G1=(V 1, E 1, F1 ) будем называть подграфом графа G тогда и только тогда, когда выполняются следующие условия.
1. V 1 Ì V и E 1 Ì E.
2. F1(e) = F(e) для каждого e Î E 1.
3. Если e Î E 1 и F(e)=(v&w), то v Î V 1 и w Î V 1.
Иначе говоря, подграф графа G состоит из части ребер и вершин G, для которых сохраняются отношения инцидентности, имеющие место в графе G при выполнении разумного требования о том, что множество вершин подграфа G должно включать все граничные точки множества его ребер. Граф G называется также надграфом графа G 1.
