3.2 Элементы теории графов

Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. Например, при изучении электрических цепей на первый план может выступать характер соединений различных её компонентов – резисторов, м/с, источников и т. п.

В подобных случаях удобно рассматриваемые объекты изображать точками, называемые вершинами, а связи между ними – линиями, называемые ребрами. Множество вершин (Х=х₁, х₂,…,х_n, Х=n), связи между которыми определены множеством ребер (V=v₁, v₂,…,v_m, V=m), называется графом и обозначают G= (X, V).

Леонард Эйлер –первая работа по графам в 1736 г., когда работал в Российской Академии (решение задачи о Кенигсбергских мостах). Можно ли совершить прогулку, чтобы, выйдя из любого места города, вернуться в него, пройдя один раз по каждому мосту? Эйлер доказал, что подобный маршрут имеется только для такого графа, каждая из вершин которого связана с четным числом ребер. Кирхгоф в середине прошлого века применил графы для анализа электрических цепей.

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

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

М

x1

x2

v1

v2

ультиграф – граф, у которого любая пара вершин соединена более чем одним ребром.

К

v3

ратные ребра – ребра, соединяющие одну и ту же пару вершин (v7,.v8).

v4

v7 v8

Мультичисло – наибольшее число кратных ребер.

С

x3

x4

v5

тепень вершины – число ребер, связанных с одной вершиной

(

v6

петля учитывается дважды).

Инцидентность. Если ребро соединяет пару вершин, то говорят, что ребро инцидентно этим вершинам, а вершина инцидентна ребру

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

Смежность – отношение между однородными объектами (вершинами), инцидентность – отношение между разнородными объектами (вершинами и ребрами).

И зоморфизм.

Г рафы G=(X,V) и G^=(X^,V^), для которых сохраняется

о тношение инцидентности, называется изоморфным.

О ни различаются лишь начертанием.

П ланарность. При конструировании ЭА

к топологическому чертежу часто предъявляется

требование расположения проводников схемы на

п лоскости без пересечений. Возникает задача

о пределения планарности графа. Граф G=(X,V)

н азывается плоским, если он расположен на плоскости

т аким образом, что ребра имеют общие точки лишь в

вершинах. Граф G^=(X^,V^), изоморфный плоскому

G =(X,V), расположенный на плоскости и имеющий

п ересечения ребер, называется планарным.

плоский планарный

Маршрут в графе - последовательность m ребер (не обязательно различных) (v₁, v₃, v₂, v₃, v₅), (v₅, v₆, v₄, v₄). Первый маршрут проходит через последовательность вершин (х₁, х₂, х₃, х_2, х₃, х₄) и соединяет вершины х₁ и х₄, а второй - через последовательность вершин (х₃, х_4, х_4, х₂, х₄) и соединяет вершины х₃ и х₄. Число ребер в маршруте m называется его длиной.

x3

v2

v6

v5

v3

х1

v1

v4

х2

x4

Замкнутый маршрут приводит в ту же вершину, из которой он начался.

Цепь – маршрут, в котором нет повторяющихся ребер (v₂, v₅, v₆).

Простая цепь– маршрут, все вершины которого различны (v₁, v₂, v₅).

Циклом – называется последовательность ребер v₁=(х₁, х_i),…, v_k=(x_j, x₁), при которой в результате обхода вершин графа х₁, х_i,…,x_j по этим ребрам возвращаются в исходную вершину x₁. Каждое ребро в цикле встречается не более одного раза, вершины могут повторяться несколько раз. Цикл - замкнутая цепь (v₂, v₃, v₄, v₅).

Простой цикл – цикл, в котором нет повторяющихся вершин, кроме первой и последней (v₂, v₄, v₅). Цикл называется сложным, если такие имеются.

Связный граф – граф, в котором перемещаясь из вершины в вершину, можно попасть в каждую вершину.

Деревья и лес. Дерево – связный неориентированный граф, не содержащий циклов. Дерево на множестве p вершин всегда содержится q=p-1 ребер, т.е. минимальное количество ребер для того, чтобы граф был связным. При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты (два дерева или дерево и изолированная вершина). Несвязный граф, компоненты которого являются деревьями, называется лесом.

Д обавленное

р

Т₁

ебро

цикл

Т₂

Дерево Образование цикла Лес

Неориентированный граф G=(X,V) с множеством вершин Х и множеством ребер V может быть задан в числовой форме матрицей инциденций C=||c_ij||_nxm, в которой элемент c_ij =1, если вершина х_i инцидентна ребру v_j, и c_ij =0 в противном случае.

	v1 v2 v3 v4 v5 v6
x1	1 0 0 0 0 0
x2	1 1 1 1 0 0
C = x3	0 1 1 0 1 0
x4	0 0 0 1 1 1

10