ต้นไม้ (อังกฤษ: 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 นั้นไม่มีวัฏจักรเชิงเดียว ดังนั้น ต้นไม้ต้นเดียวอาจเรียกว่า ป่า ได้
ดูเพิ่ม นไม, ทฤษฎ, กราฟ, สำหร, บความหมายอ, นไม, แก, ความกำกวม, นไม, งกฤษ, tree, กราฟท, สองจ, ดยอดใดๆจะม, เด, นทางถ, งก, นได, เพ, ยงว, เด, ยว, หร, อกล, าวอ, กน, ยหน, งว, เป, นกราฟท, ไม, ฏจ, กรแต, เป, นกราฟท, เช, อมต, อก, นหมด, สำหร, บกราฟท, ไม, เช, อมต, อก, นหมดเราเร, . sahrbkhwamhmayxun duthi tnim aekkhwamkakwm tnim xngkvs tree khux krafthisxngcudyxdidcamiwithiedinthangthungknidephiyngwithiediyw hruxklawxiknyhnungwa epnkrafthiimmiwtckraetepnkrafthiechuxmtxknhmd sahrbkrafthiimechuxmtxknhmderaeriykwa pa forest krafthiepntnim enuxha 1 swnprakxbkhxngtnim 2 tnimpraephthtang 3 khunsmbti 4 pa 5 duephimswnprakxbkhxngtnim aekikhib leaf hmaythung cudyxdthimiradbkhnethakb hnung king hmaythung esnechuxmthiechuxmmathiib rak root hmaythung cudyxdidcudyxdhnungthithukkahndkhunmaihepnrak khwamsungkhxngcudyxd vertice height hmaythung canwnesnechuxmbnwithicakcudyxdidthungrak khwamsungkhxngtnim tree height hmaythung khwamsungkhxngibthimakthisudtnimpraephthtang aekikhtnimthxdkham spanning tree hmaythung krafyxykhxngkrafidsungmilksnaepntnimaelamicudyxdthukcudkhxngkrafepncudyxdthukcudkhxngtnimdwy tnimmirak root tree epntnimthithukkahndihcudyxdhnungcudthithukkahndihepn rak sungcathaihsamarthkahndthisthangihkbesnechuxmtang idxyangepnthrrmchati odyxaccaihepnthisthangthichi ekhaha rak hrux xxkcak rak tnimyxy subtree hmaythungkrafyxykhxngtnimkhunsmbti aekikhtha G epn tnimaebbimmithisthangechingediyw G casxdkhlxngkbenguxnikhthismmulkndanlangni G epnkrafthiechuxmtxknaelaimmiwtckr 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 esnpa aekikh twxyangkrafthieriykwapa tha G epnkrafaebbimmithisthangechingediywcaeriykwa pa id ktxemux G nnimmiwtckrechingediyw dngnn tnimtnediywxaceriykwa pa idduephim aekikhtnim okhrngsrangkhxmul ekhathungcak https th wikipedia org w index php title tnim thvsdikraf amp oldid 4700070, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
