Метод графов

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

Одним из них – матрица инциденций. МИ – это матрица с 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