กราฟกลุ่ม7

บทนยิ าม 4.1 กราฟ T เรยี กวา่ กราฟป่า (forest) ถ้า T ไมบ่ รรจวุ ฏั จกั ร

บทนยิ าม 4.2 กราฟป่า T เรยี กวา่ กราฟตน้ ไม้ (tree) ถา้ T เป็นกราฟเชอ่ื มโยง

“ตัวอย่าง กราฟ G ไม่เป็นทงั้ กราฟปา่ และกราฟตน้ ไม้ เนือ่ งจาก G บรรจุวฏั จกั ร คือ V1,V2,V3,V1

“ตัวอยา่ ง กราฟ D ไมเ่ ป็นทง้ั กราฟปา่ และกราฟตน้ ไม้ เน่อื งจาก D บรรจุวัฏจกั ร คือ V1,V2,V3,V10,V1

“ตัวอย่าง กราฟ H เป็นกราฟป่า เน่อื งจาก H ไมบ่ รรจุวัฏจกั ร นอกจากน้ี H เป็นกราฟตน้ ไม้ เนื่องจาก H เปน็ กราฟเชอ่ื มโยง

“ตัวอยา่ ง กราฟ M เปน็ กราฟปา่ เนอื่ งจาก M ไมบ่ รรจุวัฏจักร แต่ กราฟ M ไมเ่ ปน็ กราฟตน้ ไม้ เนอื่ งจาก M ไม่เปน็ กราฟเช่ือมโยง

“ตัวอย่าง กราฟ J ไมเ่ ป็นทั้งกราฟปา่ และกราฟต้นไม้ เนื่องจาก J บรรจวุ ฏั จกั ร คอื V1,V2,V3,V1

“ตัวอย่าง กราฟ K เปน็ กราฟปา่ เนอ่ื งจาก K ไมบ่ รรจวุ ัฏจกั ร แต่กราฟ K ไมเ่ ปน็ กราฟต้นไม้ เนอ่ื งจาก K ไมเ่ ปน็ กราฟเชื่อมโยง

“ตัวอย่าง กราฟ N เปน็ กราฟปา่ เนอ่ื งจาก N ไมบ่ รรจวุ ัฏจักร แตก่ ราฟ N ไมเ่ ปน็ กราฟต้นไม้ เนอ่ื งจาก N ไมเ่ ปน็ กราฟเชื่อมโยง

ทฤษฏบี ท 4.3 ให้ G เป็นกราฟทม่ี ดี ีกรี ของแต่ละจุดยอดมีค่าอย่างนอ้ ย เทา่ กบั 2 จะได้ว่า G มวี ฏั จกั ร

พสิ ูจนท์ ฤษฏีบท 4.3 พิจารณากรณที ี่ G เปน็ กราฟเชิงเดียว V1 V2 V6 V3 V5 V4 ดังนั้นเมื่อ i มีคา่ เพม่ิ มากข้ึนจะทาให้มีจานวนนับ k ท่ที าใหจ้ ุดยอด vk มาซ้ากับจุดยอด vj (j < k) ในวิถี ทาใหเ้ กดิ วัฏจกั ร

ตัวอย่างโจทย์ จากรูปท่กี าหนดให้กราฟ U มวี ัฏจักรหรือไม่ V1 V2 V4 V3 ดังน้ัน deg (V1) = 3 , deg (V2) = 2 , deg (V3) = 3 , deg (V4) = 2 เนื่องจาก กราฟ U เป็นกราฟท่ีมีดีกรีของแต่ละจุดยอดมีค่าอย่างน้อยเท่ากับ 2 จะไดว้ า่ U มวี ัฏจกั ร

ทฤษฎีบท 4.4 ให้ T เป็นกราฟต้นไม้ท่ีมอี นั ดับ p (p ≥ ������) จะได้ว่า T มีจดุ ปลาย อย่างน้อย 2 จุด

พสิ ูจน์ทฤษฎีบท 4.4 สมมตวิ า่ กราฟตน้ ไม้ T ไมม่ ีจดุ ปลาย ดงั น้นั แตล่ ะจุดยอดใน T จะมดี ีกรีอย่างนอ้ ยเทา่ กบั 2

พสิ ูจนท์ ฤษฎบี ท 4.4 (ต่อ) ถา้ กราฟตน้ ไม้ T ซ่งึ มีอนั ดบั p (p ≥2) มจี ุดปลายอยา่ งน้อย 2 จุด กรณที ี่ p = 2 กรณีท่ี p = 3 กรณที ี่ p = 4

ตัวอย่างโจทย์ จากรปู ท่ีกาหนดให้กราฟ Z เปน็ กราฟต้นไมห้ รือไม่ V1 V2 V3 V4 V5 กราฟ Z เป็นกราฟป่า V8 V6 เน่ืองจาก Z ไม่บรรจุวัฏจักร และ เนื่องจาก Z เป็นกราฟเชื่อมโยง V7 จึงทาให้ Z เป็นกราฟต้นไม้ท่ีมี V10 อันดับ p ≥ ������ จะได้ว่า Z มีจุด V9 ปลายอยา่ งน้อย 2 จดุ V11

ออกแบบโจทยป์ ัญหาจรงิ บริษทั Grp จากดั รับเหมาตดิ ต้ังระบบอินเทอรเ์ นต็ ตกลงรับงานวางสายอนิ เทอร์เน็ตใหก้ ับ หมู่บา้ นจดั สรรแหง่ หนง่ึ โดยกาหนดจดุ ทีต่ ิดตงั้ ทัง้ หมด 5 จุด คือ A , B, C, D, E, และ F โดยการวาง สายไปตามถนน บริษัท Grp จากดั จะมวี ิธีการวางสายสญั ญาณอย่างไร เพ่ือใหบ้ รษิ ัทลงทนุ นอ้ ยท่สี ุด หากคา่ ใชจ้ า่ ยข้นึ อยูก่ บั ระยะของการวางสายสัญญาณ ( ระยะทางการเชอ่ื มต่อสายอนิ เทอรเ์ น็ตแต่ละ จดุ แสดงตามภาพ หนว่ ยเป็นเมตร ) กระบวนการคดิ ใชเ้ รอ่ื งกราฟตน้ ไม้เข้ามาแกป้ ัญหา

กรณที ่ี 1 B 10 C B 10 C A 30 20 30 20 A 20 50 30 20 E 10 D 10 40 F 60 E D F 20 20 10 10 20 20 20 30 30 40 50 60 จะได้ระยะทางท่ีตอ้ งวางสายอนิ เทอรเ์ นต็ คอื 10 + 10 + 20 + 20 + 30 = 90 ดงั นน้ั บริษทั Grp จากัดจะตอ้ งวางสายอนิ เทอรเ์ นต็ 90 เมตร

กรณที ่ี 2 B 10 C B 10 C A 30 20 30 20 A 20 50 30 20 E 10 D 10 40 F 60 E D F 20 20 10 10 20 20 20 30 30 40 50 60 จะไดร้ ะยะทางทีต่ ้องวางสายอนิ เทอรเ์ นต็ คอื 10 + 10 + 20 + 20 + 30 = 90 ดงั นน้ั บริษทั Grp จากัดจะต้องวางสายอนิ เทอร์เนต็ 90 เมตร

กรณที ่ี 3 30 B 10 C B 10 C A 20 20 30 A 20 50 30 20 F E 10 D 10 40 F 60 E D 20 20 10 10 20 20 20 30 30 40 50 60 จะไดร้ ะยะทางทีต่ ้องวางสายอนิ เทอรเ์ นต็ คอื 10 + 10 + 20 + 20 + 30 = 90 ดงั นน้ั บริษทั Grp จากัดจะต้องวางสายอนิ เทอร์เนต็ 90 เมตร

รายชอ่ื สมาชิก นางสาวกาญจนา วงษค์ ามี รหสั นักศกึ ษา 594143004 นางสาวสิริวรรณ ทักษณิ าวัฏ รหัสนกั ศกึ ษา 594143074 นางสาวชนนิกานต์ แซจ่ าง รหัสนกั ศึกษา 594143082 นางสาวสภุ ารตั น์ เคนคาพนั รหัสนักศกึ ษา 594143087 นางสาวบุญญิสา จนี ขี รหสั นกั ศึกษา 594143090 หม่เู รยี น 59/6 สาขาคณิตศาสตร์