Earl Star

En stjärngraf är en sammankopplad graf där alla kanter kommer från samma vertex. En stjärna med ett vertex betecknas vanligtvis , vilket kallas stjärnans ordning.

Andra definitioner

• Sk  är den fullständiga tvådelade grafen K 1, k . [1] .

• ett träd med en inre nod och k löv. Dessutom definierar vissa författare S k som ett träd av ordning k med en maximal diameter på 2; då har stjärngrafen k > 2 k  - 1 blad.

En grafstjärna med tre revben kallas tass eller klo [2] ( eng.  klo ).

Stjärngrafen S k har spetsarnas nåd, när k är jämnt och inte, om k är udda.

En stjärngraf kan också beskrivas som en sammankopplad graf , där högst en vertex har grad större än en.

Relation till andra typer av grafer

Klografer är viktiga i definitionen av klofria grafer, grafer som inte har subgrafer som är klor [3] [4] .

Stjärngrafen är en speciell sorts träd . Som vilket träd som helst kan en stjärngraf kodas med Prüfer - sekvensen ; Prufer-sekvensen för stjärngrafen K 1, k består av k − 1 kopior av den centrala vertexen [5] .  

Andra användningsområden

Uppsättningen av avstånd mellan hörnen på en klograf är ett exempel på ett metriskt utrymme som inte kan isometriskt bäddas in i ett euklidiskt utrymme av någon dimension [6] .

Topologin för Zvezda -datornätverket , byggt i form av ett stjärndiagram, spelar en viktig roll i distribuerad datoranvändning .

Anteckningar

1. ↑ Offentligt utbildningsmaterial av VSUES . Hämtad 3 oktober 2016. Arkiverad från originalet 5 oktober 2016. (obestämd)
2. ↑ V.A. Evstigneev, V.N. Kasjanov. Ordbok över grafer i datavetenskap. - Novosibirsk. — (Design och optimering av 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. Tryck, sid. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Arkiverad 23 oktober 2012 på Wayback Machine . 
5. ↑ Gottlieb, J.; Julström, B.A.; Rothlauf, F. & Raidl, GR (2001), Prüfer numbers: A poor representation of spaning trees for evolutionary search , Proc. Genetic and Evolutionary Computation Conference , Morgan Kaufmann, sid. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Hämtad 4 januari 2013. Arkiverad 26 september 2006 på Wayback Machine .  
6. ↑ Linial, Nathan (2002), Finita metriska utrymmen – kombinatorik, geometri och algoritmer, Proc. International Congress of Mathematicians, Peking , vol. 3, sid. 573–586