wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Lý thuyết đồ thị

Total questions: 108

Worksheet time: 54mins

Name
Class
Date
1.

Đồ thị lưỡng phân có bao nhiêu đỉnh?

a)

n

b)

m

c)

m + n

d)

. m*n

2.

Cho đồ thị vô hướng như hình vẽ. Một chu trình có độ dài 4 là

a)

b, c, d, e, f

b)

c, f, e, d, e

c)

a, b, c, f, e

d)

c, f, e, d, c

3.

Cho đồ thị vô hướng như hình vẽ. Một đường đi đơn có độ dài 4 là

a)

d, b, c, d, b

b)

a, b, c, b, d

c)

a, b, a, b, c

d)

b, c, f, e, a

4.

Ma trận kề của đồ thị sau là

a)

b)

c)

d)

5.

Ma trận kề của đồ thị sau là

a)

b)

c)

d)

6.

Cho ma trận kề của đồ thị vô hướng như sau:

Hỏi đồ thị nào sau đây ứng với ma trận kề trên?

a)

b)

c)

d)

7.

Ma trận kề của đồ thị sau là

a)

b)

c)

d)

8.

Đỉnh của đồ thị vô hướng gọi là có bậc n nếu:

a)

v kề với n – 1 đỉnh khác trong đồ thị G.

b)

v kề với n đỉnh khác trong đồ thị G.

c)

Đồ thị G có n đỉnh.

d)

Đồ thị G có n – 1 đỉnh.

9.

Tổng các phần tử của ma trận kề của đồ thị vô hướng đúng bằng:

a)

Hai lần số cạnh của đồ thị

b)

Một nửa số cạnh của đồ thị

c)

Số cạnh của đồ thị

d)

Số đỉnh của đồ thị

10.

Trong các đồ thị sau đây, đồ thị nào là đồ thị liên thông mạnh?

a)

b)

c)

d)

11.

Cho đồ thị như hình vẽ. Hãy cho biết đâu là một đường đi Hamilton của đồ thị?

a)

1,2,3,6,9,8,7,6,5,4,1

b)

1,4,3,2,7,6,5,10,9,8,7,2,1

c)

1,2,3,4,5,6,7,8,9,10,5,4

d)

1,2,3,4,5,6,7,8,9,10

12.

Đồ thị G được gọi là đồ thị nửa Hamilton khi và chỉ khi:

a)

G có chu trình Euler

b)

G không có chu trình Hamilton

c)

G có đường đi Hamilton

d)

G có đường đi Euler

13.

Cho đồ thị như hình vẽ. Hãy cho biết đâu là một đường đi Euler của đồ thị?

a)

4,3,2,6,7,8,9,10,5,4,6,9,5,6

b)

6,2,3,4,5,6,7,8,9,5,10,9,5,4

c)

2,6,7,8,9,10,5,4,3,2

d)

2,6,7,8,9,10,5,4,3,2

14.

Cho đồ thị như hình vẽ. Hãy cho biết đâu là một đường đi Euler của đồ thị?

a)

a, e, c, f, b, d, e, d, f

b)

a, e, c, f, b, f, d, e, d

c)

a, e, c, f, b, d, f, e, a

d)

a, e, c, f, b, d, f, e, d

15.

Thuật toán Floyd được áp dụng để

a)

tìm đường đi ngắn nhất giữa hai đỉnh bất kì của đồ thị.

b)

tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị.

c)

tìm đường đi ngắn nhất giữa các cặp đỉnh bất kì của đồ thị.

d)

tìm cây khung nhỏ nhất của đồ thị.

16.

Cho đồ thị như hình vẽ. Hãy cho biết kết quả của thuật toán duyệt theo chiều sâu DFS(1)?

a)

1, 2, 6, 7, 8, 4, 5, 3, 10, 9

b)

. 1, 2, 3, 6, 8, 4, 5, 7, 10, 9

c)

1, 2, 3, 4, 5, 10, 9, 6, 7, 8

d)

. 1, 2, 3, 7, 8, 4, 5, 6, 10, 9

17.

Cho đồ thị vô hướng G và đồ thị là đồ thị bù của G. Hãy chọn phát biểu đúng?

a)

b)

c)

d)

18.

Tổng các phần tử của ma trận kề của đồ thị có hướng đúng bằng:

a)

Một nửa số cạnh của đồ thị

b)

Số đỉnh của đồ thị

c)

Số cạnh của đồ thị

d)

Hai lần số cạnh của đồ thị

19.

Đồ thị k đều n đỉnh thì có bao nhiêu cạnh

a)

b)

c)

d)

20.

Cho ma trận kề của đồ thị có hướng như sau:

Hỏi đồ thị nào sau đây ứng với ma trận kề trên?

a)

b)

c)

d)

21.

Thuật toán Dijkstra được áp dụng trong trường hợp nào sau đây?

a)

Đồ thị có hướng có trọng số âm

b)

Đồ thị vô hướng hoặc có hướng có trọng số không âm

c)

Đồ thị vô hướng hoặc có hướng có trọng số âm

d)

Đồ thị vô hướng có trọng số âm

22.

Cho đồ thị như hình vẽ. Hãy cho biết đâu là một chu trình Euler của đồ thị?

a)

a, e, c, f, b, f, d, e, d, a

b)

a, e, c, f, b, d, f, e, a, d

c)

a, e, c, f, b, d, f, e, d, a

d)

a, e, c, f, b, d, a, f, d, a

23.

Cho đồ thị như hình vẽ. Cạnh nào dưới đây là cạnh treo?

a)

. Cạnh (b,c)

b)

Cạnh (b,e)

c)

. Cạnh (a,b)

d)

Cạnh (a,f)

24.

Cho đồ thị như hình vẽ. Hãy cho biết đâu là một chu trình Hamilton của đồ thị?

a)

f, e, d, b, f, c, e, a, d, f

b)

b, f, c, e, d, a, b

c)

a, e, c, f, b, d, f, e, d, a

d)

e, c, f, b, d, a

25.

Bậc của mọi đỉnh trong thị vòng Cn bằng:

a)

. n – 1

b)

. 2n

c)

2

d)

3

26.

Ma trận kề của đồ thị có hướngthì:

a)

không được là ma trận vuông

b)

luôn là ma trận đơn vị

c)

có thể là ma trận không đối xứng

d)

luôn là ma trận đối xứng

27.

Trong các đồ thị sau đây, đồ thị nào còn được gọi là đồ thị nửa Euler?

a)

Đồ thị (4)

b)

Đồ thị (1)

c)

Đồ thị (3)

d)

Đồ thị (2)

28.

Cho đồ thị như hình vẽ. Hãy cho biết đâu là một chu trình Euler của đồ thị?

a)

1,4,6,9,8,7,3,2,4,5,1

b)

. 1,4,5,10,9,8,7,3,2,1

c)

1,4,6,9,10,5,9,8,7,6,3,7,2,6,5,4,3,2,1

d)

1,4,3,6,5,10,9,8,7,6,2,1,2,6,5,4,3,2,1

29.

Trong các đồ thị sau đây, đồ thị nào chỉ có đường đi Euler nhưng không có chu trình Euler?

a)

Đồ thị (4)

b)

Đồ thị (2)

c)

Đồ thị (1)

d)

Đồ thị (3)

30.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh N đến đỉnh B có độ dài bằng:

a)

11

b)

12

c)

10

d)

15

31.

Cho đồ thị có ma trận trọng lượng như bên dưới. Đường đi ngắn nhất từ đỉnh 2 đến đỉnh 4 của đồ thị có độ dài bằng:


a)

4

b)

3

c)

2

d)

-2

32.

Đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi:

a)

tất cả các đỉnh của G đều có bậc chẵn.

b)

. đồ thị G có đúng hai đỉnh bậc lẻ.

c)

. tất cả các đỉnh của G đều có bậc lẻ.

d)

đồ thị G có đúng hai đỉnh bậc chẵn.

33.

Cho đồ thị như hình vẽ. Hãy cho biết đường đi ngắn nhất từ đỉnh A đến đỉnh Z là dãy đỉnh nào sau đây?

a)

A – D – Z

b)

A – B – C – Z

c)

. A – B – Z

d)

A – Z 

34.

Cho đồ thị có ma trận trọng lượng như bên dưới. Hãy cho biết đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4 là dãy đỉnh nào sau đây?

a)

1 – 3 – 4                                                                                         1 – 3 – 4

b)

1 – 2 – 4

c)

1 – 2 – 3 – 4

d)

1 – 3 – 2 – 4

35.

Cho đồ thị như hình vẽ. Hãy cho biết đường đi ngắn nhất từ đỉnh a đến đỉnh z là dãy đỉnh nào sau đây?

a)

a – c – d – f – g – z

b)

a – c – d – e – g – z

c)

a – c – e – g – f – z

d)

a – b – d – f – z

36.

Cho ma trận trọng số W của đồ thị có hướng G (gồm bốn đỉnh theo thứ tự dòng và cột của ma trận lần lượt là A, B, C, D) như sau:

Hãy cho biết đường đi ngắn nhất từ đỉnh A đến đỉnh D là dãy đỉnh nào sau đây?

a)

A – B – D

b)

A – B – C – D

c)

A – C – B – D        

d)

A – C – D

37.

Cho ma trận trọng số W của đồ thị có hướng G (gồm bốn đỉnh theo thứ tự dòng và cột của ma trận lần lượt là A, B, C, D) như sau:

Hãy cho biết đường đi ngắn nhất từ đỉnh D đến đỉnh C là dãy đỉnh nào sau đây?

a)

D – B – C – A

b)

D – A – B – C

c)

D – B – A – C

d)

C – A – B – D  

38.

Đồ thị G được gọi là đồ thị Euler khi và chỉ khi:

a)

G có đường đi Hamilton

b)

G có chu trình Euler

c)

G có đường đi Euler

d)

G có chu trình Hamilton

39.

Đồ thị G được gọi là đồ thị nửa Euler khi và chỉ khi:

a)

G không có chu trình Euler

b)

G có đường đi Hamilton

c)

G có đường đi Euler

d)

G có chu trình Hamilton

40.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh a đến đỉnh z có độ dài bằng

a)

69

b)

58

c)

77

d)

78

41.

Cho ma trận trọng số W của đồ thị có hướng G (gồm bốn đỉnh theo thứ tự dòng và cột của ma trận lần lượt là A, B, C, D) như sau:

Hãy cho biết giá trị tại dòng thứ 3 cột thứ 2 của ma trận trọng lượng thứ hai (A2) là bao nhiêu?

a)

– 1

b)

3

c)

5

d)

– 4

42.

Cho ma trận trọng số W của đồ thị có hướng G (gồm bốn đỉnh theo thứ tự dòng và cột của ma trận lần lượt là A, B, C, D) như sau:

Hãy cho biết độ dài đường đi ngắn nhất từ đỉnh A đến đỉnh D

a)

5

b)

3

c)

-4

d)

-1

43.

Đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi:

a)

đồ thị G có đúng hai đỉnh bậc lẻ.

b)

tất cả các đỉnh của G đều có bậc lẻ.

c)

tất cả các đỉnh của G đều có bậc chẵn.

d)

đồ thị G có đúng hai đỉnh bậc chẵn.

44.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh A đến đỉnh Z có độ dài bằng:

a)

7

b)

5

c)

3

d)

6

45.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh a đến đỉnh z có độ dài bằng:

a)

77

b)

58

c)

78

d)

69

46.

Đường đi Hamilton là đường đi

a)

đi qua tất cả các đỉnh bậc chẵn của đồ thị.

b)

đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.


c)

đi qua tất cả các đỉnh bậc lẻ của đồ thị.

d)

đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.


47.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh E đến đỉnh N có độ dài bằng:

a)

9

b)

8

c)

10

d)

11

48.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh A đến đỉnh O với điều kiện phải đi qua đỉnh I có độ dài bằng:

a)

34

b)

32

c)

30

d)

38

49.

Tất cả các chu trình độ dài chẵn đều có sắc số là

a)

1

b)

4

c)

3

d)

2

50.

Nếu đồ thị G chứa đồ thị con đẳng cấu với Kn thì sắc số của G sẽ

a)

nhỏ hơn n

b)

lớn hơn hoặc bằng n

c)

bằng 3

d)

bằng n

51.

Cho đồ thị vô hướng có các đỉnh có bậc lần lượt là 4, 3, 3, 2, 2. Hỏi đồ thị G có bao nhiêu cạnh?

a)

5

b)

3

c)

2

d)

7

52.

Cho đồ thị vô hướng, cạnh gọi là cạnh cầu nếu:

a)

khi xóa bỏ cạnh e sẽ làm tăng số thành phần liên thông cùa đồ thị

b)

khi xóa bỏ cạnh e sẽ làm giảm số thành phần liên thông cùa đồ thị

c)

cạnh e là khuyên

d)

cạnh e là cạnh bội

53.

Cho đồ thị , hãy cho biết đâu là tính chất đúng của một đơn đồ thị có hướng?

a)

b)

c)

d)

54.

Cho đồ thị vô hướngcó n đỉnh, hãy chọn phát biểu SAI?

a)

Số các đỉnh bậc chẵn là số lẻ

b)

Tổng bậc của các đỉnh bậc lẻ là số chẵn

c)

Nếu đồ thị có đúng hai đỉnh cùng bậc thì hai đỉnh này không thể đồng thời có bậc 0 hoặc bậc n – 1

d)

Số các đỉnh bậc lẻ là số chẵn

55.

Đồ thị G được gọi là đồ thị Hamilton khi và chỉ khi:

a)

G có chu trình Euler

b)

G có chu trình Hamilton

c)

G có đường đi Hamilton

d)

. G có đường đi Euler

56.

Cho đồ thị như hình vẽ. Đỉnh nào dưới đây là đỉnh cắt?

a)

Đỉnh h

b)

Đỉnh e

c)

Đỉnh f

d)

Đỉnh g

57.

Cho G là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh (v ≥ 3). Khi đó ta có:

a)

e ≤ 2v - 6

b)

e ≤ 3v - 4

c)

e ≤ 3v - 4

d)

e ≤ 3v - 6

58.

Cho đồ thị vô hướng . Hãy chọn khẳng định đúng trong các khẳng định sau?

a)

Thuật toán BFS(i) duyệt một số đỉnh của đồ thị, mỗi đỉnh đúng một lần

b)

Thuật toán BFS(i) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị

c)

. Thuật toán BFS(i) duyệt tất cả các thành phần liên thông của đồ thị

d)

Thuật toán BFS(i) duyệt tất cả các đỉnh của đồ thị thuộc cùng thành phần liên thông với i

59.

Cho đồ thị vô hướng . Hãy chọn khẳng định đúng trong các khẳng định sau?

a)

Thuật toán DFS(i) duyệt tất cả các đỉnh của đồ thị thuộc cùng thành phần liên thông với i

b)

Thuật toán DFS(i) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị

c)

. Thuật toán DFS(i) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

d)

Thuật toán DFS(i) duyệt tất cả các thành phần liên thông của đồ thị

60.

Cho đồ thị G như hình bên dưới. Hãy cho biết sắc số của G là bao nhiêu?

a)

4

b)

2

c)

3

d)

5

61.

Khẳng định nào đúng trong các khẳng định sau đây?

a)

Cây là một đơn đồ thị vô hướng, liên thông và không có chu trình sơ cấp

b)

Cây là một đa đồ thị vô hướng, liên thông và có chu trình sơ cấp


c)

Cây là một đơn đồ thị vô hướng, liên thông và có chu trình sơ cấp

d)

Cây là một đa đồ thị vô hướng, liên thông và không có chu trình sơ cấp

62.

Khẳng định nào đúng trong các khẳng định sau đây?

a)

Sắc số của một đồ thị là số màu ít nhất cần dùng để tô các đỉnh của đồ thị sao cho hai đỉnh kề nhau được tô bằng hai màu khác nhau.

b)

Sắc số của một đồ thị là số màu ít nhất cần dùng để tô các cạnh của đồ thị sao cho hai cạnh kề nhau được tô bằng hai màu khác nhau.

c)

Sắc số của một đồ thị là số màu nhiều nhất cần dùng để tô các đỉnh của đồ thị sao cho hai đỉnh kề nhau được tô bằng hai màu khác nhau.

d)

Sắc số của một đồ thị là số màu nhiều nhất cần dùng để tô các cạnh của đồ thị sao cho hai cạnh kề nhau được tô bằng hai màu khác nhau.

63.

Cho đồ thị vô hướng như sau:

Trọng lượng cây khung nhỏ nhất của đồ thị với điều kiện cây khung phải chứa cạnh BG là

a)

30

b)

25

c)

21

d)

22

64.

Đơn đồ thị vô hướng G có thể tô bằng 2 màu khi và chỉ khi:

a)

Tất cả các đỉnh của G đều có bậc lẻ

b)

Tồn tại chu trình độ dài lẻ trong G

c)

Tất cả các đỉnh của G đều có bậc chẵn

d)

Không tồn tại chu trình độ dài lẻ trong G

65.

Đơn đồ thị đầy đủ Kn thì có sắc số là bao nhiêu?

a)

3

b)

n

c)

n-1

d)

2

66.

Đỉnh của đồ thị vô hướng gọi là có bậc n nếu:

a)

Đồ thị G có n đỉnh.

b)

v kề với n đỉnh khác trong đồ thị G.

c)

v kề với n – 1 đỉnh khác trong đồ thị G.

d)

Đồ thị G có n – 1 đỉnh.

67.

Đồ thị là một đa đồ thị có hướng thì:

a)

G không có khuyên.

b)

G có cung bội.

c)

G có số lượng đỉnh là số lẻ.

d)

G không có cung bội.

68.

Cho đồ thị vô hướng . Biết rằng G có 15 cạnh, 3 đỉnh có bậc là 4 và các đỉnh còn lại có bậc là 3. Hỏi đồ thị G có tất cả bao nhiêu đỉnh?

a)

9

b)

4

c)

6

d)

3

69.

Cho đồ thị , hãy cho biết đâu là tính chất đúng của một đa đồ thị vô hướng?

a)

b)

c)

d)

70.

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán DFS(b)

a)

. b, g, e, f, h, d, c, a

b)

b, d, a, b, g, e, f, h

c)

b, g, e, h, f, d, c, a

d)

b, e, g, f, h, d, c, a

71.

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(a) (nếu một đỉnh có nhiều đỉnh kề ưu tiên duyệt đỉnh kề theo thứ tự của bảng chữ cái)

a)

a, d, e, b, f, c

b)

a, e, c, f, b, d

c)

a, d, b, f, c, e

d)

a, e, d, f, c, b

72.

Cho đồ thị G có ma trận trọng số như sau:

Hãy cho biết sắc số của G là bao nhiêu?

a)

4

b)

6

c)

5

d)

3

73.

Cho đồ thị G như sau:

Hãy cho biết sắc số của G là bao nhiêu?

a)

6

b)

3

c)

2

d)

4

74.

Cho cây T có số đỉnh là n. khi đó ta có số cạnh của cây T bằng

a)

2n – 1

b)

2n

c)

n – 1

d)

n

75.

Đồ thị vô hướng được gọi là liên thông khi:

a)

b)

c)

d)

76.

Khuyên trong đồ thị là một cạnh có

a)

Không có khái niệm này

b)

đỉnh đầu bậc lẻ và đỉnh cuối bậc chẵn.

c)

đỉnh đầu bậc chẵn và đỉnh cuối bậc lẻ.

d)

đỉnh đầu và đỉnh cuối trùng nhau.

77.

Đỉnh của đồ thị vô hướng gọi là đỉnh cô lập nếu:

a)

b)

c)

d)

78.

Đồ thị vô hướng được gọi là liên thông khi:

a)

b)

c)

d)

79.

Cho đồ thị vô hướng, đỉnh gọi là đỉnh cắt (điểm khớp) nếu:

a)

khi xóa bỏ đỉnh u và các cạnh liên thuộc với nó thì sẽ làm giảm số thành phần liên thông cùa đồ thị.

b)

đỉnh u luôn là đỉnh treo.

c)

khi xóa bỏ đỉnh u và các cạnh liên thuộc với nó thì sẽ làm tăng số thành phần liên thông cùa đồ thị.

d)

đỉnh u luôn là đỉnh cô lập.

80.

Đồ thị vô hướng được gọi là liên thông khi:

a)

b)

c)

d)

81.

Đỉnh của đồ thị vô hướng gọi là đỉnh cô lập nếu:

a)

b)

c)

d)

82.

Đỉnh của đồ thị vô hướng gọi là đỉnh cô lập nếu:

a)

b)

c)

d)

83.

Chu trình Hamilton là chu trình

a)

đi qua tất cả các đỉnh bậc chẵn của đồ thị.

b)

đi qua tất cả các đỉnh bậc lẻ của đồ thị.

c)

đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.

d)

. đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.

84.

Chu trình Euler là chu trình


a)

đi qua tất cả các đỉnh bậc chẵn của đồ thị.

b)

đi qua tất cả các đỉnh bậc lẻ của đồ thị.

c)

đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.

d)

đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.

85.

Trong các đồ thị sau đây, đồ thị nào còn được gọi là đồ thị Euler?

a)

Đồ thị (4)

b)

Đồ thị (1)

c)

Đồ thị (3)

d)

Đồ thị (2)

86.

Cho G là một đơn đồ thị phẳng liên thông có 8 đỉnh và mỗi đỉnh đều có bậc là 3. Khi đó số miền của đồ thị là bao nhiêu?


a)

6

b)

5

c)

4

d)

3

87.

Đồ thị là một đơn đồ thị vô hướng thì:

a)

G có thể có cạnh bội.

b)

G có cạnh bội.

c)

G có khuyên.

d)

G không có khuyên.

88.

Một đồ thị vô hướng có 19 cạnh và mỗi đỉnh đều có bậc lớn hơn hoặc bằng 3. Hỏi đồ thị này có tối đa bao nhiêu đỉnh?

a)

38

b)

3

c)

12

d)

19

89.

Giả sử đơn đồ thị G có 15 cạnh và đồ thị bù của G có 13 cạnh. Hỏi đồ thị G có bao nhiêu đỉnh?

a)

8

b)

15

c)

28

d)

13

90.

Đồ thị vòng Cn có số cạnh là

a)

2n

b)

n

c)

n-1

d)

91.

Cho đồ thị vô hướng như hình vẽ. Một đường đi có độ dài 5 là

a)

a, b, c, d, e, c

b)

b, c, f, e, a, d

c)

a, b, d, e, a, f

d)

a, b, f, e, d, c

92.

Đồ thị đầy đủcó bao nhiêu cạnh?

a)

n

b)

2n

c)

d)

93.

Giả sử đồ thị G1 và G2 là hai đồ thị đẳng cấu với nhau. Hãy chọn phát biểu đúng?

a)

Số đỉnh của G1 lớn hơn số đỉnh của G2

b)

Số đỉnh của G2 bằng số cạnh của G1

c)

Số đỉnh của G2 lớn hơn số đỉnh của G1

d)

Số đỉnh của G1 bằng số đỉnh của G2

94.

Đồ thị lưỡng phân có bao nhiêu đỉnh?

a)

n

b)

m+n

c)

m*n

d)

m

95.

Mỗi đỉnh của đồ thị đầy đủcó bậc là bao nhiêu?

a)

2n – 1

b)

n – 1

c)

2n

d)

n

96.

Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh A đến đỉnh O với điều kiện phải đi qua đỉnh H có độ dài bằng:

a)

32

b)

36

c)

34

d)

30

97.

Trong các đồ thị sau đây, đồ thị nào là đồ thị phẳng?

a)

K5

b)

K3,4

c)

K3,3

d)

K2,2

98.

Cho đồ thị vô hướng có các đỉnh có bậc lần lượt là 4, 3, 3, 2, 2. Hỏi đồ thị G có bao nhiêu cạnh?

a)

3

b)

2

c)

7

d)

5

99.

Cho T là một cây có n đỉnh. Hãy chọn khẳng định SAI trong các khẳng định sau đây:

a)

T là một đồ thị liên thông và nếu hủy bất kỳ một cạnh nào của nó cũng không làm mất tính liên thông

b)

T không có chu trình và nếu thêm một cạnh mới nối 2 đỉnh bất kỳ của T thì sẽ tạo ra một chu trình.

c)

Giữa 2 đỉnh bất kỳ của T, luôn tồn tại một đường đi sơ cấp duy nhất nối 2 đỉnh này.

d)

T không có chu trình và có n – 1 cạnh.

100.

Cho đồ thị vô hướng như sau:

Trọng lượng cây khung nhỏ nhất của đồ thị là

a)

22

b)

21

c)

25

d)

23

101.

Cho đồ thị vô hướng như sau:

Trọng lượng cây khung nhỏ nhất của đồ thị là

a)

21

b)

15

c)

23

d)

17

102.

Cho đồ thị có ma trận trọng số như sau:

Trọng lượng cây khung nhỏ nhất của đồ thị là

a)

25

b)

. 21

c)

23

d)

. 28

103.

Đồ thị là một đa đồ thị vô hướng thì:

a)

G có cạnh bội.

b)

G có thể có khuyên.

c)

G không có cạnh bội.

d)

G phải có khuyên.

104.

Cho G là một đơn đồ thị phẳng với e cạnh, v đỉnh và có k thành phần liên thông (k ≥ 1). Khi đó số miền r trong biểu diễn phẳng của G được tính theo công thức nào sau đây?

a)

v - e + r = k + 1

b)

e - v + r = k + 1

c)

. e - v + r = k

d)

v - e + r = k

105.

Đỉnh của đồ thị vô hướng gọi là có bậc n nếu:

a)

. v kề với n – 1 đỉnh khác trong đồ thị G.

b)

. v kề với n đỉnh khác trong đồ thị G.

c)

Đồ thị G có n đỉnh.

d)

Đồ thị G có n – 1 đỉnh.

106.

Đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi:

a)

. tất cả các đỉnh của G đều có bậc chẵn.

b)

. đồ thị G có đúng hai đỉnh bậc lẻ.

c)

tất cả các đỉnh của G đều có bậc lẻ.

d)

đồ thị G có đúng hai đỉnh bậc chẵn

107.

Cho đồ thị có ma trận trọng lượng như bên dưới. Đường đi ngắn nhất từ đỉnh 2 đến đỉnh 4 của đồ thị có độ dài bằng:

a)

3

b)

-2

c)

2

d)

4

108.

Đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi:

a)

đồ thị G có đúng hai đỉnh bậc lẻ.

b)

đồ thị G có đúng hai đỉnh bậc chẵn.

c)

tất cả các đỉnh của G đều có bậc lẻ.

d)

tất cả các đỉnh của G đều có bậc chẵn.

Similar Resources on Wayground

TANGO N5 (4/10)　ともだち

105 questions

TANGO N5 (4/10)　ともだち

quiz

Worksheet

•

University

Tổng hợp 100 câu đầu

103 questions

Tổng hợp 100 câu đầu

quiz

Worksheet

•

University

Cấu trúc dữ liệu

106 questions

Cấu trúc dữ liệu

quiz

Worksheet

•

University

Hệ thống pháp luật

104 questions

Hệ thống pháp luật

quiz

Worksheet

•

University

Practice Questions: Vietnam's Integration & Economic Development

108 questions

Practice Questions: Vietnam's Integration & Economic Development

quiz

Worksheet

•

University

KINH tế chính trị 3

113 questions

KINH tế chính trị 3

quiz

Worksheet

•

University

CNXHKH

109 questions

CNXHKH

quiz

Worksheet

•

University

MÔ THẦN KINH

110 questions

MÔ THẦN KINH

quiz

Worksheet

•

University