Изменения

Перейти к: навигация, поиск

Циклическое пространство графа

8 байт убрано, 08:35, 9 декабря 2011
Размерность линейного пространства обобщенных циклов
<tex> dim(C) = m - n + k </tex>
|proof=
<tex> dim(C)=dim(Ker(i))=m-Rang(A) </tex>, где <tex> Rang(A) = </tex> максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть цикл в <tex> G </tex>, то из-за того что каждой вершине инцидентно четное число ребер, сума столбцов соответствующих этим ребрам = 0 значит эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex> то он будет ЛЗ. Если же множество ребер не содержит цикл, то набор ЛНЗ (если он ЛЗ, значит коэффициенты взятые из линейной комбинации образовывали образуют <tex> x \in C </tex>, значит существует цикл). Максимальное число ребер, которые мы можем выделить из G и которые не содержат цикл <tex>= n - k </tex> (в каждой компоненте связности выделим цикл).
Итого: <tex> dim(C)=m - n + k </tex>
}}
Анонимный участник

Навигация