Csillaggráf

A matematika, azon belül a gráfelmélet területén egy S_k csillaggráf vagy röviden csillag (star) megegyezik a K_1,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 S_k 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.)
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 S_k 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ó kapcsolata

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 K₃ háromszöggráf és a K_1,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 K_1,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 S₃, S₄, S₅ és S₆ csillaggráfok.

További alkalmazásai

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.

Jegyzetek

A Wikimédia Commons tartalmaz Csillaggráf témájú médiaállományokat.

1. .
2. .
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. Archiválva 2006. szeptember 26-i dátummal a Wayback Machine-ben Archivált másolat. [2006. szeptember 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. december 31.).
6. .
7. .