Нахождение ксс

ТеоремаЛюбая вершина орграфа принадлежит ровно одной КСС орграфа.

, где - множество вершин, достижимых из ,- множество вершин, из которых достижимо .

Пример

- группировка, - отношение влияния.

Кланы – совокупности группировок с равными «правами» по отношению друг к другу и к внешним группировкам.

Сети

Орграф, в котором отсутствуют контуры, называется сетью. В сети есть следующие особые элементы:

вершина-исток()

вершина-сток()

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

Циклы в графе Эйлеровы и Гамильтоновы циклы

Цикл в графе называется Эйлеровым, если любое ребро графа участвует в его образовании ровно один раз. Граф, содержащий Эйлеров цикл называетсяЭйлеровым.

Теорема ЭйлераГраф является Эйлеровым тогда и только тогда, когда степени всех его вершин четные.

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

Свойства «Эйлеровости» и «Гамильтоновости» являются независимыми.

Цикломатика графа

Пусть - граф. Цикл в графе может быть записан в виде , где

Пример

Каждый цикл может быть представлен в качестве двоичного вектора. Множество циклов образует пространство двоичных векторов.Цикломатический базис– совокупность линейно независимых циклов графа, с помощью которых могут быть получены все остальные циклы.Цикломатическое число графа - мощность базисной системы циклов графа .

Пример

Граф, у которого цикломатическое число равно 0, называется деревом(илиациклическим графом). Многокомпонентный ациклический граф называетсядеревом.Остов графа– частичный граф исходного графа, в котором число вершин и число компонент связности совпадает с числом вершин и числом компонент связности исходного графа, но цикломатическое число равно 0.

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

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			1	1
		1			1	1	1	1

Множество всех циклов графа:

Число циклов в графе не превосходит .

Пример

123

Теорема КенигаГраф двудолен тогда и только тогда, когда он не содержит циклов нечетной длины.

Разделяющие множества. Разрезы

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

Пример

- разделяющее множество, разрез.

цикл разрез (коцикл)

Коциклический ранг - число линейно независимых коциклов графа..

Пример

.