1.ง่าย
กราฟอย่างง่ายมี 6 จุดยอดที่มีดีกรี 3, 3, 2, 2, 1, 1 มีกี่เส้นเชื่อม |E|
deg: 3, 3, 2, 2, 1, 1
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
ต้นไม้มี 36 จุดยอด มีกี่เส้นเชื่อม |E|
|V| = 36
|E| =
3.ปานกลาง
กราฟเชื่อมโยงมี 16 จุดยอดและ 27 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม
|V| = 16|E| = 27
k =
4.ปานกลาง
ต้นไม้มี 2 จุดยอดดีกรี 3, 4 จุดยอดดีกรี 4 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
2 × deg 34 × deg 4
L =
5.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(G) ของเส้นทางที่สั้นที่สุดจาก A ไป G ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: G
d(G) =
6.ยาก
มีวอล์กปิดความยาว 2 ที่เริ่มและจบที่ B กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N
M = เมทริกซ์ประชิดL = 2
N =
เฉลย
- 1. |E| = 6
- 2. |E| = 35
- 3. k = 12
- 4. L = 12
- 5. d(G) = 14
- 6. N = 3
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com