Пятница, 25.07.2025, 02:48
Шпоры сук
Главная | Каталог статей | Регистрация | Вход
Меню сайта
Категории раздела
Шпоры по дисмату [36]
Физика [13]
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » Шпоры по дисмату

24. Циклы (фундментальные циклы)

Мультиграф — граф, где между двумя заданными вершинами может быть несколько дуг. Дуги, соединяющие одну и ту же пару вершин, принято называть параллельными. Мультиграф, у которого максимальное число параллельных дуг — s, называют s-графом.

Рассмотрим неориентированный мультиграф (s-граф) Gn — вершин, m — ребёр, p — связных компонент. ρ(G) = n − p — коцикломатическое число (число ребер в остовах всех p связных компонент графа). ν(G) = m − ρ(G) = m − n + p — цикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. ν(G) — наибольшее число независимых круговых токов в электрической цепи. ρ(G) — наибольшее число независимых разностей потенциалов в электрической цепи.

Далее в этом разделе разговор будет вестись о неориентированных графах. Напомним, что циклом в неориентированном графе называется цепь, у которой совпадают начало и конец. Цикл будем называть простым, если в нем нет одинаковых вершин (кроме первой и последней). Такие циклы можно представлять как множества ребёр. Рассмотрим операцию ⊕ сложения по модулю 2 или симметрической разности над множествами ребёр:

M1 ⊕ M2 = {e | (e ∈ M1 ∧ e ∉ M2) ∨ (e ∉ M1 ∧ e ∈ M2) }.

Рассмотрим ряд вспомогательных фактов:

0M = Ø

1M = M

M ⊕ Ø = M

M ⊕ M = Ø

M называется линейной комбинацией {Mi}, если M = ⊕ αiMi, где αi ∈ {0, 1}.

Таким образом множество подмножеств ребёр графа оказывается линейным пространством над полем {0, 1}.

Множество циклов {Zi} называется независимым, если ∀i Zi не является линейной комбинацией остальных.

Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы системы называют фундаментальными. В приведенном на рисунке графе циклы: Φ1 = (1100100), Φ2 = (0010011), Φ3 = (1111000) — образуют фундаментальную систему циклов (разумеется, читатель знаком с формой представления подмножеств некоторого множества в виде битовых векторов). Отметим, что не любая линейная комбинация циклов является циклом (Φ1 ⊕ Φ2 = (1110111) циклом не является).

Теорема

Рассмотрим граф G = (VE): неориентированный, связный (p = 1) и немультиграф (s = 1). Тогда количество фундаментальных циклов в точности равно ν(G) = m − n + 1.

Доказательство. Приведем конструктивное доказательство этого факта (оно одновременно содержит алгоритм построения фундаментальной системы циклов). Рассмотрим T(VET) — некоторый остов графа G, который существует ввиду связности. Этому остову соответствует кодерево T*(VET*), где ET* = E \ ET. Отметим, что кодерево разумеется не является деревом. Каждое ребро e ∈ T* из кодерева при добавлении его к остову T очевидно порождает ровно один простой цикл Ze. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро e.

Покажем, что любой цикл графа G зависит от {Ze}, где e пробегает все множество ребер кодерева T*. Понятно, что любой элемент фундаментальной системы зависит от неё же самой, поэтому далее будем считать, что Z ≠ Ze.

Пусть теперь некоторый цикл Z содержит ребра e1, …, ek ∈ T*. Такие ребра в Z обязательно есть, в противном случае Z ⊂ T, что невозможно, так как T — дерево. Обозначим цикл, соответствующий ребруei, как Zi. Докажем индукцией по k, что Z = Z1 ⊕ … ⊕ Zk.

База: пусть k = 1, тогда e1 ∉ TZ \ {e1} ⊂ T и Z = Z1, так как если бы Z ≠ Z1, то концы e1 были бы соединены в T двумя цепями, что невозможно.

Пусть (индукционное предположение) Z = Z1 ⊕ … ⊕ Zm для всех циклов Z, содержащих m < k ребер из кодерева. Далее ребра кодерева будем называть хордами. Рассмотрим цикл Z c k хордамиe1, …, ek ∈ T*. Рассмотрим Zk. Имеем Z′ := (Z \ {ek}) ∪ (Zk \ {ek}) — тоже цикл (возможно, не простой). Но Z′ содержит только k − 1 хорду e1, …, ek−1. По индукционному предположению Z′ = Z1⊕ … ⊕ Zk−1. Добавим к этому циклу Zk. Имеем:

Z′ ⊕ Zk = (Z \ {ek}) ∪ ((Zk \ {ek}) ⊕ Zk) = (Z \ {ek}) ∪ {ek} = Z.

Таким образом, {Ze}, где e ∈ T*, является фундаментальной системой циклов. Поскольку все фундаментальные системы содержат одинаковое число элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом T. Число ребер в ней равно числу ребер в кодереве.

|ET*| = |E| − |ET| = m − (n − 1) = m − n + 1.

Алгоритм построения фундаментальной системы циклов (для графа такого, как в условии теоремы):

Построим любое остовное дерево T исходного графа G.

Добавим к T некоторое ребро e, которое является ребром графа, но не принадлежит остову.

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

Все циклы {Ze} (соответствующие всем ребрам, взятым не из остова) образуют фундаментальную систему циклов.

Категория: Шпоры по дисмату | Добавил: DmitryMax (18.06.2014)
Просмотров: 397 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:
Форма входа
Поиск