การประยุกต์ของกราฟ

 

 

ในชีวิตประจำวันเกี่ยวกับความคิด การตัดสินใจ หลายปัญหาสามารถใช้ทฤษฎีกราฟช่วยในการแก้ปัญหาได้ ตัวอย่างของการแก้ปัญหาด้วยกราฟเช่น ปัญหาการจัดสรรทรัพยากร (assignment problem) 

 

 

สมจิต สมใจ สมคิด สมบูรณ์ และสมชาย เป็นบุคคลที่ได้รับการจัดสรรให้ทำงาน ซึ่งมีงานทั้นสิ้นห้างานคือ 1, 2, 3, 4 และ 5

    • สมจิต ทำงานได้ทุกงาน
    • สมใจ ทำงานได้ทุกงาน ยกเว้นงานที่ 3
    • สมคิด ทำงานได้ เฉพาะงานที่ 1 และงานที่ 4
    • สมบูรณ์ ทำงานได้เฉพาะงานที่ 2, 4 และที่ 5
    • สมชาย ทำงานได้ทุกงาน

 

 

การแก้ปัญหาด้วยการแทนด้วยกราฟ เพื่อตรวจสอบดูว่ามีวิธีการจัดแบ่งงานให้กันทำได้อย่างไร

 

 

ปัญหานี้เห็นได้ชัดว่า งาน 3 มี สมจิต และสมชายทำได้ งาน 2 มีผู้ได้ 4 คน งาน 1 ก็มีผู้ทำได้ 4 คน ส่วนงาน 4 ทำได้ทุกคน งาน 5 ทำได้ 4 คน ซึ่งการจัดแบ่งงานอาศัยกราฟดูได้ 

ยังมีปัญหาอื่น ๆ ที่ทำได้ด้วยกราฟ เช่น

ปัญหาการเล่นเกม
ปัญหาการแบ่งของเหลวจากถ้วยตวง
การหาเส้นทางสั้นที่สุด
การประยุกต์ใช้กราฟควบคุมโครงการ

 

 

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

ติดตาม

Get every new post delivered to your Inbox.

%d bloggers like this: