Cykl (teoria grafów)

W nieukierunkowane wykresie , A cykl jest szereg kolejnych krawędzi ( prosty łańcuch ), którego dwa punkty końcowe są identyczne. W grafach skierowanych równoważnym pojęciem jest obwód , nawet jeśli czasami mówimy o cyklu (na przykład w wyrażeniu skierowany graf acykliczny ).

Termin cykl czasami określa również wykres cyklu składający się z podstawowego cyklu o długości n . VSnie{\ displaystyle C_ {n}}

Terminologia

Jeśli łańcuch jest elementarny, to znaczy nie przechodzi dwukrotnie przez ten sam wierzchołek, wówczas mówimy o cyklu elementarnym . Cykl elementarny nie zawiera innego cyklu. W cyklu elementarnym każdy wierzchołek ma stopień równy dwa.

Długość elementarnego cyklu jest liczbą krawędzi (lub wierzchołków). Biorąc pod uwagę wykres , minimalną długość jego cyklu nazywany jest siatka o , podczas gdy maksymalna długość jego cyklu nazywany jest obwodem o . sol{\ displaystyle G}sol{\ displaystyle G}sol{\ displaystyle G}

Jeśli na grafie dwa wierzchołki cyklu są połączone krawędzią, która nie należy do cyklu, krawędź ta nazywana jest cięciwą cyklu. Cykl G jest indukowana w kiedy nie ma strun. Mówi się, że wykres jest kordowy lub triangulowany, jeśli każdy z jego cykli czterech lub więcej wierzchołków ma sznur. sol{\ displaystyle G}

Gdy cykl zawiera nieparzystą liczbę (odwrotnie parzystą) krawędzi, nazywa się to cyklem nieparzystym ( cykl odwrotnie parzysty ).

W ważonych wykresów The masy cyklu jest sumą mas krawędzi zawiera. Jeśli ta waga jest ujemna, mówimy o cyklu wchłaniania .

Obecność cykli

Twierdzenie  -  prosty wykres minimalnej stopnia ma cykl o długości co najmniej równej . δ≥2{\ displaystyle \ delta \ geq 2}(δ+1){\ Displaystyle (\ delta +1)}

Demonstracja

sol{\ displaystyle G}ma co najmniej jeden ciąg, ponieważ . Albo najdłuższy z tych łańcuchów. δ≥2{\ displaystyle \ delta \ geq 2}(v0,v1,⋯,vnie){\ displaystyle (v_ {0}, v_ {1}, \ cdots, v_ {n})}

Rozważmy sąsiadów . Wszystkie są częścią tego łańcucha, ponieważ w przeciwnym razie moglibyśmy zbudować dłuższy łańcuch, łącząc sąsiada, który nie należy do łańcucha. vnie{\ displaystyle v_ {n}}

Niech będzie sąsiadem, którego indeks jest minimalny (tj. Najbardziej oddalony ). Wzdłuż łańcucha znajduje się co najmniej wierzchołki bo wykres jest prosty. Na przykład góra znajduje się co najmniej w wierzchołkach tego łańcucha. vm{\ displaystyle v_ {m.}}m{\ displaystyle _ {m.}}vnie{\ displaystyle v_ {n}}vm{\ displaystyle v_ {m.}}deg⁡(vnie){\ displaystyle \ deg (v_ {n})}vnie{\ displaystyle v_ {n}}deg⁡(vnie)≥δ{\ Displaystyle \ deg (v_ {n}) \ geq \ delta}vm{\ displaystyle v_ {m.}}δ{\ displaystyle \ delta}vnie{\ displaystyle v_ {n}}

Cykl ma więc długość co najmniej równą . (vm,vm+1,⋯,vnie,vm){\ displaystyle (v_ {m.}, v_ {m + 1}, \ cdots, v_ {n}, v_ {m.})}δ+1{\ displaystyle \ delta +1}

Niekierunkowy graf bez cykli nazywany jest lasem . Z powyższego twierdzenia wynika, że ​​las musi koniecznie mieć wierzchołki stopnia zerowego (izolowane) lub pierwszego stopnia (liście). Ten warunek nie jest wystarczający, wykres o minimalnym stopniu zerowym lub jeden może nadal zawierać cykle.

Powiązane problemy

• Problem cyklu Hamiltona polega na znalezieniu cyklu elementarnego przechodzącego przez wszystkie wierzchołki.
• Problem cyklu Eulera polega na znalezieniu cyklu, który przechodzi dokładnie raz przez każdą krawędź.
• Problem chińskiego listonosza jest znalezienie krótszy cykl przechodzenia przynajmniej raz przez każdą krawędź.

Zobacz też

• Graf acykliczny

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">