สารบัญ
7 ความสัมพันธ์: กราฟ (คณิตศาสตร์)กราฟสองส่วนบริบูรณ์อภิธานศัพท์ทฤษฎีกราฟทฤษฎีบทสี่สีทฤษฎีบทห้าสีต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดปัญหาวิถีสั้นสุด
กราฟ (คณิตศาสตร์)
วาดของกราฟระบุชื่อที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ (Graph) ประกอบไปด้วยเซตของวัตถุที่เรียกว่าจุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้จุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) กราฟเป็นวัตถุพื้นฐานของการศึกษาในวิยุตคณิต หัวข้อทฤษฎีกราฟ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ A อย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็นความสัมพันธ์สมมาตร จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย J.J.
ดู กราฟเชิงระนาบและกราฟ (คณิตศาสตร์)
กราฟสองส่วนบริบูรณ์
ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ (complete bipartite graph) คือ กราฟสองส่วนที่จุดยอดทุกจุดในเซตแรก เชื่อมโยงกับจุดยอดทุกจุดในเซตที่สอง.
ดู กราฟเชิงระนาบและกราฟสองส่วนบริบูรณ์
อภิธานศัพท์ทฤษฎีกราฟ
ทฤษฎีกราฟเติบโตอย่างรวดเร็วในวงการวิจัยด้านคณิตศาสตร์ และมีคำศัพท์เฉพาะทางอยู่หลายคำ บทความนี้จะรวบรวมคำและความหมายของศัพท์ในทฤษฎีกราฟ.
ดู กราฟเชิงระนาบและอภิธานศัพท์ทฤษฎีกราฟ
ทฤษฎีบทสี่สี
แผนที่ที่ระบายด้วยสี 4 สี ทฤษฎีบทสี่สี (Four color theorem) กล่าวว่า แผนที่ทางภูมิศาสตร์สามารถระบายด้วยสี 4 สี ซึ่งไม่มีพื้นที่ที่อยู่ติดกันมีสีเดียวกันได้เสมอ เราเรียกพื้นที่ว่าติดกันก็ต่อเมื่อมันมีส่วนของขอบร่วมกัน ไม่ใช่แค่จุดร่วมกัน และพื้นที่แต่ละชิ้นจะต้องติดเป็นอันหนึ่งอันเดียวกัน ไม่ใช่แยกเป็นหลายๆ ส่วน อย่างมิชิแกน หรืออาเซอร์ไบจาน เป็นที่ประจักษ์ว่าสี 3 สีนั้นไม่เพียงพอ ซึ่งพิสูจน์ได้ไม่ยาก นอกจากนั้น เราสามารถพิสูจน์ได้ว่าสี 5 สีนั้นเพียงพอในการระบายแผนที่ ทฤษฎีบทสี่สี เป็นทฤษฎีบทแรกที่ถูกพิสูจน์ด้วยคอมพิวเตอร์ แต่การพิสูจน์นี้ไม่เป็นที่ยอมรับจากนักคณิตศาสตร์ส่วนใหญ่ เพราะว่ามันไม่สามารถตรวจสอบด้วยคนได้ และบางคนถึงกับกังวลในความถูกต้องของตัวแปลภาษา (คอมไพเลอร์) และฮาร์ดแวร์ที่ใช้ทำงานโปรแกรมสำหรับการพิสูจน์ การขาดความสง่างามทางคณิตศาสตร์ก็เป็นอีกสาเหตุหนึ่ง ดังคำกล่าวอันหนึ่งว่า "บทพิสูจน์ทางคณิตศาสตร์ที่ดีเป็นดั่งบทกวี — แต่นี่มันคือสมุดจดเบอร์โทรศัพท์ชัดๆ!".
ดู กราฟเชิงระนาบและทฤษฎีบทสี่สี
ทฤษฎีบทห้าสี
ทฤษฎีบทห้าสี (five color theorem) ในทางทฤษฎีกราฟ กล่าวว่า แผนที่สามารถระบายสีได้ด้วยสีไม่เกินห้าสี ที่จริงแล้วมันเป็นจริงโดยอัตโนมัติตามทฤษฎีบทสี่สีอยู่แล้ว แต่ทฤษฎีบทนี้มีความน่าสนใจตรงที่มันสามารถพิสูจน์ได้ง่ายกว่ามาก.
ดู กราฟเชิงระนาบและทฤษฎีบทห้าสี
ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด
ต้นไม้แบบทอดข้ามเล็กสุดของยูคลิด ที่มีจุด 25 จุด ในระนาบ ต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด หรือ ต้นไม้แผ่ทั่วที่น้อยที่สุดแบบยุคลิด (Euclidean minimum spanning tree) เป็นปัญหาทางทฤษฎีกราฟเกี่ยวกับการหาต้นไม้ทอดข้ามที่น้อยที่สุดบนระนาบแบบยูคลิด หรือก็คือวิธีเชื่อมโยงจุดต่าง ๆ บนระนาบสองมิติ ให้เป็นต้นไม้และมีระยะทางรวมระหว่างจุดต่าง ๆ น้อยที่สุด โดยมองจุดต่าง ๆ เป็นจุดยอดและ ระยะทางระหว่างจุดยอดเป็นเส้นเชื่อม.
ดู กราฟเชิงระนาบและต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด
ปัญหาวิถีสั้นสุด
วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1) ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น.