Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
บทความนี้ต้องการการจัดหน้า หรือ ให้ คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้เพื่อชี้ชัดข้อบกพร่อง |
ลำดับพรือเฟอร์ (อังกฤษ: Prüfer sequence, Prüfer code หรือ Prüfer numbers) เป็นหนึ่งในสาขาคณิตศาสตร์เชิงการจัด, ลำดับพรือเฟอร์ ของต้นไม้ คือลำดับการเข้าร่วมกับต้นไม้ ลำดับพรือเฟอร์ สำหรับต้นไม้ที่มี n จุดยอด จะมีขนาด n-2 ตัว เสมอ และสามารถสร้างต้นไม้ได้โดยใช้ขั้นตอนวิธีที่จะกล่าวในส่วนต่อไป ลำดับพรือเฟอร์ ถูกใช้ครั้งแรกสำหรับการพิสูจน์ Cayley's formula โดย (Heinz Prüfer) ใน ค.ศ. 1918
นิยาม
ลำดับพรือเฟอร์ n ลำดับ คือลำดับของเลขจำนวนเต็ม (integers) :
( a1,a2,…,an−2)
ดังนั้น ∀i : 1 ≤ i ≤ n−2 : 1 ≤ ai ≤n
ซึ่งจะเป็นลำดับที่มีขนาด n−2 ตัวและมีค่าระหว่าง 1 ถึง n
แนวคิดนี้กำหนดไว้เพื่อจุดประสงค์ในการพิสูจน์ Cayley's formula
ขั้นตอนวิธีที่ใช้ในการแปลงต้นไม้ไปเป็นลำดับพรือเฟอร์
กำหนด ต้นไม้ T ซึ่งสามารถนำมาสร้าง ลำดับพรือเฟอร์ ที่สามารถใช้แทนกันได้
ต้นไม้ T มี n จุดยอด ซึ่งแต่ละจุดยอดจะมีค่า 1 ถึง n ไม่ซ้ำกันในแต่ละจุดยอด
- ถ้าต้นไม้ T มีจุดยอดทั้งหมดน้อยกว่าหรือเท่ากับ 2 ( n ≤ 2 ) จะหยุดการทำงาน ,ถ้าไม่ใช่ ทำขึ้นตอนที่ 2
- เลือกใบของต้นไม้ที่มีค่าต่ำที่สุด
- นำค่าจากใบที่ติดกับใบที่เราเลือกใส่ลงใน ลำดับพรือเฟอร์
- ลบใบที่เราเลือกออกจากต้นไม้ แล้ววนกลับไปทำขั้นตอนที่ 1 ใหม่
ขั้นตอนวิธีที่ใช้ในการแปลงลำดับพรือเฟอร์ไปเป็นต้นไม้
Pseudocode
กำหนด ลำดับพรือเฟอร์ ขนาด 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
ลำดับพรือเฟอร์ ของต้นไม้ที่มี n จุดยอดนั้น จะชัดเจนแล้วว่าลำดับพรือเฟอร์ จะมีขนาด n − 2 และค่าในแต่ละลำดับจะอยู่ระหว่าง 1 ถึง n แต่สิ่งที่ชัดเจนน้อยกว่าคือ ถ้าให้ลำดับพรือเฟอร์ ขนาด n-2 ช่อง และค่าในแต่ละลำดับจะอยู่ระหว่าง 1 ถึง n จะมีต้นไม้ที่แปลงจาก ลำดับพรือเฟอร์ นั้นออกมาเป็นต้นไม้ได้ ผลที่ได้ตามมาก็คือ ลำดับพรือเฟอร์ ให้ bijection เก็บถาวร 2011-12-06 ที่ เวย์แบ็กแมชชีน ระหว่าง กลุ่มของต้นไม้ที่มี n จุดยอด กับ กลุ่มของลำดับพรือเฟอร์ ที่มีขนาด n-2 ตัว และค่าในแต่ละลำดับจะอยู่ระหว่าง 1 ถึง n ซึ่งในกลุ่มของลำดับพรือเฟอร์ มีขนาด nn-2 ดังนั้นการมี bijection เก็บถาวร 2011-12-06 ที่ เวย์แบ็กแมชชีน นี้แสดงถึงการพิสูจน์ 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) ! การพิสูจน์จะเห็นได้ว่าในลำดับพรือเฟอร์ ลำดับที่ i จะปรากฏตรงกับ (di − 1) ครั้ง
- Cayley's formula ทั่วไป : ต้นไม้ที่เป็น spanning tree ใน complete graph โดยจำกัดการนับ ลำดับพรือเฟอร์ ซึ่งวิธีการคล้ายกับการหาจำนวน spanning tree ของ complete bipartite graph ถ้ากราฟ G เป็น complete bipartite graph ที่มีจุดยอด 1 ถึง n1 ในส่วนแรก และ n1+1 ถึง n ในส่วนที่สอง แล้ว จำนวนของ spanning tree ของกราฟ G เท่ากับ n1n2-1n2n1-1 เมื่อ n=n1+n2
อื่นๆ
- ตัวอย่าง ลำดับพรือเฟอร์ จาก ต้นไม้ เก็บถาวร 2011-12-08 ที่ เวย์แบ็กแมชชีน
- ตัวอย่าง ต้นไม้ จากลำดับพรือเฟอร์ เก็บถาวร 2011-12-08 ที่ เวย์แบ็กแมชชีน
อ้างอิง
- ขั้นที่ใช้ในการแปลงต้นไม้ไปเป็นลำดับพรือเฟอร์ http://www.proofwiki.org/wiki/Pr%C3%BCfer_Sequence_from_Labeled_Tree#Finiteness[]
- bijection ระหว่างลำดับพรือเฟอร์กับต้นไม้ http://www.proofwiki.org/wiki/Bijection_between_Pr%C3%BCfer_Sequences_and_Labeled_Trees เก็บถาวร 2011-12-06 ที่ เวย์แบ็กแมชชีน
- นิยามของลำดับพรือเฟอร์ http://www.proofwiki.org/wiki/Definition:Pr%C3%BCfer_Sequence เก็บถาวร 2014-01-23 ที่ เวย์แบ็กแมชชีน
- 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" เก็บถาวร 2011-10-01 ที่ เวย์แบ็กแมชชีน. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) : 343–350.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudbthkhwamnitxngkarkarcdhna cdhmwdhmu islingkphayin hruxekbkwadenuxha ihmikhunphaphdikhun khunsamarthprbprungaekikhbthkhwamniid aelanapayxxk phicarnaichpaykhxkhwamxunephuxchichdkhxbkphrxng ladbphruxefxr xngkvs Prufer sequence Prufer code hrux Prufer numbers epnhnunginsakhakhnitsastrechingkarcd ladbphruxefxr khxngtnim khuxladbkarekharwmkbtnim ladbphruxefxr sahrbtnimthimi n cudyxd camikhnad n 2 tw esmx aelasamarthsrangtnimidodyichkhntxnwithithicaklawinswntxip ladbphruxefxr thukichkhrngaerksahrbkarphisucn Cayley s formula ody Heinz Prufer in kh s 1918niyamladbphruxefxr n ladb khuxladbkhxngelkhcanwnetm integers a1 a2 an 2 dngnn i 1 i n 2 1 ai n sungcaepnladbthimikhnad n 2 twaelamikharahwang 1 thung n aenwkhidnikahndiwephuxcudprasngkhinkarphisucn Cayley s formulakhntxnwithithiichinkaraeplngtnimipepnladbphruxefxrkahnd tnim T sungsamarthnamasrang ladbphruxefxr thisamarthichaethnknid tnim T mi n cudyxd sungaetlacudyxdcamikha 1 thung n imsakninaetlacudyxd thatnim T micudyxdthnghmdnxykwahruxethakb 2 n 2 cahyudkarthangan thaimich thakhuntxnthi 2 eluxkibkhxngtnimthimikhatathisud nakhacakibthitidkbibthieraeluxkislngin ladbphruxefxr lbibthieraeluxkxxkcaktnim aelwwnklbipthakhntxnthi 1 ihm khwamcakd xngkvs Finiteness thukkhrngthiphankhntxnthi 4 cudyxdcahayip 1 cudesmx emuxphanip n 2 rxb caehluxcudyxdephiyng 2 cud khntxnwithikcahyudthangan khxmulnaekha xngkvs Inputs tnim T khxmulnaxxk xngkvs Outputs ladbphruxefxr sungmikhnad n 2 twkhntxnwithithiichinkaraeplngladbphruxefxripepntnimPseudocode kahnd ladbphruxefxr khnad n tw a 1 a 2 a n caaeplngidtnimthimicudyxd n 2 cud Convert Prufer 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 thakarsrangesnechuxm edge rahwangcudyxdodyeluxkcakibthixyulangsudkhxng 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 thakarsrangesnechuxm edge kbcudyxdthiehluxxnsudthayekhakbtnim 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 TCayley s formulaladbphruxefxr khxngtnimthimi n cudyxdnn cachdecnaelwwaladbphruxefxr camikhnad n 2 aelakhainaetlaladbcaxyurahwang 1 thung n aetsingthichdecnnxykwakhux thaihladbphruxefxr khnad n 2 chxng aelakhainaetlaladbcaxyurahwang 1 thung n camitnimthiaeplngcak ladbphruxefxr nnxxkmaepntnimid phlthiidtammakkhux ladbphruxefxr ih bijection ekbthawr 2011 12 06 thi ewyaebkaemchchin rahwang klumkhxngtnimthimi n cudyxd kb klumkhxngladbphruxefxr thimikhnad n 2 tw aelakhainaetlaladbcaxyurahwang 1 thung n sunginklumkhxngladbphruxefxr mikhnad nn 2 dngnnkarmi bijection ekbthawr 2011 12 06 thi ewyaebkaemchchin niaesdngthungkarphisucn Cayley s formula echn camitnimthimi n cudyxd nn 2 tntwxyangkarprayuktichCayley s formula samarthnaipphisucneruxngtxipni canwn spanning tree in complete graph Kn thimichn d1 d2 dn caethakb n 2 d1 1 d2 1 dn 1 karphisucncaehnidwainladbphruxefxr ladbthi i caprakttrngkb di 1 khrng Cayley s formula thwip tnimthiepn spanning tree in complete graph odycakdkarnb ladbphruxefxr sungwithikarkhlaykbkarhacanwn spanning tree khxng complete bipartite graph thakraf G epn complete bipartite graph thimicudyxd 1 thung n1 inswnaerk aela n1 1 thung n inswnthisxng aelw canwnkhxng spanning tree khxngkraf G ethakb n1n2 1n2n1 1 emux n n1 n2xuntwxyang ladbphruxefxr cak tnim ekbthawr 2011 12 08 thi ewyaebkaemchchin twxyang tnim cakladbphruxefxr ekbthawr 2011 12 08 thi ewyaebkaemchchinxangxingkhnthiichinkaraeplngtnimipepnladbphruxefxr http www proofwiki org wiki Pr C3 BCfer Sequence from Labeled Tree Finiteness lingkesiy bijection rahwangladbphruxefxrkbtnim http www proofwiki org wiki Bijection between Pr C3 BCfer Sequences and Labeled Trees ekbthawr 2011 12 06 thi ewyaebkaemchchin niyamkhxngladbphruxefxr http www proofwiki org wiki Definition Pr C3 BCfer Sequence ekbthawr 2014 01 23 thi ewyaebkaemchchin Prufer H 1918 Neuer Beweis eines Satzes uber Permutationen Arch Math Phys 27 742 744 Jens Gottlieb Bryant A Julstrom Gunther R Raidl and Franz Rothlauf 2001 Prufer numbers A poor representation of spanning trees for evolutionary search ekbthawr 2011 10 01 thi ewyaebkaemchchin Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2001 343 350