Система независимых циклов

Замкнутый маршрут в неориентированном графе называется циклом. Для ориентированного графа определено аналогичное понятие контура как замкнутого пути.

Определение системы независимых циклов

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

Для пояснения линейной комбинации цикла рассмотрим совокупность двух циклов данного графа:

Обход представимых циклов:

Как указано на рис.35, исключая из обхода ребро пройденное туда и обратно получаем новый цикл: . Этот цикл получен в результате линейной комбинации исходных циклов и является линейно-зависимым от них.

Приведём формальное определение.

Сопоставим каждую цифру в двоичный m-разрядный вектор, где m – число рёбер графа.

Перенумеруем рёбра: для i-ого цикла компоненты вектора -

Тогда линейной комбинацией векторов называется результат векторной операции сложения по модулю 2.

Системой независимых циклов графа называется максимальная совокупность линейно-независимых циклов графа.

Цикломатическое число (ню)

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

Число циклов , где m – число рёбер, n – число вершин, p – число компонент связности.

Система независимых циклов плоского (планарного) графа

Граф, который можно представить на плоскости без пересечения его рёбер называется плоским или планарным. Края конечных граней плоского изображения графа составляют систему независимых циклов.

Пример:

Дерево. Остов граф

Конечный связный граф без циклов называется деревом.

Из свойств отсутствия циклов и связности следует, что т.е. у дерева количество рёбер на 1 меньше, чем вершин.

Вершины дерева, к которым инцидентно только одно ребро, называются листьями или висячими вершинами.

Одна из вершин дерева может быть объявлена корнем дерева. Существует различных деревьев на n вершинах. Доказательство этой цифры сводится к двум конструктивным построениям:

- сведению дерева к набору номеров вершин и, наоборот,

- восстановлению по набору дерева.

Однозначность этого процесса позволяет заключить, что число деревьев равно числу наборов.

Процесс построения набора по дереву

Этот процесс состоит из следующих этапов:

Рассматриваем дерево с количеством вершин . Вначале набор пуст. Если преобразованное дерево сохранило только 2 вершины, то процесс заканчивается, иначе находим среди листьев вершины с наименьшим номером. Эту вершину вместе с инцидентной ей ребром исключаем из дерева, а в набор включаем номер вершины, с которой соединена удаляемая вершина.

Процесс восстановления дерева по набору

1. Строим набор В – последовательность номеров вершин

2. Если в наборе В остаётся всего 2 номера вершин, то соединим их и искомое дерево построено, иначе находим в наборе В минимальный номер, которого нет в наборе А и соединяем эту вершину с вершиной, номер которой указан первым в наборе. Вычеркиваем эти номера из наборов А и В. Снова выполняем шаг 2.

Любой граф без циклов называется ациклическим (или лесом). Компонентами леса являются деревья.

Остов графа.

Если граф несвязный, то рассматриваются его отдельные компоненты. Остов такого графа определяется, как совокупность остовов его компонент.

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

В общем случае, для графа можно построить несколько остовов.