ผู้ใช้:Wudtichai/ทดลองเขียน
ลำดับ Prüfer ( อังกฤษ: Prüfer sequence,Prüfer code หรือ Prüfer numbers ) เป็นหนึ่งในสาขา คณิตศาสตร์เชิงการจัด, ลำดับ Prüfer ของ ต้นไม้ (ทฤษฎีกราฟ) คือลำดับการเข้าร่วมกับต้นไม้ ลำดับ Prüfer สำหรับต้นไม้ที่มี n จุดยอด จะมีขนาด n-2 ตัว เสมอ และสามารถสร้างต้นไม้ได้โดยใช้อัลกอริทึมที่จะกล่าวในส่วนต่อไป ลำดับ Prüfer ถูกใช้ครั้งแรกสำหรับการพิสูจน์ Cayley's formula โดย Heinz Prüfer ใน ค.ศ.1918
นิยาม[แก้]
ลำดับ Prüfer n ลำดับ คือลำดับของเลขจำนวนเต็ม(integers):
( a1,a2,…,an−2)
ดังนั้น ∀i : 1 ≤ i ≤ n−2 : 1 ≤ ai ≤n
ซึ่งจะเป็นลำดับที่มีขนาด n−2 ตัวและมีค่าระหว่าง 1 ถึง n
แนวคิดนี้กำหนดไว้เพื่อจุดประสงค์ในการพิสูจน์ Cayley's formula
อัลกอริทึมที่ใช้ในการแปลงต้นไม้ไปเป็นลำดับ Prüfer[แก้]
กำหนด ต้นไม้ T ซึ่งสามารถนำมาสร้าง ลำดับ Prüfer ที่สามารถใช้แทนกันได้
ต้นไม้ T มี n จุดยอด ซึ่งแต่ละจุดยอดจะมีค่า 1 ถึง n ไม่ซ้ำกันในแต่ละจุดยอด
- ถ้าต้นไม้ T มีจุดยอดทั้งหมดน้อยกว่าหรือเท่ากับ 2 ( n ≤ 2 ) จะหยุดการทำงาน ,ถ้าไม่ใช่ ทำขึ้นตอนที่ 2
- เลือกใบของต้นไม้ที่มีค่าต่ำที่สุด
- นำค่าจากใบที่ติดกับใบที่เราเลือกใส่ลงใน ลำดับ Prüfer
- ลบใบที่เราเลือกออกจากต้นไม้ แล้ววนกลับไปทำขั้นตอนที่ 1 ใหม่
- ความจำกัด(อังกฤษ: Finiteness): ทุกครั้งที่ผ่านขั้นตอนที่ 4 จุดยอดจะหายไป 1 จุดเสมอ เมื่อผ่านไป n-2 รอบ จะเหลือจุดยอดเพียง 2 จุด อัลกอริทึมก็จะหยุดทำงาน
- ข้อมูลนำเข้า(อังกฤษ: Inputs): ต้นไม้ T
- ข้อมูลนำออก(อังกฤษ: Outputs): ลำดับ Prüfer ซึ่งมีขนาด n-2 ตัว
อัลกอริทึมที่ใช้ในการแปลงลำดับ Prüferไปเป็นต้นไม้[แก้]
Pseudocode[แก้]
กำหนด ลำดับ Prüfer ขนาด n ตัว {a[1], a[2], ..., a[n]} จะแปลงได้ต้นไม้ที่มีจุดยอด n+2 จุด
Convert-Prüfer-to-Tree(a) 1 n ← length[a] 2 T ← a graph with n + 2 isolated nodes, numbered 1 to n + 2 3 degree ← an array of integers 4 for each node i in T 5 do degree[i] ← 1 6 for each value i in a 7 do degree[i] ← degree[i] + 1
ทำการสร้างเส้นเชื่อม(edge) ระหว่างจุดยอดโดยเลือกจากใบที่อยู่ล่างสุดของ tree
8 for each value i in a 9 for each node j in T 10 if degree[j] = 1 11 then Insert edge[i, j] into T 12 degree[i] ← degree[i] - 1 13 degree[j] ← degree[j] - 1 14 break
ทำการสร้างเส้นเชื่อม(edge) กับจุดยอดที่เหลืออันสุดท้ายเข้ากับต้นไม้
15 u ← v ← 0 16 for each node i in T 17 if degree[i] = 1 18 then if u = 0 19 then u ← i 20 else v ← i 21 break 22 Insert edge[u, v] into T 22 degree[u] ← degree[u] - 1 23 degree[v] ← degree[v] - 1 24 return T
Cayley's formula[แก้]
ลำดับ Prüfer ของต้นไม้ที่มี n จุดยอดนั้น จะชัดเจนแล้วว่าลำดับ Prüfer จะมีขนาด n − 2 และค่าในแต่ละลำดับจะอยู่ระหว่าง 1 ถึง n แต่สิ่งที่ชัดเจนน้อยกว่าคือ ถ้าให้ลำดับ Prüfer ขนาด n-2 ช่อง และค่าในแต่ละลำดับจะอยู่ระหว่าง 1 ถึง n จะมีต้นไม้ที่แปลงจาก ลำดับ Prüfer นั้นออกมาเป็นต้นไม้ได้ ผลที่ได้ตามมาก็คือ ลำดับ Prüfer ให้ bijection ระหว่าง กลุ่มของต้นไม้ที่มี n จุดยอด กับ กลุ่มของลำดับ Prüfer ที่มีขนาด n-2 ตัว และค่าในแต่ละลำดับจะอยู่ระหว่าง 1 ถึง n ซึ่งในกลุ่มของลำดับ Prüfer มีขนาด nn-2 ดังนั้นการมี bijection นี้แสดงถึงการพิสูจน์ Cayley's formula เช่น จะมีต้นไม้ที่มี n จุดยอด nn-2 ต้น
ตัวอย่างการประยุกต์ใช้[แก้]
- Cayley's formula สามารถนำไปพิสูจน์เรื่องต่อไปนี้: จำนวน spanning tree ใน complete graph Kn ที่มีชั้น d1,d2,...,dn จะเท่ากับ (n-2)!(d1-1)!(d2-1)!...(dn-1)! การพิสูจน์จะเห็นได้ว่าในลำดับ Prüfer ลำดับที่ i จะปรากฏตรงกับ (di − 1) ครั้ง
- Cayley's formula ทั่วไป : ต้นไม้ที่เป็น spanning tree ใน complete graph โดยจำกัดการนับ ลำดับ Prüfer ซึ่งวิธีการคล้ายกับการหาจำนวน spanning tree ของ complete bipartite graph ถ้ากราฟ G เป็น complete bipartite graph ที่มีจุดยอด 1 ถึง n1 ในส่วนแรก และ n1+1 ถึง n ในส่วนที่สอง แล้ว จำนวนของ spanning tree ของกราฟ G เท่ากับ n1n2-1n2n1-1 เมื่อ n=n1+n2
อื่นๆ[แก้]
- ตัวอย่าง ลำดับ Prüfer จาก ต้นไม้
- ตัวอย่าง ต้นไม้ จากลำดับ Prüfer
อ้างอิง[แก้]
- อัลกอริทึมที่ใช้ในการแปลงต้นไม้ ไปเป็นลำดับ Prüfer http://www.proofwiki.org/wiki/Pr%C3%BCfer_Sequence_from_Labeled_Tree#Finiteness
- ตัวอย่าง ต้นไม้ จาก ลำดับ Prüfer http://www.proofwiki.org/wiki/Labeled_Tree_from_Pr%C3%BCfer_Sequence
- bijection ระหว่าง ลำดับ Prüfer กับ ต้นไม้ http://www.proofwiki.org/wiki/Bijection_between_Pr%C3%BCfer_Sequences_and_Labeled_Trees
- นิยามของ ลำดับ Prüfer http://www.proofwiki.org/wiki/Definition:Pr%C3%BCfer_Sequence
- Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arch. Math. Phys. 27: 742–744.
- Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf. (2001). "Prüfer numbers: A poor representation of spanning trees for evolutionary search". Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001): 343–350.
External link[แก้]
- Prüfer code – from MathWorld