Star (grafteori) - Star (graph theory)
| Stjärna | |
|---|---|
 Stjärnan S 7 . (Vissa författare indexerar detta som S 8. )
| |
| Hörn | k + 1 |
| Kanter | k |
| Diameter | 2 |
| Omkrets | ∞ |
| Kromatiskt nummer | 2 |
| Kromatiskt index | k |
| Egenskaper |
Edge-transitive Tree Unit distance Bipartite |
| Notation | S k |
| Tabell över diagram och parametrar | |
I grafteori , en stjärna S k är den komplett bipartit graf K 1, k : ett träd med en intern nod och k blad (men inga interna noder och k + 1 blad när k ≤ 1). Alternativt vissa författare definierar S k att vara det träd av ordning k med maximal diameter 2; i vilket fall en stjärna på k > 2 har k - 1 blad.
En stjärna med tre kanter kallas en klo .
Stjärnan S k är kantgraciös när k är jämn och inte när k är udda. Det är en kanttransitiv tändsticksgraf och har diameter 2 (när k > 1), omkrets ∞ (den har inga cykler), kromatiskt index k och kromatiskt nummer 2 (när k > 0). Dessutom har stjärnan en stor automorfismgrupp, nämligen den symmetriska gruppen på k-bokstäver.
Stjärnor kan också beskrivas som de enda anslutna graferna där högst ett toppunkt har en grad större än en.
Förhållande till andra diagramfamiljer
Klor är anmärkningsvärda i definitionen av klofria grafer , grafer som inte har någon klo som en inducerad subgraf . De är också ett av undantagsfallen i Whitney-grafens isomorfiska teorem : i allmänhet är grafer med isomorfa linjediagram själva isomorfa, med undantag för klo och triangel K 3 .
En stjärna är en speciell typ av träd . Som med alla träd kan stjärnor kodas av en Prüfer-sekvens ; Prüfer-sekvensen för en stjärna K 1, k består av k - 1 kopior av mittpunkten.
Flera diagraminvarianter definieras i termer av stjärnor. Stjärnens arboricitet är det minsta antalet skogar som en graf kan delas in i så att varje träd i varje skog är en stjärna, och stjärnkromatiskt antal i en graf är det minsta antalet färger som behövs för att färga dess hörn på ett sådant sätt varannan färgklass tillsammans bildar en subgraf där alla anslutna komponenter är stjärnor. Graferna för grenbredd 1 är exakt de diagram där varje ansluten komponent är en stjärna.
Andra applikationer
Uppsättningen av avstånd mellan topparna på en klo ger ett exempel på ett ändligt metriskt utrymme som inte kan inbäddas isometriskt i ett euklidiskt utrymme av någon dimension.
Det stjärnnät , ett datornätverk modellerad efter stjärnan grafen, är viktig i distribuerad databehandling .
En geometrisk realisering av stjärngrafen, bildad genom att identifiera kanterna med intervall av viss fast längd, används som en lokal kurvmodell i tropisk geometri . En tropisk kurva definieras som ett metriskt utrymme som är lokalt isomorft till en stjärnformad metrisk graf.