เรื่องของ Graph Theory #6 : Graph Connectivity & Euler and Hamilton Paths

สรุปความจากเอกสารบทเรียนเรื่อง Graph Theory – การเชื่อมถึงกันของ Graph .. Path คืออะไร .. เมื่อ Path มาประยุกต์ ตามแบบ Euler หรือ Hamilton เพื่อแก้ไขปัญหา

  • บทที่ 8 Graph โดย ดร. อรรจน์ โกญจนาท
  • Wikipedia เรื่อง Path(Graph)

สรุป Graph Theory : Graph Connectivity

AYK : G = (V, E) ซึ่ง E = { ea , eb , … } = { (va1 , va2) , (vb1 , vb2) , … }

Path

Path คือ Sequence ของ Edge, ที่เริ่มจาก Vertex u เชื่อมต่อกัน จนสุดที่ Vertex v, มีความยาว n เป็นผลรวมของขนาดของ Edge ตลอดเส้นทาง ซึ่งมีค่า Nonnegative

  • Pass Through” หมายถึง Path ได้ผ่าน Vertex ใดบ้าง
  • Transverse” หมายถึง Path ได้ผ่าน Edge ใดบ้าง

ใน Undirected Graph, Path จะกลายเป็น Circuit ต่อเมื่อ เริ่ม,จบลง ที่ Vertex เดียวกัน และมีความยาวมากกว่า ศูนย์ ซึ่งหากไม่มี Edge ซ้ำกันเลยใน Circuit .. จะเรียกว่า Simple Circuit

ทำนองเดียวกัน สำหรับใน Directed Graph, เรียก Circuit ที่มีทิศทางว่า Cycle

ตัวอย่าง

  • Acquaintanceship Graph : แสดงความสัมพันธ์ระหว่างบุคคล ซึ่งสร้างเป็น Path ได้
  • Collaboration Graph : เช่นการแสดงความสัมพันธ์ของ Paper ที่มี Author เขียนสองคน ซึ่งในงานชิ้นอื่นก็โยงไปหา Coauthor คนต่อไป
  • Hollywood Graph : คือ Collaboration Graph ของ Actor

Connectedness in Undirected Graph

จะเรียกว่า Undirected Graph นั้น Connected เมื่อมี Path สำหรับทุก Vertex ภายใน Graph

Conected Subgraph ถูกเรียกว่า Connected Component สามารถนำมา Union เพื่อให้เป็น Graph ที่ไม่เชื่อมต่อ

Vertex ที่ลบแล้วได้ Connected Component จะถูกเรียกว่า Cut Vertex หรือ Articulation Point

Edge ที่ลบแล้ว ได้ Connected Component ถูกเรียกว่า Cut Edge หรือ Bridge

ตัวอย่างเช่น Cut Vertex -> b , c , e ส่วน Cut Edge -> ( c , e ) , ( a , b )

Connectedness in Directed Graph

เมื่อต้องพิจารณา Direction ด้วยด้วย .. จะเรียกว่า Strongly Connected หากมี Path จากทั้งไปและกลับระหว่างสองจุดใดใด ใน Graph

ถ้าหากแปลง Directed Graph ให้เป็น Undirected Graph แล้ว มี Path สำหรับทุกคู่ Vertex ภายใน Graph จะเรียก Directed Graph นั้นว่า Weakly Connected

ตัวอย่าง G เป็น Strongly Connected และ H เป็น Weakly Connected

สรุป Graph Theory : Euler and Hamilton Paths

กล่าวถึงปัญหาที่เกี่ยวข้องกับการเดินตาม Edge ภายใน Graph โดยผ่าน Edge ที่ไม่ซ้ำกัน และกลับมาที่เดิม

Euler Path and Circuits

ในศตวรรษที่ 18 นักคณิตศาสตร์ชื่อ Leonhard Euler ได้แสดงการแก้ปัญหา Seven Bridges of Königsberg ด้วยการ Model ให้สะพานและสถานที่อยู่ในรูปของ Graph

จากคำถามที่ว่า “เป็นไปได้ไหม ที่จะเดินข้ามแต่ละสะพาน เพียงครั้งเดียว จนครบทุกสะพาน แล้วย้อนกลับมาที่สุดเดิม” จะสามารถเปลี่ยนเป็นคำถามทางคณิตศาสตร์ได้คือ “เราจะหา Simple Circuit ของ Multigraph ที่ประกอบด้วยทุก Edge ได้อย่างไร” และนิยามให้ผลลัพธ์ คือ Euler Circuit … ส่วนถ้ามี Path ที่ประกอบด้วยทุก Edge ใน Graph, Path ดังกล่าว จะถูกเรียกว่า Euler Path

Graph จะมี Euler Circuit หรือไม่ สามารถสังเกตจาก

Hamilton Path and Circuits

คล้ายกับ Euler Path และ Euler Circuit เพียงแต่ .. Hamiltonian Path ก็คือ Path ที่กำหนดว่า การเดินทาง (Transverse) จะต้องผ่านแต่ละ Vertex เพียงครั้งเดียว ให้ครบทุก Vertex ใน Graph .. ซึ่งถ้าหากครบทุก Vertex แล้วกลับมาเริ่มที่จุดเริ่มต้น จะเรียกว่
Hamilton Circuit (Hamiltonian Circuit)

ปัจจุบันยังไม่มีข้อกำหนด ทฤษฎี เพื่อบอกได้ว่า Graph มี Hamiltonian Path/Circuit หรือไม่ เพียงแต่มีข้อสังเกตว่า ยิ่ง Graph มี Edge มากขึ้น โอกาสมี Hamiltonian Path/Circuit ก็สามารถมีได้สูงขึ้น (สามารถดูเพิ่มเติม Dirac’s Theorem และ Ore’s Theorem)

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s