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

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

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

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

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

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

v1 v2

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

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

v7 v8

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

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

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

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

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

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

Изоморфизм.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цепь – маршрут, в котором нет повторяющихся ребер (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 _ĳ || _n_x_m, в которой элемент c _ĳ =1, если вершина х_i инцидентна ребру v _j, и c _ĳ =0 в противном случае.