Каждый граф укладывается в R3.

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

При доказательстве упомянутой формулы Эйлер использовал технику двойного (повторного) счёта. Он посчитал количество инцидентных пар (v,e), где e — ребро и v — одна из его концевых вершин двумя разными способами. Вершина v принадлежит парам deg(v), где deg(v) — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней. Однако каждое ребро принадлежит двум инцидентным парам, так как имеет две концевые вершины. Поэтому число инцидентных пар равно 2|E|. Поскольку две данные формулы предназначены для одного и то же множества, их значения одинаковы.

Чётность или нечётность суммы целых чисел не зависит от количества чётных слагаемых. Сумма чётна, если число нечётных слагаемых чётно (и нечётна в противном случае). Так как одна часть уравнения всегда чётна (2|E|), другая часть должна содержать чётное число нечётных слагаемых, т. е. вершин нечётной степени.

Число вершин нечетной степени в любом графе четно.

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

Пусть дан (n,m) – граф G. Составим сумму степеней всех его вершин.

,

где – множества четных и нечетных натуральных чисел соответственно.

Так как первое слагаемое – четное число, то равенство примет вид

.

Отсюда , т. е. сумма всех нечетных степеней графа – четное число. Сумма нечетных чисел может быть четна тогда и только тогда, когда число слагаемых этой суммы четно, следовательно, число вершин нечетной степени четно.

Изоморфизм

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

Графы и называются изоморфными, если существует такая биекция множества на множество , что тогда и только тогда, когда . Отображение в этом случае называется изоморфизмом графа на граф .

Тот факт, что графы и изоморфны, записывается так: .

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

(вершина графа )
(вершина графа )

Заметим, что в этом примере есть и другие изоморфизмы первого графа на второй.

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

Изоморфизм - бинарное отношение на множестве графов. Очевидно, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.

Геометрическая реализация — фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе.

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

Каждый граф укладывается в R3.

Все вершины произвольного графа G помещаем в различных точках координатной оси х. Рассмотрим пучок плоскостей, проходящих через ось х, и зафиксируем |E| различных таких плоскостей. Теперь каждое ребро (u, v) изобразим полуокружностью, проходящей в соответствующей плоскости через вершины u, v. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах.

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

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

Пример плоского графа приведен на рис. 4.12. Изоморфный ему полный граф (рис.4.13), укладываемый на плоскости, имеет два пересекающихся ребра, поэтому граф не является плоским - он только планарный.

Существуют и непланарные графы. На рисунке показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K₅ и K_3,3 соответственно.

3. Пустой граф (вполне несвязный граф, нуль-граф) — регулярный граф степени 0, то есть граф, не содержащий рёбер.

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

Произведения графов

a) Декартовым произведением G₁□G₂ называется граф G, для которого V(G)= V₁xV₂ – декартово произведение множеств вершин исходных графов, а E(G) определяется следующим образом: вершины (и_1, u₂) и (v₁, v₂) смежны в графе G тогда и только тогда, когда или и₁₌v₁, а u₂ и v₂ смежны в G₂, или и₂₌v₂, а u₁ и v₁ смежны в G_1.

b) Категорийным произведением G₁xG₂ называется граф G, для которого V(G)= V₁xV₂ – декартово произведение множеств вершин исходных графов, а E(G) определяется следующим образом: вершины (и₁, u₂) и (v₁, v₂) смежны в графе G тогда и только тогда, когда u₁ и v₁ смежны в G₁ и u₂ и v₂ смежны в G₂.

c) Сильным произведением G₁ x G₂ называется граф G, для которого V(G)= V₁xV₂ – декартово произведение множеств вершин исходных графов, а E(G) определяется следующим образом: вершины (и₁, u₂) и (v₁, v₂) смежны в графе G тогда и только тогда, когда u₁ и v₁ смежны в G₁, а u₂ и v₂ смежны в G₂ или и₂=v₂, или u₂ и v₂ смежны в G₂, а u₁ и v₁ смежны в G₁ или и₁=v₁.

Примеры:

Предположим, что G является неориентированным графом.

В качестве маршрута графа G={V,E}, V={a₁, a₂, ...,a_n}, E={l₁₂=(a₁, a₂),…,l_{k-1 k}=(a_k-1, a_k)} определяют такую очередность ребер M={l₁₂,l₂₃,…,l_{k-1 k}}, что для двух соседних ребер характерна общая инцидентная вершина, a₁ есть начальная, a_n- конечная вершины. Под длиной маршрута понимают количество ребер маршрута.

Маршрут M именуют цепью в случае, когда все его ребра различны. Простой цепью маршрут M можно назвать, если все его вершины, за исключением первой и последней, различны.

Так, для графа, изображенного на рис. 1 обозначим: abdbe - маршрут, а не цепь, abcdbe представляет собой непростую цепь, abe является простой цепью.

Цепь, которая предполагает совпадение начальной и конечной вершин, имеет название цикла, в случае, когда цепь простая, — простого цикла.

Не нашли, что искали? Воспользуйтесь поиском по сайту: