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

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

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

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

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

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

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

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 его вершин существует соединяющие их ребра.

подграф

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

полный граф

Метод графов

Рисунок изображающий граф на плоскости называется диаграммой графа. Другими словами граф равен диораме графа. Кроме геометрического есть и другие способы задания графа.

Одним из них – матрица инциденций. МИ – это матрица с n – строки которые соответствуют вершинам и m – столбцами которые соответствуют ребрам. Для неориентированного графа столбец соответствующий ребру x_i x_j содержит 1 в строках соответствующий x_i x_j и 0 – в остальных строках.

(1;2) (1;3) (2;3) (3;4)

1 1 1 0 0

2 1 0 1 0

3 0 1 1 1

4 0 0 0 1

5 0 0 0 0

6 0 0 0 0

Для орграфа столбец соответствующий дуге x_i x_j содержит – 1 в строке кот. соответствует вершине x_i, 1 кот. Соответствует вершине x_j и 0 в остальных.

Петлю в таком случаи удобнее представлять другим значением в строке x_i.

(1;2) (1;3) (2;3) (3;4) (4;5) (5;6) (6;5) (6.6)

1 -1 -1 0 0 0 0 0 0

2 1 0 1 0 0 0 0 0

3 0 1 1 1 0 0 0 0

4 0 0 0 1 1 0 0 0

5 0 0 0 0 1 -1 1 0

6 0 0 0 0 0 1 -1 2

Более удобных и наиболее распространенный способ задания графа является матрица смежностей. МС – это квадратная матрица порядка n где b_ij = 1, если существует ребро соединения.

B = [ b_ij ]

Шины x_i x_j и b_ij = 0

1 2 3 4 5 6

1 0 1 1 0 0 0

2 1 0 1 0 0 0

3 1 1 0 1 0 0

4 0 0 0 0 1 0

5 0 0 0 0 0 1

6 0 0 0 0 1 0

Матрица смежностей неориентированного графа всегда является симметричной если граф имеет петли то на главной диагонали будет стоять первый.

Достоинством МС что с ее помощью можно за один шаг дать ответ на вопрос: существует ли ребро которое идет из вершины x_i в вершину x_j.

Матрица смежностей графа в общем случае не симметрична. Элемент b_ij этой матрицы равен 1 если есть дуга выходящая из вершины x_i и входит в вершину x_j в противном случаи b_ij = 0.

1 2 3 4 5 6

1 0 1 1 0 0 0

2 0 0 0 0 0 0

3 0 1 0 1 0 0

4 0 0 0 1 0 0

5 0 0 0 1 0 1

6 0 0 0 0 1 0

У многих случаях (практическое решение) используя взвешенные графы.

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

Для взвешенного графа по аналогии с матрицей сложности определяется матрица весов.

Весам несуществующих ребер или дуги обычно присваивают значение ∞. Иногда 0, в зависимости от задачи. Также весами ребер или дуг могут быть функции.

1 2 3 4 5 6

1 ∞ 3 3 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ ∞ ∞

3 ∞ 4 ∞ 2 ∞ ∞

4 ∞ ∞ ∞ ∞ ∞ ∞

5 ∞ ∞ ∞ 2 ∞ 5

6 ∞ ∞ ∞ ∞ 5 4