Плоские графы. Эйлеровы графы. Гамильтовы графы. Орграфы

Пусть дано непустое множество X, состоящее из элементов, называемых точками (x ₁, x ₂, …), и на X задано множество отношений T, позволяющих установить соответствие между каждым элементом множества X и некоторым его подмножеством. Каждая пара точек x_i, x_j множества X, между которыми установлено отношение из множества T, называется ребром.

Определение 1. Непустое множество X и множество отношений T называется графом и обозначается G(X,T). Граф называется конечным, если множество X конечно.

С геометрической точки зрения граф G(X,T) представляет собой непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат данному множеству точек. При изображении графов ребра могут быть прямолинейны или криволинейны, длины ребер и расположение вершин произвольно. На следующих рисунках изображен один и тот же граф.

Ребра графа обозначают парой вершин (x ₁, x ₂).

Определение 2. Вершины, не принадлежащие ни одному ребру графа, называются изолированными.

Пример 1. Рассмотрим граф

Вершины x ₁, x ₄, x ₅ - изолированные (точка пересечения диагоналей не принадлежит графу). Граф может не иметь ребер. Тогда он состоит из изолированных точек.

Пример 2. Граф

состоит только из изолированных точек.

Определение 3. Две вершины называются смежными, если они соединены ребром, два различных ребра смежные, если они имеют общую вершину.

Определение 4. Ребро и любая из его вершин называются инцидентными.

Определение 5. Ребро графа G(X,T), у которого начальная и конечная вершины совпадают, называется петлей.

Пример 3. Рассмотрим граф

На рисунке ребро (x ₃, x ₃) является петлей.

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

Существуют различные способы задания конечного графа G(X,T). Пусть x ₁, x ₂, …, x_n - вершины графа, l ₁, l ₂, …, l_m - ребра графа.

Определение 6. Матрицей смежности называется матрица А_nn, у которой элемент a_ij равен количеству ребер, соединяющих вершины x_i и x_j.

Определение 7. Матрицей инцидентности называется матрица В_nm, у которой элемент b_ij равен 1, если вершина x_i инцидентна ребру l_j, и равен 0 в противном случае.

Пример 4. Для графа

матрицы смежности и инцидентности имеют вид

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

Характеристики графа

Определение 1. Граф G(X,T) называется полным, если любые две различные вершины соединены одним, и только одним ребром.

Пример 1. Граф

является полным.

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

Определение 2. Дополнением графа G(X,T) называется граф с теми же вершинами, что и граф G(X,T), и теми ребрами, которые необходимо добавить к графу G(X,T), чтобы получился полный граф.

Пример 2.

G(X,T) Полный граф

Определение 3. Степенью вершины x_i графа G(X,T) называется число d_i, равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень - четное (нечетное) число.

Теорема 1. Если конечный граф G(X,T) (без петель) имеет n вершин и m ребер, то

. (1)

Доказательство. Рассмотрим граф

Очевидно, что d ₁=3, d ₂ =2, d ₃ =2, d ₄ =3. Сложим эти числа:
d ₁ + d ₂ + d ₃ + d ₄=10. В этой сумме каждое ребро участвует дважды: 10:5=2.

Рассмотрим произвольный граф G(X,T). Каждая вершина графа x_i инцидентна d_i ребрам. Если сложить эти величины по всем вершинам, то в полученной сумме каждое ребро будет участвовать дважды, т.е. эта сумма будет равна 2 m.

Теорема 2. Число нечетных вершин любого графа четно.

Доказательство. Так как левая часть равенства (1) является четным числом, то нечетных вершин должно быть четное число.

Теорема 3. Во всяком графе с n вершинами (n >2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Доказательство. Предположим противное - все вершины имеют разные степени: 0, 1, 2, …, n - 1. Но если в графе есть вершина степени 0, то не может быть вершины со степенью n - 1. Получено противоречие.

Теорема 4. Если в графе с n вершинами (n >2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n -1.

Путь и цикл в графе

Определение 1. Путем от x_i до x_j называется такая последовательность ребер графа, ведущая от x_i к x_j, в которой два соседних ребра имеют общую вершину и никакое ребро не встречается дважды. Длиной пути называется число ребер этого пути.

Определение 2. Путь от x_i до x_j называется простым, если он не проходит через одну вершину более одного раза.

Пример 1. Рассмотрим граф

В данном графе есть следующие пути от x ₁ до x ₆:

1) x ₁, x ₂, x ₅, x ₆ - путь длиной 3;

2) x ₁, x ₂, x ₃, x ₅, x ₆ - путь длиной 4;

3) x ₁, x ₂, x ₄, x ₅, x ₆ - путь длиной 4;

4) x ₁, x ₂, x ₃, x ₅, x ₄, x ₂, x ₅, x ₆ - путь длиной 7.

Первые три пути являются простыми.

Определение 3. Циклом называется путь, в котором начальная и конечная вершины совпадают. Длиной цикла называется число ребер в этом цикле.

Определение 4. Цикл называется простым, если он не проходит через одну вершину более одного раза.

Пример 2. Рассмотрим граф

В данном графе есть следующие циклы:

1) x ₁, x ₅, x ₄, x ₁ - цикл длиной 3;

2) x ₁, x ₂, x ₃, x ₁ - цикл длиной 3;

3) x ₁, x ₂, x ₄, x ₅, x ₃, x ₁ - цикл длиной 5;

4) x ₁, x ₂, x ₄, x ₅, x ₂, x ₃, x ₁ - цикл длиной 6;

и т. д.

Первые три цикла являются простыми.

Теорема. Если у графа G(X,T) все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

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

Связность графа, деревья

Определение 1. Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах, и несвязными в противном случае.

Определение 2. Граф называется связным, если любые две его вершины связны, и несвязным в противном случае.

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

В первом случае мы имеем связный граф, во втором - несвязный.

Теорема 1. Связный граф G(X,T) представляет собой простой цикл тогда, и только тогда, когда каждая его вершина имеет степень 2.

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

Необходимость. Пусть граф G(X,T) представляет собой простой цикл. Он является замкнутым простым путем. Из любой его вершины можно попасть в любую другую, не проходя ни через какую вершину два раза. Очевидно, что степень любой вершины такого графа равна 2.

Достаточность. Пусть граф G(X,T) связный и степень каждой его вершины равна 2. Любые две его вершины соединены путем. Возьмем произвольную вершину. Пойдем по одному из двух ребер, к которым принадлежит эта вершина. Мы попадем в следующую вершину, из которой выходит два ребра. По одному мы пришли. Двигаемся далее по второму ребру. Таким образом, все вершины графа будут пройдены и мы вернемся в исходную вершину. Путь замкнется. Следовательно, этот граф является циклом.

Определение 3. Ребро (x_i, x_j) называется мостом, если в графе G(X,T), полученном после удаления ребра (x_i, x_j), вершины x_i и x_j несвязны.

Пример 2.

В исходном графе ребро (x ₃, x ₅) является мостом.

Существует несколько признаков мостов:

1) Ребро (x_i, x_j) является мостом тогда, и только тогда, когда (x_i, x_j) является единственным путем, соединяющим вершины x_i и x_j.

2) Ребро (x_i, x_j) является мостом тогда, и только тогда, когда найдутся две вершины x_k и x_m, такие, что любой путь, соединяющий их, содержит вершины x_i и x_j.

3) Ребро (x_i, x_j) является мостом тогда, и только тогда, когда оно не принадлежит ни одному циклу.

Определение 4. Связный граф без циклов называется деревом.

Определение 5. Вершина дерева, имеющая степень 1, называется висячей.

По аналогии с генеалогическими деревьями вводятся родовые понятия для вершин.

Пример 3.

Вершина x ₁ называется корневой, пути от нее называются ветвями. Вершина x ₂ называется родительской по отношению к вершинам x ₄, x ₅, x ₆ и прародительской по отношению к вершинам x ₈, x ₉. Вершины x ₂ и x ₃ называются дочерними к вершине x ₁.

Пример 4. Кубок по настольному теннису разыгрывают 16 команд по олимпийской системе. Схему турнира можно изобразить деревом.

Любое ребро в дереве является мостом. Для каждой пары вершин дерева существует единственный соединяющий их путь.

Теорема 2. Дерево с n вершинами имеет n -1 ребро.

Изображение графа

Один и тот же граф может быть изображен по-разному.

Пример. На данных рисунках изображен один и тот же граф.

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

1) одинаковое ли число вершин в графах;

2) одинаковое ли число ребер в графах;

3) одинаковое ли в графах число вершин имеют степень k.

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

Плоские графы

Определение 1. Граф G(X,T) называется плоским, если его можно изобразить на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Чертеж графа, на котором никакие два ребра не пересекаются, называют плоским представлением графа.

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

Пример 1. Дан граф

Его плоским представлением является граф

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

Примером неплоского графа может служить полный граф с пятью вершинами.

Любые попытки начертить его плоское представление обречены на неудачу.

Определение 2. Гранью в плоском представлении графа G(X,T) называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

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

Определение 4. Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

Пример 2.

Данный граф имеет четыре обычные грани, ограниченные циклами (x ₁, x ₂, x ₆, x ₁), (x ₅, x ₆, x ₇, x ₅), (x ₂, x ₃, x ₄, x ₅, x ₂), (x ₂, x ₅, x ₇, x ₆, x ₂), и одну бесконечную грань, ограниченную циклом (x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₁). Грани (x ₁, x ₂, x ₆, x ₁) и (x ₂, x ₅, x ₇, x ₆, x ₂) являются соседними, а грани (x ₁, x ₂, x ₆, x ₁) и (x ₂, x ₃, x ₄, x ₅, x ₂) соседними не являются. Часть плоскости, ограниченная простым циклом (x ₂, x ₅, x ₆, x ₂), не является гранью, так как содержит внутри себя цикл (x ₅, x ₆, x ₇, x ₅).

Пример 3.

В данном графе часть плоскости, ограниченная простым циклом (x ₁, x ₂, x ₃, x ₄, x ₁), является гранью, так как ребро (x ₁, x ₅), расположенное внутри грани, не является циклом.

Пример 4.

Часть плоскости, заключенная между циклами (x ₁, x ₂, x ₃, x ₄, x ₅, x ₁) и (x ₆, x ₇, x ₈, x ₆), не является гранью, так как она содержит внутри себя цикл и к тому же она не ограничена циклом. Ребро (x ₁, x ₆) является мостом, соединяющим два цикла.

Определение 5. Мост, соединяющий два цикла, называется перегородкой.

Пример 5.

Данный граф не имеет бесконечной грани, так как она не ограничена изнутри простым циклом. Мост (x ₁, x ₂) является перегородкой.

В плоском представлении дерева за грань принимают всю плоскость чертежа.

Для всякого плоского графа без перегородок число вершин n, число ребер m и число граней с учетом бесконечной g связаны соотношением n - m + g = 2, которое называется формулой Эйлера.

Определение 6. Плоский граф G(X,T) называется максимально плоским, или триангулированным, если к нему невозможно добавить ни одного ребра так, чтобы полученный граф был плоским.

Пример 6. Рассмотрим граф

Данный граф можно сделать максимально плоским:

Каждая грань в плоском представлении максимально плоского графа имеет три вершины.

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

Теорема. Для любого плоского графа G(X,T) существует плоское представление, в котором все ребра - прямолинейные отрезки.

Эйлеровы графы

Определение 1. Эйлеровым путем в графе называется путь, содержащий все ребра графа и проходящий через каждое по одному разу.

Пример 1. Рассмотрим граф

Он имеет эйлеров путь (x ₄, x ₁, x ₃, x ₂, x ₁, x ₅, x ₃).

Определение 2. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа и проходящий через каждое по одному разу.

Определение 3. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Пример 2. Рассмотрим граф

Данный граф является эйлеровым, так как он имеет эйлеров цикл (x ₂, x ₅, x ₄, x ₁, x ₂, x ₃, x ₄, x ₂).

Теорема 1. Эйлеров граф связный, и все его вершины четны.

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

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

Теорема 2. Если граф G(X,T) связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 3. Если граф G(X,T) обладает эйлеровым путем с концами А и В, то граф G(X,T) связный и А и В его единственные нечетные вершины.

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

Если путь начинается в А и кончается в В, то А и В нечетные вершины, даже если путь неоднократно проходил через них. В любую другую вершину путь должен привести и вывести из нее, т.е. остальные вершины четные.

Теорема 4. Если граф G(X,T) связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.

Теорема 5. Если граф G(X,T) связный, то можно построить цикличный маршрут, содержащий все ребра в точности 2 раза, по одному в каждом направлении.

Гамильтоновы графы

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

Пример 1. Рассмотрим граф

Он имеет гамильтоновы пути (x ₃, x ₄, x ₅, x ₁, x ₂) и (x ₃, x ₄, x ₂, x ₅, x ₁).

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

Определение 3. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Пример 2. Рассмотрим граф

Данный граф является гамильтоновым, так как он имеет гамильтоновы циклы (x ₁, x ₇, x ₆, x ₃, x ₄, x ₅, x ₂, x ₁) и (x ₁, x ₆, x ₃, x ₄, x ₅, x ₂, x ₇, x ₁).

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

Теорема. Граф с m вершинами имеет гамильтонов цикл, если для любой его вершины A_i степень (A _i) > m /2.

Сети Петри

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

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

Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, разновременно при выполнении некоторых условий.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Дата добавления: 2014-12-27