418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.4

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

กรณีที่ 1

เราพิสูจน์ว่าถ้า แล้ว edge จะต้องเป็น tree edge หรือว่า forward edge

พิสูจน์: เนื่องจาก เรารู้ว่า DFSALL(u) เริ่มทำงานก่อน DFSALL(v) และ เนื่องจาก

Error

Too many requests (f061ab2)

เรารู้ว่า DFSALL(v) ถูกเรียกก่อนที่ DFSALL(u) จะทำงานเสร็จ

ฉะนั้นจะต้องมี path ใน DFS tree จาก ถึง

Error

Too many requests (f061ab2)

ดังนั้น จึงเป็น tree edge หรือไม่ก็ forward edge

รายการเลือกการนำทาง