Zakořeněný graf - Rooted graph

v matematika, a zejména v teorie grafů, a zakořeněný graf je graf ve kterém vrchol byl rozlišen jako kořen.[1][2] Oba režie a neorientovaný byly studovány verze kořenových grafů a existují také definice variant, které umožňují více kořenů.

Zakořeněné grafy mohou být také známy (v závislosti na jejich použití) jako špičaté grafy nebo vývojové grafy. V některých aplikacích těchto grafů existuje další požadavek, aby byl celý graf dosažitelný z kořenového vrcholu.

Variace

v teorie topologických grafů, pojem zakořeněného grafu může být rozšířen tak, aby zvážil více vrcholů nebo více hran jako kořenů. První z nich se někdy v tomto kontextu nazývají vrcholově zakořeněné grafy, aby se odlišily od okrajově zakořeněných grafů.[3] Zajímavé jsou také grafy s více uzly označenými jako kořeny kombinatorika, v oblasti náhodné grafy.[4] Tyto grafy se také nazývají vynásobte zakořeněné grafy.[5]

Podmínky zakořeněné řízený graf nebo zakořeněný digraf také vidět rozdíly v definicích. Zjevnou transplantací je považovat digraf zakořeněný identifikací konkrétního uzlu jako root.[6][7] Nicméně v počítačová věda, tyto výrazy běžně odkazují na užší představu, konkrétně zakořeněný směrovaný graf je digraf s rozlišovacím uzlem r, takže existuje přímá cesta z r do jiného uzlu než r.[8][9][10][11] Autoři, kteří dávají obecnější definici, je mohou označit jako připojeno (nebo 1 připojeno) zakořeněné digrafy.[6]

Umění počítačového programování definuje kořenové digrafy o něco širší, jmenovitě orientovaný graf se nazývá rootovaný, pokud má aspoň jeden uzel, který může zasáhnout všechny ostatní uzly; Knuth poznamenává, že takto definovaný pojem je jakýmsi prostředníkem mezi pojmy silně propojený a připojený digraf.[12]

Aplikace

Vývojové grafy

v počítačová věda se nazývají kořenové grafy, ve kterých může kořenový vrchol dosáhnout všech ostatních vrcholů vývojové grafy nebo vývojové diagramy.[13] Někdy je přidáno další omezení určující, že vývojový graf musí mít jediný výstup (dřez ) vrchol také.[14]

Vývojové grafy lze zobrazit jako abstrakce z vývojové diagramy, s odstraněnými nestrukturálními prvky (obsah a typy uzlů).[15][16] Snad nejznámější podtřídou vývojových grafů jsou kontrolní grafy toku, použito v překladače a programová analýza. Libovolný vývojový graf lze převést na kontrolní vývojový graf provedením kontrakce hran na každé hraně, která je jedinou odchozí hranou od jejího zdroje a jedinou příchozí hranou do jejího cíle.[17] Dalším typem běžně používaného vývojového grafu je graf volání, ve kterém uzly odpovídají celému podprogramy.[18]

Byl vyvolán obecný pojem vývojového grafu programový graf,[19] ale stejný termín byl také použit k označení pouze řídicích grafů toku.[20] Také byly volány vývojové grafy neoznačené vývojové diagramy,[21] a správné vývojové diagramy.[15] Tyto grafy se někdy používají v testování softwaru.[15][18]

Pokud je potřeba mít jediný výstup, vývojové grafy mají dvě vlastnosti, které nejsou sdíleny s směrovanými grafy obecně. Tokové grafy mohou být vnořeny, což je ekvivalent volání podprogramu (i když neexistuje žádná představa o předávání parametrů) a vývojové grafy lze také sekvencovat, což je ekvivalent sekvenčního provádění dvou částí kódu.[22] Prime grafy toku jsou definovány jako vývojové grafy, které nelze rozložit pomocí vnoření nebo řazení pomocí zvoleného vzoru podgrafů, například primitiv strukturované programování.[23] Teoretický výzkum byl proveden za účelem stanovení například podílu grafů primárního toku vzhledem k vybrané sadě grafů.[24]

Teorie množin

Peter Aczel použil kořenové směrované grafy tak, že každý uzel je dosažitelný z kořene (kterému říká přístupné špičaté grafy) formulovat Aczelův anti-nadační axiom v nepodložená teorie množin. V této souvislosti každý vrchol přístupného špičatého grafu modeluje (neopodstatněnou) množinu v Aczelově non-well-foundet teorie množin a oblouk od vrcholu v k vrcholu w modeluje, že v je prvkem w . Aczelův anti-nadační axiom uvádí, že každý přístupný špičatý graf takto modeluje rodinu (nepodložených) množin.[25]

Kombinatorická teorie her

Vzhledem k čistě kombinační hra, je přidružený zakořeněný orientovaný graf, jehož vrcholy jsou pozice hry a jejichž hrany jsou pohyby, a přechod grafu od kořene se používá k vytvoření herní strom. Pokud graf obsahuje řízené cykly, pak se pozice ve hře mohla nekonečně mnohokrát opakovat, a pravidla jsou obvykle nutné, aby se zabránilo pokračování hry na neurčito. Jinak je graf a směrovaný acyklický graf, a pokud to není zakořeněný strom, pak hra má transpozice. Tento graf a jeho topologie je důležité při studiu složitost hry, Kde složitost stavového prostoru je počet vrcholů v grafu, průměrná délka hry je průměrný počet vrcholů procházejících od kořene k vrcholu bez přímí nástupci a průměr větvící faktor stromu hry je průměr překonat grafu.

Kombinatorický výčet

Počet zakořeněných neorientovaných grafů pro 1, 2, ... uzly je 1, 2, 6, 20, 90, 544, ... (sekvence A000666 v OEIS )

Související pojmy

Zvláštní případ zájmu je zakořeněné stromy, stromy s rozlišujícím kořenovým vrcholem. Pokud jsou směrované cesty z kořene v zakořeněném digrafu dodatečně omezeny na jedinečnost, pak získaný pojem je (rootovaný) stromovost —Rovnaný grafický ekvivalent kořenového stromu.[7] Kořenový graf obsahuje arborescenci se stejným kořenem právě tehdy, pokud lze celý graf získat z kořene, a počítačoví vědci studovali algoritmické problémy hledání optimálních arborescencí.[26]

Zakořeněné grafy lze kombinovat pomocí kořenový produkt grafů.[27]

Viz také

Reference

  1. ^ Zwillinger, Daniel (2011), Standardní matematické tabulky a vzorce CRC, 32. vydání, CRC Press, str. 150, ISBN  978-1-4398-3550-0
  2. ^ Harary, Franku (1955), „Počet lineárních, směrovaných, zakořeněných a spojených grafů“, Transakce Americké matematické společnosti, 78: 445–463, doi:10.1090 / S0002-9947-1955-0068198-2, PAN  0068198. Prosáknout. 454.
  3. ^ Gross, Jonathan L .; Yellen, Jay; Zhang, Ping (2013), Příručka teorie grafů (2. vyd.), CRC Press, str. 764–765, ISBN  978-1-4398-8018-0
  4. ^ Spencer, Joel (2001), Zvláštní logika náhodných grafů, Springer Science & Business Media, kapitola 4, ISBN  978-3-540-41654-8
  5. ^ Harary (1955, str. 455).
  6. ^ A b Björner, Anders; Ziegler, Günter M. (1992), „8. Introduction to greedoids“, in White, Neil (ed.), Matroid aplikace Encyklopedie matematiky a její aplikace, 40, Cambridge: Cambridge University Press, str.284–357, doi:10.1017 / CBO9780511662041.009, ISBN  0-521-38165-7, PAN  1165537, Zbl  0772.05026CS1 maint: ref = harv (odkaz). Viz zejména str. 307.
  7. ^ A b Gordon, Gary; McMahon, Elizabeth (1989), „Greedoidní polynom, který odlišuje zakořeněné arborescence“, Proceedings of the American Mathematical Society, 107 (2): 287–287, doi:10.1090 / s0002-9939-1989-0967486-0
  8. ^ Ramachandran, Vijaya (1988), „Fast Parallel Algorithms for Reducible Flow Graphs“, Souběžné výpočty: 117–138, doi:10.1007/978-1-4684-5511-3_8. Viz zejména str. 122.
  9. ^ Okamoto, Yoshio (2003), „Zakázaná malá charakterizace antimatroidů pro vyhledávání kořenových digrafů“, Diskrétní aplikovaná matematika, 131 (2): 523–533, doi:10.1016 / S0166-218X (02) 00471-7. Viz zejména str. 524.
  10. ^ Jain, Abhinandan (2010), Dynamika robotů a více těl: Analýza a algoritmySpringer Science & Business Media, s. 136, ISBN  978-1-4419-7267-5
  11. ^ Chen, Xujin (2004), „Efektivní algoritmus pro nalezení maximálních cyklů v redukovatelných grafech toku“, Přednášky z informatiky: 306–317, doi:10.1007/978-3-540-30551-4_28, hdl:10722/48600. Viz zejména str. 308.
  12. ^ Knuth, Donald (1997), Umění počítačového programování, svazek 1, 3 / E, Pearson Education, s. 372, ISBN  0-201-89683-4
  13. ^ Gross, Yellen & Zhang (2013, str. 1372).
  14. ^ Fenton, Norman Elliott; Hill, Gillian A. (1993), Konstrukce a analýza systémů: Matematický a logický rámec, McGraw-Hill, s. 319, ISBN  978-0-07-707431-9.
  15. ^ A b C Zuse, Horst (1998), Rámec softwarového měření, Walter de Gruyter, s. 32–33, ISBN  978-3-11-080730-1
  16. ^ Samaroo, Angelina; Thompson, Geoff; Williams, Peter (2010), Testování softwaru: Průvodce nadací ISTQB-ISEB, BCS, The Chartered Institute, str. 108, ISBN  978-1-906124-76-2
  17. ^ Tarr, Peri L .; Vlk, Alexander L. (2011), Inženýrství softwaru: Pokračující příspěvky Leona J. OsterweilaSpringer Science & Business Media, s. 58, ISBN  978-3-642-19823-6
  18. ^ A b Jalote, Pankaj (1997), Integrovaný přístup k softwarovému inženýrstvíSpringer Science & Business Media, s.372, ISBN  978-0-387-94899-7
  19. ^ Thulasiraman, K .; Swamy, M. N. S. (1992), Grafy: Teorie a algoritmy, John Wiley & Sons, str. 361, ISBN  978-0-471-51356-8
  20. ^ Čechich, Alejandra; Piattini, Mario; Vallecillo, Antonio (2003), Kvalita softwaru na základě komponent: Metody a technikySpringer Science & Business Media, s. 105, ISBN  978-3-540-40503-0
  21. ^ Beineke, Lowell W .; Wilson, Robin J. (1997), Spojení grafů: Vztahy mezi teorií grafů a dalšími oblastmi matematiky, Clarendon Press, str.237, ISBN  978-0-19-851497-8
  22. ^ Fenton & Hill (1993, str. 323).
  23. ^ Fenton & Hill (1993, str. 339).
  24. ^ Cooper, C. (2008), „Asymptotický výčet vývojových diagramů predikátových spojů“, Kombinatorika, pravděpodobnost a výpočet, 5 (3): 215, doi:10.1017 / S0963548300001991
  25. ^ Aczel, Peter (1988), Nepodložené sady.Přednášky CSLI, 14, Stanford, CA: Stanford University, Centrum pro studium jazyka a informací, ISBN  0-937073-22-9, PAN  0940014
  26. ^ Drescher, Matthew; Vetta, Adrian (2010), „Aproximační algoritmus pro maximální problém s výskytem listnatých stromů“, ACM Trans. Algoritmy, 6 (3): 46:1–46:18, doi:10.1145/1798596.1798599.
  27. ^ Godsil, C. D.; McKay, B. D. (1978), „Nový grafový produkt a jeho spektrum“ (PDF), Býk. Jižní. Matematika. Soc., 18 (1): 21–28, doi:10.1017 / S0004972700007760, PAN  0494910

Další čtení

  • McMahon, Elizabeth W. (1993), „O greedoidním polynomu pro zakořeněné grafy a zakořeněné digrafy“, Journal of Graph Theory, 17 (3): 433–442, doi:10,1002 / jgt.3190170316
  • Gordon, Gary (2001), „Charakteristický polynom pro zakořeněné grafy a zakořeněné digrafy“, Diskrétní matematika, 232 (1–3): 19–33, doi:10.1016 / S0012-365X (00) 00186-2

externí odkazy