แบบฝึกหัดกราฟ (graph)

แบบฝึกหัด 2.1

1.   จงหา V(G) และ E(G) ของกราฟ G ที่กำหนดให้ต่อไปนี้

           (1)  

           (2)                                                              

           (3)  

           (4)

           (5)  

           (6)  

            (7)  

            (8) 

2.   จงเขียนแผนภาพของกราฟ G เมื่อกำหนดให้

           (1)   V(G)   =   {V1, V2, V3 , V4}  

                   E(G)   =   {V1, V2, V1V3,V3V3}  

           (2) )   V(G)   =  {V1,V2,V3,V4}  

                   E(G)   =   {V1V2, V2V3, V2V4, V4V4} 

           (3) )   V(G)   = {V1, V2, V3, V4, V5, V6}  

                   E(G)   =   {V1V3, V2V4, V2V6, V3V5,V3V6, V4V5, V4V6}  

           (4) )   V(G)   =   {V1, V2, V3, V4}  

                   E(G)   =   {V1V1, V1V2, V2V3, V2V4, V3V3, V4V4}  

           (5) )   V(G)   =   {V1, V2 ,V3, V4}  

                   E(G)   =   {V1V2, V1V4, V2V3, V2V4, V4V4}  

           (6)   V(G)   =   {a , b ,c, d}

                   E(G)   =   {ab, cd, bd, bc}

           (7)   V(G)   =   {e, f, g, h, I, j}

                   E(G)   =   {eh, ej, hi, ij, fh, hi}

           (8)   V(G)   =   {k, m, n, p, q, r}

                   E(G)   =   {km, mp, kp, qr}

3.   กำหนดกราฟดังรูป

จงพิจารณาว่าข้อความต่อไปนี้   ถูกหรือผิด

           (1)   จุดยอด u และจุดยอด z เป็นจุดยอดประชิด

           (2)   จุดยอด v และจุดยอด z เป็นจุดยอดประชิด

           (3)   เส้นเชื่อม d เกิดกับจุดยอด v

           (4)   เส้นเชื่อม c เกิดกับจุดยอด u

           (5)   เส้นเชื่อม f เกิดกับจุดยอด v

4.   ที่จอดรถแห่งหนึ่งมีรถที่จอดประจำ 6 คัน ในช่วงเวลาต่างๆ ดังนี้

            คันที่ 1 จอดเฉพาะช่วงเวลา 7 นาฬิกา   ถึง   15   นาฬิกา

            คันที่ 2 จอดเฉพาะช่วงเวลา 12 นาฬิกา   ถึง   21   นาฬิกา

            คันที่ 3 จอดเฉพาะช่วงเวลา 9 นาฬิกา   ถึง   13   นาฬิกา

            คันที่ 4 จอดเฉพาะช่วงเวลา 16 นาฬิกา   ถึง   24   นาฬิกา

            คันที่ 5 จอดเฉพาะช่วงเวลา 8 นาฬิกา   ถึง   18   นาฬิกา

            คันที่ 6 จอดเฉพาะช่วงเวลา 22 นาฬิกา   ถึง   8   นาฬิกา

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

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

5. (1) จงเขียนกราฟโดยมีจุดยอด 6 จุด ซึ่งแทนด้วยประเทศต่างๆ ดังนี้ ไทย ลาว กัมพูชา พม่า มาเลเซีย และเวียดนาม และจุดยอดสองจุดมีเส้นเชื่อมก็ต่อเมื่อประเทศที่แทนด้วยจุดยอดทั้งสองมีอาณาบริเวณติดต่อกัน

     (2)   ถ้าต้องการระบายสีแผนที่ของประเทศทั้งหกโดยที่ประเทศที่มีอาณาบริเวณติดต่อกันต้องระบายสีคนละสี   จะต้องใช้สีอย่างน้อยที่สุดกี่สี