Síkgrafikon

A síkgráf  olyan gráf , amely úgy rajzolható meg egy síkon , hogy a csúcsokon kívül más éleket nem keresztezhetünk . Síkgráfnak nevezzük a síkgráf bármely konkrét képét egy síkban, ahol nem keresztezik élek nem csúcsokban . Más szóval egy síkgráf izomorf valamilyen síkon ábrázolt síkgráfhoz úgy, hogy csúcsai a sík pontjai, az élei pedig görbék a síkon, amelyek ha metszik egymást, akkor csak mentén. a csúcsokat. Azokat a területeket, amelyekre a gráf feloszt egy síkot, lapjainak nevezzük . A sík határtalan része is egy arc, az úgynevezett külső felület . Bármely síkgráf kiegyenesíthető, azaz átrajzolható a síkon úgy, hogy minden éle vonalszakasz legyen.

Tulajdonságok

Euler-képlet

Összefüggő síkgráf esetén a következő összefüggés áll fenn a csúcsok , élek és lapok száma között (beleértve a külső felületet is):

Euler találta meg 1736-ban [1] , miközben a konvex poliéderek tulajdonságait tanulmányozta . Ez az összefüggés más felületekre is érvényes az Euler-karakterisztikának nevezett tényezőig . Ez a felületi invariáns , síkra vagy gömbre egyenlő kettővel, és például egy tórusz felületére  nulla.

A képletnek számos hasznos következménye van. Először is, egy gráf minden síkbeli halmozásának ugyanannyi lapja van. Másodszor, ha minden oldalt legalább három él határol (feltéve, hogy a gráfnak kettőnél több éle van), és mindegyik él két oldalt választ el , akkor

Következésképpen,

vagyis nagyobb számú él esetén egy ilyen gráf minden bizonnyal nem síkbeli. Ennek az ellenkezője nem igaz: ellenpéldaként vehetjük a Petersen-gráfot . Ebből következik, hogy egy síkgráfban mindig lehet legfeljebb 5 fokos csúcsot találni.

Az általános képlet könnyen általánosítható szétkapcsolt gráf esetén is:

ahol  az összekapcsolt komponensek száma a grafikonon.

Két példa nem síkbeli gráfokra

Teljes gráf öt csúcsgal

Lemma. Öt csúcsú (K 5 ) teljes gráf nem simítható.

Bizonyíték. Ez nem megy neki .

"Házak és kutak"

Három kút problémája . Három ház és három kút van. Lehetséges-e úgy utakat fektetni a házak és kutak közé, hogy minden háztól minden kúthoz egy út vezessen, és ne keresztezze egymást két út? Hidat nem lehet építeni.

Lemma. Egy teljes kétrészes gráf , amelynek minden része (K 3,3 ) három csúcsa van, nem fektethető síkra.

Bizonyíték. Az Euler-képlet szerint a gráfnak 5 lapja van.

Másrészt: bármely lap (beleértve a külsőt is) páros számú élt tartalmaz, ami legalább 4-et jelent. Mivel minden él pontosan két lapban szerepel, a relációt kapjuk , F  az oldalak száma  , E az élek száma. Ebbe az egyenlőtlenségbe behelyettesítjük az F = 5 és E = 9 értékeket , és látjuk, hogy nem teljesül.

A Pontrjagin-Kuratovszkij tétel

Nyilvánvaló az állítás: ha egy G gráf K 5 vagy K 3,3 homeomorf részgráfot tartalmaz , akkor az nem bontható fel a síkon. Kiderül, hogy ennek az ellenkezője is igaz.

Egy gráf akkor és csak akkor sík, ha nem tartalmaz egy öt csúcsból álló teljes gráfhoz (K 5 ) vagy egy „házak és kutak” gráfhoz (K 3,3 ) homeomorf részgráfokat .

A tétel a következő változatban is megfogalmazható (néha Wagner-tételnek is nevezik ).

A gráf akkor és csak akkor sík, ha nem tartalmaz K 5 -re vagy K 3,3 -ra összehúzódó részgráfokat .

Számítógépes síkosság-ellenőrzés

Az első algoritmust a Kuratowski részgráf lineáris időben történő megtalálására Hopcroft és Tarjan fejlesztette ki 1974-ben [2] .

A nem síkbeli gráfok jellemzői

Síkgráfok feladatokban

Színező kártya . Egy sík térképet adott számú színnel kell kiszínezni, hogy bármely két ország, amelynek közös határszakasza van, eltérő színű legyen. Kiderült, hogy enklávék hiányában négy szín mindig elegendő, de ezt az állítást rendkívül nehéz bizonyítani, lásd: Négy szín probléma .

Gráf-helyreigazítás ( Fari tétele ). Bármely síkgráf újrarajzolható úgy, hogy sík maradjon, és az élek szakaszokká váljanak.

Általánosítások

Egy gráf akkor illeszkedik valamilyen felületre, ha élek keresztezése nélkül rárajzolható. A halmozott gráfot geometrikusnak nevezzük , csúcsai a felület pontjai, az élei pedig a rajta lévő vonalak. Azokat a területeket, amelyekre a gráf feloszt egy felületet , lapoknak nevezzük . A síkgráf egy síkon elhelyezett gráf.

A G gráf metszéspontszáma a G  gráf lapos rajzának éleinek legkisebb számú metszéspontja . Így egy gráf akkor és csak akkor sík, ha metszéspontja nulla.

A toroid gráf  egy tóruszra fektethető gráf.

Lásd még

Jegyzetek

  1. ↑ Harari F. Gráfelmélet URSS 126. o
  2. ↑ Hopcroft, John & Tarjan, Robert E. (1974), Efficient planarity testing , Journal of the Association for Computing Machinery vol. 21 (4): 549–568 , DOI 10.1145/321850.321852  .

Linkek