Küszöb grafikon

A gráfelméletben a küszöbgráf egy olyan gráf, amely egy csúcsú gráfból építhető fel a következő két művelet egymás utáni végrehajtásával:

  1. Egy izolált csúcs hozzáadása a gráfhoz
  2. Egy domináns csúcs hozzáadása a gráfhoz, azaz. egyetlen csúcs, amely az összes többi csúcshoz kapcsolódik.

Például az ábrán látható grafikon egy küszöb gráf. Felépíthető egy csúcsból (1. csúcs), és a fekete csúcsokat izolált csúcsokként és a piros csúcsokat domináns csúcsokként számsorrendben hozzáadva.

A küszöbgráfokat Chvatal és Hammer vezette be [1] . A gráfokról szóló fejezet Golumbik [2] könyvében jelent meg , míg Mahadev és Peled könyve [3] teljes egészében a küszöbgráfoknak szentelt.

Alternatív definíciók

Egy ekvivalens definíció a következő: a gráf küszöbérték, ha létezik valós szám , és minden csúcsra olyan súlyt adunk , hogy bármelyik két csúcsra , akkor és csak akkor él, ha .

Egy másik ekvivalens definíció: a gráf küszöbérték, ha létezik valós szám , és minden csúcshoz olyan súlyt adunk , hogy bármely csúcshalmazra akkor és csak akkor független , ha

A "küszöb gráf" elnevezés a definícióból ered: S egy "küszöb" annak a tulajdonságnak, hogy legyen éle, vagy ezzel egyenértékűen, T egy halmaz függetlenségének küszöbe.

Dekompozíció

A csúcsok szekvenciális összeadását használó definícióból egy alternatív módot kaphatunk a küszöbgráf karaktersorozat értelmében történő egyedi leírására. mindig a karakterlánc első karaktereként szolgál, és a gráf első csúcsát képviseli. Minden következő karakter vagy , ami egy elszigetelt csúcsot jelent, vagy , ami egy domináns csúcs hozzáadását jelenti. Például egy karakterlánc egy három levelű csillagot jelöl, de egy három csúcsból álló utat. Az ábrán látható grafikon vonallal ábrázolható

Grafikonok és felismerés összekapcsolt osztályai

A küszöbgráfok a kográfok , osztott gráfok és triviálisan tökéletes gráfok speciális esetei [4] . Minden olyan gráf, amely egyben kográf és egy osztott gráf is, küszöbgráf. Minden olyan gráf, amely triviálisan tökéletes gráf és egy triviálisan tökéletes gráf komplementere is egy küszöbgráf. A küszöbgráfok az intervallumgráfok speciális esetei is . Mindezek az összefüggések a tiltott generált részgráfokkal való jellemzésükkel magyarázhatók. A kográf egy négy csúcsú P 4 generált utak nélküli gráf, a küszöbgráfok pedig a generált P 4 , C 4 vagy 2K 2 részgráfok bázisainak gráfjai [5] . A C 4 négy csúcsból álló ciklus, a 2K 2 pedig a komplementere, vagyis két külön él. Ez megmagyarázza azt is, hogy a küszöbgráfok miért zártak komplementerre. P 4 önkomplementer, ezért ha a gráf nem tartalmaz generált P 4 , C 4 és 2K 2 részgráfokat , akkor a komplementere sem rendelkezik velük [6] .

Heggernes és munkatársai kimutatták, hogy a küszöbgráfok lineáris időben felismerhetők. Ha a grafikon nem küszöbérték, akkor egy akadály jelenik meg P 4 , C 4 vagy 2K 2 formájában .

Lásd még

Jegyzetek

  1. ↑ Chvatal, Hammer, 1977 .
  2. ↑ Golumbic, 1980 .
  3. ↑ Mahadev, Peled, 1995 .
  4. ↑ Emelicsev, Melnyikov, Sarvanov, Tyshkevich, 1990 , p. 227. Következmény 50.11.
  5. ↑ Emelicsev, Melnyikov, Sarvanov, Tyshkevich, 1990 , p. 224. Következmény 50.3.
  6. ↑ Emelicsev, Melnyikov, Sarvanov, Tyshkevich, 1990 , p. 227. Következmény 50.12.

Irodalom

Linkek