Prüfer dizisi - Prüfer sequence

İçinde kombinatoryal matematik, Prüfer dizisi (Ayrıca Prüfer kodu veya Prüfer numaraları) bir etiketli ağaç eşsiz sıra ağaçla ilişkili. Üzerinde bir ağacın sırası n köşelerin uzunluğu var n - 2 ve basit bir yinelemeli algoritma ile oluşturulabilir. Prüfer dizileri ilk olarak Heinz Prüfer kanıtlamak Cayley formülü 1918'de.^[1]

Bir ağacı Prüfer dizisine dönüştürmek için algoritma

Yalnızca iki köşe kalana kadar ağaçtan köşeleri yinelemeli olarak kaldırarak etiketli bir ağacın Prüfer dizisi oluşturulabilir. Özellikle etiketli bir ağacı düşünün T köşeli {1, 2, ..., n}. Adımda benen küçük etiketli yaprağı çıkarın ve benPrüfer dizisinin inci öğesi bu yaprağın komşusunun etiketi olacaktır.

Etiketli bir ağacın Prüfer dizisi benzersizdir ve uzunluğu vardır n − 2.

Hem kodlama hem de kod çözme, tamsayı radix sıralamasına indirgenebilir ve paralelleştirilebilir.^[2]

Misal

Prüfer dizisi {4,4,4,5} olan etiketli ağaç.

Sağda gösterilen ağaçta çalışan yukarıdaki algoritmayı düşünün. Başlangıçta tepe 1 en küçük etikete sahip yapraktır, bu nedenle önce çıkarılır ve 4 Prüfer dizisine yerleştirilir. Daha sonra tepe 2 ve 3 kaldırılır, böylece 4 iki kez daha eklenir. Vertex 4 artık bir yaprak ve en küçük etikete sahip, bu yüzden kaldırılıyor ve diziye 5 ekliyoruz. Sadece iki köşemiz kaldı, bu yüzden duruyoruz. Ağacın sırası {4,4,4,5}.

Bir Prüfer dizisini ağaca dönüştürmek için algoritma

İzin Vermek {a [1], a [2], ..., a [n]} Prüfer dizisi olun:

Ağaç sahip olacak n + 2 numaralandırılmış düğümler 1 -e n + 2Her bir düğüm için derecesini, dizide görünme sayısı artı 1'e ayarlayın. Örneğin, sözde kodda:

 Prüfer'i Ağaca Dönüştür(a) 1 n ← uzunluk[a] 2 T ← ile bir grafik n + 1 numaralı izole edilmiş düğüm -e n + 2 3 derece ← tamsayı dizisi 4 için her düğüm ben içinde T yapmak 5     derece[ben] ← 1 6 için her değer ben içinde a yapmak 7     derece[ben] ← derece[ben] + 1

Ardından, dizideki her numara için a [i], ilk (en düşük numaralı) düğümü bulun, j1'e eşit derece ile kenarı ekleyin (j, bir [i]) ağaca doğru ve derecelerini azalt j ve a [i]. Sözde kodda:

 8 için her değer ben içinde a yapmak 9     için her düğüm j içinde T yapmak10         Eğer derece[j] = 1 sonra11 Ekle kenar[ben, j] içine T12             derece[ben] ← derece[ben] - 113             derece[j] ← derece[j] - 114             kırmak

Bu döngünün sonunda 1. dereceye sahip iki düğüm kalacaktır (onları arayın sen, v). Son olarak, kenarı ekleyin (u, v) ağaca.^[3]

15 sen ← v ← 016 için her düğüm ben içinde T17     Eğer derece[ben] = 1 sonra18         Eğer sen = 0 sonra19             sen ← ben20         Başka21             v ← ben22             kırmak23 Ekle kenar[sen, v] içine T24 derece[sen] ← derece[sen] - 125 derece[v] ← derece[v] - 126 dönüş T

Cayley formülü

Üzerinde etiketli bir ağacın Prüfer dizisi n köşeler benzersiz bir uzunluk dizisidir n - 1 ile arasındaki etiketlerde 2 n. Belirli bir sıra için S uzunluk n–2 1 ile arasındaki etiketlerde n, var benzersiz Prüfer dizisi olan etiketli ağaç S.

Hemen ortaya çıkan sonuç, Prüfer dizilerinin bir birebir örten etiketli ağaçların arasında n köşeler ve uzunluk dizileri kümesi n - 1 ila etiketlerinde 2 n. İkinci setin boyutu var nⁿ⁻²bu yüzden bu bijeksiyonun varlığı kanıtlıyor Cayley formülü yani var nⁿ⁻² etiketli ağaçlar n köşeler.

Diğer uygulamalar^[4]

• Cayley'in formülü, aşağıdaki iddiayı kanıtlamak için güçlendirilebilir:

Tam bir grafikte yayılan ağaçların sayısı ${ displaystyle K_ {n}}$ Bir dereceyle ${ displaystyle d_ {i}}$ her köşe için belirtilmiş ${ displaystyle i}$ eşittir multinom katsayısı

${ displaystyle { binom {n-2} {d_ {1} -1, , d_ {2} -1, , dots, , d_ {n} -1}} = { frac {(n -2)!} {(D_ {1} -1)! (D_ {2} -1)! Cdots (d_ {n} -1)!}}.}$

Kanıt, Prüfer sıra numarasında bunu gözlemleyerek takip eder. ${ displaystyle i}$ tam olarak görünüyor ${ displaystyle (d_ {i} -1)}$ zamanlar.

• Cayley'in formülü genelleştirilebilir: etiketli bir ağaç aslında bir yayılan ağaç etiketli tam grafik. Numaralandırılmış Prüfer dizilerine kısıtlamalar koyarak, benzer yöntemler, tam bir yayılma ağacının sayısını verebilir. iki parçalı grafik. Eğer G köşeleri 1 ila n₁ tek bölümde ve köşelerde n₁ + 1 n diğer bölümde, etiketli yayılan ağaçların sayısı G dır-dir ${ displaystyle n_ {1} ^ {n_ {2} -1} n_ {2} ^ {n_ {1} -1}}$, nerede n₂ = n − n₁.
• Düzgün dağıtılmış rastgele Prüfer dizileri oluşturmak ve bunları karşılık gelen ağaçlara dönüştürmek, tekdüze dağıtılmış rasgele etiketlenmiş ağaçlar oluşturmak için basit bir yöntemdir.

Referanslar

Dış bağlantılar

• Prüfer kodu - dan MathWorld