- •Основные объекты графов
- •Способы задания графов
- •Изоморфизм на графах
- •Элементы графов
- •Степень вершины. Степень графа
- •Типы графов
- •Операции на графах
- •Связность в графах Понятие цепи
- •Связность графа
- •Компоненты связности графа
- •Нахождение компонент связности
- •Связность в орграфах
- •Нахождение ксс
- •Циклы в графе Эйлеровы и Гамильтоновы циклы
- •Цикломатика графа
- •Алгоритм нахождения базисной системы циклов
- •Разделяющие множества. Разрезы
- •Алгоритм нахождения базисной системы разрезов
- •Устойчивость графа Внешняя устойчивость графа
- •Внешняя устойчивость орграфа
- •Внутренняя устойчивость графа
- •Алгоритм нахождения пустых подграфов
- •Полные подграфы. Плотность графа
- •Алгоритм нахождения полных подграфов
Алгоритм нахождения базисной системы разрезов
1. Построить остов графа . 2. Удалять поочередно по одному ребру (остов распадается на две компоненты). Добавить к разрезу те хорды, концы которых принадлежат разным компонентам.
Пример
|
остов |
хорды | ||||||
1 |
|
|
|
|
1 |
|
| |
|
1 |
|
|
|
|
1 |
1 | |
|
|
1 |
|
|
1 |
1 |
1 | |
|
|
|
1 |
|
1 |
1 |
| |
|
|
|
|
1 |
1 |
1 |
|
Число коциклов в графе равно .
Устойчивость графа Внешняя устойчивость графа
Пусть - некоторый граф. Подмножество вершин называетсямножеством внешней устойчивости, если 1)2)
Мощность минимального множества внешней устойчивости называется числом внешней устойчивости графа. Для того, чтобы найти все множества внешней устойчивости графа, надо найти все покрытия модифицированной матрицы смежности графа. Модификация заключается в добавлении единичной главной диагонали.
Пример
|
Множества внешней устойчивости:
Внешняя устойчивость орграфа
есть множество положительной внешней устойчивостиорграфа, если 1)2).Число положительной внешней устойчивостиорграфа – мощность минимального множества положительной внешней устойчивости.
есть множество отрицательной внешней устойчивостиорграфа, если 1)2).Число отрицательной внешней устойчивостиорграфа – мощность минимального множества отрицательной внешней устойчивости.
Поиск множеств положительной (отрицательной) внешней устойчивости орграфа производится по модифицированной матрице смежности (модификация заключается в добавлении единичной главной диагонали) с помощью покрытия. При этом покрытия столбцов строками порождают все множества положительной внешней устойчивости, а покрытия всех строк столбцами порождают все множества отрицательной внешней устойчивости.
Пример
|
Множества положительной внешней устойчивости:
Множества отрицательной внешней устойчивости: