1.ง่าย
จงหาผลบวกของดีกรีของทุกจุดยอดของกราฟที่แสดง Σ deg
|V| = 6
Σ deg =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
ป่า (กราฟที่ไม่มีวัฏจักร) มี 13 จุดยอดและ 2 ส่วนประกอบเชื่อมโยง มีกี่เส้นเชื่อม |E|
|V| = 13c = 2
|E| =
3.ปานกลาง
กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ
|V| = 7|E| = 9
- 1วงจรออยเลอร์
- 2ทางเดินออยเลอร์ ไม่มีวงจร
- 3ไม่ใช่ทั้งสองอย่าง
4.ปานกลาง
กราฟเชื่อมโยงมี 8 จุดยอดและ 8 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม
|V| = 8|E| = 8
k =
5.ยาก
มีวอล์กความยาว 3 จาก A ไป D กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N
M = เมทริกซ์ประชิดL = 3
N =
6.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(G) ของเส้นทางที่สั้นที่สุดจาก A ไป G ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: G
d(G) =
เฉลย
- 1. Σ deg = 16
- 2. |E| = 11
- 3. ไม่ใช่ทั้งสองอย่าง
- 4. k = 1
- 5. N = 3
- 6. d(G) = 14
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com