กราฟเชิงระนาบ - วิกิพีเดีย

# กราฟเชิงระนาบ

### จากวิกิพีเดีย สารานุกรมเสรี

ในทฤษฎีกราฟ กราฟเชิงระนาบ (planar graph) คือ กราฟที่สามารถวาดบนระนาบได้โดยไม่มีเส้นเชื่อมใดๆ ตัดกัน เช่น กราฟต่อไปนี้เป็นกราฟเชิงระนาบ:

(รูปที่สอง สามารถวาดให้ไม่มีเส้นเชื่อมตัดกันได้ โดยย้ายเส้นทแยงมุมเส้นหนึ่งออกไปข้างนอก)

แต่กราฟสองรูปข้างล่างนี้ ไม่เป็นกราฟเชิงระนาบ

K5
K3,3

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

## [แก้] ลักษณะเฉพาะ

คราซิเมียร์ส คูราโตวสกี (Kazimierz Kuratowski) นักคณิตศาสตร์ชาวโปแลนด์ ได้ศึกษากราฟเชิงระนาบและสามารถระบุลัีกษณะเฉพาะของกราฟเชิงระนาบ ในทฤษฎีที่รู้จักกันในชื่อ ทฤษฎีบทของคูราโตวสกี ซึ่งกล่าวว่า

  กราฟจะเป็นกราฟเชิงระนาบ ก็ต่อเมื่อ กราฟนั้นไม่ประกอบด้วยกราฟย่อยซึ่งเป็น การกระจาย ของ K5 (กราฟแบบบริบูรณ์ที่มี 5 จุดยอด) หรือ K3,3 (กราฟแบบสองเชิงแบบบริบูรณ์ ที่มีจุดยอด 6 จุดโดย จุดยอด 3 จุดจะเชื่อมโยงกับจุดยอดอีก 3 จุด)

การกระจายของกราฟ เป็นผลลัพธ์มาจากการแทรกจุดยอดลงไปในเส้นเชื่อม นั่นคือ เปลี่ยนจากเส้นเชื่อม •——• ไปเป็น •—•—• และอาจทำซ้ำอย่างนี้อีกหลายครั้ง ลักษณะเฉพาะดังกล่าวสามารถเขียนได้อีกรูปแบบหนึ่ง ซึ่งเป็นที่รู้จักกันว่า "ทฤษฎีบท P" ได้ดังนี้

  กราฟจะเป็นกราฟเชิงระนาบ ก็ต่อเมื่อ กราฟนั้นไม่มีกราฟย่อยซึ่งสมานสัณฐานกับ K5 หรือ K3,3

และ

  กราฟจะเป็นกราฟเชิงระนาบ ก็ต่อเมื่อ กราฟนั้นไม่มี K5 หรือ K3,3 เป็นไมเนอร์

รูปทั่วไปของทฤษฎีของคูราโตวสกีที่มีขอบเขตการใช้งานที่กว้างขวางมากถูกพิสูจน์โดยนีล โรเบิร์ตสันและพอล ซีมัวร์ในทฤษฎีบทโรเบิร์ตสัน-ซีมัวร์ที่เป็นเหมือนหลักไมล์อีกอันหนึ่งของทฤษฎีกราฟ ในภาษาของทฤษฎีนี้ K5 และ K3,3 คือ "ไมเนอร์ต้องห้าม" ของเซตของกราฟเชิงระนาบที่มีขนาดจำกัด

ในทางปฏิบัติ วิธีของคูราโตวสกีนั้นใช้ตรวจสอบกราฟว่าเป็นกราฟเชิงระนาบหรือไม่ได้ค่อนข้างช้า อย่างไรก็ตาม ยังมีอัลกอริทึมที่มีประสิทธิภาพมากกว่าในการแก้ปัญหานี้ สำหรับกราฟที่มี n จุดยอด เรามีอัลกอริทึมที่ใช้เวลา O(n) ในการตรวจสอบว่ากราฟเป็นกราฟเชิงระนาบหรือไม่

ในบางกรณี ทฤษฎีบทด้านล่างที่ได้มาจากสูตรของออยเลอร์นี้ก็ยังอาจใช้ได้ด้วย สำหรับกราฟเชิงระนาบเชื่อมโยงเชิงเดียว ที่มี n จุดยอด และ e เส้นเชื่อม:

  ทฤษฎีบทที่ 1. ถ้า n ≥ 3 แล้ว e ≤ 3n - 6
  ทฤษฎีบทที่ 2. ถ้า n > 3 และไม่มีวัฏจักรที่มีความยาว 3, แล้ว e ≤ 2n - 4

สังเกตว่าทฤษฎีบทนี้ใช้คำว่า ถ้า, ไม่ได้ใช้คำว่า "ก็ต่อเมื่อ" ดังนั้นจึงยังไม่ใช้การระบุลักษณะเฉพาะที่ครบถ้วน นั่นคือผลจากทฤษฎีบทนี้จึงแสดงได้แค่ว่ากราฟที่ไม่ตรงตามเงื่อนไขเหล่านี้ไม่เป็นกราฟเชิงระนาบ แต่ไม่สามารถพิสูจน์ได้ว่ากราฟนี้เป็นกราฟเชิงระนาบ ดังนั้นถ้าทั้งสองทฤษฎีบทนี้ไม่สามารถระบุอะไรได้แล้ว เราจึงต้องใช้ทฤษฎี P ในการตรวจสอบ

ยกตัวอย่างเช่น กราฟ K3,3 มีจุดยอด 6 จุด มี 9 เส้นเชื่อม และไม่มีวัฎจักรที่มีความยาว 3. ดังนั้น ด้วยทฤษฎีบทที่สอง กราฟนี้จึงไม่เป็นกราฟเชิงระนาบ

### [แก้] สูตรของออยเลอร์

สูตรของออยเลอร์ (Euler's formula) กล่าวว่า ถ้ากราฟเชิงระนาบเชื่อมโยงจำกัด (finite connected planar graph) ถูกวาดในระนาบโดยไม่มีเส้นเชื่อมตัดกัน และ v คือ จำนวนของจุดยอด, e คือจำนวนของเส้นเชื่อม และ f คือจำนวนของหน้า (face) (บริเวณที่ถูกล้อมด้วยเส้นเชื่อม ซึ่งรวมถึงบริเวณด้านนอกซึ่งมีขนาดไม่จำกัดด้วย) แล้ว

  v − e + f = 2

นั่นคือ ลักษณะเฉพาะของออยเลอร์เท่ากับ 2 ตัวอย่างเช่น จากกราฟเชิงระนาบรูปแรกในหน้านี้ เราจะได้ v=6, e=7 และ f=3 จากกราฟรูปที่สอง ถ้าวาดโดยไม่มีเส้นเชื่อมตัดกัน เราจะได้ v=4, e=6 และ f=4 สูตรของออยเลอร์สามารถพิสูจน์ได้ดังนี้: ถ้ากราฟไม่เป็นต้นไม้แล้ว เราจะลบเส้นเชื่อมที่อยู่บนวัฏจักรออกไป ซึ่งจะเป็นการลด e และ f ลงอย่างละ 1 ดังนั้น v − e + f จึงเป็นค่าคงที่ ให้ทำซ้ำจนกว่าจะได้ต้นไม้ เราจะได้ v = e + 1 และ f = 1 ดังนั้น v - e + f = 2

ในกราฟเชิงระนาบเชิงเดียวเชื่อมโยงจำกัด หน้าใดๆจะถูกล้อมด้วยเส้นเชื่อมอย่างน้อย 3 เส้น และเส้นเชื่อมทุกๆเส้นจะสัมผัสกับหน้าอย่างมาก 2 หน้า; โดยการใช้สูตรของออยเลอร์ เราสามารถแสดงให้เห็นได้ว่า กราฟเหล่านี้เป็นกราฟที่เบาบาง นั่นคือ e ≤ 3v - 6 ถ้า v ≥ 3

## [แก้] คุณสมบัติพิเศษอื่น ๆ

### [แก้] ความสัมพันธ์ระหว่างจำนวนจุดยอดและเส้นเชื่อม

  (รอการเพิ่มเติมเนื้อหา)

### [แก้] การทดสอบความสมสัณฐาน

  (รอการเพิ่มเติมเนื้อหา)

### [แก้] การระบายสี

  (รอการเพิ่มเติมเนื้อหา)

### [แก้] กราฟคู่กัน

  (รอการเพิ่มเติมเนื้อหา)

| กราฟเชิงระนาบ เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น

ข้อมูลเกี่ยวกับ กราฟเชิงระนาบ ในภาษาอื่น สามารถหาอ่านได้จากเมนู ภาษาอื่น ๆ ด้านซ้ายมือ
ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%81/%E0%B8%A3/%E0%B8%B2/%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F%E0%B9%80%E0%B8%8A%E0%B8%B4%E0%B8%87%E0%B8%A3%E0%B8%B0%E0%B8%99%E0%B8%B2%E0%B8%9A.html".

หมวดหมู่: บทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ | ทฤษฎีกราฟ

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Česky
- Deutsch
- English
- Français
- עברית
- Italiano
- 日本語
- Lietuvių
- Polski
- Português
- Tiếng Việt
- 中文