Yıldız (grafik teorisi) - Star (graph theory)
| Star | |
|---|---|
 Yıldız S 7 . (Bazı yazarlar bunu S 8 olarak indeksler .)
| |
| tepe noktaları | k+1 |
| Kenarlar | k |
| Çap | 2 |
| çevre | ∞ |
| kromatik sayı | 2 |
| kromatik indeks | k |
| Özellikleri |
Kenar geçişli Ağaç Birim mesafe Bipartite |
| gösterim | S k |
| Grafikler ve parametreler tablosu | |
Olarak grafik teorisi , bir yıldız S k olan tam ikili grafik K 1, k : bir ağaç , bir iç düğüm ile k yaprakları (ama herhangi bir iç düğüm noktaları ve k + 1 yaprak zaman k ≤ 1). Alternatif olarak, bazı yazarlar S k'yi maksimum çapı 2 olan k dereceli ağaç olarak tanımlar ; bu durumda k > 2 olan bir yıldızın k − 1 yaprağı vardır.
3 kenarı olan bir yıldıza pençe denir .
Yıldız S k olan kenardan zarif zaman k bile olup k garip. Bu bir kenar geçişli kibrit çöpü grafiğidir ve çapı 2 ( k > 1 olduğunda ), çevresi ∞ (döngü yoktur), kromatik indeksi k ve kromatik sayısı 2'dir ( k > 0 olduğunda ). Ek olarak, yıldızın büyük bir otomorfizm grubu, yani k harfleri üzerinde simetrik grubu vardır.
Yıldız aynı zamanda en az bir köşe sahip olan tek bağlı grafik olarak tarif edilebilir derecede olandan daha büyüktür.
Diğer grafik aileleriyle ilişkisi
Pençesiz grafiklerin tanımında pençeler dikkat çekicidir, indüklenmiş bir alt grafik olarak herhangi bir pençesi olmayan grafikler . Bunlar, aynı zamanda, özel durumlarda biri Whitney grafiktir izomorfizm teoremi : Genel olarak, olan grafikler izomorf çizgi grafiğidir pençe hariç ve bir üçgen, izomorf kendileri K 3 .
Yıldız, özel bir ağaç türüdür . Herhangi bir ağaçta olduğu gibi, yıldızlar da bir Prüfer dizisi ile kodlanabilir ; K 1, k yıldızı için Prüfer dizisi , merkez tepe noktasının k − 1 kopyalarından oluşur .
Birkaç grafik değişmezi , yıldızlar cinsinden tanımlanır. Yıldız ağaçsılığı , her ormandaki her ağaç bir yıldız olacak şekilde bir grafiğin bölünebileceği minimum orman sayısıdır ve bir grafiğin yıldız kromatik sayısı , köşelerini bu şekilde renklendirmek için gereken minimum renk sayısıdır. her iki renk sınıfı birlikte tüm bağlı bileşenlerin yıldız olduğu bir alt grafiği oluşturur. Grafikleri branchwidth 1 tam olarak bağlı her bileşeni, bir yıldız olduğu grafiklerdir.
Diğer uygulamalar
Bir pençe uçları arasında mesafeler grubu sonlu bir örneğini sağlar metrik alan gömülemez izometrik bir içine Öklid alan herhangi bir boyutta.
Yıldız grafiğinden sonra modellenen bir bilgisayar ağı olan yıldız ağı , dağıtılmış hesaplamada önemlidir .
Belirli bir uzunluktaki aralıklarla kenarların tanımlanmasıyla oluşturulan yıldız grafiğinin geometrik bir gerçekleştirmesi, tropikal geometride yerel bir eğri modeli olarak kullanılır . Tropikal bir eğri, yıldız şeklindeki bir metrik grafiğe yerel olarak eşbiçimli olan bir metrik uzay olarak tanımlanır.