แบบฝึกหัด (ข้อที่มี  อยู่หน้าข้อแสดงว่ามีอยู่ในหน้าเฉลย)

ในแบบฝึกหัดที่1-3 จงหาจำนวนจุด จำนวนเส้นทางแต่ละเส้นทาง และดีกรีของแต่ละจุดใน กราฟไม่ระบุทิศ ทางที่ให้มา

1.

2.

3.

3.

4.หาผลรวมของดีกรีของจุดของแต่ละกราฟในข้อ1-3 และจงพิสูจน์ว่าผลรวมของดีกรีทั้งหมดเท่ากับสองเท่าของ จำนวนด้าน

5.มีกราฟธรรมดาที่มีจุดทั้งหมด 15 จุดและแต่ละจุดมีดีกรีเท่ากับ5หรือไม่?

6.จงหาผลรวมของคนที่เข้าร่วมงานเลี้ยงงานหนึ่ง ซึ่งไม่มีใครเอามือซ้ายของตัวเองจับมือขวาของตัวเองเลย

ในแบบฝึกหัดที่7-9 จงหาจำนวนจุดและเส้นทางและ หา in-degree และ out-degreeของแต่ละจุดของ directed multIgraph

7.

8.

9.

10.กราฟในข้อที่7-9 จงหาผลรวมของ in-degree และ out-degree และผลรวมของดีกรีทั้งหมดเท่า กับสองเท่าของจำนวนด้าน

11.จงสร้างกราฟที่ไม่ระบุทิศทางที่ขีดเส้นใต้ด้วยกราฟที่มีเส้นทางที่ระบุทิศทางจากรูป

12.จงวาดตามกราฟที่ให้มานี้

a) K7

b)K1,8

c)K4,4

d)C7

e)W7

f)Q4

จากข้อ 13 - 17 ให้ทำการพิจารณาว่าเป็น Bipartite graph หรือไม่

13.

14.

15.

16.

17.

18. ค่า n ใดที่ทำให้ กราฟต่อไปนี้เป็น Bipartite graph

a)Kn b)Cn c)Wn d)Qn

19. ต้องมีจำนวน vertice n ตั้งแต่เท่าไหร่ที่ทำให้เป็นไปตามกราฟพวกนี้

a)Kn b)Cn c)Wn d)Km,n e)Qn

20. มีจำนวนด้านทั้งหมดกี่ด้านที่เกิดจากดีกรีของจุด ดังต่อไปนี้ 4,3,3,2,2 (ให้วาดรูปแสดงด้วย)

21.จะมีกราฟธรรมดาที่มี5 จุดตามดีกรีต่อไปนี้หรือไม่ ถ้ามีจงวาดกราฟนั้นด้วย

a) 3,3,3,3,2

b)1,2,3,4,5

c)1,2,3,4,4

d)3,4,3,4,3

e)0,1,2,2,3

f)1,1,1,1,1

22.มีกี่กราฟย่อยที่ประกอบด้วยตั้งแต่ 1 จุดขึ้นไปในกราฟ K2

23.มีกี่กราฟย่อยที่ประกอบด้วยตั้งแต่ 1 จุดขึ้นไปในกราฟ K3

24.มีกี่กราฟย่อยที่ประกอบด้วยตั้งแต่ 1 จุดขึ้นไปในกราฟ W3

25.จงวาดกราฟย่อยตามกราฟต่อไปนี้

26.จงเขียนกราฟ G โดยให้จำนวนจุดเท่ากับ v และจำนวนเส้นทางเท่ากับ e.ให้มีจำนวนดีกรีสูงสุด ในจำนวน m นจุดของกราฟ G เป็นจำนวน M. ให้มีจำนวนดีกรีต่ำสุดในจุดของกราฟ G จงแสดง

กราฟธรรมดาจะถูกเรียกว่า regular กราฟ ถ้าทุกๆจุดของกราฟนี้มีดีกรีเท่ากัน แต่ถ้าทุกๆจุดในกราฟมีดีกรีเท่ากับ n จะเรียกว่า n - regular กราฟ

27.ค่าใดของ n ที่เป็นไปตาม regular กราฟ

a)Kn b)Cn c)Wn d)Qn

28.ค่าใดของ m และ n ที่ทำให้ Km,n เป็น regular graph

29.มีกี่จุดที่เป็นจำนวน จุด ของ regular graph ใน ดีกรี 4 และ 10 มีจำนวนเท่าไหร่ ?

ในแบบฝึกหัดที่ที่ 30-32 จงหาผลรวมของการ union ของคู่กราฟธรรมดานี้

30.

31.

32.

33. complement graph ของ G ของกราฟอย่างง่าย G ที่มีจุดเหมือนกับกราฟ G .จะมีสองจุดที่ Adjacent กันใน G และถ้าสองจุดนั้นไม่ adjacent กันใน G จงหากราฟต่อไปนี้ a)Kn b)Km.,n c)Cn d)Qn ตามเงื่อนไข

34. ถ้า G เป็น กราฟธรรมดา ที่มี 15 เส้นทาง และ G มี 13 edges จะมีจำนวน จุด ของ G เท่าไหร่?

35. ถ้า กราฟธรรมดา G มี จำนวนจุดเท่ากับ v และ มีเส้นทางเท่ากับ e จำนวน edges G มีเท่าไหร่ ?

36. จงแสดงว่า ถ้า G เป็น bipartite simple graph ที่มี จำนวนจุดเท่ากับ v และ มีเส้นทางเท่ากับ e ดังนั้น

37. จงแสดงว่า ถ้า G เป็น กราฟธรรมดา ที่มี จำนวนจุดเท่ากับ v ดังนั้น การ union ของ G และ G คือ K n ?

38. จงบรรยาย algorithm ของ bipartite กราฟ?

39. จงวาด mesh network สำหรับการติดต่อภายในของ processor 9 ตัวที่ทำงานแบบ parallel

40. ถ้า mesh network สำหรับการติดต่อภายใน n = m ² processor, P(I,j) เป็นการติดต่อสำหรับ processor 4 ตัว, P(( I ? 1 ) mod m ,j ) , P(I,(j ?1) mod m) ดังนั้นการติดต่อแบบ wrap around ของระบบ จงวาด ระบบ mesh network สำหรับ processor 16 ตัว

41. จงแสดงทุก ๆคู่ ของ processor ของ mesh network ของ n = m² processor ที่สามารถติดต่อโดยใช้ O( ? n ) = O (m) ที่ใช้ในการติดต่อในช่วงสั้น ๆ กับการติดต่อโดยตรงกับ processor

ไปหน้าเฉลยคำตอบ