204512/บรรยาย 5

ทบทวน

Graph

เซตของโหนด
เซตของเส้นเชื่อม
ตัวอย่าง

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

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

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

path คือ ลำดับของโหนด ที่

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 64493977
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Tue, 13 Jan 2026 19:02:06 GMT


Sensitive client information

IP address: 158.108.32.49

$(V_{i},V_{i+1})\in E$ สำหรับทุกๆ เรียก

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 55388291
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Tue, 13 Jan 2026 19:02:03 GMT


Sensitive client information

IP address: 158.108.32.49

$V_{1}$ เป็นจุดเริ่มต้น ,$V_{k}$ เป็นจุดสิ้นสุด

Thm

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

Spanning tree

ปัญหา minimum spanning tree

Invariant

Blue Rule และ Red Rule

Blue Forest

Buruvka

Prim's Algorithm

Kruskal's Alogorithm

Path Compress