Earl stjerne

En stjernegraf er en sammenhængende graf , hvor alle kanter stammer fra samme toppunkt. En stjerne med et toppunkt betegnes normalt , hvilket kaldes stjernens rækkefølge.

Andre definitioner

• S k  er den komplette todelte graf K 1, k . [1] .

• et træ med én indre knude og k blade. Derudover definerer nogle forfattere S k som et træ af orden k med en maksimal diameter på 2; så har stjernegrafen k > 2 k  - 1 blade.

En grafstjerne med tre ribben kaldes en pote eller klo [2] ( eng.  claw ).

Stjernegrafen S k har spidserne nåde, når k er lige, og ikke, hvis k er ulige.

En stjernegraf kan også beskrives som en sammenhængende graf , hvor højst ét ​​toppunkt har grad større end én.

Relation til andre typer grafer

Klografer er vigtige i definitionen af ​​klofri grafer, grafer, der ikke har undergrafer, der er kløer [3] [4] .

Stjernegrafen er en speciel slags træ . Som ethvert træ kan en stjernegraf kodes ved hjælp af Prüfer -sekvensen ; Prufer-sekvensen for stjernegrafen K 1, k består af k − 1 kopier af det centrale vertex [5] .  

Andre anvendelser

Sættet af afstande mellem hjørnerne af en klograf er et eksempel på et metrisk rum , der ikke kan indlejres isometrisk i et euklidisk rum af nogen dimension [6] .

Topologien af ​​Zvezda -computernetværket , bygget i form af en stjernegraf, spiller en vigtig rolle i distribueret computing .

Noter

1. ↑ Offentlige undervisningsmaterialer fra VSUES . Hentet 3. oktober 2016. Arkiveret fra originalen 5. oktober 2016. (ubestemt)
2. ↑ V.A. Evstigneev, V.N. Kasyanov. Ordbog over grafer i datalogi. - Novosibirsk. — (Design og optimering af programmer). - ISBN 978-591124-036-3 .
3. ↑ Faudree, Ralph ; Flandrin, Evelyne & Ryjáček, Zdeněk (1997), Claw-free graphs - A survey , Discrete Mathematics bind 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. Tryk, s. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Arkiveret 23. oktober 2012 på Wayback Machine . 
5. ↑ Gottlieb, J.; Julstrom, B.A.; Rothlauf, F. & Raidl, GR (2001), Prüfer-tal: En dårlig repræsentation af spændende træer til evolutionær søgning , Proc. Genetic and Evolutionary Computation Conference , Morgan Kaufmann, s. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Hentet 4. januar 2013. Arkiveret 26. september 2006 på Wayback Machine .  
6. ↑ Linial, Nathan (2002), Finite metric spaces–combinatorics, geometry and algorithms, Proc. International Congress of Mathematicians, Beijing , vol. 3, s. 573-586