Основные понятия теории графов. Изолированная и висячая вершина. Основные задачи теории графов. Проблемы надежности

Основные понятия теории графов.

Совокупность множеств вершин Х и множеств связей между ними U называется графом. G(X,U)

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

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

Если в графе присутствуют и ребра и дуги – граф называют смешанным.

Две вершины называются смежными если они соединены ребром или дугой.

Две связи называются смежными если они имеют общую вершину.

Вершина xi инцидентна uij если она является началом или концом uij.

Ребро / дуга uij инцидентна xi если она входит или выходит из этой вершины.

Число дуг/ребер, инцидентных вершине xi называется степенью этой вершины ρ(xi).

Для неографа ∑(i=1 до |x|)ρ(xi)=2|V|.

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

ρ(х1)=3 ρ(х2)=ρ(х3)=2 ρ(х4)=1 ρ(х5)=0

Вершина, не имеющая инцидентных ребер (дуг) называется изолированной ρ(хi)=0.

Вершина, инцидентная только одному ребру/дуге называется висячей.

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

Граф в котором все вершины попарно смежны – полный Kn.

n – количество вершин. Для полного графа |V|=(n(n-1))/2

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

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

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

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

Если вершины графа можно разбить на два непересекающихся подмножества x1∩x2=0 так, что не существует ребер, соединяющих вершину из х1 с вершиной х2, то такой граф называется двудольным, бихроматическим, Кёнига.

Полный двудольный граф: все вершины из х1 связаны со всеми вершинами из х2: К3,3,

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

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

Маршрут, в котором все ребра различны – цепь.

Маршрут, для которого различны все вершины – простая цепь.

Замкнутая цепь – цикл, замкнутая простая цепь – простой цикл.

Цикл, в котором содержатся все ребра – Эйлеров цикл. Необходимое и достаточное условие его существования – четкость степеней всех вершин.

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

Достаточное условие существования:

1.  если в графе с n вершинами для любой пары вершин xi, xj выполняется условие: ρ(xi)≥n, то в таком графе существует Гамильтонов цикл.

Или

2.В графе существует гамильтонов цикл, если для любой вершины xi выполняется условие ρ(xi)≥n/2

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

Связный граф без циклов - дерево

Любое дерево, построенное на n вершинах содержит (n-1) ребер; а лес, состоящий из n вершин, р деревьев, содержит (n-p) ребер.

Число различных деревьев связанного помеченного графа равно n ^n-2/

Для n=2: n ^n-2  =1

Для n=3: n ^n-2  =3

Для n=4: n ^n-2  =16

Различают два крайних дерева: последовательное и звездное.

Дерево может быть выделено из любого графа, если оно содержит все вершины графа (это остов или покрывающее дерево)

Каждый граф обладает свойствами, которые оцениваются хар-ческими числами:

1.  Цикломатическое число υ(G) – число ребер, которые необходимо удалить из графа, чтобы он стал деревом (или лесом, если граф был несвязным)

K=|U| - число ребер графа

|T|=n-1 – чмсло ребер дерева

υ(G)=k-n+1

υ(G)=k-n+p (если дерево)

2.  Хроматическое число K(G) – наименьшее число непересекающихся подмножеств вершин, на которые можно разбить вершины графа так, чтобы ребра графа соединяли вершины только разных подмножеств. (только разноокрашенные вершины)

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

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

Непланарный граф нельня нарисовать на плоскости без пересечений.

Планарность – свойство, плоскость – его реализация.

Операция расширения графа – замена одного ребра uij на 2: uip и upj с введением вершины р. Операция сжатия – обратная.

Исходный, расширенный и сжатый графы изоморфны с точностью до вершины i-ой степени.