แบบฝึกหัด ชุด 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 กราฟ
=======================================================
