204512/บรรยาย 5

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: ทวีศักดิ์ อัชรางกูร รหัส : 50653807

ทบทวน

Graph

เซตของโหนด $V$
เซตของเส้นเชื่อม $E\subseteq VxV$
ตัวอย่าง

จะกล่าวว่าเส้นเชื่อม (u,v) ติดกับโหนด u และ v

u และ v เป็นจุดปลายของเส้นเชื่อม (u,v)

degree ของโหนดใดๆ คือ จำนวนเส้นเชื่อมที่ติดกับโหนดนี้

path คือ ลำดับของโหนด $V_{1},V_{2},....,V_{k}$ ที่

$(V_{i},V_{i+1})\in E$ สำหรับทุกๆ $1\leq i\leq k$ เรียก $V_{1}$ เป็นจุดเริ่มต้น ,$V_{k}$ เป็นจุดสิ้นสุด

Thm

ถ้ากราฟ $G=(V,E)$ มี m edge ให้ deg(u) แทน degree ของโหนด u

$\sum _{u\in v}deg(u)=2m$

Def

กราฟ G Connected ถ้าทุกๆ โหนด u มี path ไปยังทุกๆ โหนด v

$C\subseteq V$เป็น connected coponent ใน G ตัว ทุกๆ โหนดใน C มี path ไปถึงทุกๆ โหนดใน C และ
ไม่มี path ไปยังโหนด v อื่นๆ ที่ $V\in V-C$
Cycle คือ path ที่มีจุดเริ่มต้นเป็นจุดเดียวกับจุดสิ้นสุด ดังรูป

Def. tree คือ กราฟที่ Connected และไม่มี Cycle
Thm. ข้อความข้างล่างนี้ให้ G มี n node

1) G Connected

2) G ไม่มี Cycle

3) G มีเส้นเชื่อม n-1 เส้น

2 ข้อใดๆ จะ imply ข้อที่ 3 และ imply ว่า G เป็น tree

Proof (1,2-->3)

(I) ถ้า G Connected,G จะต้องมีอย่างน้อย n-1 edge

(II) ถ้า G มี $\geq n$ edge G มี Cycle

เพราะฉะนั้น G ไม่มี Cycle , G มี $1\leq n-1$ edge

---

Spanning tree

ให้กราฟ G = (V,E) เรียก tree ว่าเป็น spanning tree ถ้า $E'\subseteq E$

---

ปัญหา minimum spanning tree

ให้กราฟ G = (V,E) พร้อมด้วยฟังก์ชั่นน้ำหนัก w บนเส้นเชื่อม ต้องการหา spanning tree

T ที่ผลรวมของ weight บนเส้นเชื่อมน้อยที่สุด

---

Greedy framework

ทุกๆ เส้นเชื่อมจะมี

• ไม่มีสี(unknow)
• สีน้ำเงิน(accept)
• สีแดง(reject)

---

Invariant

จะมี minimum spanning tree ที่มีเส้นเชื่อมสีน้ำเงินทั้งหมดและไม่มีเส้นเชื่อมสีแดง

cut คือ partition ของเซตของโหนดออกเป็นสองส่วน$(X,{\overline {X}})$

เส้นเชื่อม e ข้าม Cut $(X,{\overline {X}})$ ถ้าจุดปลายด้านหนึ่งของ edge อยู่ใน X อีกช่วงอยู่ใน ${\overline {X}}$

---

Blue Rule และ Red Rule

blue rule พิจารณา Cut ใดๆ ที่ไม่มีเส้นเชื่อมสีน้ำเงินข้าม cut นั้น เลือกเส้นเชื่อมที่มีน้ำหนักน้อยสุด และให้ e มีสีน้ำเงิน

red rule พิจารณา Cycle ใดๆ ที่ไม่มี edge สีแดงอยู่เลือกเส้น e ที่น้ำหนักมากสุดให้ e มีสีแดง

ตัวอย่าง

Thm.

สามารถทำตาม blue rule/red rule ได้จนกระทั่งทุกๆ edge มีสีและตลอดการทำงาน invariant เป็นจริง

Proof

เมื่อเริ่มต้น (ทุกๆ edge ไม่มีสี)ทุกๆ เส้นเชื่อมไม่มีสี invariant เป็นจริง

assume ว่า invariant จริงมี minimum spanning tree ตาม invariant

blue rule ถ้า apply blue rule กับ edge e,บน cut$(X,{\overline {X}})$ ถ้า $e\in T$ assume ว่า $e\notin T$ ดังรูป

เนื่องจาก T เป็น Spanning tree มี path จาก u ไป v บน T

path นี้จะต้องข้าม $(X,{\overline {X}})$ จะมี $e'\in T$ ที่ข้าม cut $(X,{\overline {X}})$
Claim

ให้ $T'=T\cup \{e\}-\{e'\}$ T' เป็น Minimum Spanning Tree

Proof

1)T' ไม่มี Cycle T' เป็น tree และวิ่งผ่านทุกโหนดในกราฟ

2)T' Connected เป็น tree และวิ่งผ่านทุกโหนดในกราฟ

เราทราบว่า e มีน้ำหนักน้อยสุดใน cut$(X,{\overline {X}})$

น้ำหนัก $e\leq$ น้ำหนักของ e' imply ว่า น้ำหนักของ $T'\leq$น้ำหนักของ T

นั่นคือ invariant ยังจริงอยู่หลังทำ Blue rule

Red rule

ให้ทำ red rule ให้ edge $e\in (u,v)$ เป็นสีแดงบน Cycle C

ถ้า $e\notin T$ assume $e\in T'$ ดังรูป

พิจารณารูปข้างล่าง

พิจารณา $T'=T\cup \{e\}-\{e'\}$

น้ำหนักของ $T'\leq$น้ำหนักของ T

นอกจากนี้ T' เป็น spanning tree ดังนั้นหลังจากการทำ red rule,จะมี minimum spanning tree

T' ที่มี edge สีน้ำเงินทั้งหมด และไม่มี edge สีแดงเลย แสดงว่า invariant จริงอยู่

---

Blue Forest

---

Buruvka

ห้าม edge weight ซ้ำกัน

ทำงาน $O(m\log n)$

2,1,2 และ 2,3,4

เริ่มต้นเรามีกราฟ ทุกๆโหนดมองรอบตัวเองและเลือก edge ที่น้ำหนักน้อยที่สุดออกมา และทำเช่นนี้จนกว่าจะเชื่อมทุกโหนดได้ ดังรูป

ตัวอย่างการยุบ

Comment ข้อเสียของวิธีนี้คือ กรณีที่ edge เท่ากันจะทำให้เกิด Cycle เพราะว่าการเลือกแต่เฉพาะส่วนที่ใกล้ตัวเองไม่ได้คำนึงถึงตัวอื่น

---

Prim's Algorithm

เลือกตัวที่ใกล้ที่สุดออกไปเรื่อยๆ จนกระทั่งเป็น tree

---

Kruskal's Alogorithm

หลักคือ เอา edge มาเรียงกันจากน้อยไปมากหลังจากนั้นก็โยนเข้าไปเรื่อยๆให้ไม่เกิด Cycle

จะเกิดปัญหาก็ต่อเมื่อโยน edge เข้าไปแล้วทำให้เกิด Cycle ยึดหลักการ Sort edge

การทำงาน $O(m\log n)$

ตัวอย่าง

---

Union-Find

ยึดหลักการทำงานของ Kruskal ซึ่งแต่ละโหนดเป็นอิสระต่อกันซึ่งโครงสร้างพื้นฐาน คือ Set ดังรูป

ถ้าหากไม่อยู่ใน Set เดียวกันก็จับมา Union กัน

element n ตัว มี Set s {{1},{2},{3},....{n}}

• find(x) คือ identity ของ set ที่มี x อยู่
• union(x) รวม set ที่มี x กับ y เข้าด้วยกัน

ดังรูป

make set(x)

parent(x)<--x,rank(x)<---0

while(parent(x)<>x)

x<--parent(x)

return x

union(x,y)

$r_{x}$<-- find(x)

$r_{y}$<-- find(y)

parent$(r_{x})$<-- $r_{x}$

if rank$(r_{x})$ < rank $(r_{y})$

parent$(r_{x})$<--$r_{y}$

else

parent$(r_{y})$<--$r_{x}$

if rank$(r_{x})$= rank $(r_{y})$

rank$(r_{x})$<-- rank $(r_{x})$ + 1

Observation 1

ถ้า parent(x)<>x,rank(x)< rank(parent(x))

Observation 2

สำหรับ tree ที่ root มี rank k

tree มี node $\geq 2^{k}$ โหนด

Observation 3

โหนดมี rank k มีไม่เกิน ${\frac {n}{2^{k}}}$ โหนด ดังภาพ

Find ทำงานในเวลา O(m log* n)

---

Path Compress

แนวคิด log*n ดังรูป

Algorithm ของ Path Compress

if parent(x)<>x

parent(x) = find(parent(x))

return parent(x)

อธิบาย

{1},{2},{3,4},{5,6,..,16},{17,..$2^{16}$},....,{k+1,..,$2^{k}$},....,{65537,$2^{65536}$} ดังรูปประกอบด้านล่าง

จะเขียนสมการได้ว่า ${\frac {n}{2^{k+1}}}+{\frac {n}{2^{k+2}}}+.....\leq {\frac {n}{2^{k}}}$

การทำ find m รอบ

$O(m\log *n+n\log *n)$

---