แบบฝึกหัดที่ 2

1. มีเมืองอยู่ 7 เมือง แต่ละเมืองมีถนนเชื่อมกัน 4 สาย
1) สามารถเดินทางจากเมืองหนึ่งไปอีกเมืองหนึ่งได้หรือไม่
2) ถ้ามีการปิดถนนเพื่อทำการซ่อมแซมจะปิดถนนซ่อมได้มากที่สุดกี่สายโดยที่ยังสามารถทำให้สามารถเดินทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งได้เสมอ

แบบฝึกหัดชุด 1

แบบฝึกหัด ชุด 1

1. จงหาผลบวกของดีกรีของทุก ๆ จุดยอดในกราฟ G เมื่อ V(G) = { a, b, c, d } และ E(G) ดังต่อไปนี้
1) E(G) = {ab, ac, bc, cd } 2) E(G) = [ab, ac, ad, ba, bb, cb, cd }

2. ถ้ากำหนด G = (V(G), E(G)) เมื่อ V(G) = {a, b, c, d} และ deg(a) = 2, deg(b) = 3 dec(c) = 3
และ deg(d) = 3 มีกราฟ G เกิดขึ้นหรือไม่ พร้อมบอกเหตุผลประกอบคำตอบ

3. ถ้าจุดยอดของกราฟ G มีดีกรี 3 หรือ 5 เท่านั้น |V(G)|=14 และ |E(G)|=25 จงหาจำนวนของจุดยอดที่มีดีกรี 3
และดีกรี 5

4. ถ้าจุดยอดแต่ละจุดในกราฟ G มีดีกรี 2 เท่านั้น และ |E(G)| = 10 จงหาจำนวนจุดยอดในกราฟ G

5. จงสร้างกราฟ G ในข้อ 4 ตามหัวข้อต่อไปนี้
1) กราฟ G เป็นกราฟเชิงเดียว 2) กราฟ G เป็นกราฟหลายเชิง

6.ถ้ากราฟ G มี |V(G)| = 6 โดยมีดีกรีเป็น 1, 2, 3, 5, 5 และ 6 จงหาจำนวนเส้นเชื่อมในกราฟ G

7. ถ้าจุดยอดแต่ละจุดในกราฟ G มีดีกรีของทุก ๆ จุดยอดเท่ากัน และ |E(G)| = 10
จงหาจำนวนของจุดยอดที่เป็นไปได้ในการสร้างกราฟ G

8. งานเลี้ยงหนึ่งมีผู้มาร่วมงาน 5 คน คือ นิด น้อย หน่อย แอน และ เอ ซึ่งแต่ละคนจะทักทายกันด้วยการจับมือกัน
เป็นไปได้หรือไม่ที่ผู้มาร่วมงานทั้ง 5 คน ซึ่งแต่ละคนจะจับมือทักทายกันเป็นจำนวน 0, 1, 2, 3 และ 3 ครั้งตามลำดับ

9. นายอิสระกล่าวว่า "นักเรียนชั้นมัธมศึกษาปีที่ 5 ห้องหนึ่ง มีนักเรียน 10 คนซึ่งแต่ละคนมีเพื่อน 5 คนในชั้นเรียน
มีนักเรียน 6 คนซึ่งแต่ละคนมีเพื่อน 1 คนในชั้นเรียน มีนักเรียน 7 คนซึ่งแต่ละคนมีเพื่อน 3 คนในชั้นเรียน" อยากทราบว่าคำกล่าวของนายอิสระเป็นไปได้หรือไม่

10. จงเขียนกราฟที่ถอดแบบกัน 2 กราฟ โดยที่กราฟดังกล่าวมีจุด 5 จุด และมีเส้น 6 เส้น

11. จงยกตัวอย่างกราฟที่มี 3 จุด ซึ่งไม่ถอดแบบกันจำนวน 4 กราฟ



=======================================================

หลักสูตร

หลักสูตร : วิทยาศาสตร์บัณฑิต สาขาคณิตศาสตร์
คณะวิทยาศาสตร์ มหาวิทยาลัยราชภัฏอุบลราชธานี

รหัสวิชา : 4094504

ชื่อวิชา : ทฤษฎีกราฟเบื้องต้น (Introduction to Graph Theory)

รายละเอียดของวิชา :
นิยามของกราฟไ ความไม่ขาดตอนของกราฟ  วิถี  ต้นไม้  กราฟแบบออยเลอร์และแฮมิลตัน กราฟเชิงระนาบ  การให้สีกราฟ  ไดกราฟ และการไหลของข่ายงาน

------------------------------------------------------------------------------------

การวัดและประเมินผล :
คะแนนระหว่างภาค 60 คะแนน
คะแนนปลายภาค 40 คะแนน

--------------------------------------------------------------------------------------

หนังสืออ้างอิง
1. สาขาคณิตศาสตร์มัธยมศึกษา สถาบันส่งเสริมการสอนวิทยศาสตร์และเทคโนโลยี. ทฤษฎีกราฟเบื้องต้น.
กรุงเทพฯ : บริษัทรากขวัญจำกัด, 2546.
2. สำนักคณิตศาสตร์และคอมพิวเตอร์ สถาบันส่งเสริมการสอนวิทยาศาสตร์และเทคโนโลยี.
ความรู้เบื้องต้นเกี่ยวกับทฤษฎีกราฟพร้อมแบบฝึกหัดและแนวคิดกรุงเทพฯ : บริษัทรากขวัญจำกัด, 2544.
3. นวรัตน์ อนันต์ชื่น. ทฤษฎีกราฟ.กรุงเทพฯ : มหาวิทยาลัยศิลปากร, 2540.
4. ชะเอม สายทอง. ทฤษฎีกราฟ. กรุงเทพฯ : โอเดียนสโตร์, 2544.
ฯลฯ

---------------------------------------------------------------------------------

ผู้สอน  รองศาสตราจารย์พีระพล  ศิริวงศ์
Email : perapon99@gmail.com
Blog : http://krupee.blogspot.com
          http://graph-drill.blogspot.com