- •Основы теории графов
- •Введение
- •Глава 1. Способы задания графов. Операции над графами. Метрические характеристики графов. Упорядочивание элементов орграфов
- •1. Способы задания графов. Операции над графами. Метрические характеристики графов
- •Основные понятия и определения
- •1.2. Операции над графами
- •1.3. Маршруты, цепи, циклы
- •. Способы задания графов
- •1.5. Метрические характеристики графа.
- •1.6. Упорядочивание дуг и вершин орграфа
- •1.8. Определение экстремальных путей на графах.
- •1.9. Порядковая функция орграфа без контуров.
- •Вопросы для повторения.
- •Глава 2. Нахождение минимальных и максимальных путей на орграфах
- •1. Нахождение кратчайших путей. Алгоритм Дейкстры
- •2. Нахождение кратчайших путей. Алгоритм Беллмана-Мура
- •Алгоритм нахождения максимального пути
- •4. Особенности алгоритмов теории графов
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и клики
- •1. Деревья (основные определения)
- •2. Задача об остове экстремального веса
- •3. Обходы графов. Фундаментальные циклы
- •4. Клики, независимые множества
- •Вопросы для повторения.
- •Глава 4. Планарные графы
- •1. Планарность графов
- •2. Алгоритм укладки графа на плоскости
- •Вопросы для повторения.
- •Глава 5. Потоки в сетях
- •1. Потоки в сетях
- •Теорема Форда-Фалкерсона
- •Случайные графы
- •Заключение
- •Библиографический список
- •Оглавление
- •Основы теории графов
- •394026 Воронеж, Московский просп., 14
. Способы задания графов
1) Латинская матрица.
Направление дуг задается порядком букв в их названии.
Таблица 1
|
A |
B |
C |
D |
E |
A |
|
A B |
A C |
|
|
B |
B A |
|
|
B D |
|
C |
C A |
|
|
|
C E |
D |
|
D B |
|
|
|
E |
|
|
|
E D |
E E |
Рис. 13 .
Если граф не ориентированный, то в латинской матрице просто штрихуют соответствующие клетки в таблице.
2) Матрица смежности вершин.
A B C D E
Это квадратная матрица P порядка n, где n – число вершин. Её стоки и столбцы соответствуют вершинам графа. Элементы Pij матрице смежности равны числу дуг, идущих из i вершины в j. Если орграф не содержит параллельных дуг то матрица является бинарной и состоит только из 0 и 1.
В случае неориентированного графа ему вместе с ребрами xi,xj принадлежит ребро xj,xi, поэтому матрица смежности вершин будет симметрической.
Теорема. Графы изоморфны тогда и только тогда, кода их матрице смежности вершин получаются друг из друга одновременными перестановками строк и столбцов.
Следствие. Ранги матриц смежности вершин изоморфных графов равны.
Матрица смежности вершин однозначно определяет структуру графа.
Определение. Рангом графа называется ранг его матрицы смежности вершин. Обозначение: rang G.
3) Матрица смежности дуг.
Это квадратная матрица Q порядка m, где m – число дуг. Элементы qij этой матрицы равны 1, если дуга ui непосредственно предшествует дуге uj и равны 0 в остальных случаях. Для неориентированного графа элемент qij=1 если ui и uj смежны, и qij=0 в остальных случаях.
Это матрица смежности дуг для предыдущего графа без петли u9.
4) Матрица инциденций.
Это прямоугольная матрица R размерностью n x m, где m – число дуг, а n – число вершин. Элементы rij этой матрицы равны 1, если дуга ui исходит из i-ой вершины; -1, если дуга uj входит в i вершину; 0, если дуга не инцидентна i-ой вершине. В случае неориентированного графа элементами матрицы будут элементы 1 и 0, т.е. rij= 1, если вершина xi инцидентна ребру uj.
rij= 0, если вершина xi не инцидентна ребру uj.
Строки матрицы инциденций называется векторами инциденций графа G.
Матрица инциденций также однозначно определяет структуру графа.
5) Матрица весов - это матрица Ω=||ij||, где ij – вес ребра, соединяющего вершины xi и xj. Веса несуществующих ребер полагают равными 0 или в зависимости от приложений. Матрица весов является простым обобщение матрицы смежности вершин.
6) Матрица Кирхгофа графа G – квадратная матрица Bn×n=||bij||, n=Card S,
bij=-1, если вершины xi и xj смежны;
bij=0, если вершины xi и xj не смежны и i не равно j;
bij= P(xi), i=j.
Свойства матрицы Кирхгофа.
1. Суммы элементов в каждой строке и каждом столбце матрице B равны 0.
2. Алгебраические дополнения всех элементов матрицы B равны между собой.
7) Матрицы связности и достижимости.
Пусть P(G) – матрица смежности вершин графа G=(Sn, U), а D=E+P+P2+…+Pn. Введём матрицу C=||сij|| по правилу:
сij=1, если dij не равно 0,
сij=0, если dij равно 0.
Матрица C называется матрицей связности, если G – неорграф, и матрицей достижимости, если G –орграф.
В матрице C содержатся информация о существовании связей между различными элементами графа G посредством маршрутов. Это значит, что в графе G тогда и только тогда существует маршрут из вершины xi в вершину xj, когда cij=1.
8) Матрица контрдостижимости.
Определяется следующим образом:
Ln×n=||lij||.
lij= 1, если вершина xi достижима из вершины xj,
lij= 0, если вершина xi не достижима из вершины xj.
Теорема. L=CT.
Матрицы C и L используются для нахождения сильных компонент графа. Пусть F=C*L, где операция * означает поэлементное произведение матриц C и L: fij=сijlij. Элемент fij матрицы F равен 1 тогда и только тогда, когда вершины xi и xj взаимно достижимы. Т.о., сильная компонента орграфа, содержащая вершину xi, состоит из элементов xj, для которых fij=1.
П ример.
Рис. 14
;
По матрице F легко определить состав вершин трёх подграфов, образующих сильно связные компоненты исходного графа.
X2
X3
X6
X5
X4
G2
G3
Рис. 15