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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение:

Фундаментальный цикл графа [math]G[/math] относительно остова [math]T[/math] (англ. fundamental cycle) — простой цикл [math]C[/math], полученный путем добавления к остову [math]T[/math] ребра [math]e_1e_2 \notin T.[/math]

Пример фундаментального цикла в графе. Красным выделен фундаментальный цикл, полученный добавлением ребра [math](3, 4)[/math]

Теорема:

Множество всех фундаментальных циклов относительно любого остова [math]T[/math] графа [math]G[/math] образует базис циклического пространства этого графа.

Доказательство:

[math]\triangleright[/math]

Рассмотрим остов [math]T[/math] графа [math]G[/math] и фундаментальные циклы [math] C_1 \ldots C_s [/math] относительно остова [math]T[/math]. В каждом цикле есть ребро [math]e_i[/math], которое принадлежит ровно одному из [math] C_1 \ldots C_{s} [/math]. Поэтому сумма различных фундаментальных циклов относительно остова [math]T[/math] не является пустым графом, из чего следует, что [math] C_1 \ldots C_s [/math] линейно независимы. Докажем, что любой цикл из циклического пространства графа [math]G[/math] является суммой фундаментальных циклов. Пусть [math]Z[/math] — цикл циклического пространства графа [math]G[/math], [math] e_1 \ldots e_{k} [/math] ребра принадлежащие [math]Z[/math] и не принадлежащие [math]T[/math]. Рассмотрим граф [math] F = Z \oplus C_1 \oplus \ldots \oplus C_{k} [/math]. Каждое из ребер [math] e_{t} , t = 1,\ldots ,k [/math] встречается ровно в двух слагаемых — [math]Z[/math] и [math]C_{k}[/math]. Значит [math]F[/math] содержит только ребра из [math]T[/math]. Так как [math] C_1 \ldots C_{k} [/math] простые циклы, то степени всех их вершин четны, степени вершин [math]Z[/math] тоже четны по лемме, значит степени всех вершин [math]F[/math] четны. Если [math]F[/math] непустой граф, то в [math]F[/math] есть цикл, значит цикл есть и в [math]T[/math]. Значит [math]F[/math] пустой граф, откуда следует что [math]Z = C_1 \oplus \ldots \oplus C_{k} [/math].

[math]\triangleleft[/math]

См. также

• Остовные деревья
• Циклическое пространство графа

Источники информации

• Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6