Основная образовательная программа cb. 5005. 2016 Прикладная математика, фундаментальная информатика и программирование
 Скачать 0.51 Mb.
|
Определение 1.10.Циклическим пространством  графа  называется подпространство  , сформированное из реберных множеств простых циклов.В циклическом же пространстве содержится полезная для данного исследования информация о графе .Лемма 1.1.В графе реберные множества порожденных циклов формируют циклическое пространство . Доказательство.Пространство сформировано множествами ребер простых циклов, поэтому если показать, что для простого цикла  его реберное множество сформировано множествами ребер порожденных циклов, то мы получим требуемое. Воспользуемся индукцией по количеству ребер. Пусть — не порожденный цикл. Тогда простой цикл имеет хорду  , которая разделяет его на два подцикла  и  . Из чего следует, что  , а для и утверждение доказано. ∎1.3. Пространство разрезов Определение 1.11.Разрезом называется множество ребер производящие произвольное разбиение множества узлов  на два непересекающихся множества  и  , обозначается как  . Пространство разрезов  — это подпространство , сформированное всем множеством разрезов. Для узлов  разрез из всех смежных узлу  ребер будет определяться как  .Замечание 1.2.Разрез состоит только из ребер графа, разделяющих любые две части множества его узлов. Лемма 1.2.1. Если  и  — два разреза, то и  — разрез. 2. Множество порождено всеми разрезами графа и пустым множеством  . 3. Разрезы  формируют .Доказательство.1. Пусть разрезы  и  . Тогда — множество, состоящее из тех ребер, что пересекают только одну из пары разрезов, то есть концы ребер располагаются в смежных частях одного из двух разбиений . Поэтому и — разрез. 2. Следовательно, все множество разрезов замкнуто относительно операции симметрической разности. 3. Пусть  — любой из разрезов. Тогда сумма всех разрезов вида , где  есть  , так как сумма — это операция симметрической разности, из чего следует, что при сложении разрезов все ребра между узлами сократятся и останутся лишь ребра разреза . ∎ |