112
правок
Изменения
Начало положено
{{Определение
|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex> . Если граф содержит все циклы от <tex> r </tex> до <tex> n </tex>, то такой граф называют <tex> r </tex>-панциклическим.
}}
{{Теорема
|about=J. A. Bondy
|statement=
<tex>G = <V, E> </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geq n^2/4 </tex>.
Тогда верно одно из двух утверждений:
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex> = <tex>K_{n / 2, n / 2}</tex>
}}
{{Теорема
|about=Schmeichel & Hakimi
|statement=
<tex>G = <V, E> </tex> {{---}} гамильтонов граф, <tex>|V| = n, v_1 v_2 v_3 \ldots v_n v_1 </tex> {{---}} его гамильтонов цикл, для которого выполняется неравенство <tex> deg(v_1) + deg(v_n) \geq n </tex>. <br>
Тогда <tex> G </tex> {{---}} панциклический граф, двудольный граф или граф, в котором нет только цикла длины <tex>(n-1)</tex>.
}}
== Ссылки ==
* [https://ac.els-cdn.com/0095895671900165/1-s2.0-0095895671900165-main.pdf?_tid=6388217a-d131-11e7-9e9c-00000aab0f02&acdnat=1511539751_317a50813ff61926478abcae5f032887 Pancyclic Graphs I* J.A. Bondy]
|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex> . Если граф содержит все циклы от <tex> r </tex> до <tex> n </tex>, то такой граф называют <tex> r </tex>-панциклическим.
}}
{{Теорема
|about=J. A. Bondy
|statement=
<tex>G = <V, E> </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geq n^2/4 </tex>.
Тогда верно одно из двух утверждений:
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex> = <tex>K_{n / 2, n / 2}</tex>
}}
{{Теорема
|about=Schmeichel & Hakimi
|statement=
<tex>G = <V, E> </tex> {{---}} гамильтонов граф, <tex>|V| = n, v_1 v_2 v_3 \ldots v_n v_1 </tex> {{---}} его гамильтонов цикл, для которого выполняется неравенство <tex> deg(v_1) + deg(v_n) \geq n </tex>. <br>
Тогда <tex> G </tex> {{---}} панциклический граф, двудольный граф или граф, в котором нет только цикла длины <tex>(n-1)</tex>.
}}
== Ссылки ==
* [https://ac.els-cdn.com/0095895671900165/1-s2.0-0095895671900165-main.pdf?_tid=6388217a-d131-11e7-9e9c-00000aab0f02&acdnat=1511539751_317a50813ff61926478abcae5f032887 Pancyclic Graphs I* J.A. Bondy]
