เนื้อหา

1 การ preprocess
2 การตอบคำถามว่า $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)

If you report this error to the Wikimedia System Administrators, please include the details below.
Request served via cp5021 cp5021, Varnish XID 131799218 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Sun, 10 May 2026 05:38:26 GMT
Sensitive client information
IP address: 158.108.32.49

เป็นบรรพบุรุษของ $v\,$ $v\,$ หรือไม่
- 2.1 ข้อความที่ 1
- 2.2 ข้อความที่ 2

การ preprocess

ให้ทำ $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)

\mathrm {DFS} (r)\,

(เรียก

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) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 111196665 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Sun, 10 May 2026 05:38:26 GMT Sensitive client information IP address: 158.108.32.49

จาก root)

ขั้นตอนนี้ใช้เวลา $O(|V|+|E|)\,$

การตอบคำถามว่า $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) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 131799218 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Sun, 10 May 2026 05:38:26 GMT Sensitive client information IP address: 158.108.32.49$ เป็นบรรพบุรุษของ $v\,$ หรือไม่

กำหนด vertex $u\,$ และ สอง vertex ใดๆ ในต้นไม้ มาให้ เราสามารถตรวจสอบได้ว่า $u\,$ เป็นบรรพบุรุษของ $v\,$ ได้หรือไม่ดังต่อไปนี้

ตรวจสอบว่า

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) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 132813634 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Sun, 10 May 2026 05:38:27 GMT Sensitive client information IP address: 158.108.32.49

หรือไม่

การตรวจสอบนี้ใช้เวลา

ที่เหลือคือเราต้องพิสูจน์ว่าการทดสอบนี้ถูกต้อง ซึ่งเท่ากับการพิูสูจน์ขอ้ความสองข้อความต่อไปนี้

ถ้า $u\,$ เป็นบรรพบุรุษของ แล้ว
ถ้า $u\,$ ไม่ใช่บรรพบุรุษของ $v\,$ แล้ว ข้อความ "" ไม่เป็นความจริง

ข้อความที่ 1

สมมติว่า เป็นบรรพบุรุษของ แล้ว path จาก ไปยัง จะต้องผ่าน

ฉะนั้นเมื่อทำ จาก $r\,$ เราจะได้ว่า จะถูกสำรวจก่อน ฉะนั้น $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)

\mathrm {pre} [u]<\mathrm {pre} [v]\,

นอกจากนี้ เนื่องจากเราสามารถเดินจาก ไปถึง $v\,$ เราจะได้ว่า $v\,$ จะต้องถูกสำรวจเสร็จก่อนที่ $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)

\mathrm {DFS} \,

จะสำรวจ เสร็จ กล่าวคือ

ฉะนั้นเราสรุปได้ว่า $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)

\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,

ข้อความที่ 2

ข้อความที่ 2 สมมูลกับข้อความที่ว่า "ถ้า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ " แล้ว เป็นบรรพบุรุษของ $v\,$

สมมติว่า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ เราได้ว่า $u\,$ เป็นบรรพบุรุษของ $v\,$ ใน DFS tree

แต่เนื่องจากกราฟตั้งต้น เป็นต้่นไม้อยู่แล้ว จึงเป็น DFS tree ด้วย ดังนั้น จึงเป็นบรรพบุรุษของ ใน $T\,$

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

เนื้อหา

Error

การ preprocess

Error

ข้อความที่ 1

Error

Error

Error

ข้อความที่ 2

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ