Szubhamiltoni gráf
A matematika, azon belül a gráfelmélet és gráfábrázolás területén egy szubhamiltoni gráf egy Hamilton-körrel rendelkező síkbarajzolható gráf részgráfja.[1][2]
Definíció
[szerkesztés]Egy G gráf szubhamiltoni, ha G részgráfja az azonos csúcshalmazzal rendelkező aug(G) kiegészített (augmentált) gráfnak, melyre igaz, hogy aug(G) síkbarajzolható és van Hamilton-köre. Ahhoz, hogy ez teljesüljön, magának G-nek síkbarajzolhatónak kell lennie, valamint lehetségesnek kell lennie annak, hogy a síkbarajzolhatóság megtartásával élekkel lehessen kiegészíteni (tehát nem lehet maximális síkbarajzolható) ahhoz, hogy az augmentált gráfban létezhessen minden csúcson pontosan egyszer áthaladó kör. Az aug(G) gráfot a G hamiltoni kiegészítésének nevezik.[2]
Ezzel ekvivalens definíció lenne, hogy G akkor szubhamiltoni, ha egy Hamilton-körrel rendelkező síkbarajzolható gráf részgráfja, az azonos csúcshalmaz megkövetelése nélkül. Tehát, az alternatív definíció szerint lehetséges lenne G-hez csúcsokat és éleket is adni a Hamilton-kör létrehozásához. Ha azonban egy gráfot hamiltonivá lehet alakítani csúcsok és élek hozzáadásával, akkor azt meg lehet tenni csak élek hozzáadásával is, ezért ez az extra szabadság nem ad hozzá lényegeset a definícióhoz.[3]
Egy szubhamiltoni gráf szubhamiltoni köre (subhamiltonian cycle) csúcsok olyan sorozata, melyre igaz, hogy az egymás követő csúcsok közé új élt illesztve a gráf síkba rajzolhatósága megőrződik. Egy gráf pontosan akkor szubhamiltoni, ha van szubhamiltoni köre.[4]
Története és alkalmazásai
[szerkesztés]A szubhamiltoni gráfok családját (bár nem ezen a néven) (Bernhart & Kainen 1979) vezette be, aki igazolta, hogy ezek éppen a kétlapos könyvbe ágyazással rendelkező gráfok.[5] A szubhamiltoni gráfokat és a hamiltoni kiegészítéseket felhasználták a gráfábrázolásban, gráfok univerzális ponthalmazba való beágyazásában, több gráf szimultán beágyazásában és a hierarchikus gráfábrázolásban.[2]
Kapcsolódó gráfcsaládok
[szerkesztés]A síkbarajzolható gráfok némelyik osztálya minden esetben tartalmaz Hamilton-kört, ezért szubhamiltoni is; ezek közé tartoznak a 4-összefüggő síkbarajzolható gráfok[6] és a Halin-gráfok.[7]
Minden, legfeljebb négy maximális fokszámú síkbarajzolható gráf szubhamiltoni,[4] ahogy a szeparáló háromszögek nélküli síkbarajzolható gráfok is.[8] Ha egy tetszőleges síkbarajzolható gráf éleit kettő hosszúságú utakra osztjuk fel, az eredményül kapott felosztott gráf minden esetben szubhamiltoni.[2]
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Subhamiltonian graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods 8 (2): 198–218, DOI 10.1137/0608018.
- ↑ a b c d Di Giacomo, Emilio & Liotta, Giuseppe (2010), "The Hamiltonian augmentation problem and its applications to graph drawing", WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010, Proceedings, vol. 5942, Lecture Notes in Computer Science, Berlin: Springer, pp. 35–46, DOI 10.1007/978-3-642-11440-3_4.
- ↑ Például egy 2003-as technicai riportjában, "Book embeddings of graphs and a theorem of Whitney", Paul Kainen a szubhamiltoni gráfokat a síkbarajzolható Hamilton-körű gráfok részgráfjaiként definiálja a csúcshalmazra vonatkozó megszorítás nélkül, de azt írja: „a szubhamiltoni gráf definíciójában ki lehet kötni, hogy a kiterjesztés csak új élek hozzáadását foglalja magába.”
- ↑ a b Bekos, Michael A.; Gronemann, Martin & Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs", STACS.
- ↑ Bernhart, Frank R. & Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B 27 (3): 320–331, DOI 10.1016/0095-8956(79)90021-2.
- ↑ Nishizeki, Takao & Chiba, Norishige (2008), "Chapter 10. Hamiltonian Cycles", Planar Graphs: Theory and Algorithms, Dover Books on Mathematics, Courier Dover Publications, pp. 171–184, ISBN 9780486466712.
- ↑ Cornuéjols, G.; Naddef, D. & Pulleyblank, W. R. (1983), "Halin graphs and the travelling salesman problem", Mathematical Programming 26 (3): 287–294, DOI 10.1007/BF02591867.
- ↑ Kainen, Paul C. & Overbay, Shannon (2007), "Extension of a theorem of Whitney", Applied Mathematics Letters 20 (7): 835–837, DOI 10.1016/j.aml.2006.08.019.