Main Алгоритмические методы в теории графов.

Алгоритмические методы в теории графов.

0 / 0
How much do you like this book?
What’s the quality of the file?
Download the book for quality assessment
What’s the quality of the downloaded files?
Year:
2012
Publisher:
ЗНУ
Language:
russian
Pages:
243
ISBN 10:
9665994085
ISBN 13:
9789665994084
File:
DJVU, 2.16 MB
Download (djvu, 2.16 MB)
Conversion to is in progress
Conversion to is failed

Most frequent terms

 
0 comments
 

To post a review, please sign in or sign up
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

Combinatorial Functional Equations: Basic Theory

Year:
2019
Language:
english
File:
PDF, 1.78 MB
0 / 0
Курапов СВ. АЛГОРИТМИЧЕСКИЕ МЕТОДЫ В ТЕОРИИ ГРАФОВ Запорожье-2012

Оглавление Введение 5 Глава 1 СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ 7 1.1. Генерирование соединений 7 1.1.1. Перестановки 7 1.1.2. Сочетания 10 1.1.3. Размещения 11 1.2. Элементы теории графов 11 1.3. Связанные списки 15 1.4. Алгоритм формирования матрицы инциденций 17 1.5. Подграфы и суграфы 19 1.6. Клики графа, множество вершинных покрытий и независимое множество вершин 19 1.7. Алгоритм выделения клик графа методом корневого дерева 22 Глава 2 ПРОСТРАНСТВО СУГРАФОВ 29 2.1. Деревья, разрезающие множества и циклы 29 2.2. Операции над суграфами 33 2.3. Графы и пространство суграфов 33 2.4. Размерность подпространств циклов и разрезов 35 2.5. Связь между подпространствами циклов и разрезов 35 2.6. Ортогональность подпространств циклов и разрезов 36 2.7. Свойства характерных подмножеств подпространства циклов и 40 подпространства разрезов 2.8. Выделение конечного множества единичных циклов ( циклов) 45 2.9. Множество ребер и построение множества единичных циклов 47 2.10. Фундаментальная и базисная системы циклов и разрезов 51 2.11. Алгоритмы для выделения множества единичных разрезов и циклов. 59 2.11.1. Формирование множества единичных циклов алгоритмом поиска в ширину 60 2.11.2. Формирование множества единичных циклов из циклов полного графа. 61 2.12. Множество единичных разрезов и циклов как инварианты графа 63 Глава 3 СВОЙСТВА МНОЖЕСТВА ЕДИНИЧНЫХ ЦИКЛОВ 66 3.1. 0-подмножество единичных циклов и дубль-циклы в графе 66 3.2. Алгоритм выделения множества простых циклов и дубль-циклов в графе 67 3.3. Метод эталона для нахождения дубль-циклов в полных графах 72 3.4. Свойства 0-подмножеств, состоящих из единичных циклов и дубль- 99 циклов Глава 4 ПРОГРАММНОЕ И АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СИСТЕМЫ РЕШЕНИЯ ЗАДАЧ МЕТОДАМИ ТЕОРИИ ГРАФОВ. 105 4.1. Функциональные задачи теории графов 105 4.2. Вычислительная сложность алгоритмов 111 4.3. Структура программного обеспечения и организация вычислительного процесса 113 4.3.1. Модуль DRAWNAT 113 4.3.2. Модуль RASTAMAG 11; 9 4.3.3. Модуль RASMAPKG 123 4.3.4. Модуль RASSWAZI 127 4.3.5. Модуль RASMOSTG 132 4.3.6. Модуль RASRANGR 137 4.3.7. Модуль RARRANGM 140 4.3.8. Модуль RASKLIKG 144 4.3.9. Модуль RASWEPOG 150 4.3.10. Модуль RASWNYPG 157 4.3.11. Модуль RASTAYCG 163 4.3.12. Модуль RASYROWG 171 3

4.3.13. Модуль TREENEW 185 4.3.14. Модуль DLPRIMER 200 Глава 5 ВСТРОЕННЫЕ ПРОЦЕДУРЫ 208 5.1. Встроенные процедуры системы 208 5.1.1. Procedure InputText 208 5.1.2. Procedure DrawCurcor 208 5.1.3. Procedure Formlncide 208 5.1.4. Procedure DrawTabl 209 5.1.5. Procedure DrawContur 209 5.1.6. Procedure FormSvart 209 5.1.7. Procedure FormVolna2 211 5.1.8. Procedure RandomizeGraph 212 5.1.9. Procedure RandomizeGraphNM 212 5.1.10. Procedure RandomizeGraphSave 213 5.1.11. Procedure FormStl 213 5.1.12. Procedure FormStart 214 5.1.13. Procedure FormKlicM2 214 5.1.14. Procedure FormStek 215 5.1.15. Procedure FormSave 216 5.1.16. Procedure FormSt 217 5.1.17. Procedure FormMs2 217 5.1.18. Procedure FormVerPoc 218 5.1.19. Procedure FormVolna 219 5.1.20. Procedure FormKpris 219 5.1.21. Procedure FormDiz 220 5.1.22. Procedure FormSwigug 221 5.1.23. Procedure FormDozas 221 5.1.24. Procedure FormSoasda 223 5.1.25. Procedure FormVegin 224 5.1.26. Procedure FormVolnal 226 5.1.27. Procedure FormTreeGr 226 5.1.28. Procedure FormTreeRgr 227 5.1.29. Procedure FormMatrixMinus 228 5.1.30. Procedure FormVolna2Tree 229 5.1.31. Procedure FormCircleFund 230 5.1.32. Procedure FormSecheniaj 231 5.1.33. Procedure FormOOO 232 5.1.34. Procedure FormOOOl 11 233 5.1.35. Procedure FormMonitor 233 5.1.36. Procedure FormPernum 234 5.1.37. Procedure Shell2 235 5.1.38. Procedure FormPostr 235 5.1.39. Procedure FormYk 237 5.1.40. Procedure FormRetzen 238 5.1.41. Procedure FormObr 239 Литература 241 4

Введение Настоящая монография основана на материале лекций, читающихся в Запорожском национальном университете для студентов, обучающихся по специальностям "Прикладная математика", "Информационные системы" и «Программная инженерия». Это лекции по разделу "Теория графов" курса «Дискретная математика», по курсу "Анализ и разработка алгоритмов", «Построение и анализ алгоритмов», «Вычислительные методы теории графов», «Математическая логика и теория алгоритмов», «Алгоритмы и структуры данных» и других общеобразовательных и специализированных предметов. В этой книге под одной обложкой собраны теоретические и практические методы, относящиеся к одной сравнительно молодой области человеческой деятельности. Это деятельность по созданию и исследованию алгоритмов, для которой пока не придумано общеупотребительного объединяющего названия (она является частью того, что охватывается терминами «computer science» и «информатика»). Работа в этой области требует определенных математических знаний и представления о проблемах, связанных с разработкой компьютерных программ, но она не сводится к математике или программированию. Ее роль можно сравнить с ролью технологии по отношению к науке и производству. Ведущий системный аналитик Дональд Кнут обозначил данную деятельность как «искусство программирования» [17-19]. В своей работе «Искусство программирования для ЭВМ» он предлагает массу рецептов по созданию алгоритмов и программ и учит, как самостоятельно находить эти рецепты Изучение алгоритмов является самой сердцевиной науки о вычислениях. Приемы создания алгоритмов и алгоритмические методы рассматриваются во многих не только классических университетских курсах, но и во многих инженерных дисциплинах. К настоящему времени в мировой практике накоплен огромный опыт разработки алгоритмов для решения задач комбинаторного характера, значительная часть которых - задачи на графах. Целью учебного пособия является ознакомление с важнейшими достижениями в этой области. В нем излагаются основные понятия и математические факты из теории графов и наиболее интересные и важные алгоритмы для решения задач на графах. Большое внимание уделяется умению выбрать алгоритмическую структуру для конкретно решаемой задачи, обоснованию алгоритмов и анализу их трудоемкости. Кроме теоретического материала, пособие содержит набор алгоритмов и процедур под общим названием «система GRAPHMODEL» выполненных на языке Pascal и образующей вместе с настоящим учебником единый образовательный модуль. Набор алгоритмов и процедур представленный в данной работе, предназначен для обучения студентов и пользователей методам и приемам решения прикладных задач теории графов и проведения самостоятельных 5

расчетов. Данный набор ставит своей целью дать в руки исследователей и пользователей любого уровня орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и к другим число абстрактным дисциплинам, и включает следующие задачи: • выделение множества непополнимых клик графа; • выделение внутренне устойчивых подмножеств графа; • выделение вершинных покрытий графа; • выделение множества единичных циклов (τ-циклов) графа; • формирование множества уровневых суграфов графа; • проверка графа на связность; • нахождение мостов и точек сочленения в графе; • моделирование случайных графов; • выделение фундаментальных циклов и разрезов. В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, уделяя внимание в первую очередь структуре связанных списков. Книга не требует от читателя специальной подготовки, только предполагает его знакомство с какими-либо языками программирования высокого уровня, такими как Pascal. Вместе с тем она будет полезна специалистам по разработке программ и алгоритмов и может быть использована как учебное пособие для студентов и аспирантов, специализирующихся в области компьютерных наук. 6

Глава 1. Структуры данных и алгоритмы Выбор структур данных может существенно повлиять на скорость и эффективность реализованного алгоритма. В этой главе мы рассмотрим структуры данных типа связанные списки и некоторые приемы, применяемые в алгоритмах, которые часто оказываются полезными [1-4,6-9,11,20,24,32]. 1.1. Генерирование соединений Общим именем соединений принято обозначать следующие три типа комбинаций, составляемых из некоторого числа различных между собой предметов (элементов). 1.1.1. Перестановки Возьмем η различных элементов ai, a2,...an; и будем переставлять эти элементы всевозможными способами, оставляя неизменными их число и меняя лишь их порядок. Каждая из получающихся таким образом комбинаций (в том числе и первоначальная) носит название перестановки. Общее число перестановок из η элементов вычисляется как Рп= п\ Закодируем элементы натуральными числами и займемся алгоритмом генерирования всех п\ перестановок «-элементного множества. Этой проблеме посвящено множество публикаций, в том числе хочется отметить работу [23], где представлены три изящных алгоритма генерирования перестановок. Рассмотрим алгоритм, основанный на идее записи инверсных чисел [17-19,29]. Рассмотрим следующую запись целых чисел 8 9 Перед единицей находится 3 числа больше самой 1. Перед двойкой находится 4 числа больше двух. Перед тройкой находится 2 числа больше 3. Перед четверкой находится 4 числа больше 4. Перед пятью находится 0 чисел больше 5. Перед шестью находится 2 числа больше 6. Перед семью находится 2 числа больше 7. Перед восьмью находится 0 чисел больше 8. Перед девятью находится 0 чисел больше 9. Таким образом, инверсная запись чисел будет Прямая запись Инпепсная 1 3 2 4 3 2 4 4 5 0 6 2 7 2 8 0 9 0 Обратно, перед 9, нуль чисел больше 9. Прямая запись 9. Перед 8, нуль чисел больше 8. Прямая запись 8 9. Перед 7, два числа больше 7, прямая запись 8 9 7 и т.д.

8 8 5 5 5 5 5 9 9 8 8 8 8 8 7 6 9 9 3 3 3 7 6 6 9 9 1 7 4 6 2 9 7 4 6 2 7 4 6 7 4 Применяя инверсную запись чисел, предлагается следующий алгоритм перебора всех перестановок. Данный алгоритм основан на формировании инверсной записи чисел с последующей расшифровкой. Он основан на факте существования всех инверсных записей от О до максимальной инверсной записи чисел. Максимальная инверсная запись характеризуется записью чисел в порядке убывания. Пример 1.1. Для 4 чисел максимальная инверсная запись имеет вид [3 2 1 0]. Номера столбцов Максимальная инверсная запись Начальная инверсная запись +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец 1 3 0 0 0 0 0 0 0 0 2 2 0 0 0 1 1 1 2 2 3 1 0 + 1 1 + 1 2 0 + 1 1 + 1 2 0 + 1 1 + 1 4 0 0 0 0 0 0 0 0 0 -> -> -> -> -> -> 1 1 1 1 1 1 2 2 3 4 3 4 3 4 2 2 4 3 4 3 4 3 2 2 Расшифровка Расшифровка Расшифровка Расшифровка Расшифровка Расшифровка

Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем Число во 2-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем Число во 2-м столбце 0 0 1 1 1 1 1 1 1 1 1 1 2 3 0 0 0 1 1 1 2 2 2 3 2 0 0 + 1 1 + 1 2 0 + 1 1 + 1 2 0 + 1 1 + 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 3 4 3 4 1 3 1 4 1 2 1 2 1 4 1 3 4 3 4 3 2 2 Расшифровка Расшифровка Расшифровка Расшифровка Расшифровка Расшифровка

больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем Число во 2-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец 2 2 0 0 0 + 1 1 0 0 + 1 2 0 2 0 2 2 1 1 0 + 1 1 0 0 + 1 2 1 2 0 2 2 2 2 0 + 1 1 0 0 + 1 2 2 2 0 2 3 3 0 0 0 0 0 + 1 -» -» -» -» -» 2 3 14 Расшифровка 2 4 13 Расшифровка 3 2 14 Расшифровка 4 2 13 Расшифровка 3 4 12 Расшифровка 4 3 12 Расшифровка 2 3 4 1 Расшифровка 10

Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи левый Прибавляем 1 ι столбец, правые столбцы обнуляем +1 в предпоследний столбец Новая инверсная запись +1 в предпоследний столбец Число в 3-м столбце больше, чем в максимальной инверсной записи Прибавляем 1 в левый столбец, правые столбцы обнуляем +1 в предпоследний столбец Максимальная инверсная запись и конец работы алгоритма 3 0 10 —» 2 4 3 1 Расшифровка + 1 3 0 2 0 3 1 0 0 -> 3 2 4 1 Расшифровка + 1 3 110 -> 4 2 3 1 Расшифровка + 1 3 12 0 0 0 -> 3 4 2 1 Расшифровка + 1 1 0 -> 4 3 2 1 Расшифровка 1.1.2. Сочетания Из различных η элементов будем составлять группы по т элементов в каждой, не обращая внимания на порядок элементов в группе. Получающиеся при этой комбинации элементы называются сочетаниями из η элементов по т. Общее число различных между собой сочетаний обозначается С™. Это число можно представить формулой: Ст = (1.1) т\(п — т)\ Предлагается следующий алгоритм перебора всех сочетаний. Он основан на факте существования максимальной записи сочетания чисел. Максимальная запись характеризуется записью т чисел, имеющих максимальное значение. Пример 1.2. Для сочетания трех чисел из пяти максимальная запись имеет вид 3 4 5. Номера столбцов Максимальная запись сочетаний Начальная запись сочетаний +1 в последний столбец 1 3 1 2 4 2 3 5 3 + Сочетание 11

Новая запись сочетаний +1 в последний столбец Новая запись сочетаний +1 в последний столбец Число в 3-м столбце больше, чем в максимальной записи сочетаний Прибавляем 1 в левый столбец, а значения правых столбцов изменяется на 1 по отношению к предыдущему +1 в последний столбец Новая запись сочетаний +1 в последний столбец Число в 3-м столбце больше, чем в максимальной записи сочетаний Прибавляем 1 в левый столбец, а значения правых столбцов изменяются на 1 по отношению к предыдущему +1 в последний столбец Число в 3-м столбце больше, чем в максимальной записи сочетаний Число во 2-м столбце больше, чем в максимальной записи сочетаний Прибавляем 1 в левый столбец, а значения правых столбцов изменяются на 1 по отношению к предыдущему +1 в последний столбец Новая запись сочетаний +1 в последний столбец 1 5 + 1 + 1 1 2 6 + 1 + 1 1 3 6 + 1 1 4 6 + 1 + 12 4 Сочетание 12 5 Сочетание 13 4 Сочетание 13 5 Сочетание 14 5 Сочетание 2 3 4 Сочетание 2 3 5 Сочетание 12

Число в 3-м столбце больше, чем в максимальной записи сочетаний Прибавляем 1 в левый столбец, а значения правых столбцов изменяются на 1 по отношению к предыдущему +1 в последний столбец Число в 3-м столбце больше, чем в максимальной записи сочетаний Число во 2-м столбце больше, чем в максимальной записи сочетаний Прибавляем 1 в левый столбец, а значения правых столбцов изменяются на 1 по отношению к предыдущему. 1 2 3 6 2 4 5 + 1 2 4 2 5 3 4 6 5 Сочетание Максимальная запись сочетаний и конец работы алгоритма Впредь алгоритмы такого типа будем называть «бегущей строкой». 1.1.3. Размещения Будем составлять из η различных элементов группы по т элементов в каждой, располагая взятые т элементы в различном порядке. Получающиеся при этом комбинации называются размещениями из η элементов по т. Общее число размещений из η элементов по т обозначается А™ . Это число равно произведению т последовательных целых чисел, из которых наибольшее равно η Атп = η (п-1) (п-2)...[п-(т-1)] (1.2) Алгоритм генерации размещений представляет собой сочетание алгоритма генерации всех перестановок и алгоритм генерации сочетаний. 1.2. Элементы теории графов Введем несколько основных понятий теории графов. Установим ряд результатов, основанных на этих понятиях. 13

Определение 1.1. Точное определение графа состоит в том, что задаются два множества (первое из них обязательно непустое) и предикат, указывающий, какую пару элементов первого множества соединяет тот или иной элемент второго. Именно, дан граф G = (X,U;P), если даны два множества X, U и трехместный предикат Ρ <=> Pg <=> Т*(х,у,и), удовлетворяющий следующим двум условиям [15]: а) предикат Ρ определен на всех таких упорядоченных тройках элементов х,у,и, для которыхх,у еХии elJ; б) \/иЗх,у{Р(х,и,у) & \/х ,у [Р(х ,и,у )=>(х = х &у=у) ν (х = у &у = х )]} (1-3) элементы множества X называются вершинами, элементы множества U называются ребрами, а предикат Ρ - инцидентор графа G; высказывание V(x,u,y) читается так: ребро и соединяет вершину χ с вершиной у, или и соединяет упорядоченную пару вершин ху. Условие б) говорит о том, что каждое ребро графа соединяет какую-либо пару ху его вершин, но кроме этой пары может соединять еще только обратную пару ух. Определение 1.2. Любые две вершины х,у е X графа G = (X,U;P) называются смежными, если существует ребро и, соединяющее эти вершины, т.е и = (х,у). Если ребро u g U графа G = (X,U;P) соединяет вершины х,у е X т.е. и=(х,у), то говорят, что ребро и инцидентно вершинам х,у, и наоборот, вершины х,у инцидентны ребру и. Определение 1.3. Все ребра с одинаковыми концевыми вершинами называются кратными или параллельными. Кроме того, концевые вершины ребра не обязательно различны. Если и = (х,х), то ребро и называется петлей. Граф называется простым, если он не содержит петель и кратных ребер. Определение 1.4. Граф, не имеющий ребер, называется пустым. Определение 1.5. Граф, не имеющий вершин (и, следовательно ребер), называется нуль- графом. Определение 1.6. Локальной степенью ά(χ) вершины д: е X называют число ребер, инцидентных этой вершине. Иногда степень вершины называется также её валентностью. Количество ребер графа обозначается буквой т, а количество вершин в графе - буквой п. Графически граф может быть представлен диаграммой, в которой вершина изображена точкой или кружком, а ребро - отрезком линии, соединяющим точки или кружки, соответствующие концевым вершинам графа. Например, если X = {хьХ2,хз,Х4} и U = {ui,u2,U3,U4,u5,u6} такие, что Ui = (хьх2), и2 = (хьхД и3 = (х2,хз), и4 = (хьхз), и5 = (х3,Х4), и6 =(хз,хз), и тогда этот граф G = (X,U;P) может быть представлен диаграммой на рисунке 1.1. Следующие теоремы справедливы для всех графов [30,33]. Теорема 1.1. Сумма степеней вершин графа G равна 2т, где m-число ребер графа G. 14

Теорема 1.2. Число вершин нечетной степени в любом графе четно. Ul Рис. 1.1. ГрафС С целью удобства записи мы часто будем обозначать граф G = (X,U;P) сокращенной записью - G = (X,U), подразумевая при этом, что инцидентор задан. Определим теперь понятие дополнение графа. Определение 1.7. Граф G = (X,U) называется дополнением простого графа G = (X,U), если ребро (xi,Xj) входит в U в том и только в том случае, если оно не входит в U. Другими словами, две вершины Xi и Xj смежны в G тогда и только тогда, когда они несмежны в G. На рис. 1.2 представлен граф и его дополнение. а) исходный граф б) его дополнение Рис 1.2. Граф и его дополнение. Определение 1.8. Маршрутом в графе называется чередующаяся последовательность вершин и ребер хо, щ, ,х\, ,..., хп-\, ип, ,хп ,' эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам - предшествующей и последующей. Определение 1.9. Цепь - маршрут, у которого все ребра различны. Определение 1.10. Путь - маршрут, у которого все вершины различны. Определение 1.11. Цикл - это замкнутая цепь. Рис. 1.3. ГрафС Определение 1.12. Число ребер в пути называется длиной пути. Аналогично определяется длина цикла. 15

Ребро графа G называется циклическим, если в графе G существует цикл, содержащий данное ребро. В противном случае ребро называется нециклическим. На рис. 1.3 все ребра, за исключением ию, циклические. Например, на рис. 1.3 последовательность χι, щ, хг, иг, хз является путем, а последовательность χι, щ, Х2, Щ, xs, Щ, Х4, из, χι - циклом. Необходимо указать следующие свойства путей и циклов. 1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 2. Каждая вершина цикла имеет степень 2 или другую четную степень. 3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин. Определение 1.13. Две вершины в теории графов xj, Xj называются связанными в графе G, если в нем существует путь Xj —> xj. Вершина может быть связана сама с собой. Определение 1.14. Граф G называется связным, если в нем существует путь между каждой парой вершин. Рассмотрим несвязный граф G = (X,U). Тогда множество вершин X графа G можно разбить на такие подмножества Χι, Х2,...,ХР, что вершинно-порожденные подграфы <Xi>, i = 1, 2,..., ρ связны, и никакая вершина подмножества Xi не связана ни с какой вершиной подмножества Xj, j -φ- i. Подграфы <Xi>, i = 1, 2,..., ρ называются компонентами графа G. О О О О О Gi G2 G3 G4 Рис. 1.4. Граф G с компонентами Gi, G2, G3, G4. Определение 1.15. Полный граф G = (X,U) - простой граф, в котором каждая пара вершин смежна. Если полный граф G имеет η вершин, то он обозначается через Кп. Полный граф Кп имеет п(п-1)/2 ребер. Определение 1.16. Граф G называется однородным, если в нем все вершины имеют равную степень. Если граф G однороден и d(xi) = г для всех вершин Xi в G, то G называется г- однородным графом. Определение 1.17. Граф G называется двудольным графом, если множество его вершин X можно разбить на два таких подмножества Χι и Х2, что каждое ребро, принадлежащее U, имеет 16

одну концевую вершину в подмножестве Χι, а другую - в подмножестве Хг. Непересекающееся разбиение (Х^Хг) называется двудольным разбиением. Рис. 1.5. Граф К5. Рис. 1.6. 4-однородный граф. Определение 1.18. Граф G называется к-дольным графом, если множество его вершин X можно разбить на к таких подмножеств Χι, Хг, ..., Хк, что каждое ребро, принадлежащее U, имеет одну концевую вершину в некотором подмножестве Xj, а другую - в некотором подмножестве Xj, i Φ j. Определение 1.19. Вершина Xj графа G является точкой сочленения графа G, если граф G - Xi состоит из большего числа компонент, чем G. Рис. 1.7. Точка сочленения графа. Определение 1.20. Граф G называется связным, если в нем существует путь между каждой парой вершин. Определение 1.21. Граф называется ациклическим, если он не содержит циклов. 1.3. Связанные списки Так как мы в основном будем рассматривать комбинаторные алгоритмы на графах, то рассмотрим структуры данных под названием «связанные списки» для оптимального хранения и извлечения информации. Любой инцидентор графа Ρ можно описать его матрицей смежностей. Рис. 1.8. ГрафС Пусть задан граф G, представленный на рис. 1.8, и его матрица смежностей.

Χι Χ2 Хз Χ4 Xs Хб Χ? 1 1 11 1 11 1 11 111 11 11 1 111 1 11 1 5 8 11 15 18 21 24 Χι X2 Хз X4 Xs Хб Χ? Учитывая, что матрица смежностей разрежена, будем хранить информацию в двух связанных списках (массивах). Первый список описывает количество смежных вершин к данной вершине. Поставим в соответствие данному списку идентификатор MY. Для этого примера: MY Это говорит о том, что локальная степень 1-ой вершины равна MY(2) - MY(1) = 5-1 =4. Локальная степень 2-ой вершины равна MY(3) - MY(2) = 8-5 =3. Локальная степень 3-ей вершины равна MY(4) - MY(3) = 11-8 =3 т.д. Если номер вершины N, то локальная степень вершины определится как MY(N+1)-MY(N). Следующая таблица - это последовательность смежных вершин, имеющая идентификатор MS. Следует заметить, что для получения экономных записей, мы будем обозначать и вершины и ребра цифрами, каждый раз оговаривая это отдельно. 12345678 MS ~~ MS MS Например, 1-ая вершина смежная с вершинами 2,4,6,7, которые находятся в ячейках массива MS определяемых, начиная с номера MY(1)=1 и оканчивая номером MY(2)-1=5-1=4, то есть с 1-ой ячейки по 4-ую ячейку. 2-ая вершина смежная с вершинами 1,3,4, которые находятся в ячейках массива MS определяемых, начиная с номера MY(2)=5 и оканчивая номером MY(3)-1=8-1=7, т.е. с 5-ой ячейки по 7-ую ячейку, и т.д. Если номер вершины N, то смежные с ней вершины находятся в ячейках массива MS определяемых массивом MY. Начало находится в ячейке массива MS с номером, имеющим значение ячейки массива MY(N), а окончание находится в ячейке массива MS с номером, имеющим значение ячейки массива MY(N+1) - 1. 2 9 4 17 7 4 10 5 18 1 6 11 1 19 4 7 12 2 20 7 1 13 3 21 1 3 14 5 22 5 4 15 3 23 6 2 16 4 24 18

Следующая теоретико-множественная интерпретация описывает матрицу смежностей. Дано множество вершин X графа G Χ={χι,Χ2,...,χη} и семейство Ms={Ms(xi), Ms(x2),..., Ms(xn)} множеств Ms(xj) <z X. Пример 1.3. Для графа, представленного на рис. 1.8, имеем: Х={хьх2,хз,Х4,Х5,Хб,Х7}; Ms={Ms(xi), Ms(x2), Ms(x3), Ms(x4), Ms(x5), Ms(x6), Ms(x7)}; Ms(Xi)={x2,X4,X6,X7}; MS(X2)={X1,X3,X4}; Ms(x3)={x2,X4,x5}; MS(X4) ={Х1,Х2,Х3,Х5,Хб}; MS(X5)={X3,X4,X7}; MS(X6)={X1,X4,X7}; Ms(x7)={xbx5,x6}. 1.4 Алгоритм формирования матрицы инциденций. Алгоритм формирования матрицы инциденций построен на свойстве симметричности матрицы смежностей относительно главной диагонали и на принципе последовательной нумерации элементов матрицы смежностей, находящихся в треугольных частях матрицы смежностей. Например, для графа на рис. 1.8 ι 2 3 4 5 6 7 Здесь 1-ое ребро инцидентно вершине 1 (строка) и вершине 2 (столбец). 2-ое ребро инцидентно вершине 1 (строка) и вершине 4 (столбец) и т.д. 1 2 3 4 1 5 6 5 7 δ 2 6 7 9 10 δ 9 11 3 10 12 4 11 12 Рис. 1.9. Граф G с пронумерованными ребрами. На рис. 1.9 представлен граф с пронумерованными ребрами данным алгоритмом, ниже представлена процедура формирования матрицы инциденций на языке Pascal: 19

procedure FormIncide(var Nv : integer; var My : TMasy; var Ms : TMass; var Ms3 : TMass); { Nv - количество вершин в графе; } { My - массив указателей для матрицы смежностей; } { Ms - массив элементов матрицы смежностей; } { Ms3 - массив элементов матрицы инциденций. } { Формируется матрица инциденций графа в массиве Ms3 } { } varI,J,K,NNN,P,M,L,Ll : integer; begin { инициализация } NNN:=My[Nv+l]-l; Ll:=NNNdiv2; K:=0; forJ:=ltoLldoMs3[J]:=0; { определение номера элемента } for I:= 1 to Nv do for M:= My[I] to My[I+l]-l do ifMs3[M]=0then begin P:=Ms[M]; K:=K+1; Ms3[M]:=K; for L:=My[P] to My[P+l]-l do if Ms[L]=I then Ms3[L]:=K; end; end; {Formlncide} Впредь такую нумерацию ребер графа, полученную после работы данного алгоритма, будем называть правильной. 1.5 Подграфы и су графы Граф G = (X ,U ) называется частью графа G = (X,U), если X сХи U cz U, т.е. часть графа образуется из исходного графа удалением некоторых вершин и ребер. Особо важную роль играют два типа частей графа: подграф и суграф. Часть G = (X ,U ) называют подграфом графа G = (X,U), если U = {ху е V/x,y е X }. Подграф образуется из исходного графа удалением некоторых вершин и инцидентных им ребер. Часть графа G = (X ,U ) называют суграфом графа G = (X,U), еслиX = X и U cU т.е. суграф образуется из исходного графа удалением только ребер, без удаления вершин [23]. 1.6 Клики графа, множество вершинных покрытий и независимое множество вершин. 20

Рассмотрим граф G = (X,U;P). Определение 1.22. Наибольшее по количеству элементов подмножество вершин S £ X называется независимым множеством вершин графа G, если никакие две вершины из S не смежны в графе G. Независимое множество вершин иногда называют также внутренне устойчивым множеством вершин графа G [5,13,14]. Определение 1.23. Наименьшее по количеству элементов подмножество вершин К £ X называется вершинным покрытием графа G, если любое ребро графа G имеет хотя бы одну кольцевую вершину в подмножестве К. Определение 1.24. Наибольший полный подграф графа будем называть кликой. Задача выделения множества клик в графе, задача выделения множества вершинных покрытий и задача выделения независимого множества вершин в графе тесно связаны между собой. Лемма 1.1 [12]. Для любого графа G=(X,U) и подмножества X cz X следующие утверждения эквивалентные: а) X есть вершинное покрытие в G; б) Х\Х' есть независимое множество вершин в G; в) Х\Х есть клика в дополнении G графа G, где G =(X, U), U= {{xj,xj}:xj,xj е X {xi,xj}£ U}. Таким образом, эти три задачи можно рассматривать в некотором содержании как «разные версии» одной и той же задачи. Более того, взаимосвязи между задачами, указанными в лемме, делают тривиальным вопрос о сведении между любыми двумя из них. Вычислительная сложность алгоритма выделения вершинного покрытия определяется следующей теоремой: Теорема 1.3[12]. Задача определения того, содержит ли неориентированный граф G = (X,U) вершинное покрытие с k-вершинами, является NP - полной. В основу составления многих алгоритмов для выделения множества всех вершинных покрытий в графе G положены методы Х.Магу и Дж. Уэйсмана [29], использующие методы алгебры логики. Здесь каждое ребро графа G представляется как дизъюнкция инцидентных ребру вершин. Все множество ребер графа G связывается операцией конъюнкции и приравнивается к значению 1 (истина). (Xl V Xj) & (Χι V Xj) &... & (Xn-l V Χη) =1 (1.4) Чтобы найти систему значений, выражающих вершинное покрытие, приведем левую часть выражения (1.4) к минимальной дизъюнктивной нормальной форме, раскрывая скобки и 21

пользуясь законом поглощения. Такая форма единственная ввиду отсутствия логических отрицаний. Пример 1.4. Найти всё множество вершинных покрытий для графа, представленного на рис 1.10. Рис. 1.10. ГрафС Рис. 1.11 Граф дополнения G графа G. Исходной информацией для решения задачи о выделении множества вершинных покрытий графа G, является матрица смежностей графа G, записанная в виде списка: 7 - количество вершин в графе. 1: 5 6 2: 3 7 3: 2 4 5 6 7 4: 3 7 5: 1 3 6: 1 3 7: 2 3 4 Записываем ребра графа G как дизъюнкцию инцидентных вершин, объединенных операцией конъюнкции, используя выражение (1.4) (Xl V Х5) & (Xl V Х6) & (Х2 V Хз) & (Х2 V Х7) & (Хз V Х4) & (Хз V Х5) & (Хз V Х6) & (Хз V Х7) & &(Х4 V Х7)= 1. Для удобства записи операцию дизъюнкции обычно заменяют знаком сложения, а операцию конъюнкции - знаком умножения. Тогда, используя свойство логического умножения Xj xj = Xi, получаем (Xl + Х5) (Xl + Хб) (Х2 + Хз) (Х2 + Х7) (ХЗ + Х4) (ХЗ + Хб) (ХЗ + Хб) (ХЗ + X?) (Х4 + X?) = = (Xl + Х5Хб) (Х2 + ХЗХ7) (ХЗ + Х4Х5Х6Х7) (Х4 + Х7) = = (XlX2 + X1X3X7 + Х2Х5Х6 + Х3Х5Х6Х7) (Х3Х4 + Х3Х7+ Х4Х5Х6Х7) = = (ΧιΧ2Χ3Χ4 + X1X3X7+ Х2Х3Х4Х5Х6+ Х2Х4Х5Х6Х7 + Х3Х5Х6Х7) = 1- 22

Все множество вершинных покрытий: Κι = (χιΧ2χ3Χ4), К2= (Х1Х3Х7), К3 = (Х2Х3Х4Х5Х6), K4= (X2X4X5X6X7), К5 = (х3х5ХбХ7). Тогда множество независимых вершин организуется как дополнение: Si= {X5,X6,X7}, S2= {Х2,Х4,Х5,Хб}, S3= {Xl,X7}, S4= {Х1,Хз}, S5= {Xl,X2,X4}· Пример 1.5. Найти всё множество клик для графа, представленного на рис 1.10. Исходной информацией для решения задачи о выделении множества клик графа G, является матрица смежностей графа G, записанная в виде списка: 1: 2 3 4 7 2: 1 4 5 6 3: 1 4: 1 2 5 6 5: 2 4 6 7 6: 2 4 5 7 7: 1 5 6 Записываем ребра графа G как дизъюнкцию инцидентных вершин, объединенных операцией конъюнкции, используя выражение (1.4) (Xl V Х2) & (Χι V Хз) & (Χι V Х4) & (Χι V Χγ) & (Χ2 V Χ4) & (Χ2 V Χ5) & (Χ2 V Хб) & (Χ4 V Χ5) & & (Χ4 V Χ6) & (Χ5 V Хб) & (Χ5 V Χ7) & (Хб V Χγ) = 1. (Χΐ + Χ2) (Χΐ + Χ3) (Xl + Χ4> (Χΐ + Χ7> (Χ2 + Χ4> (Χ2 + Χ5> (Χ2 + Хб) (Χ4 + Χ5> (Χ4 + Хб) (Χ5 + Хб) (Χ5 + Χ7> (Хб + Χ7) = (Xl + Х2Х3Х4Х7) (Χ2 + Χ4Χ5Χ6) (Χ4 + Х5Хб) (Χ5 + ХбХ7> (Хб + Χ7> = = (Χ1Χ2 + Χ1Χ4Χ5Χ6 + Х2Х3Х4Х7 + Х2Х3Х4Х5Х6Х7) (Χ4Χ5 + Χ4Χ6Χ7 + Х5Хб) (Хб + Χ7> = = (XlX2 + Χ1Χ4Χ5Χ6 + Х2Х3Х4Х7 + Х2Х3Х4Х5Х6Х7) (Χ4Χ5Χ7 + Χ4Χ6Χ7+ Х5Хб) = = (Χ1Χ2Χ4Χ5Χ7 + Χ1Χ2Χ4Χ6Χ7+ Χ1Χ2Χ5Χ6+ Χ1Χ4Χ5Χ6 + Х2Х3Х4Х6Х7 + Х2Х3Х4Х5Х7) = 1. Тогда множество клик организуется как дополнение: Fi = {х3,Хб}, F2 = {ХЗ,Х5}, F3 = {Х3,Х4,Х7}, F4 = {Х2,ХЗ,Х7}, F5 = {Х1,Х5}, F6 = {Х1,Хб}· 1.7 Алгоритм выделения клик графа методом корневых деревьев. Рассмотрим следующий алгоритм выделения множества клик графа. Данный алгоритм использует метод корневых деревьев и подчеркивает мысль об удачном выборе структуры данных для реализации вычислений [28]. 23

Рис. 1.12. Граф G. Идея алгоритма очень проста, вся необходимая информация для определения клики, включающей вершину N, содержится в N-строке матрицы смежностей, ее нужно просто эффективно извлечь. Организация такого вычисления представлена в нумерации списка смежных вершин для заданной вершины [28]. Пример 1.6 Рассмотрим следующий граф, представленный на рис. 1.12. Выделим клики данного графа. Матрица смежности этого графа имеет вид: 123456 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Или в виде списка смежных вершин: 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 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 23456789 10 14 6 7 8 10 15 6 7 9 10 12 7 8 9 10 13 6 7 9 10 12 3 5 8 10 12 3 4 5 10 12 4 6 9 10 13 4 5 8 10 123456789 Тогда список смежных вершин с 1-ой, можно записать в виде массива Ms(Xj): 24

2 3 4 5 6 7 8 9 10 MsCXj) Последовательно рассматриваем элементы массива Ms(x ). Естественно, что вершины 3,5 и 9 не смежны с вершиной 2. Тогда список смежных вершин Ms(x ) сократится и будет иметь вид: 1 2 4 6 7 8 10 MsCXj) Следующая вершина 4. Вершина 6 не смежна с вершиной 4. После этого список смежных вершин Ms(x ) имеет вид: 2 4 7 8 10 MsCXj) Вершина 8 не смежная с вершиной 7. Список смежных вершин Ms(x ) будет иметь вид: 2 4 7 10 MsCXj) В результате произведенных действий выделилась клика графа {1,2,4,7,10}. Посмотрим на этот процесс несколько с другой стороны. Будем работать только с индексами списка смежных вершин. И будем удалять не вершины из списка, а только индексы. Тогда данный процесс можно записать, учитывая, что индексов всего 9 и номера несмежных вершин вычеркиваются из списка (текущий номер выделен жирным шрифтом и подчеркнут, а перед удаляемыми номерами стоит знак минус): (1-23-45678 -9) ->(1 3-5679)^(136-79) ->(1 369)- это клика. Расшифровывая запись, получим клику как множество вершин {1,2,4,7,10}. Производим следующее формирование индексов, учитывая, что предпоследний индекс был равен 6 и стоял на 3-м месте. Увеличиваем его значение на единицу, записывая последующие значения на единицу больше предыдущих. (I 3 7 -8 9) -> (1 3 7 9) -> (1 3 7 9) -> (1 3 7 9) -это клика. Вновь производим переформирование индексов, учитывая, что предпоследний индекс был равен 7 и стоял на 3-м месте. (X 3 -8 9) —> (1 3_9) —> (1 3 9J -это не клика, так как данное множество включается в клику с номерами 1,3,7,9. 25

Вновь производим переформирование индексов, учитывая, что предпоследний индекс был равен 3 и стоял на 2-м месте, поэтому запись последующих номеров 4 5 6 7 8 9. £! -4 5 6 7 -8 9) -> (1 5 -6 7 9) -> (1 5 7 9) -> (1 5 7 £1 -это клика. Далее (! 5 -8 9) —> (1 5. 9) —» (1 5 91- это не клика, так как данное множество включается в клику 1,5,7,9; (i 6 7 -8 9) —> (1 6.-7 9) —> (1 6 9) - это не клика, так как данное множество включается в клику 1,3,6,9; (1 7 -8 9) —» (1 Ζ 9) —> (1 7 £) - это не клика, так как данное множество включается в клику 1,5,7,9; (i "8 9) —» (1 9} - это не клика, так как данное множество включается в клику 1,5,7,9; (2 -3 4 5 6 -7 8 9) -> (2 4 5 6 8 9) -> (2 4 5 -6 -8 9) -> (2 4 5 9) - это клика; (2 4 6 -7 8 9) -> (2 4 6 8 9) -> (2 4 6 -8 9) -> (2 4 6 9) - это клика; (2 4 -7 8 9) -> (2 4 8 9) -> (2 4 8 9) -> (2 4 8 9) - это клика; (2. 5 -6 7 8 9) —> (2 5 -6 -8 9) ^ (2 5 9J - это не клика, так как данное множество включается в клику 2,4,5,9; (2 6 -7 8 9) -> (2 6 -8 9) ^ (2 6 9) - это не клика, так как данное множество включается в клику 2,4,6,9; (2,-7 8 9) —» (2 8_ 9) —» (2 8 9} - это не клика, так как данное множество включается в клику 2,4,8,9; (3 -4 -5 6 7 8 9) -> (3 6 -7 -8 9) -> (3 6 9) - это не клика, так как данное множество включается в клику 1,3,6,9; (3 7 8 9) -> (3 7 8 9) -> (3 7 8 9) -> (3 7 8 9) - это клика; (4_5 6 -7 8 9) ->(4 5 -6 -8 9) —> (4 5 9} - это не клика, так как данное множество включается в клику 2,4,5,9; (4_6 -7 8 9) —»(4 6.-8 9) ^^(4 6 9) - это не клика, так как данное множество включается в клику 2,4,6,9; (4_-7 8 9) —»(4 8_9) —> (4 8 9} - это не клика, так как данное множество включается в клику 2,4,8,9; (5_-6 7 -8 9) —> (5 7 9) —> (5 7 9} - это не клика, так как данное множество включается в клику 1,5,7,9; 26

(5.-8 9) —> (5 9J - это не клика, так как данное множество включается в клику 1,5,7,9; (6.-7 -8 9) —> (6 9.) - это не клика, так как данное множество включается в клику 1,ЗД9; (7. 8 9) —> (7 8.9) —> (7 8 9J - это не клика, так как данное множество включается в клику 3,7,8,9; (8. 9) —> (8 23 - это не клика, так как данное множество включается в клику 3,7,8,9; Расшифровывая запись 13 6 9, получим клику как множество вершин (1,2,4,7,10). Запись номеров 1 3 7 9 - это клика Запись номеров 1 5 7 9 - это клика Запись номеров 2 4 5 9 - это клика Запись номеров 2 4 6 9 - это клика Запись номеров 2 4 8 9 - это клика Запись номеров 3 7 8 9 - это клика Конец перебора для 1-ой вершины. 1,2,4,8,10); 1,2,6,8.10); 1,3,5,6,10); 1,3,5,7,10); 1,3,5,9,10); 1,4,8,9,10). Рис. 1.13. Корневое дерево для выделения клик с вершиной χι графа G. Для вершины хг вновь записываем список смежных с ней вершин, за исключением вершины хь Формируем список индексов и находим клики, включающие вершину хг. Для вершины хз вновь записываем список смежных с ней вершин, за исключением вершин χι и хг. Формируем список индексов и находим клики, включающие вершину хз. Процесс продолжаем до полного перебора всех вершин. Выделенный список представляет собой непополнимое множество клик графа. 27

На рис 1.13 представлено корневое дерево для выделения клик вершины 1 графа G нашего примера. Вычислительная сложность алгоритма определяется следующей теоремой: Теорема 1.4 [21,22,27,28]. Задача определения того, содержит ли неориентированный граф G = (X,U) полный подграф с k-вершинами, является NP - полной. 28

Глава 2. ПРОСТРАНСТВО СУГРАФОВ Продолжим вводить основные понятия теории графов. Установим ряд результатов, основанных на этих понятиях. 2.1. Деревья, разрезающие множества, циклы Граф G называется связным, если в нем существует путь между каждой парой вершин. Граф называется ациклическим, если он не содержит циклов. Деревом Τ графа G называется связный ациклический суграф графа G. Ребра дерева Τ называются ветвями Т, а ребра графа не вошедшие в соответствующее дерево Т*, - хордами. Рис 2.1. а) Граф G, б) дерево графа Т, в) хорды графа относительно дерева Т. Рассмотрим некоторые свойства дерева графа. Теорема 2.1. Рассмотрим суграф G графа G на η вершинах. Пусть G имеет η вершин и т ребер. Тогда следующие утверждения эквивалентны: 1. G - является деревом G. 2. Существует единственный путь между двумя любыми вершинами в G . 3. G является связным и ациклическим, и т =п-\. 4. Если G является ациклическим, и любые две несмежные вершины G соединяются ребром, то получающийся граф имеет точно один цикл. Следствие 2.1.1. Суграф G графа G на η вершинах является деревом графа G тогда и только тогда, когда G ациклический, связный и имеет п-\ ребер. Теорема 2.2. Суграф G графа G на« вершинах является деревом G тогда и только тогда, когда G* является ациклическим и имеет п-\ ребер. Теорема 2.3. Граф G является связным тогда и только тогда, когда он имеет дерево. Ранг связного графа G, обозначаемый через p(G), определяется как п-1. Цикломатическое число связного графа G, обозначаемое μ(β), определяется как т - п + 1. Заметим, что p(G) + μ(ϋ) = т. Ранг и цикломатическое число являются одними из наиболее важных характеристик графа. Рассмотрим дерево Τ связного графа G. Обозначим ветви Τ через t\, ti,..., ίη-ι, а хорды Т - через b\, Ьъ ..., bm.n+\, где т - число ребер, а п - число вершин в графе G. Поскольку Τ - ациклический, то по теореме 2.3 граф Τ и Ъ\ содержит точно один цикл Q. 29

Этот цикл состоит из хорды а и тех ветвей Т, которые принадлежат единственному пути между концевыми вершинами Ь\. Цикл Q называется фундаментальным циклом графа G относительно хорды Ь\ дерева Т. Множество всех т - п+ 1 фундаментальных циклов Ci, C2,...,Cm.n+i графа G относительно хорд дерева Τ называется фундаментальным множеством циклов (фундаментальная система циклов) графа G относительно Т. Важной особенностью фундаментального цикла Ci является то, что он содержит только одну хорду, т.е. хорду Ь\. Далее, хорда Ь\ не присутствует ни в одном другом фундаментальном цикле относительно Т. К разрезающему множеству S связного графа G относится такое минимальное множество ребер графа G, что удаление их из графа G разделяет последний, т.е. граф G-S становится несвязным. а) Граф G о о -Ш- о I 6 о- ■о J£ul о о ό в) G2 = G - S: г) G3 = G-S3 Рис. 2.2. Иллюстрация определения разрезающего множества. В качестве примера рассмотрим подмножество Si = (щ, из, щ, ию) ребер графа G (рис. 2.2,6). Граф Gi несвязный. Кроме того, удаление любого собственного подмножества Si не может превратить граф G в несвязный. Таким образом, Si - разрезающее множество графа G. Рассмотрим теперь множество S2 = (wi, иг, щ, щ, щ). Граф G2 = G - S2 (рис. 2.2,в) - несвязный. Однако множество S3 = (щ, иг, щ, щ\ являющееся собственным подмножеством S2, также превращает граф G в несвязный. Граф G3 = G - S3 показан на рис. 2.2,г. Следовательно, S2 не будет разрезающим множеством графа. Заметим, что по определению разрезающего множества, данного выше, если S является разрезающим множеством графа G, то ранги G и G-S отличаются, по крайней мере на единицу, т.е. p(G) - p(G-S) > 1. Приведем следующее определение разрезающего множества: Разрезающим множеством S связного графа G является такое минимальное множество ребер G, что удаление S разбивает граф G на две компоненты, т.е. p(G) - p(G-S) = 1. Определим понятие «разрез», которое связано с понятием «разрезающее множество». 30

Рассмотрим связный граф G с множеством вершин X. Пусть Χι и Хг, - два таких непересекающихся подмножества множества X, что X = Χι и Хг т.е. Χι и Х2 не имеют общих вершин, а вместе содержат все вершины множества X. Тогда множества S всех тех ребер, которые имеют одну вершину в Χι, а другую - в Хг, называется разрезом графа G. Разрез обычно обозначается через <Χι, Хг>. В качестве примера рассмотрим граф G, изображенный на рис. 2.3. Если Χι = (jti,jt2, *з, χα) и Хг = fa, Хб, χί), то разрез <Χι, Хг> - это множество ребер (щ, щ, щ). Д1#- lly -и?- Uyjr ■Щ- €f а) граф G б) разрез <Χι, Хг> графа G Рис 2.3. Определение разреза. Отметим, что разрез <Χι, Хг> графа G является минимальным множеством ребер, удаление которых из графа G разбивает исходный граф на два графа Gi и G2, являющиеся порожденными подграфами на множествах вершин Χι и Хг соответственно. Графы Gi и G2 могут быть несвязными. Если оба эти графа связные, то <Хь Хг> - по-прежнему минимальное множество ребер, разделяющих граф G точно на две компоненты связности. Тогда по определению <Χι, Хг> есть разрезающее множество графа G. Предположим, что для разрезающего множества S графа G величины Χι и Хг являются соответственно множествами вершин двух компонент Gi и G2 графа G-S. Тогда S есть разрез <Χι, Хг>. Таким образом, имеет место следующая теорема: Теорема 2.4. Разрез <Χι, Хг> связного графа G есть разрезающее множество графа G, если соответствующие подграфы G, порожденные на множествах вершин Χι и Хг, - связные. Если S - разрезающее множество связного графа G, а Χι и Хг - множество вершин двух компонент G-S, то S = <Χι, Хг>. 31

Теорема 2.5. Разрез в связном графе G есть объединение нескольких реберно- непересекающихся разрезающих множеств графа G. Теорема 2.6. Множество ребер, инцидентных вершине χ в связном графе G, есть разрезающее множество тогда и только тогда, когда л; не является точкой сочленения в графе G. Дерево связного графа можно использовать для получения множества фундаментальных циклов в графе. Множество всех базисных разрезающих множеств по отношению к п-\-ветви дерева Τ связного графа G называется фундаментальным множеством разрезающих множеств {фундаментальная система разрезов) графа G по отношению к дереву Т. Обсудим некоторые интересные результаты, связывающие разрезающие множества и циклы соответственно. Эти результаты выявляют двойственную природу циклов и разрезающих множеств. Они приводят к альтернативным характеризациям разрезающих множеств и циклов относительно дерева Т. Теорема 2.7. Разрезающее множество связного графа G содержит по крайней мере одну ветвь каждого дерева графа G. Теорема 2.8. Цикл связного графа G содержит по крайней мере одну хорду графа G. Теорема 2.9. Множество ребер S связного графа G является разрезающим множеством G тогда и только тогда, когда S - минимальное множество ребер, содержащих по крайней мере одну ветвь каждого дерева графа G. Теорема 2.10. Циклом связного графа G является минимальное множество ребер графа, содержащее по крайней мере одну хорду по отношению к дереву графа G. Теорема 2.11. Множество ребер С связного графа G есть цикл в G, если оно является минимальным множеством, содержащим по крайней мере одну хорду по отношению к дереву графа G Теорема 2.12. Цикл и разрезающее множество связного графа имеют четное число общих ребер. Это очень важная теорема. Она формирует соотношение ортогональности между разрезающими множествами и циклами. Фундаментальные циклы и разрезающие множества связного графа были определены относительно дерева. И не удивительно, что фундаментальные циклы и разделяющие множества связаны между собой следующим образом: Теорема 2.13. 1. Фундаментальный цикл по отношению к хорде дерева Τ связного графа состоит точно из тех ветвей Т, которым соответствуют фундаментальные разрезающие множества, включающие эту хорду. 32

2. Фундаментальное разрезающее множество по отношению к ветви дерева Τ связного графа состоит точно из тех хорд дерева Т, которым соответствуют фундаментальные циклы, включающие эту ветвь. 2.2. Операции над с\ графами В этом разделе мы введем несколько операций над су графами. Рассмотрим су графы Gi = (X,U1)hG2 = (X,U2). Объединение суграфов Gi и G2, обозначаемое как Gi u G2, представляет собой такой суграф G3= (X, Ui u U2), что множество его ребер является объединением Ui и U2. Например, су графы Gi и G2 и их объединение представлены на рис. 2.4, а, б, в. Пересечение суграфов Gi и G2, обозначаемое как Gi n G2, представляет собой граф G3= (X, Ui n U2). Таким образом, множество ребер G3 состоит только из ребер, присутствующих одновременно в Gi и G2. Пересечение суграфов Gi и G2 (рис. 2.4, а, б) показано на рис. 2.4, г. Количество ребер в пересечении двух суграфов будем называть модулем пересечения. Кольцевая сумма двух графов Gi и G2, обозначаемая как Gi Θ G2, представляет собой граф G3, порожденный на множестве ребер Ui Θ U2. Другими словами, граф G3 состоит только из ребер, присутствующих либо в Gi, либо в G2, но не в обоих суграфах одновременно. Кольцевая сумма суграфов (рис. 2.4, а, 6} показана на рис. 2.4, д. Легко убедиться в том, что три рассмотренные операции коммутативны, т.е. Gi и G2 = G2 u Gi , Gi n G2 = G2 η d , Gi Θ G2 = G2 Θ Gi. Заметим также, что эти операции бинарны, т. е. определены по отношению к двум су графам. 2.3. Графы и пространство суграфов Пусть G = (X,U;P) - граф с пронумерованным множеством ребер U = {ui, U2,...,um}n вершин, Ρ - инцидентор, а £ g - множество всех суграфов этого графа. Относительно операции сложения (будем называть ее кольцевой суммой) (Χ,ϋ,; Ρ) Θ (X,U2; Р) = (X,(U, u U2)4U, n U2),; Ρ) (2.1) множество £ g образует абелеву группу. Действительно, £g заведомо является группоидом; относя каждому суграфу G = (X,U; P) строку чисел (ai,oi2,...,ai,...,am), в которой i = (1,2,...,m), и определяя сложение строк как покомпонентное по модулю 2, мы получим изоморфный £g группоид, элементами которого служат всевозможные строки длины т из нулей и единиц и который уже, без всякого сомнения, представляет собой абелеву группу. 33

α; = 1, если щ е U; [О, если и ι £ U. а) суграф Gi б) суграф G2 в) объединение суграфов Gi nG2 © © г) пересечение суграфов Gi и G2 д) кольцевая сумма суграфов Gi и G2 е) пустой суграф Рис.2.4. Суграфы. В дальнейшем группу £g удобно рассматривать как линейное пространство над полем коэффициентов GF(2) = {0,1}, называемое пространством суграфов данного графа G. Размерность этого пространства dimfo =m ибо множество элементов (1,0,....0),(0.1 0) (0.0 1), представляющих однореберные суграфы, образует базис Рассмотрим множество £q всех т - векторов (суграфов) над полем GF(2). Если ωι, = (αϊ, α2,..., am) и ω2 = (βι, β2, .··, pm) - элементы £G, то ωι Θ ω2 = (αϊ + β„ α 2+ β2,..., am + pm). Если λ принадлежит GF(2), то λω = (λαι, λα2,..., λα,η). Нетрудно установить, что £о-абелева группа относительно операции θ, в которой нулевым элементом считается w-вектор (0,0,...,0). Таким образом, множество £g удовлетворяет первой аксиоме в определении векторного пространства. Легко убедиться в том, что элементы множеств £G и GF(2) удовлетворяют и другим аксиомам этого определения (см. пример 2.1). Таким образом, £g векторное пространство над полем GF(2). Если U = {ui, u2,...,um}, то подмножества {iii}, {u2},...,{um} образуют базис для £g. Из того, что каждый реберно- 34

порожденный суграф графа G соответствует единственному подмножеству множества U и что кольцевой сумме любых 2-реберно-порожденных суграфов можно поставить в соответствие кольцевую сумму двух соответствующих множеств ребер, следует, что множество всех реберно-порожденных суграфов графа G является векторным пространством. Заметим, что £g включает в себя нуль-граф 0. Теорема 2.14. Для графа G пространство £g является m-мерным векторным пространством над полем GF(2). 2.4. Размерность подпространств циклов и разрезов Пусть Τ - дерево связного графа G на η вершинах и т ребрах. Ветви Τ обозначим через ti, t2, ..., tn-i, а хорды bi, Ьг, ..., bm.n+i. Пусть Q и Si - базисный цикл и разрезающее множество по отношению к ti и bi соответственно. По определению, каждый базисный цикл включает в себя только одну хорду, не присутствующую ни в одном другом базисном цикле. Таким образом, никакой базисный цикл нельзя представить в виде кольцевой суммы других базисных циклов. Следовательно, базисные циклы Ci, Сг, ..., Cm-n+i независимы. Аналогично базисные разрезающие множества Si, S2, ..., Sn-i также являются независимыми, так как каждое из них содержит только одну ветвь, не присутствующую ни в одном другом. Чтобы доказать, что Ci, C2, ..., Cm.n+i (Si, S2, ..., Sn-i) образуют базис подпространства циклов (разрезов) графа G, необходимо показать, что любой суграф подпространства циклов (разрезов) графа G можно представить в виде кольцевой суммы циклов С; (разрезов Si). Рассмотрим любой суграф С подпространства циклов графа G. Пусть он содержит хорды Ъц, bi2, ..., bir. Пусть С - кольцевая сумма базисных циклов Си, Са, ···, Си. Очевидно, что С содержит только хорды Ъц, Ъя, ..., bir и не содержит других хорд дерева Т. Поскольку суграф С также содержит только эти хорды, то С Θ С не содержит ни одной хорды. Покажем, что С Θ С - пустое множество. Если это неверно, то по предыдущим рассуждениям множество С Θ С содержит только ветви и, следовательно, не содержит цикла. С другой стороны, так как множество С Θ С - кольцевая сумма циклов, то оно является либо циклом, либо реберно- непересекающимся циклом. Получаем противоречие. Следовательно, С Θ С - пустое множество. Из этого следует, что С = С= Си ®Ci2 Θ ... Θ Cir. Другими словами, каждый суграф подпространства циклов графа G можно представить в виде кольцевой суммы циклов Ci. Точно таким же образом мы можем доказать, что каждый суграф подпространства разрезов графа G можно представить в виде кольцевой суммы Si. 2.5. Связь между подпространствами циклов и разрезов 35

В данном разделе приведем некоторые теоремы, устанавливающие связь между подпространством циклов и подпространством разрезов. Теорема 2.15. Любой су граф в подпространстве циклов графа G имеет четное число общих ребер с любым суграфом в подпространстве разрезов того же графа. Теорема 2.16. Суграф графа G принадлежит подпространству циклов графа G, если он имеет четное число общих ребер с любым суграфом в подпространстве разрезов того же графа. Доказательство. Предположим, что G - связный граф. Пусть Τ - дерево графа G. Обозначим ветви дерева Τ через Х\,Хг, · · ·, а хорды - через bi, Ъг, ... Рассмотрим любой суграф Q графа G, имеющий четное число общих ребер с любым суграфом в подпространстве разрезов графа G. Предположим, не нарушая общности, что суграф С содержит хорды Ьь Ъг, ..., br. Обозначим через Q' кольцевую сумму базисных циклов ci, сг, ...,сг - по отношению к хордам bi, b2, ..., br. Очевидно, что Q' содержит только хорды bi, Ъг, ..., Ьг. Следовательно, Q' Θ Q не содержит ни одной хорды. Поскольку Q' — кольцевая сумма нескольких циклов графа G, то это множество имеет четное число общих ребер с каждым суграфом в подпространстве разрезов графа G. Из того, что Q также обладает этим свойством, следует, что им обладает и Q' Θ Q. Теперь убедимся, что Q' Θ Q — пустое множество. Если это не так, то Q' Θ Q состоит только из ветвей. Пусть а, — любая ветвь в Q' Θ Q. Тогда а, — единственное общее ребро между Q' Θ Q и базисным разрезающим множеством по отношению к аг. Однако это невозможно, так как Q' Θ Q должно иметь четное число общих ребер с любым разрезающим множеством. Таким образом, Q' Θ Q должно быть пустым. Другими словами Q=Q'=ci Θ С2 Θ ...Θ сг и, следовательно, Q принадлежит подпространству циклов графа G. Доказательство второй части теоремы аналогично. 2.6. Ортогональность подпространств циклов и разрезов Каждое «-мерное векторное пространство над полем F изоморфно векторному пространству всех «-векторов над тем же полем. Следовательно, векторное пространство £g графа G изоморфно векторному пространству всех m-векторов над полем GF(2), где т — число ребер графа G. Пусть щ, иг, ..., ит - ребра графа G. Предположим, что мы сопоставили каждому реберно- порожденному суграфу G,, графа G такой m-вектор Wi, что j-й элемент w\ равен 1 тогда и только тогда, когда ребро щ принадлежит суграфу G\. Тогда кольцевая сумма G\ Θ G} двух суграфов G\ и Gj будет соответствовать m-вектору wx + w}, являющемуся суммой по mod 2 векторов уц, и wy Легко видеть, что описанное соответствие действительно определяет изоморфизм между £g и векторным пространством всех m-векторов над полем GF(2). В самом деле, если мы выберем {ui}, {112},. . ., {um} в качестве базисных векторов для пространства £g, to элементами w, будут 36

координаты Gb связанные с этим базисом. При определении этого изоморфизма мы опять использовали символ £g для обозначения векторного пространства всех m-векторов, сопоставленных суграфам графа G. Пусть £с обозначает подпространство m-векторов, представляющих суграфы в подпространстве циклов графа G, a £s — подпространство, представляющее суграфы в подпространстве разрезов графа G. Рассмотрим два таких вектора w\ и wj, когда вектор Wi, находится в пространстве £с, а вектор wj — в пространстве £s. Из того, что любой подграф в пространстве £с имеет четное число общих ребер с произвольным суграфом в пространстве £s, следует, что скалярное произведение <wb wf> векторов wx и w} равно сумме по mod 2 четного числа единиц. Это означает, что <щ, wp = 0. Иначе говоря, m-векторы в пространстве £с ортогональны подобным векторам в пространстве £s. Таким образом, имеет место следующая теорема: Теорема 2.17. Подпространства циклов и разрезов графа ортогональны. Рассмотрим теперь прямую сумму £с ξ £s- Мы знаем, что dim (£с ξ £s) = dim(£c) + dim(£s) - dim(£c η £s). Поскольку dim(£c) + dim(£s) = m, получаем, что dim (£c ξ £s) = m - dim(£c η £s). Теперь ортогональные подпространства £с и £s будут также и ортогональными дополнениями £g тогда и только тогда, когда dim (£с ξ £s) = т. Иными словами, £с и £s будут ортогональными дополнениями в том и только в том случае, если dim(£c n £s) = 0, т.е. £cn£s — нулевой вектор (все элементы которого равны нулю). Поэтому мы получаем следующую теорему: Теорема 2.18. Подпространства £с и £s циклов и разрезов графа являются ортогональными дополнениями тогда и только тогда, когда £с Г\ £s— нулевой вектор. Пусть £с и £s — ортогональные дополнения. Это означает, что каждый вектор в пространстве £g можно представить кольцевой суммой w\ + Wj, где вектор уц, принадлежит пространству £с, а вектор w} — пространству £s. Другими словами, каждый суграф графа О можно представить кольцевой суммой двух суграфов, один из которых принадлежит подпространству циклов, а другой — подпространству разрезов. В частности, сам граф G можно представить таким же образом. Предположим, что £с и £s не являются ортогональными дополнениями. Тогда, очевидно, существует такой суграф, который нельзя представить как кольцевую сумму суграфов в пространствах £с и £s. Возникает вопрос: можно ли в этом случае представить граф G кольцевой суммой суграфов, принадлежащих пространствам £с и £s? Ответом является следующая теорема: Теорема 2.19. Любой граф G можно представить в виде кольцевой суммы двух суграфов, один из которых принадлежит подпространству циклов, а другой — подпространству разрезов графа G. Доказательство этой теоремы можно найти в работах [28,30]. 37

Рассматривая примеры, иногда для удобства будем обозначать ребра графа числами, оговаривая это каждый раз, то есть запись множества ребер {111,114,117} будем иногда представлять как запись {1,4,7}. Пример 2.1. Рассмотрим граф G = (X,U), представленный на рис.2.5. Запишем базис пространства £ g в виде однореберных суграфов (номера ребер читаются справа налево). ei = (0,0,0,0,0,0,0,1); е2= (0,0,0,0,0,0,1,0); е3 = (0,0,0.0,0,1,0,0); е4= (0,0,0,0,1,0,0,0); е5 =(0,0,0,1,0,0,0,0); е6= (0,0,1,0,0,0,0,0); е7= (0,1,0,0,0,0,0,0); е8= (1,0,0,0,0,0,0,0). Любой вектор пространства £ с, может быть представлен в виде /о = (0,0,0,0,0,0,0,0); /, = (0,0,0,0,0,0,0,1); f2= (0,0,0,0,0,0,1,0); /3 = (0.0,0,0,0,0.1,1); /254= (1Д,1Д,1Д,1,0); /255= (1,1,1,1,1,1,1,1). Для данного графа можно записать и следующий базис qi = 42 = qs = Q4 = qs= Чб = q?= qs = = (0,0,0,0,0,0,0,1); = (0,0,0,0,0,0,1,1); = (0,0,0,0,0,1,1,1); = (0,0,0,0,1,1,1,1); = (0,0,0,1,1,1,1,1); = (0,0,1,1,1,1,1,1); = (0,1,1,1,1,1,1,1); = (1,1,1,1,1,1,1,1). Размер данного базиса равен восьми, что не противоречит лемме. Следующая система независимых векторов, 38

ci = lxei + 1χβ2 + 1*ез + 0xe4 + Oxes + Охеб + Οχβγ + Oxes; C2 = Oxei + Охег + 1хез + 1χβ4 + lxes + Охеб + Οχβγ + Oxes; сз = Oxei + Охег + Охез + 0χβ4 + lxes + 1хеб + Ιχβγ + Oxes; C4 = Oxei + 1хег + Охез + Oxe4 + Oxes + Охеб + 1x^7 + lxes; характеризующая циклы графа и их количество, точно также не противоречит лемме. Пример 2.2. Рассмотрим граф G, представленный на рис.2.6. Рис. 2.6. Граф G и его дерево. Фундаментальная система циклов: Ci = (0,1,0,0,0,1,1) ={1,2,6}; С2 = (0,1,1,0,1,0,0) ={3,5,6}; С3 = (1,0,0,1,1,0,0) ={3,4,7}. Фундаментальная система разрезов: Si =(0,0,0,0,0,1,1)= {1,2}; 52 = (1,0,1,0,1,0,0) ={3,5,7}; 53 = (1,0,0,1,0,0,0)= {4,7}; 54 = (0,1,1,0,0,0,1) ={1,5,6}. Образуем подпространство квазициклов: KCi=Ci = (0,1,0,0,0,1,1) ={1,2,6}; КС2 = С2 = (0,1,1,0,1,0,0) = {3,5,6}; КСз = С3 = (1,0,0,1,1,0,0) ={3,4,7}; КС4 = Ci® C2 = (0,0,1,0,1,1,1) = {1,2,3,5}; КС5 = Ci® Сз = (1,1,0,1,1,1,1) = {1,2,3,4,6,7}; КС6= С2 θ Сз = (1,1,1,1,0,0,0) = {4,5,6,7}; КС7 = С, Θ С2 Θ Сз = (1,0,1,1,0,1,1) = {1,2,4,5,7}. Образуем подпространство разрезов: KSi = Si = (0,0,0,0,0,1,1) ={1,2}; KS2 = S2 = (1,0,1,0,1,0,0) ={3,5,7}; KS3 = S3 = (1,0,0,1,0,0,0) ={4,7}; KS4 = S4 = (0,1,1,0,0,0,1) ={1,5,6}; 39

KS5 = Si Θ S2 = (1,0,1,0,1,1,1) = {1,2,3,5,7}; KS6 = Si Θ S3 = (1,0,0,1,0,1,1) = {1,2,4,7}; KS7 = Si Θ S4 = (0,1,1,0,0,1,0) = {2,5,6}; KS8 = S2 Θ S3 = (0,0,1,1,1,0,0) = {3,4,5}; KS9 = S2 Θ S4 = (1,1,0,0,1,0,1) = {1,3,6,7}; KS10 = S3 Θ S4 = (1,1,1,1,0,0,1) = {1,4,5,6,7}; KSn = Si Θ S2 Θ S3 = (0,0,1,1,1,1,1) = {1,2,3,4,5}; KSi2 = Si Θ S2 Θ S4 = (1,1,0,0,1,1,0) = {2,3,6,7}; KSi3= Si Θ S3 Θ S4 = (1,1,1,1,0,1,0) = {2,4,5,6,7}; KSi4=s2es3es4 = (0,1,0,1,1,0,1) = {1,3,4,6}; KSi5= Si Θ S2 Θ S3 Θ S4 = (0,1,0,1,1,1,0) = {2,3,4,6}. 2.7. Свойства характерных подмножеств подпространства циклов и подпространства разрезов В данном разделе рассмотрим некоторые характерные подмножества суграфов, принадлежащих подпространству циклов и подпространству разрезов. Данные подмножества можно разделить и сопоставить следующим образом: Подпространство циклов Единичный цикл (τ-цикл) Простой цикл Квазицикл Подпространство разрезов Единичный разрез Простой разрез Квалиразрез Любой суграф, принадлежащий подпространству циклов С, в общем случае является квазициклом. В задаче выделения максимально плоского суграфа особую роль играют простые циклы. Особая роль простых циклов объясняется тем, что границей грани в плоском графе, как правило, является простой цикл. Простые циклы - это квазициклы, у которых локальная степень вершин в точности равна двум [25]. Мощность подмножества простых циклов в графе меньше мощности множества квазициклов. Подмножество простых циклов обозначим Сс. card Cc ^ card С (2.2) Однако, существует подмножество с мощностью еще меньшей, чем подмножество простых циклов, обладающее определенными характерными свойствами. С этой целью введем определение единичного цикла (τ-цикла) графа. Определение 2.1. τ-циклом (единичным циклом) в графе называется простой цикл, между двумя любыми несмежными вершинами которого в соответствующем графе не существует маршрутов меньшей длины, чем маршруты, принадлежащие данному циклу. 40

Подмножество, состоящее из τ-циклов, будем называть подмножеством τ-циклов и обозначать Ст. Следует также различать τ-циклы и циклы из полной τ-системы циклов, согласно определению Мак-Лейна [25]. Однако, как в большинстве случаев, для трехсвязных графов и графов с более высокой степенью связности полная τ-система циклов обязательно состоит из τ-циклов [25]. Сказанное поясним на примерах. Рассмотрим суграф, состоящий из ребер ui,113,1113,1115 графа G , представленного на рис. 2.7. Как видно, это простой цикл. Но в то же время, это не τ-цикл, так как между вершинами xj и xg в графе существует маршрут меньшей длины, проходящей по ребру им. а)ГрафСа б) Графвь Рис. 2.7 Графы Ga и d,. Рассмотрим граф Gb, представленный на рис. 2.7. Пусть цикл состоит из ребер ui,ii2,U3,U6,U8,U9,uii,ui2. Данный суграф есть простой цикл. Однако этот суграф не может быть τ-циклом, так как в соответствующем графе между вершинами хг и Х8 имеется маршрут меньшей длины (а именно, маршрут, проходящий по ребрам щ и ию), чем маршруты, принадлежащие этому суграфу (например, маршрут, проходящий по ребрам 111,113,118,119 или U2,U6,Un,Ui2). Как следует из определения, любой τ-цикл представляет собой подграф. Обратное не верно. Понятие τ-цикла графа G тесно связано с минимальными (s-t) маршрутами графа. Поэтому введем необходимые понятия и определения. Определение 2.2. Связностью χ = %(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному графу. Очевидно, что связность несвязного графа равна 0, а связность графа, имеющего точку сочленения, равна 1. Полный граф Кп нельзя сделать несвязным, сколько бы вершин из него не 41

удалять, а тривиальный граф получается из К после удаления (п-1) вершин; поэтому χ(Κ ) = п- 1. Иногда χ называют еще вершинной связностью. Пусть Xj и х2 - две различные вершины связного графа G. Определение 2.3. Две простые цепи, соединяющие х{ и х2, называются непересекающимися (или вершинно-непересекающимися), если у них нет общих вершин, отличных от х{ и х2 (и, следовательно, нет общих ребер). В дальнейшем нам понадобится теорема Менгера. Теорема 2.20 (Теорема Менгера). Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s-t)-nenefi (т.е. цепей между вершинами s и t, см. рис.2.8). Рис. 2.8. Граф для иллюстрации теоремы Менгера На рис.2.8 представлен граф, у которого две несмежные вершины s и t можно разделить, удалив три вершины (но не меньше). Из теоремы Менгера вытекает, что наибольшее число непересекающихся (s-t)-nenefi для данного графа равно 3. Рассмотрим единичные циклы, проходящие по k-му ребру, соединяющему вершины s и t графа G. Удалим из графа ребро к, получим граф G-k, где вершины s и t теперь несмежны. Если применить κ графу G-k теорему Менгера, то удается выделить наименьшее число вершин, разделяющих несмежные вершины s и t. Обозначим это множество через υ(κ). Выделим все простые цепи минимальной длины, проходящие по вершинам из множества υ(κ), добавим κ этим простым цепям ребро к и получим множество единичных циклов для ребра к. Естественно, что для изоморфных графов количество единичных циклов и их длины будут совпадать для изоморфных ребер к и к. В качестве примера рассмотрим граф G-k (см. рис.2.10). Данные рассуждения можно применить ко всем ребрам графа G и сформировать множество единичных циклов. 42

ребро к Рис. 2.9. ГрафС Минимальные цепи, проходящие через множество вершин и(к) = {b,d,i} - это; Рис. 2.10. Минимальные s-t цепи. Рассмотрим граф G, представленный на рис.2.9, и пронумеруем его вершины и ребра. 1 Рис.2.11. Граф G с пронумерованными вершинами и ребрами. Для перечисления всех τ-циклов, проходящих по 1-му ребру, следует удалить 1-е ребро и найти все маршруты минимальной длины, соединяющие вершины s и t (принадлежащие 1-му ребру). 43

Все множество маршрутов минимальной длины между вершинами s и t можно разбить на три непересекающихся подмножества, где маршруты, принадлежащие к одному подмножеству, проходят только по одной разделяющей вершине и имеют одинаковую длину. По первой разделяющей вершине проходит единственный (s-t)-MapuipyT {119,1119}. По второй разделяющей вершине проходят следующие (s-t)-MapuipyTbi: {117,1113,1114}; {ll7,Ui5,ll2o}; {u7,Ui8,U2l}. По третьей разделяющей вершине проходят следующие (s-t)-MapuipyTbi: {112,113,1112}; {ιΐ5,ιι6,ιΐι2}; {u8,ui2,ui7}. Исходя из этого, можно записать все множество τ-циклов, проходящих по 1-му ребру: С[ = {{ui,u9,ui9}; {111,112,113,1112}; {ui,u5,u6,ui2}; {ui,u7,ui3,ui4}; {Ul,U7,Ui5,U2o}; {Ul,U7,Ui8,U2l}; {Ul,U8,Ui2,Ui7}}. Для изучения свойств τ-циклов нам понадобится следующая теорема. Теорема 2.21. Для любого связного графа без петель и кратных ребер линейное подпространство квазициклов имеет базис из τ-циклов (единичных циклов). Доказательство. Для графа без петель и кратных ребер набор всех его квазициклов может рассматриваться как линейное пространство над полем GF(2). Если мы докажем, что набор всех τ-циклов графа является системой образующих этого пространства, то из них, очевидно, можно выделить и базис. Известно, что любой квазицикл можно представить в виде суммы простых циклов. Значит, нам достаточно доказать, что любой простой цикл есть сумма некоторых τ-циклов. Пусть вершины А1?А2,...,А образуют простой цикл. Если это τ-цикл, то наше утверждение справедливо. Если нет, то существуют вершины графа В1?В2,...,Вг, отличные от всех А1?А2,...,А , и вершины А. и A (i<j) такие, что путь А.,В1,В2,...,Вг,А содержит меньше ребер, чем пути от А. к А. по нашему циклу. В этом случае цикл А ,...,А есть сумма цикла А1,А2,...А,В1,...,Вг,А,А+1,...,А и цикла А.,А.+1,...,А,Вг,...,Вг Отметим, что каждый из двух новых циклов имеют не более р-1 вершин. На следующем шаге если хотя бы один из двух наших новых циклов не является единичным, то аналогично разбиваем его на сумму двух простых циклов (если оба не являются единичным - оба разбиваем). И так далее. После каждого шага цикл А1?А2,...,А будет суммой всех образованных нами циклов. Любой такой цикл, для которого справедливо вышесказанное, является τ-циклом. Значит, не позже чем после (р-3) шагов мы получим представление цикла А,,А0,...,А в виде линейной комбинации τ-циклов. Если в качестве исходного базиса выбрать 1 ζ ρ χ 44

фундаментальную систему циклов и применить доказанное выше, получим базис, состоящий из τ-циклов. Теорема доказана. 2.8. Выделение конечного множества единичных циклов (τ-циклов) Ввиду важности вопроса выделения конечного множества τ-циклов из множества квазициклов, предлагается алгоритм выделения множества τ-циклов в графе. Построение алгоритма начинается с выделения всех ребер в графе G. Выберем любое ребро графа. Одну из вершин такого выбранного ребра пометим индексом 1, другую - индексом 2. Вершины графа, смежные с вершиной, имеющей индекс 2, и ещё не помеченные, пометим индексом 3. Вершины графа, смежные с вершиной, имеющей индекс 3, и ещё не помеченные, пометим индексом 4 и т д Число, выражающее индекс последней помеченной вершины (вершин) графа, будем называть глубиной проникновения разметки относительно выбранного ребра. Данный процесс представляет собой разметку вершин графа относительно выбранного ребра волновым алгоритмом (алгоритмом поиска в ширину). Построим простые циклы, проходящие по выбранному ребру, относительно первоначальной ориентации. С этой целью выберем все вершины графа G, смежные с вершиной, помеченной индексом 1. Будем идти от любой выбранной вершины, имеющей глубину проникновения d, к вершинам, имеющим глубину проникновения (d-Ι), проходя при этом по ребрам графа, затем от вершины (d-Ι) к вершинам (d-2) и т.д. Остановим этот процесс тогда, когда подойдем к вершине, имеющей индекс 2. Пройдя по всем таким образом построенным маршрутам, построим систему циклов, проходящих по выбранному ребру j. Обозначим такое множество циклов через Sj. Переориентируем направление ребра, т.е. вершина, имеющая индекс 1, будет иметь индекс 2, а вершина, имеющая индекс 2, будет иметь индекс 1. И вновь построим разметку вершин. Описанным выше методом выделим систему циклов и обозначим её τ-циклы, проходящие по выбранному ребру, будут образованы как Cj=CjnCj\ (2.3) Множество τ-циклов графа G будет образовано как объединение всех τ-циклов, проходящих по всем ребрам графа ш CT=UCi(i=1'2,...,m). (2.4) i=l Пример 2.3. Рассмотрим граф G (рис.2.12). 45

Рис.2.12. ГрафС Если в качестве выбранного ребра взять ребро 13, то процесс разметки вершин имеет вид, представленный на рис.2.13. Система циклов, проходящих по ребру 13, для разметки, показанной на рис.2.13,а: а) б) Рис.2.13. Процесс разметки вершин. С!з= {{U5,ll8,lli3}, {Ui,ll3,U8,lli3}, {Ui,ll2,ll9,lli3}, {U6,U8,U12,U13}, {Uio,Uii,Ui2,Ui3}}. Система циклов, проходящих по ребру 13, для разметки, представленной на рис.2.13,6: СИ= {{U5,U8,Ui3},{ll4,U5,U9,Ui3},{Ui,U2,U9,Ui3},{Uio,Uii,Ui2,Ui3},{u5,U7,Uio,Ui3}}. Пересечение множеств с[3и С23: С13= С13ПС123= {{U5,U8,Ul3},{Ui,U2,U9,Ui3},{Uio,Uii,Ui2,Ui3}}. Каждому ребру принадлежат следующие τ-циклы: iUi,U3,U5},{Ui,U2,U9,Ui3}}; Сз=< u2,u3,U4}, {111,112,119,1113}}; 112,113,114}, {ui,u3,ii5}}; U4,u8,u9}, {112,113,114}}; U1,U3,U5},{U5,U6,U12},{U5,U8,U13}}; U5,U6,Ui2},{U6,U7,Uii}}; U6,U7,Uii},{U7,U8,Uio}}; u5,u8,ui3}, {u7,u8,uio}, {u3,u8,u9}}; U4,U8,U9},{Ui,U2,ll9,lli3}}; {u7,u8,uio}, {uio,un,ui2,ui3}}; 46

Сп = {{u6,U7,Uii},{Uio,UibUi2,Ui3}}; С12= {{U5,U6,Ul2},{Uio,Uii,Ui2,Ui3}}; С13 = {{U5,U8,Ui3},{UbU2,U9,Ui3},{Uio,Uii,Ui2,Ui3}}. Множество τ-циклов получим как объединение: с =cIuc2uc3u:4ucsuc6uc7u:euc9ucI0uc11u:I2ucI3 = = {{Ι1ι,1ΐ3,115}, {U2,ll3,ll4}, {114,118,119}, {ΐΐ5,116,11ι2}, {u5,U8,Ui3}, {u6,U7,U8}, {u7,U8,Uio}, {Ui,U2,U9,Ui3}, {Uio,Ui 1,U12,U13} }. Таким образом, множество τ-циклов состоит из 9-ти элементов. Цикломатическое число графа G равно 7. Следовательно, для построения базиса нужно удалить два τ-цикла. Очевидно, что для любого трехсвязного и более графа G множество τ-циклов имеет мощность меньшую, чем мощность множества простых циклов, но большую или равную цикломатическому числу графа v(G) < card CT< card C° < card С (2.5) 2.9. Множество ребер и построение множества единичных циклов Здесь мы покажем, что построение множества единичных циклов должно производиться относительно всего множества ребер графа. Пример 2.4 Следующий пример демонстрирует невозможность получения полного множества единичных циклов, если построение производится только относительно хорд для выбранного дерева графа. Рассмотрим граф, представленный на рис. 2.14. 10 11 Рис. 2.14. Граф G и его дерево. Рассмотрим единичные циклы относительно 8-ой хорды: ci= {u8,u9,iiio}; С2= {ui,u8,u9,ui3}; с3= {u7,u8,u9,ui2}; ci = {u8,u9,uio}; C2 = {U4,U5,ll6,ll8,lli2}; C3'= {lli,U2,ll3,U4,ll8}; C4 = {U4,U5,U8,Ui2,Ui5}; C5 = {u4,U5,U9,Ui3,Ui4}. 47

Рис. 2.15. Единичные циклы относительно 8-й хорды. ЕДИНИЧНЫЙ ЦИКЛ ОТНОСИТеЛЬНО 8-Й ХОрДЫ {ll8,U9,Uio} · Рассмотрим единичные циклы относительно 9-й хорды: ci= {u8,u9,uio}; С2= {U4,U5,ll6,ll8,lli2}; Сз = {U2,U3,U4,U9,Ui3}; С4= {U3,U4,U7,U9,U15}; С5= {U3,U4,U9,Ui2,Ui5}; ci = {u8,u9,uio}; C2 = {Ui,U8,U9,Ui3}; C3 = {U7,U8,U9,Ui2}. Рис. 2.16. Единичные циклы относительно 9-й хорды. ЕДИНИЧНЫЙ ЦИКЛ ОТНОСИТеЛЬНО 9-Й ХОрДЫ {Us,U9,Uio}. Рассмотрим единичные циклы относительно 10-й хорды: ci = {u8,u9,uio}; с2= {u7,uio,ui2}; с3= {ubuio,ui3}; ci = {u8,u9,uio}; с2 = {u7,uio,ui2}; с3'= {ubUio,Ui3}. Рис. 2.17. Единичные циклы относительно 10-й хорды. ЕдИНИЧНЫе ЦИКЛЫ ОТНОСИТеЛЬНО 10-ОЙ ХОрДЫ {ll8,U9,Ulo}, {ubUio,Ui3}, {U7,Ui0,Ui2}. Рассмотрим единичные циклы относительно 11-й хорды: 48

ci = {113,115,1111}; c2 = {u2,uibUi4}; c3= {u6,un,ui5}; ci = {u3,u5,uii}; c2' = {u2,iii 1,1114}; c3' = {u6,un,ui5}. Рис. 2.18. Единичные циклы относительно 11-й хорды. Единичные циклы относительно 11-й хорды {113,115,1111}, {112,1111,1114}, {ii6,ui 1,1115}. Рассмотрим единичные циклы относительно 12-й хорды: ci= {117,1110,1112}; С2= {U7,ll8,ll9,lli2}; С3= {Ui,U2,Ui2,Ui5}; с4= {ui,u7,ui2,ui3}; с5 = {ui,u6,ui2,ui4}; ci = {u7,uio,ui2}; С2'= {Ui,U2,Ui2,Ui5}; Сз = {Ui,U6,Ui2,Ui4}. Рис. 2.19. Единичные циклы относительно 12-й хорды. Единичные циклы относительно 12-й хорды {117,1110,1112}, {111,112,1112,1115}, {ui,U6,ui2,ui4 Рассмотрим единичные циклы относительно 13-й хорды: ci = {ubuio,ui3}; С2= {U6,U7,Ui3,Ui4}; сз= {u2,u7,ui3,ui5}; ci = {ιΐι,ιΐιο,ιΐπ}; С2'= {Ui,U7,Ui2,Ui3}; сз = {u6,u7,ui3,ui4}; с4'= {u2,u7,ui3,ui5}; С5 = {Ui,U8,U9,Ui3}.

Рис. 2.20. Единичные циклы относительно 13-й хорды. Единичные циклы относительно 13-й хорды {ιΐι,ιΐιο,ιΐπ}, {116,117,1113,1114}, {112,117,1113,1115}. Рассмотрим единичные циклы относительно 14-й хорды: ci = {ιι2,ιΐιι,ιΐι4}; С2= {U6,u7,ui3,ui4}; с3 = {ui,u6,ui2,ui4}; ci = {ιι2,ιΐιι,ιΐι4}; с2'= {u2,U6,ui4,ui5}; сз = {u2,u3,ii5,iii4}; с4'= {u6,u7,ui3,ui4}; С5 = {Ui,U6,Ui2,Ui4}. Рис. 2.21. Единичные циклы относительно 14-й хорды. Единичные циклы относительно 14-й хорды {2,11,14}, {6,7,13,14}, {1,6,12,14}. Рассмотрим единичные циклы относительно 15-й хорды: ci = {u6,uii,ui5}; С2= {U3,U5,ll6,Ui5}; Сз= {U2,U6,Ui4,Ui5}; с4= {u2,u7,ui3,ui5}; с5= {ui,u2,ui2,ui5}; ci = {u6,un,ui5}; c2'= {u2,u7,ui3,ui5}; c3'= {111,112,1112,1115}. Рис. 2.22. Единичные циклы относительно 15-й хорды. 50

Единичные циклы относительно 15-й хорды {ιΐ6,ιΐι 1,1115}, {112,117,1113,1115}, {111,112,1112,1115}. Рассмотрим единичные циклы относительно 4-го ребра: Ci = {Ui,U2,U3,U4,U8}; С2= {U3,U4,U8,U12,U15}; С3= {U4,U5,U6,U8,Ui2}; с4= {u4,u5,U6,U7,u9}; С5= {ll2,ll3,U4,ll9,lli3}; С6= {U4,U5,U9,Ui3,Ui4}; Cl С2 с3 с4 С5 = {Ui,U2,U3,U4,U8}; = {U3,U4,U8,U12,U15}; = {U4,U5,U6,U8,Ui2}; = {U4,U5,U6,U7,U9}; = {U2,U3,U4,U9,U13}; C6 = {U4,U5,U9,Ui3,Ui4}. Рис. 2.23. Единичные циклы относительно 4 ребра дерева. Единичные циклы относительно 4-го ребра {ui,U2,U3,U4,U8}, {u3,U4,U8,ui2,uis}, {11^115,116,118,1112}, {U4,U5,U6,U7,U9}, {U2,U3,U4,U9,U13}, {U4,U5,U9,Ui3,Ui4}. Как видно из данного примера, если построение производится только относительно хорд для выбранного дерева графа, то множество единичных циклов будет не полно. В частности во множество единичных циклов не вошли единичные циклы, проходящие по четвертому ребру. 2.10 Фундаментальная система циклов и разрезов и базисная единичная система циклов и разрезов Обычно в теории графов применяется фундаментальная система циклов и разрезов. Данная система образуется в результате выделения случайного дерева графа, тем самым, разделяя ребра графа на ветви дерева и хорды. Каждый фундаментальный цикл образуется как объединение хорды и ветвей дерева. Рассматривая все хорды для выделенного дерева графа, строим матрицу фундаментальных циклов. Например, для графа G (см. рис.2.26) относительно дерева Τ = {1,3,7,10,11} матрица фундаментальных циклов имеет вид: U2 U4 Сф= и5 u6 U8 U9 u2 1 Еди] u4 1 нична u5 1 1Я u6 1 u8 1 бло1 u9 1 чная Ui 1 1 1 Бло1 u3 1 1 1 1 шая г u7 1 1 1 юдма UlO 1 1 1 1 1 трицг un 1 1 1 1 ιπ Матрица фундаментальных разрезов имеет вид 51

Sa— Ul u3 Uio Ull Ul 1 u3 1 u7 1 Uio 1 Ull 1 Единичная блочная подматрица u2 1 1 1 u4 Us 1 1 1 u6 1 1 u8 I 1 u9 1 1 1 Транспонированная блочная подматрица р = π* Что касается базисной единичной системы циклов и разрезов, принцип их выбора отличается от выбора фундаментальной системы циклов и разрезов. Согласно теореме 2.10 базис единичных циклов может быть построен из множества единичных циклов с проверкой на независимость методом Гаусса, где количество базисов равно цикломатическому числу графа v(G) = m-n+1 Например, для графа G (см. рис.2.26) система единичных базисных циклов состоит из следующих единичных циклов: ci = {ui,u2,u5}; c2= {U4,u5,u7}; c4= {ui,u3,u6}; с5 = {u4,U6,u9}, c6 = {u8,u9,un}; с7= {u7,u8,ui0}. Базис единичных разрезов строится из множества единичных разрезов, так чтобы их количество было равно рангу графа p(G) = п-1. Например, для графа G (см. рис.2.26) система единичных базисных разрезов состоит из следующих единичных разрезов: Si = {Ui,U2,U3}; S2 = {Ui,U4,U5,U6}; S3 = {U4,U7,U8,U9}; S4 = {u2,U5,U7,Uio}, S5 = {u8,Uio,Un}. Характерной особенностью систем базисных единичных циклов и разрезов является то, что их элементы обладают минимальной мощностью. Любой суграф, принадлежащий подпространству разрезов S, в общем случае является квалиразрезом. Единичным разрезом будем называть квалиразрез, состоящий из инцидентных ребер, принадлежащих данной вершине; будем его обозначать через W(xj) для i - вершины (см. рис. 2.24,а). Реберным разрезом будем называть квалиразрез, состоящий из инцидентных ребер, принадлежащим двум концевым вершинам данного ребра, за исключением самого ребра; будем его обозначать через W(uy) для ребра иу-, соединяющего вершины Xi и Xj.(cm. рис. 2.24,6). 2 1 8 а) б) Рис.2.24. Единичный разрез {ui,U6,u7} и реберный разрез {ui,U3,ii4,U5}. Количество ребер в квазицикле будем называть длиной цикла. 52

Между единичными разрезами и единичными циклами существует связь, устанавливаемая следующими леммами. Лемма 2.1. Кольцевая сумма множества единичных разрезов графа есть пустое множество. Доказательство. Этот факт следует из линейной независимости любых п-1 вершин. Лемма 2.2. Кольцевая сумма реберных разрезов для любого квазицикла графа есть пустое множество. Доказательство. Пусть длина цикла равна р, и реберный разрез равен кольцевой сумме единичных разрезов для концевых вершин ребра W(u4) = W(xi) Θ W(xj), тогда W(ui2) Θ W(u23) θ... θ W(upi) = (W(xi) Θ W(x2)) θ (W(x2) Θ W(x3)) θ... Θ (W(xp) Θ W(xi)) = 0. (2.6) И кольцевая сумма есть пустое множество, так как единичные разрезы присутствуют в правой части выражения (2.6) дважды (см. рис. 2.25). Рис.2.25. Цикл графа. Лемма 2.3. Кольцевая сумма пересечения единичных разрезов для циклических ребер любого квазицикла графа - квазицикл. Доказательство. Любое ребро графа можно представить в виде uy· = W(xj) n W(xj), а любой квазицикл можно представить как кольцевую сумму ребер, тогда с = щ2 θ u23 Θ... Θ upi = (W(xi) n W(x2)) Θ (W(x2) η W(x3)) Θ... ®(W(xp) nW(xi)). (2.7) P Отсюда следуете =£ (W(xk) nW(xk+i) (2.8) k=\ Пример 2.5. Для иллюстрации рассмотрим следующий граф G представленный на рис. 2.26 Рис. 2.26. Граф G. Кольцевая сумма единичных разрезов графа равна: {Ui,U2,U3} Θ {Ui,U4,U5,U6} Θ {U4,U7,U8,U9} Θ {u2,U5,U7,Ui0} Θ {u8,Uio,Uii} Θ {u3,U6,U9,Un} = 0. 53

Выберем цикл {114,116,119}. Кольцевая сумма реберных разрезов равна {Ui,U5,U6,U7,U8,U9} Θ {u3,U4,ll6,ll7,ll8,Uii} Θ {Ui,U3,U4,U5,U9,Uii} =0. Цикл представляется как сумма пересечений единичных разрезов: С = ({Ui,U4,U5,U6} П {U4,U7,U8,U9}) θ ({U4,U7,U8,U9} П {u3,U6,U9,Un}) Θ ({u3,U6,ll9,Uii} П П {Ui,U4,U5,U6}) = {U4} Θ {U6} Θ {U9} = {ll4,U6,U9}. Так как множество единичных циклов обязательно содержит базис подпространства циклов, то любой единичный цикл может быть представлен как линейная комбинация базисных единичных циклов. Пример 2.6. В качестве примера рассмотрим граф, представленный на рис.2.27. Выделим множество единичных циклов: Cl = {U2,U3,U6,U8}, С2 = {ll8,U9,Uio,Ui2}, C3 = {Ui,U2,U4,U7}, C4 = {U4,U5,Uii,Ui2}, с5 = {ubu3,u5,u9,ui2}, с6 = {ubu3,u5,u8,uio}, с7 = {ui,u2,u5,u6,uio}, с8 = {u4,u5,U6,u7,uio}, С9 = {u2,U3,U7,U9,Un}, Сю = {Ui,U3,ll4,U9,Uii}, Си = {u6,U7,U8,U9,Un}, C12 = {u6,U7,Uio,Uii,Ui2}. Рис. 2.27. Граф G. Выделим базис подпространства циклов, состоящий из единичных циклов. Это циклы: Ci = {U2,U3,U6,U8}, C2 = {u8,U9,Uio,Ui2}, C3 = {Ui,U2,U4,U7}, C4 = {U4,U5,Un,Ui2}, с5= {ubu3,u5,u9,ui2}. Тогда остальные циклы, принадлежащие множеству единичных циклов, можно записать как линейную комбинацию единичных циклов базиса: с6 = с2 Θ с5= {u8,u9,uio,ui2} Θ {ui,u3,u5,u9,ui2} = {ui,u3,u5,u8,ui0}; C7 = Ci Θ C2 θ C5= {U2,U3,U6,U8} Θ {ll8,U9,Uio,Ui2} θ {Ui,U3,U5,U9,Ui2} = {Ui,U2,U5,U6,Uio}; C8 = Ci Θ C2 θ C3 θ C5 = {U2,U3,U6,U8} θ {u8,U9,Ui0,Ui2} Θ {Ui,U2,U4,U7} Θ {Ui,U3,U5,U9,Ui2} = = {U4,U5,U6,U7,Uio}; c9 = c3 Θ c4 θ c5= {ui,u2,ii4,u7} Θ {U4,u5,uii,ui2} θ {ui,u3,u5,u9,ui2} ={u2,u3,u7,u9,un}; do = c4 Θ c5= {114,115,1111,1112} θ {ubu3,u5,u9,ui2} = {ui,u3,ii4,u9,un}; 54

си = ci Θ c3 Θ c4 Θ c5 = {u2,U3,U6,u8} Θ {ui,U2,U4,u7} Θ {114,115,1111,1112} θ {111,113,115,119,1112} = = {U6,ll7,ll8,ll9,llii}; Ci2 = Ci Θ С20 Сз θ C4 Θ C5 = {U2,U3,U6,U8} θ {U8,U9,Uio,Ui2} Θ {Ui,U2,U4,U7} Θ θ {U4,U5,Uii,Ui2} Θ {Ui,U3,U5,U9,Ui2} = {U6,U7,U10,U11,U12}. Выделим другой базис подпространства циклов, состоящий из единичных циклов. Это циклы: Cl = {U2,U3,U6,U8}, С2 = {U8,U9,Uio,Ui2}, C3 = {Ui,U2,U4,U7}, С4= {U4,U5,Un,Ui2},C6= {Ui,U3,U5,U8,Uio}. Остальные циклы, принадлежащие множеству единичных циклов, можно записать как подстановку в линейную комбинацию единичных циклов выражения cs = сг θ Сб: с5 = с2 Θ с6= {u8,u9,ui0,ui2} Θ {ui,u3,U5,u8,ui0} = {ui,u3,u5,u9,ui2}; C7 = Ci Θ C6= {ll2,ll3,U6,U8} Θ {Ui,U3,U5,U8,Uio} = {Ui,U2,ll5,U6,llio}; C8 = Ci Θ C3 θ Сб = {U2,U3,U6,U8} Θ {Ui,U2,U4,U7} θ {Ui,U3,U5,U8,Uio} = {U4,U5,U6,ll7,llio}; C9 = C2 Θ Сз θ C4 θ C6= {u8,U9,Um,Ui2} θ {Ui,U2,ll4,U7} Θ {U4,U5,Uii,Ui2} θ {Ui,U3,U5,U8,Uio} = ={u2,u3,u7,u9,un}; Сю = C2 Θ C4 Θ C6 = {u8,U9,Ui0,Ui2} Θ {U4,U5,Uii,Ui2} Θ {Ui,U3,U5,U8,Uio} = {Ui,U3,U4,U9,Un}; en = ci Θ c20 сз θ c4 Θ Сб = {u2,u3,u6,u8} θ {u8,u9,ui0,ui2} Θ {ui,u2,ii4,u7} Θ θ {U4,u5,uii,ui2} Θ {ui,u3,U5,u8,uio} = {u6,u7,u8,u9,un}; C12 = Ci Θ Сз Θ C4 Θ C6 = {U2,U3,U6,ll8} Θ {Ui,U2,U4,U7} Θ {U4,U5,Uii,Ui2} 0{lli,ll3,U5,U8,Uio} = = {u6,U7,Uio,Uii,Ui2}. Рассмотрим свойства единичных циклов и единичных разрезов для графа К5. Рис. 2.28. Граф Ks и его пять четырехвершинных подграфов. Множество единичных разрезов S для графа К5: si = {ui,u2,u3,u4}; s2 = {ubU5,U6,u7}; s3 = {u2,u5,u8,u9}; s4 = {u3,U6,u8,ui0}; s5 = {u4,u7,u9,ui0}. Множество единичных циклов С для графа К5: ci = {111,112,115}; с2 = {ιΐι,ιΐ3,ιι6}; сз = {ui,U4,u7}; с4 = {u2,u3,u8}; с5 = {u2,ii4,u9}; с6 = {u3,U4,uio}; с7 = {u5,u6,u8}; с8 = {u5,u7,u9}; с9 = {u6,u7,ui0}; сю = {u8,u9,ui0}. 55

Как видно, все единичные циклы принадлежат четырехвершинным подграфам (см. рис. 2.28). Рис. 2.29. Граф Ks с удаленным 10-м ребром и его пять четырехвершинных подграфов. Удалим из графа ребро ию (см. рис. 2.29). Из множества единичных циклов С удаляются все циклы, включающие 10-е ребро: с6 = {u3,u4,uio}; с9 = {u6,u7,iiio}; сю = {u8,u9,ui0}. Остаются единичные циклы: ci = {ιΐι,ιι2,ιι5}; с2 = {ιΐι,ιι3,ιι6}; с3 = {ui,U4,u7}; c4 = {u2,u3,u8}; c5 = {u2,U4,u9}; с7 = {u5,u6,u8}; с8 = {u5,u7,u9}. И должны в перспективе образоваться новые единичные циклы длиной четыре: с6 Θ с9 = {u3,u4,iiio} θ {ιΐ6,ιι7,ιΐιο} = {u3,u4,u6,u7}; c6 θ сю= {113,11^1110} θ {u8,u9,ui0} = {u3,ii4,u8,u9}; c9 Θ сю= {u6,u7,ui0} Θ {u8,u9,uio} = {u6,u7,u8,u9}. Однако их включение во множество оставшихся единичных циклов невозможно, так как они могут быть образованы как результат кольцевого суммирования из оставшихся единичных циклов (см. рис. 2.29): с2 Θ с3 = {ui,u3,u6} Θ {иьщ,^} = {из,щ,и6,и7}; с4 Θ с5 = {и2,и3,и8} Θ {и2,щ,и9} = {из,!^,^,^}; с7 Θ с8 = {и5,и6,и8} Θ {u5,u7,ii9} = {u6,u7,ii8,ii9}. Таким образом, множество единичных циклов Ci для графа Gi (см. рис. 2.29), полученного путем удаления 10-го ребра из графа Ks, состоит из следующих единичных циклов: ci = {ubu2,u5}; c2 = {ubu3,u6}; c3 = {иьщ,^}; с4 = {и2,и3,и8}; с5 = {и2,щ,и9}; с7 = {и5,и6,и8}; с8 = {и5,и7,и9}. 56

Рис. 2.30. Граф К5 с удаленными ию и ιΐ2 ребрами и его пять четырехвершинных подграфов. Продолжаем удалять ребра из графа К5, удалим ребро ιΐ2 (см. рис. 2.30). Из множества единичных циклов Ci = {ci,C2,C3,c4,C5,c7,c8} удаляются все циклы, включающие 2-е ребро: ci = {111,112,115}; с4 = {ιΐ2,ιΐ3,ιι8}; с5 = {u2,U4,u9}. Остаются единичные циклы: С2 = {ui,u3,u6}; с3 = {ui,U4,u7}; с7 = {u5,u6,u8}; с8 = {u5,u7,u9}. И должны в перспективе образоваться новые единичные циклы длиной четыре: Ci θ С4 = {Ι1ι,112,115} Θ {112,113,118} = {lli,U3,ll5,ll8}; Ci θ C5 = {Ι1ι,112,115} Θ {112,114,119} = {Ui,U4,U5,U9}; C4 θ C5 = {U2,U3,U8} Θ {U2,U4,U9} = {U3,U4,U8,U9}. Однако включение во множество оставшихся единичных циклов двух первых невозможно, так как они могут быть образованы как результат кольцевого суммирования из оставшихся единичных циклов (см. рис. 2.30): ci θ с4= {ui,u3,u6} Θ {u5,u6,ii8} = {ubu3,u5,u8}; ci θ c5 = {ui,U4,u7} Θ {ii5,u7,u9} = {111,114,115,119}; Вновь образованный единичный цикл с4>5 включается во множество оставшихся единичных ЦИКЛОВ: С4 θ C5 = {U3,U4,U8,U9}. Таким образом, множество единичных циклов Сг для графа G2 (см. рис. 2.30) полученного путем удаления 10-го и 2-го ребер из графа К5, состоит из следующих единичных циклов: Рис. 2.31. Граф Ks с удаленными 10,2,7 ребрами и его пять четырехвершинных подграфов. 57

C2 = {ui,u3,u6}; c3 = {ui,U4,u7}; c7 = {u5,u6,u8}; c8 = {u5,u7,u9}; c4,5 = {u3,U4,u8,u9}. Продолжаем удалять ребра из графа К5, удалим ребро и7 (см. рис. 2.31). Из множества единичных циклов С2 = {с2,сз,с7,С8 c4,s} удаляются все циклы, включающие 7- ое ребро: с3 = {ubU4,u7}; с8 = {u5,u7,u9}. Остаются единичные циклы: С2 = {ui,u3,u6}; с7 = {ιΐ5,ιΐ6,ιι8}, с4,5 = {u3,U4,u8,u9}. И должны в перспективе образоваться новые единичные циклы: Сз Θ C8 = {Ui,U4,U7} Θ {U5,U7,119} = {lli,U4,ll5,ll9}; Данный цикл сз,8 может быть включен во множество оставшихся единичных циклов, так как он не может быть образован как результат кольцевого суммирования из оставшихся единичных циклов (см. рис. 2.31): Таким образом, множество единичных циклов Сз для графа G3, полученного путем удаления 10-го, 2-го и 7-го ребер из графа К5, состоит из следующих единичных циклов: С2 = {lli,U3,U6}; C7 = {ll5,U6,ll8}, C4,5 = {ll3,U4,U8,ll9}; С3,8 = {Ui,U4,U5,U9}. Продолжаем удалять ребра из графа К5, удалим ребро ιΐι (см. рис. 2.32). Из множества единичных циклов Сз = {с2,с7,с4,5,сз,8} удаляются все циклы, включающие 1-е ребро: С2 = {lli,U3,U6}; С3,8 = {Ui,U4,U5,U9}. Остаются единичные циклы: С7 = {U5,U6,U8}, C4,5 = {U3,U4,U8,U9}. И должны в перспективе образоваться новые единичные циклы: С2 Θ С3>8 = {Ui,U3,U6} Θ {Ui,U4,U5,U9} = {ll3,U4,ll5,ll6,ll9}; ©-ЧЭ ©■ виЧН) Θ- GH-O Θ-8-© Θ Рис. 2.32. Граф К5 с удаленными 10,2,7,1 ребрами и его пять четырехвершинных подграфов. Дальнейшее образование путем удаления ребер можно приостановить, так как полученный цикл равен кольцевой сумме оставшихся циклов: С7 Θ C4,5 = {ll5,U6,ll8} Θ {U3,U4,U8,U9} = {113,114,115,116,119}. 58

Таким образом, множество единичных циклов для графа G4 (см. рис. 2.32), полученного путем удаления 10-го, 2-го, 7-го и 1-го ребер из графа К5 состоит из следующих единичных циклов: С7 = {U5,U6,U8} И С4,5 = {U3,U4,U8,U9} ИЛИ С2 = {Ui,U3,U6} И С3,8 = {Ui,U4,U5,U9}. 4 @_J_0 ©-L-0 Θ-ЧЭ ($Η^Θ Θ GH-Θ Q-ЧЭ Θ Рис. 2.33. Граф Ks с удаленными 10,2,7,6 ребрами и его пять четырехвершинных подграфов. Если удалить 6-ое ребро вместо 1-го ребра (см. рис. 2.33), то из множества единичных циклов Сз = {с2,С7, С4,5,сз,8} удаляются все циклы, включающие 6-е ребро: с2 = {ui,u3,u6}; с7 = {u5,u6,ii8}. Остаются единичные циклы: С4,5 = {U3,U4,U8,U9}; С3,8 = {Ui,U4,U5,U9}. И должны в перспективе образоваться новые единичные циклы: с2 θ с7 = {ui,U4,u7} Θ {u5,u7,u9} = {ui,u3,u5,u8}; Дальнейшее образование путем удаления ребер можно приостановить, так как полученный цикл сг,с7 равен кольцевой сумме оставшихся циклов: С4,5 θ С3,8 = {U3,U4,U8,U9} Θ {Ui,U4,U5,U9} = {Ui,U3,U5,U8}. Таким образом, множество единичных циклов для графа Gs полученного путем удаления 10-го, 2-го, 7-го и 6-го ребер из графа Ks, состоит из следующих единичных циклов: С2 = {Ui,U3,U6} И С7 = {115,116,118} ИЛИ С4,5 = {U3,U4,U8,U9} И С3,8 = {Ui,U4,U5,U9}. Аналогичные рассуждения можно провести для любого графа Gen вершинами, удаляя соответствующие ребра из полного графа Кп. 2.11. Алгоритмы для выделения множества единичных разрезов и циклов Таким образом, формирование множества единичных циклов можно осуществить двумя способами: • первый способ основан на выделении и сравнении циклов, проходящих по каждому ребру алгоритмом поиска в ширину с учетом теоремы Менгера; • второй способ основан на методе удаления ребер из полного графа с соответствующим 59

удалением единичных циклов полного графа и в случае необходимости включения в оставшееся множество единичных циклов, которые образуются как кольцевая сумма из удаленных единичных циклов. Произведя сравнительный анализ, можно сказать следующее: • количество единичных циклов в графе является постоянной величиной, равной или большей цикломатического числа графа, и не зависит от способа их выделения, в то время как множество фундаментальных циклов в точности равно цикломатическому числу графа и зависит от выбора дерева; • длина единичных разрезов графа определяет локальные степени вершин. Количество единичных циклов для полного графа с η вершинами определяется по формуле: ΙΗ_η(η-1)(η-2) N 1 (2.9) 2.11.1. Формирование множества единичных циклов алгоритмом поиска в ширину [Инициализация], m - количество ребер в графе, η - количество вершин в графе. Текущий номер ребра (mt:= 0). Шаг 1. [Выбор ребра графа]. Выбираем очередное ребро графа, прибавляя к предыдущему номеру единицу (mt:=mt+l). Если текущий номер ребра меньше или равен (m<mt), то идем на шаг 2. Иначе конец работы алгоритма. Шаг 2. [Прямая разметка ребра]. Приписываем первой выбранной из вершин ребра вес = 1, а другой - вес = 2, алгоритмом поиска в ширину распространяем волну относительно непомеченных вершин графа. Идем на шаг 3. Шаг 3. [Выбор и запись простых циклов минимальной длины после прямой разметки]. Выделяем простые циклы методом обратного хода. Записываем циклы и идем на шаг 4. Шаг 4. [Обратная разметка ребра]. Приписываем первой выбранной из вершин ребра вес = 2, а другой - вес = 1, то есть меняем направление разметки. Алгоритмом поиска в ширину распространяем волну относительно непомеченных вершин графа. Идем на шаг 5. Шаг 5. [Выбор и запись простых циклов минимальной длины после обратной разметки]. Выделяем простые циклы методом обратного хода. Записываем циклы и идем на шаг 6. Шаг 6. [Сравнение простых циклов]. Сравниваем простые циклы минимальной длины, сформированные прямой и обратной разметкой вершин данного ребра. Если циклы в обеих записях совпадают, то записываем их как единичные циклы во множество единичных циклов Ст, предварительно проверяя их на совпадение с ранее записанными. Идем на шаг 1. 60

2.11.2. Формирование множества единичных циклов из циклов полного графа [Инициализация]. Существует множество единичных циклов полного графа на η вершин, записанных как множество ребер цикла Mr и записанных как множество вершин цикла Mv, хранящихся в виде связного списка. Имеется массив номеров исключаемых ребер из полного графа. Шаг 1. [Перебор исключаемых ребер]. Последовательно выбираем текущее ребро для исключения. Если список ребер не исчерпан, идем на шаг 2. Иначе конец работы алгоритма. Шаг 2. [Выбор исключенного ребра графа]. Выбираем очередное исключаемое ребро графа. Формируем множество новых простых циклов как кольцевую сумму всех попарно пересекающихся по данному ребру единичных циклов в записи по ребрам. Одновременно формируем такое же связное множество циклов в записи по вершинам, как объединение выбранных циклов по вершинам. Идем на шаг 3. Шаг 3. [Удаление единичных циклов]. Связно удаляем единичные циклы, имеющие исключаемое ребро. Идем на 4. Шаг 4. [Проверка на включение]. Проверяем множество новых простых циклов на включение с множеством единичных циклов по записям в виде вершин. Если включение имеется, то такие простые циклы не включаются во множество единичных циклов. Если включения нет, то производится запись в массив единичных циклов. Идем на шаг 1. Сказанное рассмотрим на примере графа К5 (см. рис. 2.28). Пусть задано множество ребер {112,116,117} для удаления из полного графа. Связное множество единичных циклов запишем в виде связного списка: Множество Mv -> {Х1,Х2,Хз} -> {Xl#X2#X4} -> {Xi,X2,Xs} -> {Χι#Χ3#Χ4} -> {Xi,X3,Xs} -► {Xi,X4,Xs} -> {X2#X3#X-i} -> {X2,X3,Xs} -+ {X2,X4,X5> -► {X3,X4,Xs} Исключаем второе ребро ιΐ2. Формируем новое множество простых циклов: Цикл Новое Мг Новое Mv ΟιθΟ, {Ui,U2,U5} θ {U2,U3,U8} {Ui,U3,U5,U8} -► {Χι,Χ2,Χ3> ^ {Χι,Χ3,Χ4> {Χι,Χ2,Χ3,Χ4> С1©С5 {Ui,U2,U5} θ {U2,U4,U9} {Ui,U4,U5,U9} -► {Х1,Хг,Хз} υ {Χι,Χ3,Χ5} {Xi,X2,X3,Xs} Цикл Ci c2 Сз c4 C5 Сб c7 c8 C9 Сю Множество Mr {Ui,U2,U5} {Ui,U3,U6} {Ui,U4,U7} {U2,U3,U8} {u2,u4,u9} {U3,U4,Uio} {u5,u6,u8} {U5,U7,U9} {u6,u7,Uio}; {U8,U9,Uio} 61

C4 θ C5 {U2,U3,U8} Θ {U2,U4,U9} {Ui,U3,U4,U5} {Xl,X3,X4} U {Xl,X3,X5} {Xi,X3,X4,Xs} Как видно, после исключения единичных циклов ci,C4,cs, имеющих ребро U2, новые простые циклы включают следующие единичные циклы С2,С7,С9,Сб,сз,С8,сю. Например, новый цикл (ci Θ С4) —> {χι,Χ2,Χ3,Χ4} включает {χι,χ2,Χ4} и {х2,хз,Х4}· Новый цикл (ci Θ С5) —> {χι,Χ2,Χ3,Χ5} включает {xi,X2,xs} и {х2,хз,Х5}· Новый цикл (с4 Θ ев) —> {χι,Χ3,Χ4,Χ5} включает {xi,X4,xs} и {хз,Х4,Х5}· Поэтому во множестве новых циклов отсутствуют циклы для включения во множество единичных циклов. Множество Mv -» {Xl,X2,X4> -► {Xi,X2,Xs} -> {Х11Х41Х5} -> {Х2,ХЗ,Х4> -► {Х2,ХЗ,Х5> -> {Х2,Х4,Х5> -> {ХЗ,Х4,Х5> Исключаем ребро щ. Формируем новое множество простых циклов: Цикл Новое Мг Новое Mv С2вС7 {Ul,U3,U6} θ {U5,U6,U8} {Ul,U3,U5,U8} -> {Χΐ,ΧΣ,Χ*} U {Х2,ХЗ,Х4> {Xl,X2,X3,X4> СгвСд {Ui,U3,U6} θ {U6,U7,Uio} {Ui,U3,U7,Uio} -► {Xi,X2,X4} U {x2,X4,X5} {Xi,X2,X4,Xs} С7вСд {U5,U6,U8} θ {U6,U7,Uio} {U5,U7,U8,Uio} -► {Х2,Хз,Х4> U {X2,X4,Xs} {Х2,Хз,Х4,Х5} После исключения единичных циклов С2,С7,С7, имеющих ребро U6, некоторые новые простые циклы включают в себя оставшиеся единичные циклы, а некоторые - нет. Например, новый цикл (с2 Θ С7) —» {хьХ2,хз,Х4} не включает в себя оставшиеся единичные циклы и поэтому может быть включен во множество единичных циклов. Новый цикл (с2 θ cs>) —> {χι,Χ2,Χ4,Χ5} включает {xi,X2,xs} и {χι,Χ4,Χ5}. Новый цикл (с7 Θ С9) —> {х2,хз,Х4,Х5} включает {х2,хз,Х5} и {хз,Х4,Х5}· Поэтому циклы (с2 Θ С9) и (с7 Θ С9) не могут быть включенными во множество единичных циклов. Цикл с2 Сз с6 с7 с8 с9 Сю Множество Мг {Ui,U3,U6} {Ui,U4,U7} {U3,U4,U10} {u5,u6,u8} {u5,u7,u9} {u6,u7,u10}; {u8,u9,u10} Цикл сз Сб c8 Сю Множество Mr {ui,114,117} {u3,u4,Uio} {115,117,119} {u8,u9,Uio} -> -> -> -> Множество единичных циклов изменится. Цикл сз Сб Множество Mr {Ui,U4,U7} {u3,u4,Uio} -> -> Множество Mv {Xl,X2,X5} {Xl,X4,X5} {X2,X3,X5} {X3,X4,X5} Множество Mv {Xl,X2,X5} {Xl,X4,X5} 62

c8 Сю c2 c7 {u5,u7,u9} {u8,u9,Uio} {Ui,U3,U5,U8} -> -> -> {x2,X3,X5} {X3,X4,X5} {Xl,X2,X3,X4} Новое Mv {ХЬХ2,ХЗ,Х5} Исключаем ребро U7. Формируем новое множество простых циклов: Цикл Новое Mr Сз Θ С8 {Ui,U4,U7} θ {U5,U7,U9} {UbU4,U5,U9} -> {хьХ2,Х5} U {x2,X3,X5} После исключения единичных циклов с3,С8, имеющих ребро ιΐγ, новый простой цикл не включает в себя оставшиеся единичные циклы. Поэтому он может быть включен во множество единичных циклов. Цикл с6 Сю с2 с7 Множество Mr {u3,u4,Uio} {u8,u9,Uio} {Ui,U3,U5,U8} -> -> -> Множество единичных циклов изменится. Цикл с6 Сю с2 с7 Сз с8 Множество Mr {u3,u4,Uio} {u8,u9,Uio} {Ui,U3,U5,U8} {ubU4,U5,U9} -> -> -> -> Множество Mv {Xl,X4,X5} {X3,X4,X5} {Xl,X2,X3,X4} Множество Mv {Xl,X4,X5} {X3,X4,X5} {Xl,X2,X3,X4} {Xl,X2,X3,X5} Таким образом, для графа с удаленными ребрами ιΐ2,ιΐ6,ιΐ7 из полного графа оставшиеся единичные циклы образуют множество единичных циклов усеченного графа. 2.12. Множество единичных разрезов и циклов как инварианты графа Теперь покажем, что вектор множества единичных циклов тоже есть инвариант графа. Инвариант графа - это число (функция) графа G, которое принимает одно и то же значение на любом графе, изоморфном G. Пусть f-функция, относящая каждому графу G некоторый элемент f(G) из множества Μ произвольной природы (элементами множества Μ чаще всего служат числа и системы чисел, векторы, многочлены, матрицы). Эту функцию будем называть инвариантом, если на изоморфных графах её значения совпадают, т.е. для любых G и G G= G => f(G) = f(G) (2.10) Как известно, наиболее важные инварианты связного графа следующие: Количество вершин графа п. Количество ребер графа т. Вектор локальных степеней графа S. Плотность φ (G) - число вершин наибольшего полного подграфа (наибольшей клики) в G. 63

Неплотность s(G) - число вершин наибольшего безреберного подграфа графа G, т.е. наибольшее количество его попарно несмежных вершин. Хроматическое число γ (G) - это наименьшее число подмножества вершин при разбиении множества вершин на непересекающиеся непустые подмножества X = XiuX2uX3u...uXY (2.11) и другие инварианты [15]. Множество единичных циклов также можно считать инвариантом графа, так как их количество и длина единичных циклов постоянны для данного графа и изменяются, если изменяются другие характеристики графа. Подпространство разрезов и подпространство циклов являются нормированными пространствами, так как любому элементу подпространства можно поставить в соответствие неотрицательное вещественное число |/|, называемое нормой. В данном случае для подпространства разрезов - это длина разреза, а для подпространства циклов - это длина цикла. Причем, вновь введенное понятие удовлетворяет следующим условиям: • |/| > 0 при / Φ О, |0| = 0. • II/. + /J < II/, II +1/, II для любых l\ e R, /2 e R. || 1 ζ || || 11| || ζ И х ' ^ • ||о/| = |а|/| для любого / е R и вещественного числа а. С учетом последнего, каждую вершину графа G можно характеризовать вектором, описывающим единичные циклы, проходящие по данной вершине в виде: Xi(Pixh>P2xi2>···) (2Л2) где/? ι - количество единичных циклов длиной 1\, рг- количество единичных циклов длиной h и т.д., причем /1</2</з<.... Например, запись хп{2 χ 3,1 χ 4) означает, что по вершине χΐ2 проходят два единичных цикла длиной 3 и один единичный цикл длиной 4. Каждое ребро графа G также можно характеризовать вектором следующего вида: uiJ(xi;xJ;klxll,k2xl2,...) = uiJ(pnxln,pi2xli2^ (2.13) где/7/1 - количество единичных циклов длиной 1ц, принадлежащих вершине Х[, Pi2 - количество единичных циклов длиной l-α, принадлежащих вершине хь ..., /?ji - количество единичных циклов длиной /ji, принадлежащих вершине jtj, ρμ - количество единичных циклов длиной /j2, принадлежащих вершине х^, 64

k\ - количество единичных циклов длиной /ι, включающих ребро щ, кг - количество единичных циклов длиной /2, включающих ребро щ, и т.д., причем /1</2</з<·.. Например, запись И5,б(5хЗ, 2χ4,1χ5;4χ3,2χ4,1χ5;4χ3,2χ4,1χ5) означает, что по ребру, инцидентному вершинам xs и Хб, проходят четыре единичных цикла длиной 3, два единичных цикла длиной 4 и один единичный цикл длиной 5. В свою очередь, по вершине xs проходит пять единичных циклов длиной 3, два единичных цикла длиной 4 и один единичный цикл длиной 5. А по вершине Хб проходит четыре единичных цикла длиной 3, два единичных цикла длиной 4 и один единичный цикл длиной 5. Множеству единичных циклов можно также поставить в соответствии вектор вида: Yc= Οτ{ρλ*Ιλ,ρ2*12,...), (2.14) где/?1 - количество единичных циклов во множестве Ст длиной 1\\ рг - количество единичных циклов длиной h во множестве Ст и т.д., причем /ι</2</3<.... Таким образом, граф G характеризуется еще одним инвариантом - вектором длин единичных циклов. В общем случае, любая вершина графа может характеризоваться двумя параметрами: локальной степенью и суммой длин единичных циклов проходящих по данной вершине. А любое ребро графа - тремя параметрами: два первых - это локальные степени инцидентных вершин, а третий параметр - это сумма длин единичных циклов, проходящих по ребру и по инцидентным для данного ребра вершинам. 65

Глава 3. СВОЙСТВА МНОЖЕСТВА ЕДИНИЧНЫХ ЦИКЛОВ Рассмотрим основные свойства множества единичных циклов графа. 3.1. 0-подмножество единичных циклов и дубль-циклы в графе В этом разделе вводится фундаментальное понятие О-подмножества единичных циклов и их основные свойства. По поводу единичных циклов следует сказать: так как каждый суграф графа G представляет собой вектор из пространства суграфов £g размерностью т, то система точек xo,xi,X2,.-->Xk m - мерного линейного пространства £g называется независимой, если система векторов (χι-χο), (х2-хо),..., (xk-xo) (3.1) линейно независима. Очевидно, что независимость возможна и при к < т. Система (3.1) линейно независима тогда и только тогда, когда из соотношений λοΧο + λιΧι + λ2Χ2 + ...+ XkXk = 0. (3.2) λ0 + λι + λ2+ ...+ Xk = 0 (3.3) вытекает X0 = Xi = X2 = ...= Xk = 0. (3.4) Здесь λο,λιΛ2ν··λ*- действительные числа. Таким образом, свойство системы xo,xi,X2,...,Xk быть независимой не зависит от порядка нумерации точек. Кроме того, ясно, что если система точек независима, то всякая её подсистема также независима. Покажем, что если система векторов (3.1) линейно независима, то из соотношений (3.2) и (3.3) вытекает (3.4). В силу (3.3) соотношение (3.2) переписывается в форме (λι + λ2 + ...+ Xk) xo + λιχι + λ2Χ2 + ...+ XkXk = 0, или иначе λι(χι - xo) + λ2(χ2 - xo) +...+ Xk(xk - xo) = 0; но так как система (3.1) линейно независима, то из последнего вытека