Алгоритм нахождения базисной системы разрезов

1. Построить остов графа . 2. Удалять поочередно по одному ребру (остов распадается на две компоненты). Добавить к разрезу те хорды, концы которых принадлежат разным компонентам.

Пример

	остов					хорды
	1					1
		1					1	1
			1			1	1	1
				1		1	1
					1	1	1

Число коциклов в графе равно .

Устойчивость графа Внешняя устойчивость графа

Пусть - некоторый граф. Подмножество вершин называетсямножеством внешней устойчивости, если 1)2)

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

Пример

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Множества внешней устойчивости:

Внешняя устойчивость орграфа

есть множество положительной внешней устойчивостиорграфа, если 1)2).Число положительной внешней устойчивостиорграфа – мощность минимального множества положительной внешней устойчивости.

есть множество отрицательной внешней устойчивостиорграфа, если 1)2).Число отрицательной внешней устойчивостиорграфа – мощность минимального множества отрицательной внешней устойчивости.

Поиск множеств положительной (отрицательной) внешней устойчивости орграфа производится по модифицированной матрице смежности (модификация заключается в добавлении единичной главной диагонали) с помощью покрытия. При этом покрытия столбцов строками порождают все множества положительной внешней устойчивости, а покрытия всех строк столбцами порождают все множества отрицательной внешней устойчивости.

Пример

1 1 1 1 1 1 1 1 1 1 1 1 1 1

Множества положительной внешней устойчивости:

Множества отрицательной внешней устойчивости: