Основные сведения из теории графов

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

Графы встречаются во многих областях под разными названиями:

- «структуры» в гражданском строительстве;

- «сети» в электротехнике;

- «социограммы» в социологии и экономике;

- «молекулярные структуры» в химии;

- электрические или газовые «распределительные сети» и т.д.

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

Таким образом, граф G задается множеством вершин х₁, х₂, …, x_n (которое обозначается через Х) и множеством линий - ребер а₁, а₂, …, a_m (которое обозначается символом А), соединяющих между собой все или часть вершин.

Принято обозначать граф в виде G=(X,A).

Если ребра графа ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф в этом случае называется ориентированным.

Если ребра не имеют ориентацию, то граф называется неориентированным.

Граф, содержащий дуги и ребра, называется смешанным.

Если граф G=(X,A)является ориентированным, но мы хотим пренебречь направленностью дуг, то неориентированный граф, соответствующий первоначальному заданному, обозначают и называют неориентированным дубликатом (неориентированным двойником) графа G.

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

Например: для графа, изображенного на рисунке имеем:

а₁=(х₁х₂)

а₂=(х₂х₅)

а₃=(х₁х₃)

а₄=(х₃х₄)

а₅=(х₃х₅) и (х₅х₃) или =(х₃х₅)

а₆=(х₄х₅)

а₇=(х₂х₃)

Ориентированный граф можно задать множеством вершин и соответствий «Г» (гамма).

Соответствие Г(x_i) представляет собой множество вершин x_j ∈ X, для которых в графе G существует дуга (x_i, x_j)

Тогда для графа, изображенного на рисунке, имеем:

Г(х₁)={х₂, х₃}

Г(х₂)={х₃, х₅}

Г(х₃)={х₂, х₃}

Г(х₄)={х₂}

Г(х₅)={ х₃}

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

Граф G в этом случае задается парой G=(Х,Г)

Обратное соответствие Г^-1(x_i) представляет собой множество вершин х_j принадлежащих множеству х для которых в графе G существует дуга (x_j, x_i), т.е вершина X_i является конечной в рассматриваемых дугах.

Тогда для графа, изображенного на рисунке имеем:

Г^-1(x₁)- пустое множество