Фундаментальные циклы и разрезы

Циклы и коциклы

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

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

Здесь рассматриваются только простые циклы и разрезы, далее слово «простые» опускается.

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

Независимые множества циклов и коциклов

Рассмотрим операцию Å сложения по модулю 2 или симметрической разности над множествами ребер:

Множество М называется зависимым или линейной комбинацией множеств {M_i}ⁿ_i=1, если

Множество циклов { Z _i}ⁿ_i=1 называется независимым, если ни один из циклов Z _i не является линейной комбинацией остальных.

Множество разрезов { S _i}ⁿ_i=1 называется независимым, если ни один из разрезов S _i не является линейной комбинацией остальных.

Циклический и коциклический ранг

Максимальное независимое множество циклов (или минимальное множество ци­клов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы фундаментальной системы называются фундаментальными, а ко­личество циклов в (данной) фундаментальной системе называется циклическим рангом, или цикломатическим числом, графа G и обозначается m (G). Максималь­ное независимое множество коциклов (разрезов) (или минимальное множество коциклов, от которых зависят все остальные) называется фундаментальной си­стемой коциклов (разрезов). Коциклы (разрезы) фундаментальной системы назы­ваются фундаментальными, а количество коциклов в (данной) фундаментальной системе называется коциклическим рангом, или коцикломатическим числом, графа G и обозначается m^* (G).

Пусть T (V, E_T) — остов графа G (V, T). Кодеревом T^* (V, E^*_T)остова Т называется остовный подграф, такой что E^*_T = Е \ E_T. (Кодерево не является деревом!) Ребра кодерева называются хордами остова.

ТЕОРЕМА Если G — связный граф, то

m (G) = q – p + 1, m *(G)= p – 1.

Эйлеров цикл

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

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

ТЕОРЕМА Если граф G связен и нетривиален, то следующие утверждения эквивалентны:

G — эйлеров граф;

каждая вершина G имеет четную степень;

множество ребер G можно разбить на простые циклы.

Гамильтонов цикл

Если граф имеет простой цикл, содержащий все вершины графа (по одному ра­зу), то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом.

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

ТЕОРЕМА (Дирак) Если в графе G (V, E) " u Î V d (v) ³ р /2, то граф G является гамильтоновым.

Дата добавления: 2014-12-27