จำนวนต้นไม้ที่มีป้ายกำกับพร้อมกราฟย่อยที่กำหนดโดยใช้รหัส prufer
คำชี้แจงปัญหา
ฉันต้องการนับจำนวนต้นไม้ด้วยชุดจุดยอด $V$ = {1, 2, 3, ... , 10} ที่มี $\\$
ต้นไม้ $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (ดูเหมือน 1 - 2 - 3) เป็นกราฟย่อย
ดังนั้นถ้าฉันคิดถูกต้องฉันต้องหาจำนวนต้นไม้ที่มีป้ายกำกับที่มีจุดยอด n และขอบคงที่ 2 อัน
ตามสูตรของ Cayley มี $n^{n-2}$ ต้นไม้ที่มีจุดยอด n
สิ่งที่ฉันใช้คือต้นไม้นั่น -> อัลกอริทึมรหัส prufer คือการค้นหาใบไม้ที่เล็กที่สุดโดยต่อท้ายลำดับด้วยพาเรนต์ของใบไม้นี้และลบใบไม้และขอบนี้ที่เชื่อมต่อกับมัน เราจะมีสองช่องที่ลำดับ prufer ของเราครอบครองโดย (2,2), (3,2), (1, 2) หนึ่งในลำดับต่อไปนี้สามารถเริ่มต้นได้$n-1$สล็อต ช่องอื่น ๆ สามารถใช้จุดใดจุดหนึ่งได้ ดังนั้นเราจึงได้รับ$3 \cdot (n-1) \cdot n^{n-4}$. แต่มันผิดอย่างสิ้นเชิง ฉันพยายามใช้ข้อพิสูจน์บางประการเกี่ยวกับปัญหาที่คล้ายกันกับขอบคงที่ แต่ฉันมีปัญหาในการทำความเข้าใจดูเหมือนว่า ...
คำตอบ
ลองนึกภาพว่าต้นไม้ $T$( 3---2---1
) ถูกทำสัญญากับจุดยอดเดียวที่มีป้ายกำกับ$0$. มี$8^6$ ต้นไม้ที่มีป้ายกำกับบนชุดจุดยอด $\{0,4,5,6,7,8,9,10\}$. สำหรับ$k=1,\ldots,7$ต้นไม้เหล่านี้มีจุดยอดกี่ต้น $0$ มีปริญญา $k$เหรอ?
จุดยอด $0$ ปรากฏขึ้น $k-1$ ครั้งในรหัสPrüferของต้นไม้ดังกล่าวและรหัสPrüferแต่ละรหัสเหล่านี้มี $6$ สล็อตดังนั้นมี $\binom6{k-1}$ วิธีการวางไฟล์ $k-1$ศูนย์ในรหัส มีแล้ว$7$ ทางเลือกสำหรับแต่ละรายการที่เหลือ $6-(k-1)=7-k$ สล็อตจึงมีทั้งหมด $\binom6{k-1}7^{7-k}$ ต้นไม้ดังกล่าว
แต่ละสิ่งเหล่านี้สอดคล้องกับต้นไม้มากกว่าหนึ่งต้นในชุดจุดยอด $V$ ที่มีต้นไม้ $T$. โดยเฉพาะถ้าจุดยอด$0$ มีปริญญา $k$ ในหนึ่งในต้นไม้เหล่านี้ขอบแต่ละด้านที่ปล่อยให้มันสามารถติดกับจุดยอดใดก็ได้จากสามจุด $1,2$และ $3$ เมื่อเราขยายจุดยอด $0$ ถึง $T$ต้นไม้จึงขยายเป็น $3^k$ ต้นไม้ที่แตกต่างกันในชุดจุดยอด $V$.
สรุป $k=1,\ldots,7$เราพบว่ามีทั้งหมด
$$\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*}$$
ต้นไม้บนจุดยอดตั้ง $V$ ที่มี $T$. (ขั้นตอนสุดท้ายใช้ทฤษฎีบททวินาม)
การวิเคราะห์นี้สรุปได้อย่างง่ายดายเกี่ยวกับสูตรสำหรับจำนวนต้นไม้ที่ติดป้ายกำกับ $n$ จุดยอดที่มีทรีย่อยเฉพาะ $T$ ด้วย $m$ จุดยอด