Jumlah pohon berlabel dengan subgraf yang diberikan menggunakan kode prufer.

Aug 17 2020

Pernyataan masalah

Saya ingin menghitung jumlah pohon dengan set simpul $V$ = {1, 2, 3, ..., 10} yang memiliki $\\$

pohon $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (terlihat seperti 1 - 2 - 3) sebagai subgraf.

Jadi jika saya berpikir dengan benar, saya perlu menemukan jumlah pohon berlabel dengan n simpul dan 2 tepi tetap.

Dengan rumus Cayley ada $n^{n-2}$ pohon dengan n simpul.

Yang saya ambil adalah pohon itu -> algoritma kode prufer menemukan daun terkecil, menambahkan urutan dengan induk dari daun ini dan menghapus daun dan tepi yang terhubung dengannya. Kami akan memiliki dua slot di urutan prufer kami ditempati oleh (2,2), (3,2), (1, 2). Salah satu dari urutan ini dapat dimulai$n-1$slot. Slot lain dapat digunakan oleh salah satu dari n simpul. Jadi kami mendapatkan$3 \cdot (n-1) \cdot n^{n-4}$. Tapi itu sepenuhnya salah. Saya mencoba menggunakan beberapa bukti masalah serupa dengan satu sisi tetap, tetapi saya memiliki masalah dengan pemahaman ini tampaknya ...

Jawaban

1 BrianM.Scott Aug 17 2020 at 08:17

Bayangkan pohon itu $T$( 3---2---1) dikontrak ke simpul tunggal yang diberi label$0$. Ada$8^6$ pohon berlabel pada set puncak $\{0,4,5,6,7,8,9,10\}$. Untuk$k=1,\ldots,7$, berapa banyak dari pohon ini yang melakukan vertex $0$ bergelar $k$?

Puncak $0$ muncul $k-1$ kali dalam kode Prüfer dari pohon seperti itu, dan masing-masing kode Prüfer ini memiliki $6$ slot, jadi ada $\binom6{k-1}$ cara untuk menempatkan $k-1$nol di kode. Lalu ada$7$ pilihan untuk masing-masing sisanya $6-(k-1)=7-k$ slot, jadi ada semuanya $\binom6{k-1}7^{7-k}$ pohon seperti itu.

Masing-masing berhubungan dengan lebih dari satu pohon pada himpunan puncak $V$ yang berisi pohon $T$. Secara khusus, jika simpul$0$ memiliki gelar $k$ di salah satu pohon ini, masing-masing tepi yang meninggalkannya dapat dilampirkan ke salah satu dari tiga simpul $1,2$, dan $3$ ketika kita memperluas simpul $0$ untuk $T$, sehingga pohonnya mengembang $3^k$ pohon yang berbeda di set puncak $V$.

Menjumlahkan $k=1,\ldots,7$, kami menemukan bahwa semuanya ada

$$\begin{align*} \sum_{k=1}^73^k\binom6{k-1}7^{7-k}&=\sum_{k=0}^6\binom6k3^{k+1}7^{6-k}\\ &=3\sum_{k=0}^6\binom6k3^k7^{6-k}\\ &=3(3+7)^6\\ &=3,000,000 \end{align*}$$

pohon di set puncak $V$ yang mengandung $T$. (Langkah kedua dari belakang menggunakan teorema binomial.)

Analisis ini dengan mudah digeneralisasikan ke rumus jumlah pohon berlabel pada $n$ simpul yang berisi subpohon tertentu $T$ dengan $m$ sudut.