Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ต้นไม้ (อังกฤษ: tree) คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest)
ส่วนประกอบของต้นไม้
- ใบ (leaf) หมายถึง จุดยอดที่มีระดับขั้นเท่ากับ หนึ่ง
- กิ่ง หมายถึง เส้นเชื่อมที่เชื่อมมาที่ใบ
- ราก (root) หมายถึง จุดยอดใดจุดยอดหนึ่งที่ถูกกำหนดขึ้นมาให้เป็นราก
- ความสูงของจุดยอด (vertice height) หมายถึง จำนวนเส้นเชื่อมบนวิถีจากจุดยอดใดๆถึงราก
- ความสูงของต้นไม้ (tree height) หมายถึง ความสูงของใบที่มากที่สุด
ต้นไม้ประเภทต่างๆ
- ต้นไม้ทอดข้าม (spanning tree) หมายถึง ของกราฟใดๆซึ่งมีลักษณะเป็นต้นไม้และมีจุดยอดทุกจุดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย
- ต้นไม้มีราก (root tree) เป็นต้นไม้ที่ถูกกำหนดให้จุดยอดหนึ่งจุดที่ถูกกำหนดให้เป็น ราก ซึ่งจะทำให้สามารถกำหนดทิศทางให้กับเส้นเชื่อมต่าง ๆ ได้อย่างเป็นธรรมชาติ โดยอาจจะให้เป็นทิศทางที่ชี้ เข้าหา ราก หรือ ออกจาก ราก
- ต้นไม้ย่อย (subtree) หมายถึงของต้นไม้
คุณสมบัติ
ถ้า G เป็น ต้นไม้แบบไม่มีทิศทางเชิงเดียว G จะสอดคล้องกับเงื่อนไขที่กันด้านล่างนี้
- G เป็นกราฟที่และไม่มี (cycles)
- G ไม่มีวัฏจักรและถ้าเพิ่มเส้นเชื่อมใด ๆ เข้าไปใน G จะทำให้เกิดวัฏจักรขึ้น
- G เป็นกราฟที่เชื่อมต่อกัน และ การลบเส้นเชื่อมใด ๆ ออกทำให้ G ไม่เชื่อมต่อกัน
- จุดยอดสองจุดใด ๆ ใน G สามารถเชื่อมต่อกันด้วยวิธีเชิงเดียว ที่มีเพียงเส้นเดียวเท่านั้น
- ถ้า G มีจุดยอดเป็นจำนวนจำกัด n จุดยอด จะมีเส้นเชื่อม n − 1 เส้น
- G ไม่มีวัฏจักรและมีเส้นเชื่อม n − 1 เส้น
ป่า
ถ้า G เป็นกราฟแบบไม่มีทิศทางเชิงเดียวจะเรียกว่า ป่า ได้ ก็ต่อเมื่อ G นั้นไม่มีวัฏจักรเชิงเดียว ดังนั้น ต้นไม้ต้นเดียวอาจเรียกว่า ป่า ได้
ดูเพิ่ม
อ่านเพิ่มเติม
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN .
- Flajolet, Philippe; (2009), , Cambridge University Press, ISBN
- Hazewinkel, Michiel, บ.ก. (2001), "Tree", , , ISBN
- (November 14, 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3rd ed.), Addison-Wesley Professional
- Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters, 51 (3): 111–116, doi:10.1016/0020-0190(94)00085-9, ISSN 0020-0190.
- Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series, 49 (3): 583–599, doi:10.2307/1969046, JSTOR 1969046.
อ้างอิง
- Bender & Williamson 2010, p. 171.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
tnim xngkvs tree khux krafthisxngcudyxdidcamiwithiedinthangthungknidephiyngwithiediyw hruxklawxiknyhnungwa epnkrafthiimmiaetepnkrafthiechuxmtxknhmd sahrbkrafthiimechuxmtxknhmderaeriykwa pa forest krafthiepntnimswnprakxbkhxngtnimib leaf hmaythung cudyxdthimiradbkhnethakb hnung king hmaythung esnechuxmthiechuxmmathiib rak root hmaythung cudyxdidcudyxdhnungthithukkahndkhunmaihepnrak khwamsungkhxngcudyxd vertice height hmaythung canwnesnechuxmbnwithicakcudyxdidthungrak khwamsungkhxngtnim tree height hmaythung khwamsungkhxngibthimakthisudtnimpraephthtangtnimthxdkham spanning tree hmaythung khxngkrafidsungmilksnaepntnimaelamicudyxdthukcudkhxngkrafepncudyxdthukcudkhxngtnimdwy tnimmirak root tree epntnimthithukkahndihcudyxdhnungcudthithukkahndihepn rak sungcathaihsamarthkahndthisthangihkbesnechuxmtang idxyangepnthrrmchati odyxaccaihepnthisthangthichi ekhaha rak hrux xxkcak rak tnimyxy subtree hmaythungkhxngtnimkhunsmbtitha G epn tnimaebbimmithisthangechingediyw G casxdkhlxngkbenguxnikhthikndanlangni G epnkrafthiaelaimmi cycles G immiwtckraelathaephimesnechuxmid ekhaipin G cathaihekidwtckrkhun G epnkrafthiechuxmtxkn aela karlbesnechuxmid xxkthaih G imechuxmtxkn cudyxdsxngcudid in G samarthechuxmtxkndwywithiechingediyw thimiephiyngesnediywethann tha G micudyxdepncanwncakd n cudyxd camiesnechuxm n 1 esn G immiwtckraelamiesnechuxm n 1 esnpatha G epnkrafaebbimmithisthangechingediywcaeriykwa pa id ktxemux G nnimmiwtckrechingediyw dngnn tnimtnediywxaceriykwa pa idduephimtnim okhrngsrangkhxmul xanephimetimDiestel Reinhard 2005 Graph Theory 3rd ed Berlin New York Springer Verlag ISBN 978 3 540 26183 4 Flajolet Philippe 2009 Cambridge University Press ISBN 978 0 521 89806 5 Hazewinkel Michiel b k 2001 Tree ISBN 978 1 55608 010 4 November 14 1997 The Art of Computer Programming Volume 1 Fundamental Algorithms 3rd ed Addison Wesley Professional Jerrum Mark 1994 Counting trees in a graph is P complete Information Processing Letters 51 3 111 116 doi 10 1016 0020 0190 94 00085 9 ISSN 0020 0190 Otter Richard 1948 The Number of Trees Annals of Mathematics Second Series 49 3 583 599 doi 10 2307 1969046 JSTOR 1969046 xangxingBender amp Williamson 2010 p 171 sfn error no target CITEREFBenderWilliamson2010