เรากำลังดำเนินการเพื่อคืนค่าแอป Unionpedia บน Google Play Store
ขาออกขาเข้า
🌟เราได้ทำให้การออกแบบของเราง่ายขึ้นเพื่อการนำทางที่ดีขึ้น!
Instagram Facebook X LinkedIn

การระบายสีกราฟ

ดัชนี การระบายสีกราฟ

การระบายสีบนจุดยอดของกราฟโดยจุดยอดที่มีเส้นเชื่อมถึงกันใช้สีไม่ซ้ำกัน ในกรณีกราฟนี้ต้องใช้สีเป็นอย่างน้อย 3 สี ปัญหาที่ได้รับความสนใจอย่างมากในเรื่องทฤษฎีกราฟ คือ ปัญหาการระบายสีกราฟ (Graph coloring problem) ซึ่งเป็นปัญหาที่เกี่ยวกับการพยายามระบายสีจุดของกราฟ โดยให้จุดที่อยู่ติดกันมีสีต่างกันและใช้สีให้น้อยที่สุด การระบายสีกราฟอาจมีหลายรูปแบบ บางรูปสามารถใช้สีเพียงสองสีก็เพียงพอที่จะให้จุดที่อยู่ติดกันมีสีต่างกัน บางรูปจำเป็นต้องใช้หลายสีถึงจะเพียงพอที่จะให้จุดที่อยู่ติดกันมีสีต่างกัน ดังนั้นจะเรียกจำนวนสีอย่างน้อยที่สุดที่เพียงพอที่จะให้จุดที่อยู่ติดกันมีสีต่างกันว่า จำนวนสีของกราฟ.

สารบัญ

  1. 5 ความสัมพันธ์: กราฟทฤษฎีบทสี่สีทฤษฎีบทห้าสีทฤษฎีกราฟแผนที่

  2. การให้สีกราฟ
  3. ทฤษฎีกราฟ
  4. ปัญหาการคำนวณในทฤษฎีกราฟ

กราฟ

กราฟ อาจหมายถึง.

ดู การระบายสีกราฟและกราฟ

ทฤษฎีบทสี่สี

แผนที่ที่ระบายด้วยสี 4 สี ทฤษฎีบทสี่สี (Four color theorem) กล่าวว่า แผนที่ทางภูมิศาสตร์สามารถระบายด้วยสี 4 สี ซึ่งไม่มีพื้นที่ที่อยู่ติดกันมีสีเดียวกันได้เสมอ เราเรียกพื้นที่ว่าติดกันก็ต่อเมื่อมันมีส่วนของขอบร่วมกัน ไม่ใช่แค่จุดร่วมกัน และพื้นที่แต่ละชิ้นจะต้องติดเป็นอันหนึ่งอันเดียวกัน ไม่ใช่แยกเป็นหลายๆ ส่วน อย่างมิชิแกน หรืออาเซอร์ไบจาน เป็นที่ประจักษ์ว่าสี 3 สีนั้นไม่เพียงพอ ซึ่งพิสูจน์ได้ไม่ยาก นอกจากนั้น เราสามารถพิสูจน์ได้ว่าสี 5 สีนั้นเพียงพอในการระบายแผนที่ ทฤษฎีบทสี่สี เป็นทฤษฎีบทแรกที่ถูกพิสูจน์ด้วยคอมพิวเตอร์ แต่การพิสูจน์นี้ไม่เป็นที่ยอมรับจากนักคณิตศาสตร์ส่วนใหญ่ เพราะว่ามันไม่สามารถตรวจสอบด้วยคนได้ และบางคนถึงกับกังวลในความถูกต้องของตัวแปลภาษา (คอมไพเลอร์) และฮาร์ดแวร์ที่ใช้ทำงานโปรแกรมสำหรับการพิสูจน์ การขาดความสง่างามทางคณิตศาสตร์ก็เป็นอีกสาเหตุหนึ่ง ดังคำกล่าวอันหนึ่งว่า "บทพิสูจน์ทางคณิตศาสตร์ที่ดีเป็นดั่งบทกวี — แต่นี่มันคือสมุดจดเบอร์โทรศัพท์ชัดๆ!".

ดู การระบายสีกราฟและทฤษฎีบทสี่สี

ทฤษฎีบทห้าสี

ทฤษฎีบทห้าสี (five color theorem) ในทางทฤษฎีกราฟ กล่าวว่า แผนที่สามารถระบายสีได้ด้วยสีไม่เกินห้าสี ที่จริงแล้วมันเป็นจริงโดยอัตโนมัติตามทฤษฎีบทสี่สีอยู่แล้ว แต่ทฤษฎีบทนี้มีความน่าสนใจตรงที่มันสามารถพิสูจน์ได้ง่ายกว่ามาก.

ดู การระบายสีกราฟและทฤษฎีบทห้าสี

ทฤษฎีกราฟ

กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ทฤษฎีกราฟ (graph theory) เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ.

ดู การระบายสีกราฟและทฤษฎีกราฟ

แผนที่

231x231px แผนที่ คือ รูปภาพอย่างง่ายซึ่งจำลองบริเวณบริเวณหนึ่ง และมีการแสดงความสัมพันธ์ระหว่างองค์ประกอบต่าง ๆ เช่น วัตถุ หรือบริเวณย่อย ๆ ที่อยู่ในบริเวณนั้น แผนที่มักเป็นรูปสองมิติซึ่งแสดงระยะห่างระหว่างจุดสองจุดในบริเวณใดบริเวณหนึ่งได้อย่างถูกต้องตามหลักเรขาคณิต ยกตัวอย่างเช่น แผนที่ทางภูมิศาสตร์ นอกจากนี้เรายังสามารถวาดแผนที่แสดงคุณสมบัติของบริเวณต่าง ๆ บนพื้นโลก เช่น ความหนาแน่นของประชากร ความสูงของพื้นที่ ดัชนีการพัฒนาของมนุษย์ในแต่ละประเทศ เป็นต้น.

ดู การระบายสีกราฟและแผนที่

ดูเพิ่มเติม

การให้สีกราฟ

ทฤษฎีกราฟ

ปัญหาการคำนวณในทฤษฎีกราฟ

หรือที่รู้จักกันในชื่อ ขั้นตอนวิธีการระบายสีปัญหาการระบายสีกราฟ