Earl Star

Hvězdicový graf je souvislý graf , ve kterém všechny hrany pocházejí ze stejného vrcholu. Hvězda s vrcholem se obvykle označuje , což se nazývá řád hvězdy.

Další definice

• S k  je úplný bipartitní graf K 1, k . [1] .

• strom s jedním vnitřním uzlem a k listy. Někteří autoři navíc definují S k jako strom řádu k s maximálním průměrem 2; pak má hvězdný graf k > 2 k  - 1 listů.

Graf-hvězda se třemi žebry se nazývá tlapa nebo dráp [2] ( angl.  claw ).

Hvězdný graf S k má ladnost vrcholů, když k je sudé, a ne, když k je liché.

Hvězdný graf lze také popsat jako souvislý graf , ve kterém má nejvýše jeden vrchol stupeň větší než jedna.

Vztah k jiným typům grafů

Claw grafy jsou důležité při definici bezdrápových grafů, grafů, které nemají podgrafy, které jsou drápy [3] [4] .

Hvězdný graf je zvláštní druh stromu . Jako každý strom lze i hvězdný graf zakódovat pomocí Prüferovy sekvence ; Pruferova posloupnost pro hvězdný graf K 1, k sestává z k − 1 kopií centrálního vrcholu [5] .  

Další použití

Množina vzdáleností mezi vrcholy drápového grafu je příkladem metrického prostoru , který nelze izometricky vložit do euklidovského prostoru jakékoli dimenze [6] .

V distribuovaných výpočtech hraje důležitou roli topologie počítačové sítě Zvezda , budovaná ve formě hvězdicového grafu .

Poznámky

1. ↑ Veřejné vzdělávací materiály VSUES . Získáno 3. října 2016. Archivováno z originálu 5. října 2016. (neurčitý)
2. ↑ V.A. Evstigneev, V.N. Kasjanov. Slovník grafů v informatice. - Novosibirsk. — (Návrh a optimalizace programů). - ISBN 978-591124-036-3 .
3. ↑ Faudree, Ralph ; Flandrin, Evelyne & Ryjáček, Zdeněk (1997), Claw-free graphs - A survey , Discrete Mathematics vol. 164 (1–3): 87–147 , DOI 10.1016/S0012-365X(96)00045-3  .
4. ↑ Chudnovsky, Maria & Seymour, Paul (2005), The structure of claw-free graphs , Surveys in combinatorics 2005 , vol. 327, London Math. soc. Lecture Note Ser., Cambridge: Cambridge Univ. Stiskněte, str. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Archivováno 23. října 2012 ve Wayback Machine . 
5. ↑ Gottlieb, J.; Julstrom, B.A.; Rothlauf, F. & Raidl, GR (2001), Prüferova čísla: Slabá reprezentace kostrových stromů pro evoluční hledání , Proc. Genetic and Evolutionary Computation Conference , Morgan Kaufmann, s. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Získáno 4. ledna 2013. Archivováno 26. září 2006 na Wayback Machine .  
6. ↑ Linial, Nathan (2002), Konečné metrické prostory – kombinatorika, geometrie a algoritmy, Proc. Mezinárodní kongres matematiků, Peking , sv. 3, str. 573–586