Earl Star

A csillaggráf olyan összefüggő gráf , amelyben minden él ugyanabból a csúcsból származik. A csúcsponttal rendelkező csillagot általában jelölik , amit a csillag sorrendjének neveznek.

Egyéb meghatározások

• S k  a teljes kétrészes gráf K 1, k . [1] .

• egy fa egy belső csomóponttal és k levelekkel. Ezen túlmenően egyes szerzők az S k -t k -rendű faként határozzák meg , amelynek maximális átmérője 2; akkor a k > 2 csillaggráfnak k  - 1 levele van.

A három bordával rendelkező gráfcsillagot mancsnak vagy karomnak [2] ( eng.  claw ) nevezzük.

Az S k csillaggráf a csúcsok kegyelmével rendelkezik, ha k páros, és nem, ha k páratlan.

A csillaggráf összefüggő gráfként is leírható, amelyben legfeljebb egy csúcsnak van egynél nagyobb foka .

Más típusú grafikonokhoz való viszony

A karmos gráfok fontosak a karmok nélküli gráfok meghatározásában, olyan gráfok, amelyek nem tartalmaznak részgráfokat, amelyek karmok [3] [4] .

A csillaggrafikon egy speciális fafajta . Mint minden fa , a csillaggráf is kódolható a Prüfer - szekvencia segítségével ; a K 1, k csillaggráf Prufer-sorozata a központi csúcs k − 1 másolatából áll [5] .  

Egyéb felhasználások

A körmös gráf csúcsai közötti távolságok halmaza egy olyan metrikus tér példája, amely izometrikusan nem ágyazható be semmilyen dimenziójú euklideszi térbe [6] .

A Zvezda számítógépes hálózat csillaggráf formájában felépített topológiája fontos szerepet játszik az elosztott számítástechnikában .

Jegyzetek

1. ↑ A VSUES közoktatási anyagai . Letöltve: 2016. október 3. Az eredetiből archiválva : 2016. október 5.. (határozatlan)
2. ↑ V.A. Evstigneev, V.N. Kaszjanov. Számítástechnikai grafikonok szótára. - Novoszibirszk. — (Programok tervezése és optimalizálása). - 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 kombinatorics 2005 , vol. 327, London Math. szoc. Lecture Note Ser., Cambridge: Cambridge Univ. Nyomd. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Archiválva 2012. október 23-án a Wayback Machine -nél . 
5. ↑ Gottlieb, J.; Julstrom, B. A.; Rothlauf, F. & Raidl, GR (2001), Prüfer-számok: A feszülő fák rossz reprezentációja az evolúciós kutatáshoz , Proc. Genetikai és Evolúciós Számítási Konferencia , Morgan Kaufmann, p. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Letöltve: 2013. január 4. Archiválva : 2006. szeptember 26. a Wayback Machine -nél .  
6. ↑ Linial, Nathan (2002), Véges metrikus terek – kombinatorika, geometria és algoritmusok, Proc. International Congress of Mathematicians, Peking , vol. 3. o. 573–586