ช่วยหน่อยคับ ทฤษฎีกราฟ

[Di[s]-Stepz]

$ที่จอดรถแห่งหนึ่งมีรถที่จอดประจำ 6 คัน ในช่วงเวลาต่างๆ ดังนี้$
$คันที่ 1 จอดเฉพาะช่วงเวลา 7 นาฬิกา ถึง 15 นาฬิกา$
$คันที่ 2 จอดเฉพาะช่วงเวลา 12 นาฬิกา ถึง 21 นาฬิกา$
$คันที่ 3 จอดเฉพาะช่วงเวลา 9 นาฬิกา ถึง 13 นาฬิกา$
$คันที่ 4 จอดเฉพาะช่วงเวลา 16 นาฬิกา ถึง 24 นาฬิกา$
$คันที่ 5 จอดเฉพาะช่วงเวลา 8 นาฬิกา ถึง 18 นาฬิกา$
$คันที่ 6 จอดเฉพาะช่วงเวลา 22 นาฬิกา ถึง 8 นาฬิกา$

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

ป.ล. ความรู้เรื่องทฤษฏีกราฟสามารถหาความรู้เพิ่มได้ที่ไหนหรอคับ

[RM@]

มีรถ 6 คัน ก็คือมีจุดยอด 6 จุด ก็สมมติมันขึ้นมาครับ เช่น A, B, ... แล้วก็ทำตามคำสั่งข้อ 1. คือลากเสนเชื่อมระหว่างจุดยอดที่มีเวลาซ้อนทับกัน พอทำเสร็จ ก็ดูว่าแต่ละจุดยอดมีดีกรีเท่าไร ดีกรีสูงสุดคือคำตอบ

อ่านในหนังสือแบบเรียนก็เพียงพอสำหรับการแก้ปัญหาครับ.

[Di[s]-Stepz]

ขอบคุณ คุณRM@ มากครับ แต่ผมยังดูดีกรีไม่เป็นเลยครับ
ตอนนี้ยังผมไม่มีหนังสือเลยครับ

[RM@]

หนังสือแบบเรียนหาซื้อได้ตามร้านหนังสือที่ขายโดยเฉพาะ เช่น ร้านศึกษาภัณฑ์ ครับ.

ดีกรี ก็คือ จำนวนเส้นเชื่อมทั้งหมดที่เชื่อมต่อกับจุดยอดนั้น ๆ

ปัญหาที่ถามนี้ก็อยู่ในหนังสือเรียนครับ.

[Di[s]-Stepz]

ขอบคุณ คุณ RM@ มากครับ