Csillaggráf
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.

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ó 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. 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.

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.

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, 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. Az 1 fafelbontású gráfok pontosan azok, melyekben minden összefüggő komponens egy csillag.

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.

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

Fák (gráfelmélet)
Parametrikus gráfcsaládok
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 ≤eset , amikor nincs közbülső csúcs , de van k +levél ) . Más szerzők definíciója szerint az Sk csillag a k rendű fa , melynek maximális átmérője ebben az esetben a k >csillag k − 1 levéllel rendelkezik . 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( ha k > Girthparamétere ∞ ( nem tartalmaz kört ) , élkromatikus száma k , kromatikus száma( ha k > 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 nagyobbné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 . 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 . 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 . 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 , 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 . Azfafelbontású gráfok pontosan azok , melyekben minden összefüggő komponens egy csillag . 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 . 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 Fák ( gráfelmélet ) Parametrikus gráfcsaládok