ข่ายงาน (Network)

ข่ายงานมีวิวัฒนาการมาตั้งแต่คริสต์ศตวรรษที่สิบแปด โดยเลออนฮาร์ด ออยเลอร์ (Leonhard Euler) นักคณิตศาสตร์ชาวสวิตเซอร์แลนด์

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

ในปี ค.ศ.1736 เลออนฮารด์ ออยเลอร์ (LeonhardEuler) ซึ่งเป็นนักคณิตศาสตร์ชาวสวิส ได้แก้ปัญหาที่มีชื่อว่า ปัญหาสะพานเคอนิกส์เบิร์ก (Konig berg Bridge Problem) เป็นปัญหาที่กล่าวถึงสะพาน 7 สะพานในเมืองเคอนิกส์เบิรก์ สะพานเหล่านี้ใช้เกาะสองเกาะและแผ่นดิน ดังรูป

ขอบคุณรูปภาพจาก http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html

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

ขอบคุณรูปภาพจาก http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html

ข่ายงาน ประกอบด้วย จุดยอด ซึ่งมีการเชื่อมระหว่างจุดด้วยเส้นเชื่อม ในข่ายงานจะไม่คำนึงถึงระยะห่างระหว่างจุดยอด และเส้นเชื่อมจะเป็นเส้นแบใดก็ได้ เราจึงอาจเขียนง่าย ๆ ได้หลายแบบ

ข่ายงานที่สามารถลากเส้นเชื่อมทุกเส้นได้โดยตลอดอย่างต่อเนื่อง และไม่ซ้ำเดิม เรียกว่า ข่ายงานที่ผ่านได้

จุดยอดของข่ายงานมี 2 ชนิด คือ จุดยอดคี่ และจุดยอดคู่
- จุดยอดของข่ายงานเป็น จุดยอดคี่ เมื่อจำนวนเส้นเชื่อมที่มาพบกัน ณ จุดยอดนั้นเป็นจำนวนคี่
- จุดยอดของข่ายงานเป็น จุดยอดคู่ เมื่อจำนวนเส้นเชื่อมที่มาพบกัน ณ จุดยอดนั้นเป็นจำนวนคู่

หมายเหตุ
ในกรณีเส้นบ่วง ให้นับรูปบ่วงแต่ละรูปเป็นสองเส้นเชื่อม