ผลต่างระหว่างรุ่นของ "Bundit:2-paths routing"

รุ่นแก้ไขปัจจุบันเมื่อ 08:27, 15 กุมภาพันธ์ 2550

รับกราฟ $G=(V,E)$ ต้องการหา routing table ที่มีขนาดเล็ก??? และ วิธีการ route ที่ไม่ซับซ้อน???

ใช้ Gomory-Hu tree (cut-equivalent tree) ในการหา routing table

งานวิจัยวันที่ 15 กุมภาพันธ์ พ.ศ.2550
- สิ่งที่ผิด
  1. edge ใน gomory-hu tree มันไม่ได้โยงกลับไปหา edge ในกราฟได้ง่าย
  2. โหนดและ edge ใน tree มันไม่ได้เป็น edge ที่เชื่อมกับโหนดนั้น เช่น มี edge (u,v) มันหมายความว่า cut ของกราฟ ระหว่าง set Vu และ Vv ( Vu แทนเซตของโหนดใน subtree ที่อยู่ด้านเดียวกับ u เมื่อลบ (u,v)) มีขนาดอย่างน้อย 2 แต่ edge เหล่านี้ไม่จำเป็นต้องต่อกับ u หรือ v
  3. edge ใน cut พวกนี้ ไม่จำเป็นต้อง disjoint

@@ แถว 6: / แถว 6: @@
 * [[Media:2-paths-routing-Feb-15-2007.jpg|งานวิจัยวันที่ 15 กุมภาพันธ์ พ.ศ.2550]]
+** '''สิ่งที่ผิด'''
+**# edge ใน gomory-hu tree มันไม่ได้โยงกลับไปหา edge ในกราฟได้ง่าย
+**# โหนดและ edge ใน tree มันไม่ได้เป็น edge ที่เชื่อมกับโหนดนั้น เช่น มี edge (u,v) มันหมายความว่า cut ของกราฟ ระหว่าง set Vu และ Vv ( Vu แทนเซตของโหนดใน subtree ที่อยู่ด้านเดียวกับ u เมื่อลบ (u,v)) มีขนาดอย่างน้อย 2  แต่ edge เหล่านี้ไม่จำเป็นต้องต่อกับ u หรือ v
+**# edge ใน cut พวกนี้ ไม่จำเป็นต้อง disjoint