เครื่องตรวจสอบกราฟระนาบ

เกี่ยวกับ เครื่องตรวจสอบกราฟระนาบ

เครื่องตรวจสอบกราฟระนาบ จะตัดสินว่ากราฟเชิงเดี่ยวแบบไม่มีทิศทางนั้นเป็น กราฟระนาบ หรือไม่ — ซึ่งหมายความว่าสามารถวาดบนระนาบโดยไม่มีเส้นเชื่อมสองเส้นใดๆ ตัดกัน — และหากกราฟไม่ผ่านการทดสอบ เครื่องมือจะค้นหาและแสดงภาพ หลักฐาน Kuratowski (Kuratowski witness): ซึ่งเป็นการแบ่งย่อย (subdivision) ของ K₅ (กราฟบริบูรณ์ที่มี 5 จุดยอด) หรือ K₃,₃ (กราฟไบพาร์ไทต์บริบูรณ์แบบ 3 + 3 จุดยอด) เครื่องมือนี้สร้างขึ้นเพื่อการเรียนการสอน, การเตรียมตัวสำหรับการเขียนโปรแกรมแข่งขัน และการตรวจสอบความถูกต้องของโครงสร้างกราฟขนาดเล็กอย่างรวดเร็ว

"กราฟระนาบ" หมายถึงอะไร?

กราฟ G = (V, E) จะเป็น กราฟระนาบ หากสามารถฝังมันลงในระนาบเพื่อให้เส้นเชื่อมพบกันเฉพาะที่จุดสิ้นสุดที่ใช้ร่วมกันเท่านั้น — ไม่มีการตัดกัน หรืออาจกล่าวได้ว่า G สามารถวาดบนพื้นผิวของทรงกลมได้โดยไม่มีการตัดกัน ความเป็นระนาบเป็นคุณสมบัติทางโทโพโลยีที่แท้จริง: มันไม่ได้ขึ้นอยู่กับว่าคุณวาดกราฟอย่างไร แต่ขึ้นอยู่กับว่ามีวิธีการวาดแบบ บางอย่าง ที่ไม่ตัดกันอยู่หรือไม่

กราฟระนาบปรากฏอยู่ทุกที่ — เครือข่ายถนนและสาธารณูปโภค, การวางเส้นทางบนแผ่นวงจรพิมพ์ (PCB), กราฟเส้นเชื่อมของทรงตันเพลโต และโครงสร้างหน้าของทรงหลายหน้า อย่างไรก็ตาม กราฟ "ธรรมชาติ" จำนวนมากมักไม่เป็นระนาบ: เมื่อใดก็ตามที่คุณพยายามเชื่อมต่อบ้าน 3 หลังเข้ากับสาธารณูปโภค 3 อย่างโดยไม่ให้เส้นตัดกัน คุณจะพบกับอุปสรรคของ K₃,₃

ทฤษฎีบทของ Kuratowski — หัวใจสำคัญของเครื่องตรวจสอบ

Kazimierz Kuratowski ได้พิสูจน์ไว้ในปี 1930 ว่าความเป็นระนาบมีลักษณะเฉพาะเชิงการจัดที่ชัดเจน:

การแบ่งย่อย (subdivision) ของกราฟ H ได้มาจากการแทนที่เส้นเชื่อมบางเส้นของ H ด้วยเส้นทางที่ยาวขึ้น โดยจุดยอดภายในของเส้นทางเหล่านั้นเป็นจุดยอดดีกรี 2 ใหม่ทั้งหมด ทฤษฎีบทของ Kuratowski จึงกล่าวว่า K₅ และ K₃,₃ เป็นอุปสรรค เพียงอย่างเดียว ต่อความเป็นระนาบ — กราฟที่ไม่เป็นระนาบทุกกราฟจะมีหนึ่งในกราฟเหล่านี้ในรูปแบบที่ "ถูกยืดออก" บรรจุอยู่

กราฟต้องห้าม

สูตรของ Euler และเงื่อนไขที่จำเป็นสำหรับการตรวจสอบอย่างรวดเร็ว

ก่อนที่จะรันการค้นหาการแบ่งย่อย (ซึ่งใช้ทรัพยากรค่อนข้างสูง) เครื่องมือจะใช้เงื่อนไขที่จำเป็นสองประการที่สืบเนื่องมาจาก สูตรของ Euler: สำหรับกราฟระนาบแบบ เชื่อมโยง ใดๆ ที่วาดบนระนาบที่มีจุดยอด V, เส้นเชื่อม E และหน้า F (รวมหน้าภายนอก) เราจะได้ว่า

เมื่อรวมกับข้อสังเกตที่ว่าทุกหน้าของกราฟระนาบ เชิงเดี่ยว จะมีเส้นเชื่อมอย่างน้อย 3 เส้นเป็นขอบเขต เราจะได้ขอบเขตบนของจำนวนเส้นเชื่อมดังนี้

กราฟใดก็ตามที่ละเมิดอสมการเหล่านี้จะถือว่าไม่เป็นระนาบทันที โดยไม่ต้องค้นหาการแบ่งย่อย K₅ มี m = 10, n = 5 ⇒ 3n − 6 = 9 ดังนั้น 10 > 9 — ละเมิดขอบเขต ส่วน K₃,₃ มี m = 9, n = 6 ⇒ 2n − 4 = 8 ดังนั้น 9 > 8 — ละเมิดขอบเขตสำหรับไบพาร์ไทต์

การค้นหาการแบ่งย่อยทำงานอย่างไร

หลังจากการตรวจสอบด้วยสูตรของ Euler แล้ว เครื่องมือจะค้นหาการแบ่งย่อยโดยตรง:

1. การตรวจสอบอย่างง่าย — ตรวจหา K₅ หรือ K₃,₃ ที่เป็นกราฟย่อยโดยตรง หากจุดยอด 5 จุดเชื่อมโยงกันทุกคู่ นั่นคือ K₅ ทันที หากจุดยอด 6 จุดแยกเป็น 3 + 3 โดยมีเส้นเชื่อมข้ามทั้งหมด 9 เส้น นั่นคือ K₃,₃
2. การค้นหาการแบ่งย่อย K₅ สำหรับจุดยอดกิ่งที่เป็นไปได้ 5 จุด (แต่ละจุดมีดีกรี ≥ 4 ใน G) จะพยายามค้นหาเส้นทาง 10 เส้นทาง — หนึ่งเส้นทางต่อหนึ่งคู่ของกิ่ง — ที่ ไม่ใช้จุดยอดร่วมกันภายใน (ไม่มีจุดยอดอื่นที่ไม่ใช่กิ่งปรากฏในมากกว่าหนึ่งเส้นทาง) และหลีกเลี่ยงการใช้จุดยอดกิ่งอื่นเป็นจุดยอดภายใน หากพบจะพิสูจน์ได้ว่าไม่เป็นระนาบ
3. การค้นหาการแบ่งย่อย K₃,₃ เลือก 6 กิ่ง (แต่ละจุดมีดีกรี ≥ 3) และแบ่งเป็นสองกลุ่ม 3 + 3 แล้วค้นหาเส้นทางคู่ข้ามกลุ่ม 9 เส้นทางด้วยข้อกำหนดเดียวกับข้างต้น
4. ไม่พบหลักฐาน ⇒ เป็นกราฟระนาบ หากไม่พบการแบ่งย่อยทั้งสองภายใต้ขีดจำกัดขนาด ทฤษฎีบทของ Kuratowski รับประกันว่ากราฟนั้นเป็นกราฟระนาบ

การค้นหาเส้นทางที่ไม่ใช้จุดยอดร่วมกันเป็นปัญหาที่ยากระดับ NP-hard โดยทั่วไป ดังนั้นเครื่องมือจึงใช้ การค้นหาแบบสุ่มด้วยอัลกอริทึม Greedy ที่จำกัดขอบเขต: ในแต่ละรอบจะจัดลำดับคู่ที่ต้องการตามระดับความยาก เลือกเส้นทางสำหรับคู่ที่ยากที่สุดก่อนโดยใช้ BFS แบบสุ่ม แล้วนำจุดยอดภายในเหล่านั้นออกแล้วทำต่อไป หากการจัดลำดับนั้นล้มเหลว จะลองใหม่ด้วยลำดับที่สลับกัน — สูงสุด 40 ครั้งต่อหนึ่งชุดการกำหนดกิ่ง ในกราฟขนาดเล็กทุกรูปที่ทดสอบ (ไม่เกิน 16 จุดยอด) วิธีนี้เพียงพอที่จะค้นหาหลักฐานได้เสมอหากมีอยู่

วิธีใช้งานเครื่องคำนวณนี้

1. เลือกรูปแบบการนำเข้า โดยใช้แท็บที่ด้านบน: รายการเส้นเชื่อม (edge list) หรือรายการประชิด (adjacency list) ทั้งคู่จะสื่อถึงกราฟเดียวกัน
2. กรอกข้อมูลกราฟของคุณ กราฟจะถูกประมวลผลแบบไม่มีทิศทาง ดังนั้น A-B และ B-A คือเส้นเชื่อมเดียวกัน
3. คลิก ตรวจสอบความเป็นระนาบ เครื่องมือจะแจ้งผลลัพธ์ แสดงการให้เหตุผลทีละขั้นตอน (Euler, ไบพาร์ไทต์, Kuratowski) และแสดงภาพกราฟ
4. สำหรับกราฟที่ไม่เป็นระนาบ การแสดงผลจะใช้สีเพื่อแยกแยะการแบ่งย่อยของ K₅ หรือ K₃,₃ และแสดงรายการเส้นทางที่ไม่ใช้จุดยอดร่วมกันทั้ง 10 (หรือ 9) เส้นทาง คุณสามารถคลิกที่แถวของเส้นทางเพื่อแยกดูได้
5. สำหรับกราฟระนาบ จำนวนหน้า F = m − n + 1 + c จะถูกแจ้งพร้อมกับโครงสร้างของกราฟ

ตัวอย่างที่ 1 — K₄ เป็นกราฟระนาบ

K₄ มี n = 4, m = 6 กราฟทุกรูปที่มีจุดยอด ≤ 4 จุดจะเป็นระนาบ และความจริงแล้ว K₄ สามารถฝังเป็นรูปสามเหลี่ยมที่มีจุดยอดหนึ่งจุดอยู่ข้างในและเชื่อมต่อกับมุมทั้งสาม Euler กล่าวว่าจะมี F = 6 − 4 + 2 = 4 หน้า: ประกอบด้วยหน้าสามเหลี่ยมภายใน 3 หน้า และหน้าภายนอก 1 หน้า

ตัวอย่างที่ 2 — K₃,₃ ไม่เป็นกราฟระนาบ

K₃,₃ มี n = 6, m = 9 มันเป็นแบบไบพาร์ไทต์ ดังนั้นขอบเขตสำหรับไบพาร์ไทต์จึงมีผล: m = 9 > 2n − 4 = 8 เพียงแค่นี้ก็พิสูจน์ความเป็นกราฟที่ไม่เป็นระนาบได้แล้ว ตัวหลักฐานนั้นชัดเจนมาก — ตัวมันเองคือ K₃,₃ ที่เป็นกราฟย่อยต้องห้าม เครื่องมือจะไฮไลต์การแบ่ง 3 + 3 และเส้นเชื่อมโดยตรงทั้ง 9 เส้น

ตัวอย่างที่ 3 — กราฟ Petersen

กราฟ Petersen มี n = 10, m = 15 ดังนั้น m ≤ 3n − 6 = 24 และผ่านการตรวจสอบ Euler เบื้องต้น อย่างไรก็ตาม มันเป็นที่รู้จักกันดีว่าไม่เป็นกราฟระนาบ เครื่องมือตรวจสอบจะค้นหาการแบ่งย่อยของ K₃,₃: โดยเลือกหกจุดยอดจากห้าเหลี่ยมด้านนอกและรูปดาวห้าแฉกด้านในเพื่อให้ทุกคู่ข้ามสามารถหาเส้นทางผ่านจุดยอดสี่จุดที่เหลือได้โดยไม่ทับกัน เครื่องมือจะวาดหลักฐานนี้ ทำให้เรขาคณิตจากยุค 1930 กลายเป็นสิ่งที่จับต้องได้

การประยุกต์ใช้ความเป็นระนาบ

• การวางผัง VLSI และ PCB วงจรแบบเลเยอร์เดียวจะเป็นไปได้ก็ต่อเมื่อกราฟการเชื่อมต่อเป็นแบบระนาบ มิฉะนั้นจะต้องใช้ทางผ่าน (vias) หรือเพิ่มเลเยอร์พิเศษ
• การวาดกราฟและการแสดงภาพ กราฟระนาบช่วยให้การจัดวางแผนผังมีความชัดเจนและไม่มีเส้นตัดกัน — มีประโยชน์สำหรับแผนที่รถไฟใต้ดิน, call graphs และแผนผังวงจร
• การออกแบบอัลกอริทึม ปัญหาที่ยากระดับ NP-hard จำนวนมาก (เช่น maximum cut, vertex cover, graph isomorphism) สามารถแก้ได้ในเวลาพหุนามเมื่อจำกัดขอบเขตไว้ที่กราฟระนาบ
• การระบายสีกราฟ ทฤษฎีบทสี่สีรับประกันว่ากราฟระนาบทุกรูปสามารถระบายสีได้ด้วยสีเพียง 4 สี — ซึ่งเป็นผลลัพธ์คลาสสิกที่มีเงื่อนไขขึ้นอยู่กับความเป็นระนาบ
• การหาค่าที่เหมาะสมที่สุดเชิงการจัด การหาเส้นทางสั้นที่สุดบนระนาบ, max-flow และ min-cut ล้วนมีอัลกอริทึมเฉพาะทางที่ทำงานได้รวดเร็วขึ้น
• เคมีโมเลกุล กราฟของสารประกอบอะโรมาติกไฮโดรคาร์บอนแบบวงแหวนเบนซีนเป็นแบบระนาบ ในขณะที่โมเลกุลแบบกรงบางชนิดไม่เป็นระนาบ

คำถามที่พบบ่อย

กราฟระนาบหมายถึงอะไร?

กราฟจะเป็นกราฟระนาบหากคุณสามารถวาดมันลงบนระนาบโดยไม่มีเส้นเชื่อมสองเส้นใดๆ ตัดกัน ยกเว้นที่จุดยอดที่ใช้ร่วมกัน หรืออีกนัยหนึ่งคือกราฟจะเป็นกราฟระนาบก็ต่อเมื่อสามารถวาดบนพื้นผิวของทรงกลมได้โดยไม่มีการตัดกัน ต้นไม้, วัฏจักร, กราฟลูกบาศก์ และทรงตันเพลโตล้วนเป็นกราฟระนาบ ในขณะที่ K₅ และ K₃,₃ เป็นตัวอย่างมาตรฐานของกราฟที่ไม่เป็นระนาบ

ทฤษฎีบทของ Kuratowski คืออะไร?

ทฤษฎีบทของ Kuratowski ระบุว่ากราฟจำกัดจะเป็นกราฟระนาบก็ต่อเมื่อมันไม่มีกราฟย่อยที่เป็นการแบ่งย่อยของ K₅ หรือ K₃,₃ การแบ่งย่อยได้มาจากการแทนที่เส้นเชื่อมบางเส้นด้วยเส้นทางที่ยาวกว่าผ่านจุดยอดดีกรี 2 ใหม่ สิ่งนี้ให้หลักฐานเชิงการจัดที่เป็นรูปธรรมของความเป็นกราฟที่ไม่เป็นระนาบ

ความแตกต่างระหว่าง K₅ และ K₃,₃ คืออะไร?

K₅ มี 5 จุดยอด โดยทุกคู่จะเชื่อมต่อกันด้วยเส้นเชื่อม รวม 10 เส้น K₃,₃ มี 6 จุดยอดแบ่งออกเป็นสองกลุ่ม กลุ่มละ 3 จุด โดยทุกจุดยอดในกลุ่มหนึ่งเชื่อมต่อกับทุกจุดในอีกกลุ่มหนึ่ง รวม 9 เส้น ทั้งคู่เป็นกราฟไม่เป็นระนาบที่เล็กที่สุด และเป็นไมเนอร์ต้องห้ามสำหรับความเป็นระนาบ

อสมการของ Euler ช่วยได้อย่างไร?

สูตรของ Euler V − E + F = 2 สำหรับกราฟเชื่อมโยงระนาบ ร่วมกับความจริงที่ว่าทุกหน้าของกราฟเชิงเดี่ยวระนาบต้องมีเส้นเชื่อมอย่างน้อย 3 เส้น จะได้ m ≤ 3n − 6 กราฟเชิงเดี่ยวที่ละเมิดขอบเขตนี้จะเป็นกราฟไม่เป็นระนาบทันที สำหรับกราฟระนาบแบบไบพาร์ไทต์ ทุกหน้ามีเส้นเชื่อมอย่างน้อย 4 เส้น ทำให้ได้ขอบเขต m ≤ 2n − 4 เครื่องมือตรวจสอบจะใช้ทั้งคู่เป็นกฎสำหรับการปฏิเสธอย่างรวดเร็ว

ขีดจำกัดขนาดคือเท่าใด?

เครื่องมือตรวจสอบรองรับสูงสุด 16 จุดยอด และ 60 เส้นเชื่อม ครอบคลุมกราฟที่ใช้สอนและแข่งขันทั่วไป เช่น กราฟ Petersen, กราฟ Möbius-Kantor, ไฮเปอร์คิวบ์ขนาดเล็ก และกราฟบริบูรณ์ K₇ กราฟขนาดใหญ่กว่านี้ต้องใช้การทดสอบเฉพาะทางอย่าง Hopcroft-Tarjan

การแบ่งย่อยที่เป็นหลักฐานถูกวาดอย่างไร?

เมื่อกราฟไม่เป็นระนาบ จุดยอดกิ่ง 5 จุดของ K₅ หรือ 6 จุดของ K₃,₃ จะถูกไฮไลต์บนวงแหวนด้านใน เส้นทางที่ไม่ใช้จุดยอดร่วมกันภายในจะถูกวาดด้วยสีที่ต่างกันเพื่อให้เห็นโครงสร้างเชิงโทโพโลยีได้ชัดเจน จุดยอดและเส้นเชื่อมที่ไม่ได้เป็นส่วนหนึ่งของหลักฐานจะถูกทำเป็นสีจาง

อ่านเพิ่มเติม

• Planar graph — Wikipedia
• Kuratowski's theorem — Wikipedia
• Euler characteristic — Wikipedia
• Petersen graph — Wikipedia
• Wagner's theorem (minor version) — Wikipedia