Ciklus (grafikonelmélet)

Egy irányítatlan gráf , egy ciklus egy sor egymást követő éleket ( egyszerű lánc ), amelynek a két végpont azonos. Az irányított gráfokban ekvivalens fogalom az áramkör , még akkor is, ha néha ciklusról is beszélünk (például az irányított aciklusos gráf kifejezésben ).

A kifejezés ciklus néha szintén kijelöli a ciklus grafikon alkotja elemi ciklus hossza n . VSnem{\ displaystyle C_ {n}}

Terminológia

Ha a lánc elemi, vagyis nem halad át kétszer ugyanazon a csúcson, akkor elemi ciklusról beszélünk . Egy elemi ciklus nem tartalmaz más ciklust. Egy elemi ciklusban minden csúcs foka kettővel egyenlő.

Az elemi ciklus hossza a széleinek (vagy csúcsainak) száma. Adott egy gráf minimális hossza, ami a ciklusok az úgynevezett hálós a , míg a maximális hossza, ami a ciklusok az úgynevezett kerülete az . G{\ displaystyle G}G{\ displaystyle G}G{\ displaystyle G}

Ha egy grafikonon egy ciklus két csúcsát összeköti egy olyan él, amely nem tartozik a ciklushoz, akkor ezt az élt a ciklus akkordjának nevezzük . A G ciklusa akkor indukálódik , amikor nincs húrja. Egy gráfról azt mondjuk, hogy kordális vagy háromszög alakú, ha minden négy vagy több csúcsú ciklusának van egy zsinórja. G{\ displaystyle G}

Ha a ciklus páratlan számú (kölcsönösen páros) élt tartalmaz, akkor páratlan ciklusnak (reciprokul páros ciklusnak ) nevezzük .

A súlyozott grafikonok , a súlya egy ciklus az összege a súlyok az élek tartalmaz. Ha ez a súly negatív, akkor abszorbens ciklusról beszélünk .

A ciklusok jelenléte

Tétel  -  Egy egyszerű , minimális fokú gráfnak legalább egy hosszúságú ciklusa van . δ≥2{\ displaystyle \ delta \ geq 2}(δ+1){\ displaystyle (\ delta +1)}

Demonstráció

G{\ displaystyle G}legalább egy karakterlánca van, mivel . Vagy a leghosszabb ilyen lánc. δ≥2{\ displaystyle \ delta \ geq 2}(v0,v1,⋯,vnem){\ displaystyle (v_ {0}, v_ {1}, \ cdots, v_ {n})}

Tekintsük a . Mindannyian ennek a láncnak a részei, mert különben egy hosszabb láncot építhetnénk úgy, hogy összefűzünk egy, a lánchoz nem tartozó szomszédot. vnem{\ displaystyle v_ {n}}

Legyen az a szomszéd, akinek indexe minimális (azaz a legtávolabb van ). A lánc mentén legalább csúcsai találhatók, mivel a grafikon egyszerű. Mint , a felső van legalább csúcsai keresztül ebben a láncban. vm{\ displaystyle v_ {m}}m{\ displaystyle _ {m}}vnem{\ displaystyle v_ {n}}vm{\ displaystyle v_ {m}}deg⁡(vnem){\ displaystyle \ deg (v_ {n})}vnem{\ displaystyle v_ {n}}deg⁡(vnem)≥δ{\ displaystyle \ deg (v_ {n}) \ geq \ delta}vm{\ displaystyle v_ {m}}δ{\ displaystyle \ delta}vnem{\ displaystyle v_ {n}}

A ciklus tehát legalább egyenlő hosszúságú . (vm,vm+1,⋯,vnem,vm){\ displaystyle (v_ {m}, v_ {m + 1}, \ cdots, v_ {n}, v_ {m})}δ+1{\ displaystyle \ delta +1}

A ciklusok nélküli irányítatlan gráfot erdőnek nevezzük . Az előző tételnek az a következménye, hogy az erdőnek szükségképpen nulla fokú (elszigetelt) vagy egy fokú (levelei) csúcsai vannak. Ez a feltétel nem elegendő, a minimális nulla fokú grafikon vagy az egyik továbbra is tartalmazhat ciklusokat.

Kapcsolódó kérdések

• A Hamilton-ciklus problémája az összes csúcson áthaladó elemi ciklus megtalálása.
• Az euleri ciklus problémája abban áll, hogy megtalálunk egy ciklust, amely pontosan egyszer halad át minden élen.
• A kínai postás feladata, hogy találjon egy rövidebb ciklust, amely legalább egyszer áthalad minden élen.

Lásd is

• Aciklusos grafikon

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