กรณีที่ 1

เราพิสูจน์ว่าถ้า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ แล้ว edge $(u,v)\,$ จะต้องเป็น tree edge หรือว่า forward edge

พิสูจน์: เนื่องจาก $\mathrm {pre} [u]<\mathrm {pre} [v]\,$ เรารู้ว่า DFSALL(u) เริ่มทำงานก่อน DFSALL(v) และ เนื่องจาก $\mathrm {post} [v]<\mathrm {post} [u]\,$ เรารู้ว่า DFSALL(v) ถูกเรียกก่อนที่ DFSALL(u) จะทำงานเสร็จ

ฉะนั้นจะต้องมี path ใน DFS tree จาก $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

u\,

ถึง

v\,

ดังนั้น $(u,v)\,$ จึงเป็น tree edge หรือไม่ก็ forward edge

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

กรณีที่ 1

Error

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

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ