ในทฤษฎีกราฟ ต้นไม้คือ กราฟแบบไม่มีทิศทาง ซึ่งจุดยอดสองจุดใดๆ เชื่อมต่อกันด้วยเส้นทางเดียวหรือเทียบเท่ากับกราฟแบบไม่บอกทิศทางแบบวนซ้ำที่เชื่อมต่อกัน … โพลิฟอเรสต์ (หรือฟอเรสต์โดยตรงหรือฟอเรสต์เชิงทิศทาง) คือกราฟแบบวนรอบทิศทางที่มีกราฟแบบไม่มีทิศทางซึ่งแฝงอยู่คือฟอเรสต์
ต้นไม้ที่ชี้และไม่ชี้คืออะไร
กราฟแบบไม่มีทิศทางที่ไม่มีวัฏจักรคือ a forest และถ้าเชื่อมต่อจะเรียกว่าต้นไม้ กราฟกำกับคือป่า (หรือต้นไม้) หากเมื่อขอบทั้งหมดถูกแปลงเป็นขอบที่ไม่มีทิศทางจะเป็นป่าที่ไม่มีทิศทาง (หรือต้นไม้) ต้นไม้ที่หยั่งรากแล้วคือต้นไม้ที่มีจุดยอดหนึ่งจุดที่กำหนดเป็นราก
ทำไมต้นไม้ไม่มีทิศทาง
ทฤษฎีบท: กราฟที่ไม่มีทิศทางคือ tree iff มีเส้นทางง่ายๆ เพียงเส้นเดียวระหว่างจุดยอดแต่ละคู่หลักฐาน: ถ้าเรามีกราฟ T ซึ่งเป็นต้นไม้ จะต้องเชื่อมต่อโดยไม่มีวัฏจักร เนื่องจากเชื่อมต่อ T แล้ว ต้องมีเส้นทางง่ายๆ อย่างน้อยหนึ่งเส้นทางระหว่างจุดยอดแต่ละคู่
ต้นไม้กำกับหมายความว่าอย่างไร
ต้นไม้ที่มีทิศทางคือ กราฟกำกับแบบวนซ้ำ มีหนึ่งโหนดที่มี indegree 1 ในขณะที่โหนดอื่นทั้งหมดมี indegree 1 ดังแสดงในรูป: โหนดที่มี outdegree 0 คือ เรียกว่าโหนดภายนอกหรือโหนดปลายทางหรือลีฟ โหนดที่มี outdegree มากกว่าหรือเท่ากับหนึ่งเรียกว่าโหนดภายใน
คุณจะรู้ได้อย่างไรว่ากราฟที่ไม่มีทิศทางคือต้นไม้
ในกรณีของกราฟที่ไม่มีทิศทาง เราดำเนินการสามขั้นตอน:
- ดำเนินการตรวจสอบ DFS จากโหนดใดๆ เพื่อให้แน่ใจว่าแต่ละโหนดมีพาเรนต์เพียงตัวเดียว ถ้าไม่กลับ.
- ตรวจสอบว่ามีการเยี่ยมชมโหนดทั้งหมด หากการตรวจสอบ DFS ไม่สามารถเยี่ยมชมโหนดทั้งหมดได้ ให้ส่งคืน.
- มิฉะนั้น กราฟจะเป็นต้นไม้