Halina gróf

A gráfelméletben a Halin-gráf egy olyan síkgráf , amely egy legalább 4 csúcsból álló fából épül fel , és egyiknek sincs pontosan két szomszédja. A fát úgy rajzoljuk meg a síkon , hogy egyetlen él se metszi egymást, majd éleket adunk hozzá, hogy az összes levelét ciklusba kapcsoljuk [1] . A Halin grófok Rudolf Halin német matematikus nevéhez fűződik.aki 1971 -ben tanulmányozta őket [2] , de Halin köbös gráfjait egy évszázaddal korábban tanulmányozta Thomas Kirkman angol matematikus.[3] .

Épület

 A Halin-gráf a következőképpen épül fel : legyen egy síkba ágyazott fa négy vagy több csúcsgal úgy, hogy a gráf egyik csúcsának sincs kettes fokozata (vagyis egyetlen csúcsnak sincs pontosan két szomszédja). A Halin-gráf úgy jön létre, hogy a gráfhoz hozzáadunk egy ciklust, amely átmegy az összes levélen oly módon, hogy a táguló út sík maradjon.

Példák

A csillag  olyan fa, amelynek egyetlen belső csúcsa van. Halin konstrukcióját alkalmazva kereket , piramisgráfot kapunk . A háromszög-prizmagráf egyben Halin- gráf is - megrajzolható úgy, hogy az egyik téglalap alakú lapja egy külső ciklus, a fennmaradó élek pedig négy levelű, két belső csúcsú és öt élű fát alkotnak.

A Frucht-gráf , a két legkisebb , nem triviális automorfizmusú köbös gráf egyike, szintén Halin-gráf.

Tulajdonságok

Bármely Halin-gráf 3-kapcsolt , ami azt jelenti, hogy nem lehet egy gráfot két gráfra felosztani két csúcs eltávolításával. Szintén él-minimálisan 3-kapcsolatos, ami azt jelenti, hogy bármely él eltávolítása után a gráf már nem 3-as összeköttetésű [1] . Steinitz tétele szerint , mivel egy 3-kapcsolatú síkgráf, a Halin-gráf egy konvex poliéder csúcsainak és éleinek halmazaként ábrázolható . Tehát ez egy poliéder gráfja , de ebben az esetben is, mint a poliéder bármely gráfjának, a síkba való beágyazódása egyedi a külső lapja kiválasztásáig [1] .

Bármely Halin-gráf Hamilton-gráf , és bármely él egy Hamilton-ciklushoz tartozik. Ezen túlmenően bármely Halin-gráf Hamilton-gráf marad bármely csúcs eltávolítása után [4] . Mivel minden 2-es fokú csúcs nélküli fa két levelet tartalmaz ugyanazzal a szülővel, minden Halin-gráf tartalmaz egy háromszöget. A Halin-gráf nem lehet sem háromszög nélküli gráf , sem kétrészes gráf . Pontosabban, bármely Halin-gráf majdnem panciklikus , abban az értelemben, hogy minden hosszúságú ciklusa van 3-tól n -ig, egy páros hosszúság kivételével. Ezen túlmenően bármely Halin-gráf csaknem panciklikus marad az egyik él összehúzódása után, és minden Halin-gráf, amely nem rendelkezik harmadik fokú belső csúcsokkal, panciklikus [5] .

Bármely Halin-gráf faszélessége legfeljebb három [6] . Így számos olyan optimalizálási probléma, amely tetszőleges gráfok esetén NP-teljes , mint például a független halmaz megtalálása Halin-gráfokhoz , megoldható lineáris időben dinamikus programozással [7] .

Egy beágyazott síkgráf gyenge duálisának a síkgráf lapjainak megfelelő csúcsai és a szomszédos lapoknak megfelelő élei vannak (a gyenge duál a duálisból a külső felületnek megfelelő csúcs eltávolításával kapja meg). Halin gróf gyenge duális gráfja mindig bikapcsolt és síkon kívüli . Ez a tulajdonság felhasználható Halin-gráfok jellemzésére – egy síkba ágyazott síkgráf egy Halin-gráf, amelynek a beágyazás külső felülete egy levélciklus, akkor és csak akkor, ha a gyenge duálisa kétszeresen összefüggő és külső síkbeli [8] .

Történelem

Halin 1971-ben javasolta a gráfokat (az úgynevezett Halin-gráfokat), mint a minimális , 3 csúcsponttal összefüggő gráfok osztályát – a gráf minden élére az eltávolítása csökkenti a konnektivitást [2] . Ezek a gráfok akkor nyertek különös jelentőséget, amikor világossá vált, hogy sok olyan algoritmikus probléma, amely tetszőleges síkgráfok esetén megoldhatatlan, hatékonyan megoldható Halin-gráfokon [4] [8] , amit később kis faszélességük következményeként magyaráztak el [ 8]. 6] [7] .

Halin munkája előtt a Halin- féle köbös gráfok felsorolásának problémájával 1856-ban Thomas Kirkman foglalkozott.[3] , 1965-ben pedig Hans Rademacher [9] Rademacher poliéder alapján nevezte el ezeket a gráfokat. Ezeket f lappal rendelkező politópok köbös gráfjaiként határozta meg,amelyek egyik lapjának f − 1 éle van. Azok a grafikonok, amelyek megfelelnek ennek a definíciónak, pontosan Halin köbös gráfjai.

A Halin-gráfokat néha tető nélküli poliédereknek is nevezik [4] , de a "politóp-alapú" elnevezéshez hasonlóan ez a név a köbös Halin-gráfoknak is tulajdonítható [10] . A konvex poliédereket , amelyek gráfjai Halin-gráfok, kupolának is nevezik [11] .

Jegyzetek

  1. ↑ 1 2 3 Matematikai enciklopédia , első kiegészítő kötet, 1988, ISBN 0-7923-4709-9 , p. 281, "Halin Graph" cikk archiválva : 2014. január 11. a Wayback Machine -nél
  2. ↑ 1 2 Halin. Kombinatorikus matematika és alkalmazásai (Proc. Conf., Oxford, 1969). - London: Academic Press, 1971. - 129-136 .
  3. ↑ 1 2  
  4. ↑ 1 2 3 , DOI 10.1007/BF02591867 
  5. ↑ Skowronska. Ciklusok grafikonokban. - Elsevier Science Publishers BV, 1985. - T. 27. - S. 179-194. — (A diszkrét matematika évkönyvei).
  6. ↑ 12 Hans Bodlaender . Korlátozott faszélességű síkgráfok . - Számítástechnikai Tanszék, Utrechti Egyetem , 1988. - (Technical Report RUU-CS-88-14).
  7. ↑ 12 Hans Bodlaender . Az automatákkal, nyelvekkel és programozással foglalkozó 15. nemzetközi kollokvium anyaga. - Springer-Verlag, 1988. - T. 317. - S. 105-118. — (Számítástechnikai előadásjegyzetek).
  8. ↑ 1 2 Maciej M. Sysło, Andrzej Proskurowski. Graph Theory: Proceedings of a Conference held in Lagów, Poland, 1981. február 10-13. - Springer-Verlag, 1983. - Vol. 1018. - P. 248-256. — (Matematikai előadásjegyzetek). - doi : 10.1007/BFb0071635 .
  9. ↑ Hans Rademacher. A poliéderek bizonyos típusainak számáról // Illinois Journal of Mathematics. - 1965. - T. 9 . - S. 361-380 .
  10. ↑ L. Lovász, M. D. Plummer. Kombinatorika (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973). London: Cambridge Univ. Press, 1974. - S. 103-107. London Math. szoc. Előadási jegyzet szer., sz. 13 .
  11. ↑ Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara. Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Kanada, 2013. augusztus 8–10.–2013.–43–48.

Linkek