Earl star

Un graf stea este un graf conex în care toate muchiile provin din același vârf. O stea cu un vârf este de obicei notată , ceea ce se numește ordinea stelei.

Alte definiții

• S k  este graficul bipartit complet K 1, k . [1] .

• un arbore cu un nod intern și k frunze. În plus, unii autori definesc S k ca un arbore de ordinul k cu un diametru maxim de 2; atunci graficul stea k > 2 are k  - 1 frunze.

O stea grafică cu trei coaste se numește labă sau gheară [2] ( ing.  gheară ).

Graficul stelar S k are grația vârfurilor, când k este par și nu, dacă k este impar.

Un graf stea poate fi descris și ca un graf conectat , în care cel mult un vârf are un grad mai mare decât unu.

Relația cu alte tipuri de grafice

Graficele cu gheare sunt importante în definirea graficelor fără gheare , grafice care nu au subgrafe care sunt gheare [3] [4] .

Graficul stelar este un tip special de arbore . Ca orice arbore , un grafic stea poate fi codificat folosind secvența Prüfer ; secvența Prufer pentru graficul stelar K 1, k constă din k − 1 copii ale vârfului central [5] .  

Alte utilizări

Setul de distanțe dintre vârfurile unui grafic cu gheare este un exemplu de spațiu metric care nu poate fi încorporat izometric într-un spațiu euclidian de orice dimensiune [6] .

Topologia rețelei de calculatoare Zvezda , construită sub forma unui grafic în stea, joacă un rol important în calculul distribuit .

Note

1. ↑ Materiale educaționale publice ale VSUES . Consultat la 3 octombrie 2016. Arhivat din original pe 5 octombrie 2016. (nedefinit)
2. ↑ V.A. Evstigneev, V.N. Kasyanov. Dicționar de grafice în informatică. - Novosibirsk. — (Proiectarea și optimizarea programelor). - 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 , voi. 327, Londra Math. soc. Lecture Note Ser., Cambridge: Cambridge Univ. Apăsați, p. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Arhivat la 23 octombrie 2012 la Wayback Machine . 
5. ↑ Gottlieb, J.; Julstrom, B.A.; Rothlauf, F. & Raidl, GR (2001), Prüfer numbers: A poor representation of spanning trees for evolutionary search , Proc. Conferința de calcul genetic și evolutiv , Morgan Kaufmann, p. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Consultat la 4 ianuarie 2013. Arhivat la 26 septembrie 2006 la Wayback Machine .  
6. ↑ Linial, Nathan (2002), Spații metrice finite–combinatorice, geometrie și algoritmi, Proc. Congresul Internațional al Matematicienilor, Beijing , vol. 3, p. 573–586