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

В задачах ИО широко используются методы дискретной математики.

Приведём примеры задач:

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

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

Определение и классификация задач.

Пусть задано множество дискретных величин.

X = {x₁, x₂, …x_n}

Элементы которых будем называть вершинами. Образуем из него новое множество U = {U₁, U₂, …U_n}, состоящей из пар (x_i; x_j).

При этом будем различать 2 случая:

· когда безразлично в каком порядке берутся вершины при образовании пар, то такая пара будет ребром соединений двух вершин x_i и x_j; (x_i; x_j) = (x_j; x_i)

· когда существенно в каком порядке выбрана вершина, тогда пару (x_i; x_j) называют дугой соединяющей вершины x_i и x_j.

Пара множеств G = (X, U) называется конечным графом в случае а и конечным ориентированным графом (орграфом) – у втором случае.

Во втором случае элементами множества U является не ребра, а дуги. Между ребрами и вершинами графа существует отношение инцидентности, тоесть, говорят, что ребро x_i и x_j инцидентно к вершинам x_i и x_j и наоборот вершины x_i и x_j к ребру.

Если граф G ориентирован то дуга x_i xj выходит из вершины x_i и заходит в вершину x_j.

Вершина x_i – предшественник, а вершина x_j – последователь вершины x_i.

Подграфом графа G называется граф = .

Если ≤ х, то подграф G называется основный.

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

 

 

подграф

 

 

основный граф

 

 

 

полный граф