Főmenü megnyitása

Csillaggráf

olyan fa, melynek egyetlen közbülső csúcsa van, a többi levél

A matematika, azon belül a gráfelmélet területén egy Sk csillaggráf vagy röviden csillag (star) megegyezik a K1,k teljes páros gráffal: olyan fa, melynek egyetlen közbülső csúcsa és k levele van (kivétel a k ≤ 1 eset, amikor nincs közbülső csúcs, de van k + 1 levél). Más szerzők definíciója szerint az Sk csillag a k rendű fa, melynek maximális átmérője 2; ebben az esetben a k > 2 csillag k − 1 levéllel rendelkezik.

Csillag
Az S7 csillag. (Egyes szerzők sorszámozása szerint az S8.)
Az S7 csillag. (Egyes szerzők sorszámozása szerint az S8.)

Csúcsok száma k+1
Élek száma k
Átmérő min (2, k)
Derékbőség
Kromatikus szám min (2, k + 1)
Élkromatikus szám k
Egyéb Éltranzitív
Fa
Egységtávolság-
Gyufa-
Páros
Jelölés Sk

A három élű csillagot nevezik karomnak is.

Az Sk csillag elegánsan élcímkézhető, ha k páros, és nem az, ha k páratlan. Éltranzitív gyufagráf, átmérője 2 (ha k > 1), Girthparamétere ∞ (nem tartalmaz kört), élkromatikus száma k, kromatikus száma 2 (ha k > 0). A csillagnak egy nagy automorfizmus-csoportja van, a k betű felett értelmezett szimmetrikus csoport.

A csillagok úgy is leírhatók, mint azok az összefüggő gráfok, melyben legfeljebb egy csúcs foka nagyobb 1-nél.

Más gráfcsaládokkal való kapcsolataSzerkesztés

A karomgráf szerepel a karommentes gráfok definíciójában – ezek olyan gráfok, melyek nem tartalmazzák a karmot feszített részgráfként.[1][2] A karom az egyetlen kivétel Whitney izomorfizmustétele alól: a két összefüggő gráf élgráfjai izomorfak, az eredeti gráfok is izomorfak, kivéve a K3 háromszöggráf és a K1,3 csillaggráf esetét, melyek élgráfjai izomorfak, de ők maguk nem azok.[3]

A csillag egy speciális fa. Ahogy a többi fa, a csillag is leírható Prüfer-kódjával; a K1,k csillag Prüfer-kódja a középponti csúcs k − 1 másolatából áll.[4]

Több gráfinvariánst definiálnak csillagok segítségével. A csillagarboricitás a minimális számú erdő, amikbe a gráf felosztható oly módon, hogy az erdő fái mind csillagok legyenek,[5] egy gráf csillagkromatikus száma pedig a legkevesebb szín, ami szükséges a csúcsok színezéséhez oly módon, hogy bármely két szín együtt olyan részgráfot alkosson, amiben az összefüggő komponensek csillagok.[6] Az 1 fafelbontású gráfok pontosan azok, melyekben minden összefüggő komponens egy csillag.[7]

 
Az S3, S4, S5 és S6 csillaggráfok.

További alkalmazásaiSzerkesztés

A karom csúcsai közötti távolságok példát adnak olyan véges metrikus térre, ami nem ágyazható be izometrikusan egy tetszőleges dimenziószámú euklideszi térbe.[8]

A csillagpontos hálózat az egyik legkorábbi hálózati topológia.

A csillaggráf éleinek fix intervallumokkal helyettesítve történő mértani megvalósítását használják a tropikus geometria területén a görbék helyi modelljének megalkotására. Egy tropikus görbe olyan metrikus tér, ami lokálisan egy csillag formájú metrikus gráffal izomorf.

JegyzetekSzerkesztés

A Wikimédia Commons tartalmaz Csillaggráf témájú médiaállományokat.
  1. Faudree, Ralph; Flandrin, Evelyne & Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics 164 (1–3): 87–147, DOI 10.1016/S0012-365X(96)00045-3.
  2. 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. Press, pp. 153–171, <http://www.columbia.edu/~mc2775/claws_survey.pdf>.
  3. (Whitney 1932); (Krausz 1943); (Harary 1972), Theorem 8.3, p. 72. Harary megadja a tétel egyszerűsített bizonyítását itt: (Jung 1966).
  4. Gottlieb, J.; Julstrom, B. A. & Rothlauf, F. et al. (2001), "Prüfer numbers: A poor representation of spanning trees for evolutionary search", Proc. Genetic and Evolutionary Computation Conference, Morgan Kaufmann, pp. 343–350, <http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf>. Hozzáférés ideje: 2008-09-14 Archiválva 2006. szeptember 26-i dátummal a Wayback Machine-ben.
  5. Hakimi, S. L.; Mitchem, J. & Schmeichel, E. E. (1996), "Star arboricity of graphs", Discrete Math. 149: 93–98, DOI 10.1016/0012-365X(94)00313-8
  6. Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029.
  7. Robertson, Neil & Seymour, Paul D. (1991), "Graph minors. X. Obstructions to tree-decomposition", Journal of Combinatorial Theory 52 (2): 153–190, DOI 10.1016/0095-8956(91)90061-N.
  8. Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing, vol. 3, pp. 573–586