การประยุกต์ใช้กราฟในชีวิตประจำวัน

การแก้ปัญหาแบ่งน้ำในถัง

ในการแก้ปัญหาครั้งนี้เราเริ่มจากให้ถังที่ว่างเหล่าทั้งสองใบมีจุดเริ่มที่ 0 โดยถือว่าเป็นโหนด 0,0 การเทน้ำไปมาจะทำให้น้ำในถังทั้งสองนี้มีปริมาณที่เปลี่ยนแปลงไปซึ่งเขียนเป็นกราฟได้ ดังรูป

จุดเริ่มต้นอยูที่ (0,0) จุดสุดท้ายอยู่ที่โหนด (4,0)   (3,1)   (2,2)  หรือ (1,3) ซึ่งจะมีน้ำในสองถึงรวมกัน 4 ลิตร

การดำเนินการตามกราฟทำได้ดังนี้

  1. นำน้ำจากถัง 8 ลิตร เทลงในถัง 5 ลิตรเต็มถัง
  2. นำน้ำจากถัง 5 ลิตร เทลงถัง 3 ลิตรจนเต็มถัง
  3. นำถัง 3 ลิตรเทกลับถัง 8 ลิตรจนหมด
  4. นำน้ำจากถัง 5 ลิตรส่วนที่เหลือ 2 ลิตรเทกลับตัว 3 ลิตร
  5. เทน้ำจากถัง 8 ลิตร มายังถึง 5 ลิตรจนเต็ม
  6. เทน้ำจากถัง 5 ลิตรเติมลงในถัง 3 ลิตร จนถัง 3 ลิตรเต็ม
  7. เทน้ำจากถัง 3 ลิตรกลับไปยังถึง 8 ลิตร จะแบ่งน้ำออกเป็นสองส่วน ๆ ละ 4 ลิตร

ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์