Цикл (теория графов): различия между версиями

В [[Теория графов|теории графов]] два типа объектов обычно называются '''циклами'''.

Один тип '''циклов''', чаще называющиеся '''замкнутым обходом''', состоит из последовательности вершин, начинающейся и заканчивающейся в той же самой вершине, и каждые две последовательные вершины в последовательности смежны. Другой тип циклов, иногда называемых '''простыми циклами''', — это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин. Простые циклы можно описать набором рёбер, в отличие от замкнутых обходов, в которых наборы рёбер (с возможным повторением) не определяют однозначно порядок вершин.

{{книга

| автор = V.K Balakrishnan

| ref = Balakrishnan

}} </ref>

==Циклы без хорд==

[[Порождённый путь|Цикл без хорд]] в графе, также называемый дырой или порождённым циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу. Антидыра — это [[Дополнение графа|дополнение]] дыры. Графы без хорд можно использовать для описания [[Совершенный граф|совершенных графов]] — согласно {{не переведено 5|Строгая теорема о совершенных графах|строгой теореме о совершенных графах||strong perfect graph theorem}} граф является совершенным в том и только в том случае, когда он не содержит дыр и антидыр с нечётным числом вершин больше трёх. [[Хордальный граф]] — это специальный тип совершенных графов, в котором нет дыр, размером больше трёх.