Lí thuyết đồ thị

Description

Các nghiên cứu máy tính Quiz on Lí thuyết đồ thị , created by Thần Hoàng on 23/09/2016.
Thần  Hoàng
Quiz by Thần Hoàng, updated more than 1 year ago
Thần  Hoàng
Created by Thần Hoàng about 8 years ago
2381
2

Resource summary

Question 1

Question
Số đỉnh bán bậc ra của d tức deg+(d) bằng bao nhiêu ?
Answer
  • 1
  • 2
  • 3
  • 4

Question 2

Question
Hai đỉnh u và v gọi là kề nhau nếu?
Answer
  • Có một danh sách các cạnh nối hai đỉnh này
  • Có một cạnh (hoặc cung) nối hai đỉnh này
  • Có một danh sách các cung nối hai đỉnh này

Question 3

Question
Đỉnh v có bậc bằng 0 (deg(v)=0) gọi là?
Answer
  • Đỉnh treo
  • Đỉnh cô lập
  • Đỉnh cầu

Question 4

Question
Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số
Answer
  • chẵn
  • lẻ

Question 5

Question
Đồ thị vô hướng G có tổng số bậc là 24 hỏi đồ thị có bao nhiêu cạnh?
Answer
  • 24
  • 3
  • 6
  • 12

Question 6

Question
Đồ thị liên thông là đồ thị?
Answer
  • Giữa hai đỉnh bất kỳ đều có một cung nối
  • Giữa hai đỉnh bất kỳ đều có cạnh kề
  • Giữa hai đỉnh bất kỳ có một đường đi

Question 7

Question
Đồ thị đầy đủ là đồ thị vô hướng mà :
Answer
  • Giữa hai đỉnh bất kỳ có một cung nối
  • Giữa hai đỉnh bất kỳ có một đường đi
  • Giữa hai đỉnh bất kỳ có một cạnh nối
  • Giữa hai đỉnh bất kỳ không có cạnh chung

Question 8

Question
Cho đồ thị có hướng theo hình vẽ sau. Hãy chỉ ra đường đi từ đỉnh a đến đỉnh f:
Answer
  • a - d - e - f
  • a-d-b-f
  • a-b-e-f
  • a-d-c-f

Question 9

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 2-3; 4-5; 4-7; 5-6; 5-7; 6-7; 8-9 Số thành phần liên thông của đồ thị là:
Answer
  • 4
  • 3
  • 2
  • 1

Question 10

Question
Cho đồ thị vô hướng theo hình sau. Cho biết số thành phần liên thông của đồ thị là
Answer
  • 1
  • 2
  • 3
  • 4

Question 11

Question
Đồ thị theo hình sau là đồ thị:
Answer
  • Phẳng
  • Đầy Đủ
  • Không Phải Phẳng

Question 12

Question
Đồ thị đầy đủ K8 có bao nhiêu cạnh? ( K - số đỉnh )
Answer
  • 28
  • 24
  • 26
  • 22

Question 13

Question
Bậc của đỉnh v trong đồ thị vô hướng G là?
Answer
  • Số cung liên thuộc với nó và ký hiệu là deg-(v)
  • Số cung liên thuộc với nó và ký hiệu là deg+(v)
  • Số cạnh liên thuộc với nó và ký hiệu là deg(v)

Question 14

Question
Đỉnh v có bậc bằng 1 (deg(v)=1) gọi là?
Answer
  • Đỉnh Độc Lập
  • Đỉnh Cô Lập
  • Đỉnh Treo
  • Đỉnh Cầu

Question 15

Question
Số đỉnh bán bậc vào của c là?
Answer
  • 1
  • 2
  • 3

Question 16

Question
Cho đồ thị theo hình sau. Cho biết đường đi từ đỉnh a sang đỉnh f là ?
Answer
  • a-d-b-f
  • a-b-d-f
  • a-e-b-d-f
  • a-d-c-b-f

Question 17

Question
Chu trình trong đồ thị vô hướng là một dãy các :
Answer
  • cạnh (x0, x1), (x1, x2), …, (xn-1, xn) có x0 không trùng với xn
  • cung (x0, x1), (x1, x2), …, (xn-1, xn) có x0 trùng với xn
  • cạnh (x0, x1), (x1, x2), …, (xn-1, xn) có đỉnh đầu x0 trùng với đỉnh cuối xn
  • cung (x0, x1), (x1, x2), …, (xn-1, xn) có đỉnh đầu x0 trùng với đỉnh cuối xn

Question 18

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 2-3; 4-5; 4-7; 5-6; 6-7; 8-9 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 19

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 2-3; 2-9; 4-5; 4-7; 5-6; 6-7; 8-9 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 20

Question
Cho đồ thị vô hướng theo hình sau. Cho biết số đỉnh treo của đồ thị bằng ?
Answer
  • 6
  • 8
  • 7
  • 9

Question 21

Question
Khái niệm cạnh là của đồ thị :
Answer
  • Có hướng
  • vô hướng

Question 22

Question
Số đỉnh bán bậc ra của d tức deg+(d) bằng bao nhiêu ?
Answer
  • 1
  • 2
  • 3
  • 4

Question 23

Question
Cho đồ thị vô hướng G = (V, E) xác định bằng ma trận kề như sau: 01001 10101 01011 00101 11110 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 24

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 2-3; 4-5; 4-7; 5-6; 6-7; 8-9 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 25

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 2-3; 2-9; 4-5; 4-7; 5-6; 6-7; 8-9 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 26

Question
Cho đồ thị vô hướng G = (V, E) xác định bằng ma trận kề như sau: 01001 10111 01010 01101 11010 Số đỉnh cô lập của đồ thị là:
Answer
  • 0
  • 1
  • 2
  • 3

Question 27

Question
Số đỉnh bậc lẻ của đồ thị (theo hình vẽ) là
Answer
  • 8
  • 9
  • 10
  • 11

Question 28

Question
Số đỉnh bậc lẻ của đồ thị (theo hình vẽ) là
Answer
  • 0
  • 1
  • 2
  • 3

Question 29

Question
Cho đồ thị có hướng G = (V, E) trong đó V = {A, B, C, D, E). Biết deg+(A) = 2 ; deg-(A) = 5; deg+(B) = 5 ; deg-(B) = 6; deg+(C) = 3 ; deg-(C) = 4; deg+(D) = 2 ; deg-(D) = 3; deg+(E) = 2 ; deg-(E) = 4; Số cạnh của đồ thị là:
Answer
  • 18
  • 38
  • 25
  • 40

Question 30

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 2 của đồ thị là:
Answer
  • 3
  • 4
  • 5
  • 6

Question 31

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 1 của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 32

Question
Số đỉnh bán bậc vào của c là?
Answer
  • 1
  • 2
  • 3
  • 4

Question 33

Question
Cho đồ thị vô hướng G = (V, E) xác định bằng ma trận kề như sau: 011100 100100 100100 111000 000001 000010 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 34

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 2-3; 4-5; 4-7; 5-6; 5-7; 6-7; 8-9 Số thành phần liên thông của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 35

Question
Cho đồ thị vô hướng G = (V, E) xác định bằng ma trận kề như sau: 01001 10111 01010 01101 11010 Số cầu của đồ thị là:
Answer
  • 0
  • 2
  • 1
  • 3

Question 36

Question
Cho đồ thị vô hướng theo hình sau. Nếu bỏ cạnh (c,e) thì số thành phần liên thông của đồ thị là
Answer
  • 2
  • 3
  • 4
  • 5

Question 37

Question
Số bậc của đỉnh m bằng
Answer
  • 6
  • 5
  • 7
  • 8

Question 38

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 4 của đồ thị là:
Answer
  • 2
  • 3
  • 4
  • 5

Question 39

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 5 của đồ thị là:
Answer
  • 0
  • 1
  • 2
  • 3

Question 40

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 2-3; 2-5; 3-4; 3-5; 4-5. Ma trận kề biểu diễn đồ thị trên là:
Answer
  • 01001 10101 01010 00101 11110
  • 01001 10001 01011 00101 11110
  • 01001 10101 01011 00101 11110
  • 01001 10101 01011 00101 11111

Question 41

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 2-3; 2-5; 3-4; 3-5; 4-5. Ma trận kề biểu diễn đồ thị trên là:
Answer
  • 01001 10001 01011 00101 11110
  • 01001 10101 01010 00101 01110
  • 01001 10101 01011 00101 11111
  • 01001 10101 01011 00101 11110

Question 42

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 1-5; 2-3; 2-4; 3-4; 4-5. Ma trận kề biểu diễn đồ thị trên là:
Answer
  • 01111 10110 11010 11101 10010
  • 01110 10110 11010 11101 10010
  • 01111 10111 11010 11101 10010
  • 01001 10101 01011 00101 11110

Question 43

Question
Cho đồ thị vô hướng theo hình sau. Biểu diễn ma trận kề của đồ thị là
Answer
  • 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0
  • 1 1 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 0
  • 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0

Question 44

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng ma trận kề như sau: 01001 10101 01011 00101 11110 Khi đó biểu diễn danh sách cạnh của đồ thị trên là:
Answer
  • 1-2; 1-5; 2-3; 2-4; 3-4; 3-5; 4-5.
  • 1-2; 1-5; 2-4; 2-5; 3-4; 3-5; 4-5.
  • 1-2; 1-3; 2-3; 2-5; 3-4; 3-5; 4-5.
  • 1-2; 1-5; 2-3; 2-5; 3-4; 3-5; 4-5.

Question 45

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng ma trận kề như sau: 01100 10100 11010 00101 00010 Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều sâu (DFS) của đồ thị trên bắt đầu từ đỉnh số 3 là:
Answer
  • 3-5-2-1-4
  • 3-2-5-4-1
  • 3-2-4-5-1
  • 3-1-2-4-5

Question 46

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 1-6; 2-3; 2-6; 2-7; 3-4; 3-6; 3-7; 3-8; 4-8; 4-9; 5-6; 6-7; 7-8; 8-10. Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều sâu (DFS) của đồ thị trên bắt đầu từ đỉnh số 1 là:
Answer
  • 1-2-3-6-5-7-4-8-9-10
  • 1-2-3-4-8-7-6-5-10-9
  • 1-2-5-4-3-7-6-8-9-10
  • 1-2-5-6-7-3-4-8-9-10

Question 47

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 1-6; 2-3; 2-6; 2-7; 3-4; 3-6; 3-7; 3-8; 4-8; 4-9; 5-6; 6-7; 7-8; 8-10. Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều sâu (DFS) của đồ thị trên bắt đầu từ đỉnh số 1 là:
Answer
  • 1-2-5-6-3-7-9-8-4-10
  • 1-2-3-4-5-7-6-8-9-10
  • 1-2-3-4-8-7-6-5-10-9
  • 1-2-7-6-5-5-4-8-9-10

Question 48

Question
Cho đồ thị có hướng theo hình sau. Biểu diễn đồ thị dưới dạng danh sách cung là
Answer
  • Dau Cuoi 1 2 1 3 3 2 3 4 5 4 5 6 6 5
  • Dau Cuoi 1 2 2 3 3 2 1 4 5 4 5 6 6 5
  • Dau Cuoi 1 2 4 3 3 2 3 4 5 4 4 6 6 5

Question 49

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng ma trận kề như sau: 01100 10100 11010 00101 00010 Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng (BFS) của đồ thị trên bắt đầu từ đỉnh số 2 là:
Answer
  • 2-3-1-5-4
  • 2-1-3-4-5
  • 2-3-5-4-1
  • 2-3-4-1-5

Question 50

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5} xác định bằng ma trận kề như sau: 01111 10110 11010 11101 10010 Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng (BFS) của đồ thị trên bắt đầu từ đỉnh số 1 là:
Answer
  • 1-2-3-4-5
  • 1-4-5-2-3
  • 1-2-4-5-3
  • 1-2-5-3-4

Question 51

Question
Cho đồ thị vô hướng theo hình sau. Biểu diễn đồ thị dưới dạng danh sách cạnh là
Answer
  • Dau Cuoi 1 2 4 3 1 4 1 5 4 2 3 5 2 5
  • Dau Cuoi 1 2 2 3 1 4 1 5 4 2 4 5 2 5
  • Dau Cuoi 3 2 2 3 5 4 1 5 4 2 4 5 2 5

Question 52

Question
Cho đồ thị có hướng theo hình sau. Biểu diễn đồ thị dưới dạng ma trận kề như sau:
Answer
  • 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0
  • 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0
  • 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0
  • 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0

Question 53

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 2-4; 3-4; 3-5; 4-5; 5-6. Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng (BFS) của đồ thị trên bắt đầu từ đỉnh số 1 là:
Answer
  • 1-2-4-3-6-5
  • 1-2-3-5-4-6
  • 1-2-4-3-5-6
  • 1-3-4-2-6-5

Question 54

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 1-6; 2-3; 2-6; 2-7; 3-4; 3-6; 3-7; 3-8; 4-8; 4-9; 5-6; 6-7; 7-8; 8-10. Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng (BFS) của đồ thị trên bắt đầu từ đỉnh số 1 là:
Answer
  • 1-2-6-4-3-7-5-8-9-10
  • 1-3-2-6-5-7-4-8-9-10
  • 1-2-5-6-3-7-4-8-9-10
  • 1-2-5-6-4-3-7-8-9-10

Question 55

Question
Cho đồ thị vô hướng G = (V, E) gồm 24 đỉnh trong đó có 8 đỉnh bậc 5 và 16 đỉnh bậc 4. Khi đó số cạnh của đồ thị là
Answer
  • 52
  • 104
  • 33
  • 60

Question 56

Question
Cho đồ thị vô hướng G = (V, E) gồm 18 đỉnh trong đó có 8 đỉnh bậc 4 và 10 đỉnh bậc 6. Khi đó số cạnh của đồ thị là :
Answer
  • 46
  • 92
  • 180
  • 60

Question 57

Question
Cho đồ thị có hướng G = (V, E) trong đó V = {A, B, C, D, E). Biết deg+(A) = 4 ; deg-(A) = 3; deg+(B) = 4 ; deg-(B) = 3; deg+(C) = 2 ; deg-(C) = 2; deg+(D) = 4 ; deg-(D) = 6; deg+(E) = 5 ; deg-(E) = 3; Số cạnh của đồ thị là: A 40
Answer
  • 40
  • 20
  • 18
  • 17

Question 58

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 2 của đồ thị là:
Answer
  • 3
  • 5
  • 6
  • 4

Question 59

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 1 của đồ thị là:
Answer
  • 0
  • 1
  • 2
  • 3

Question 60

Question
bán bậc ra của đỉnh b là :
Answer
  • 0
  • 1
  • 2
  • 3

Question 61

Question
Cho đồ thị có hướng theo hình vẽ sau. Hãy chỉ ra đường đi từ đỉnh b đến đỉnh a
Answer
  • b-e-d-a
  • b-f-c-a
  • b-c-d-a
  • b-e-c-a

Question 62

Question
Cho đồ thị vô hướng theo hình sau. Nếu bỏ cạnh (d,f) thì số thành phần liên thông của đồ thị là:
Answer
  • 2
  • 3
  • 4
  • 5

Question 63

Question
Cho đồ thị vô hướng G = (V, E) gồm 25 đỉnh trong đó có 5 đỉnh bậc 6 và 20 đỉnh bậc 4. Khi đó số cạnh của đồ thị là :
Answer
  • 25
  • 55
  • 88
  • 100

Question 64

Question
Cho đồ thị có hướng G = (V, E) trong đó V = {A, B, C, D, E). Biết deg+(A) = 5 ; deg-(A) = 3; deg+(B) = 6 ; deg-(B) = 4; deg+(C) = 4 ; deg-(C) = 4; deg+(D) = 2 ; deg-(D) = 2; deg+(E) = 1 ; deg-(E) = 3; Số cạnh của đồ thị là:
Answer
  • 17
  • 35
  • 30
  • 20

Question 65

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 4 của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 66

Question
Cho đồ thị vô hướng G = (V, E) gồm 18 đỉnh trong đó có 8 đỉnh bậc 4 và 10 đỉnh bậc 6. Khi đó số cạnh của đồ thị là :
Answer
  • 180
  • 46
  • 108
  • 64

Question 67

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc chẵn bằng nhau và nhỏ nhất của đồ thị là:
Answer
  • 1
  • 2
  • 3
  • 4

Question 68

Question
Số đỉnh bậc chẵn của đồ thị (theo hình vẽ) là
Answer
  • 10
  • 9
  • 13
  • 11

Question 69

Question
Cho đồ thị vô hướng như hình vẽ. Đường đi Euler của đồ thị là:
Answer
  • 1-4-2-3-1-4-5-6-4
  • 1-2-4-1-4-3-5-6-4
  • 1-3-4-2-1-4-5-6-4
  • 1-2-3-4-1-4-5-6-4

Question 70

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 2-5; 2-6; 3-4; 3-7; 3-8; 4-8; 5-6; 6-7; 7-8. Đường đi Hamilton của đồ thị là:
Answer
  • 1-2-5-6-7-8-4-3
  • 1-2-6-5-7-8-4-3
  • 1-2-5-7-6-8-4-3
  • 1-2-5-6-7-4-8-3

Question 71

Question
Cho đồ thị vô hướng G = (V, E) xác định bằng ma trận kề như sau: 01001 10111 01010 01101 11010 Với E={a, b, c, d, e}. Đường đi Hamilton của đồ thị là:
Answer
  • bacde
  • acedb
  • abcde
  • aebcda

Question 72

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 2-4; 3-4; 4-5; 4-6; 5-6. Đường đi Euler của đồ thị là:
Answer
  • 1-2-4-1-3-4-5-6-4
  • 1-4-2-3-5-4-5-6-4
  • 1-4-2-3-1-4-5-6-4
  • 1-2-3-4-1-4-5-4-6

Question 73

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 1-5; 2-5; 3-4; 4-5; 4-6; 5-6. Chu trình không phải Euler của đồ thị đó là :
Answer
  • 1-3-4-6-5-2-1-4-5-1
  • 1-2-3-6-4-3-2-4-5-1
  • 1-4-5-2-1-3-4-6-5-1
  • 1-4-5-6-4-3-1-2-5-1

Question 74

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 1-5; 2-5; 3-4; 4-5; 4-6; 5-6. Chu trình không phải Hamilton của đồ thị đó là :
Answer
  • 1-2-3-4-5-6-1
  • 1-2-5-6-4-3-1
  • 2-5-6-4-3-1-2
  • 2-1-3-4-6-5-2

Question 75

Question
Cho đồ thị vô hướng như hình vẽ. Đồ thị có tồn tại chu trình hoặc đường đi hamilton hay không?
Answer
  • Yes !
  • No !

Question 76

Question
Cho đồ thị vô hướng như hình vẽ. Chu trình Hamilton của đồ thị là:
Answer
  • aebdca
  • abedca
  • deabcd
  • bacdeb

Question 77

Question
Số lượng cây khung của đồ thị đầy đủ 8 đỉnh là:
Answer
  • 64
  • 262144
  • 16777216
  • 80

Question 78

Question
Một đồ thị đầy đủ có 56 cạnh. Số lượng cây khung của đồ thị đó là:
Answer
  • 64
  • 262144
  • 3136
  • 80

Question 79

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-6; 2-3; 2-6; 3-4; 3-5; 3-6; 4-5; 5-6. Đường đi nào sau đây là cây khung của đồ thị:
Answer
  • 1-3-4-2-5-6
  • 1-2-6-3-5-4
  • 1-2-3-6-4-5
  • 1-2-6-4-3-5

Question 80

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-6; 2-3; 2-6; 3-4; 3-5; 3-6; 4-5; 5-6. Đường đi nào sau đây không phải là cây khung của đồ thị:
Answer
  • 1-3-4-2-5-6
  • 1-6-2-3-4-5
  • 1-2-6-5-4-3
  • 1-2-3-4-5-6

Question 81

Question
Cho đồ thị vô hướng có trọng số G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: (1-2) 33 (1-3) 17 (2-3) 18 (2-4) 20 (3-4) 16 (3-5) 4 (4-5) 9 (4-6) 8 (5-6) 14 Nếu áp dụng thuật toán Kruskal tìm cây khung nhỏ nhất thì thứ tự các cạnh được chọn lần lượt là :
Answer
  • (4-5); (4-6); (3-5); (1-2); (2-3)
  • (3-5); (4-6); (4-5); (1-3); (2-3)
  • (3-5); (4-6); (4-5); (1-3); (5-6)
  • (2-4); (4-6); (3-5); (1-3); (2-3)

Question 82

Question
Cho đồ thị vô hướng có trọng số G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: (1-2) 33 (1-3) 17 (2-3) 18 (2-4) 20 (3-4) 16 (3-5) 4 (4-5) 9 (4-6) 8 (5-6) 14 Nếu áp dụng thuật toán Prim xuất phát từ đỉnh số 1 tìm cây khung nhỏ nhất thì thứ tự các cạnh được chọn lần lượt là :
Answer
  • (1-3); (3-5); (4-5); (4-6); (2-3)
  • (1-2); (4-6); (4-5); (3-5); (2-3)
  • (1-3); (4-6); (4-5); (3-5); (5-6)
  • (1-2); (4-6); (2-4); (1-3); (2-3)

Question 83

Question
Thuật toán Kruskal
Answer
  • bắt đầu từ một đỉnh tuỳ ý của đồ thị, đầu tiên ta nối s với đỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của đỉnh s, cạnh (s,y) có độ dài nhỏ nhất. Tiếp theo trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm 3 đỉnh và 2 cạnh. Quá trình này sẽ tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n-1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm.
  • Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=(V,T) theo từng bước. Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của độ dài. Bắt đầu từ tập T=∅ , ở mỗi bước ta sẽ lần lượt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn, để tìm ra cạnh mà việc bổ sung nó vào tập T gồm n-1 cạnh

Question 84

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 2-5; 2-6; 3-4; 3-7; 3-8; 4-8; 5-6; 6-7; 7-8. Đường đi Hamilton của đồ thị là:
Answer
  • 1-2-5-6-7-4-8-3
  • 1-2-5-7-6-8-4-3
  • 1-2-6-5-7-8-4-3
  • 1-2-5-6-7-8-4-3

Question 85

Question
Cho đồ thị vô hướng G = (V, E) xác định bằng ma trận kề như sau: 01001 10111 01010 01101 11010 Với E={a, b, c, d, e}. Đường đi Hamilton của đồ thị là:
Answer
  • aebca
  • aebdc
  • abedcb
  • bacdeb

Question 86

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8} xác định bằng danh sách cạnh như sau: 1-2; 1-5; 2-5; 2-6; 3-4; 3-7; 3-8; 4-8; 5-6; 6-7; 7-8. Đường đi Hamilton của đồ thị là:
Answer
  • 1-2-5-6-7-4-8-3
  • 1-2-5-7-6-8-3-4
  • 1-2-6-5-7-8-4-3
  • 1-2-5-6-7-8-3-4

Question 87

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 2-4; 3-4; 4-5; 4-6; 5-6. Đường đi Euler của đồ thị là:
Answer
  • 1-2-4-3-1-4-6-5-4
  • 1-4-2-3-1-4-5-4-6
  • 1-2-3-4-1-4-5-4-6

Question 88

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 1-5; 2-5; 3-4; 4-5; 4-6; 5-6. Chu trình không phải Euler của đồ thị đó là :
Answer
  • 1-4-5-2-1-3-4-6-5-1
  • 1-4-5-6-4-3-1-2-5-1
  • 1-2-5-6-4-3-4-6-5-1
  • 1-3-4-6-5-2-1-4-5-1

Question 89

Question
Cho đồ thị vô hướng như hình vẽ. Đồ thị có tồn tại chu trình hoặc đường đi Euler hay không?
Answer
  • yes !
  • no !

Question 90

Question
Cho đồ thị vô hướng như hình vẽ. Đồ thị có tồn tại chu trình Euler hay không?
Answer
  • Yes
  • No

Question 91

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-3; 1-4; 1-5; 2-5; 3-4; 4-5; 4-6; 5-6. Chu trình không phải Hamilton của đồ thị đó là :
Answer
  • 3-4-6-5-2-1-3
  • 2-5-6-4-3-1-2
  • 1-3-2-4-5-6-1
  • 2-1-3-4-6-5-2

Question 92

Question
Số lượng cây khung của đồ thị đầy đủ 5 đỉnh là:
Answer
  • 15
  • 50
  • 625
  • 125

Question 93

Question
Nếu áp dụng thuật toán Prim xuất phát từ đỉnh số 1 tìm cây khung nhỏ nhất thì thứ tự các cạnh được chọn lần lượt là :
Answer
  • (1-2); (2-3); (2-5); (5-7); (4-7); (4-6)
  • (1-2); (2-5); (3-5); (5-7); (4-7); (4-6)
  • (1-2); (2-3); (2-5); (4-6); (5-7); (4-7)
  • (1-2); (2-3); (2-5); (5-6); (4-6); (4-7)

Question 94

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: 1-2; 1-6; 2-3; 2-6; 3-4; 3-5; 3-6; 4-5; 5-6. Đường đi nào sau đây là cây khung của đồ thị:
Answer
  • 1-2-6-4-3-5
  • 1-2-3-6-4-5
  • 1-2-3-6-5-4
  • 1-3-4-2-5-6

Question 95

Question
Cho đồ thị vô hướng có trọng số G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: (1-2) 33 (1-3) 17 (2-3) 18 (2-4) 20 (3-4) 16 (3-5) 4 (4-5) 9 (4-6) 8 (5-6) 14 Nếu áp dụng thuật toán Kruskal tìm cây khung nhỏ nhất thì thứ tự các cạnh được chọn lần lượt là :
Answer
  • (3-5); (4-6); (2-4); (1-3); (2-3)
  • (3-5); (4-6); (4-5); (1-3); (5-6)
  • (3-5); (4-6); (4-5); (1-2); (2-3)
  • (3-5); (4-6); (4-5); (1-3); (2-3)

Question 96

Question
Cho đồ thị vô hướng có trọng số G = (V, E) có E = {1; 2; 3; 4; 5; 6} xác định bằng danh sách cạnh như sau: (1-2) 33 (1-3) 17 (2-3) 18 (2-4) 20 (3-4) 16 (3-5) 4 (4-5) 9 (4-6) 8 (5-6) 14 Nếu áp dụng thuật toán Kruskal tìm cây khung nhỏ nhất thì thứ tự các cạnh được chọn lần lượt là :
Answer
  • (1-2); (4-6); (4-5); (3-5); (2-3)
  • (3-5); (4-6); (2-4); (1-3); (2-3)
  • (3-5); (4-6); (4-5); (1-3); (2-3)
  • (3-5); (4-6); (4-5); (5-6); (1-3)

Question 97

Question
Ta gọi cây là đồ thị vô hướng liên thông
Answer
  • có chu trình
  • không có chu trình

Question 98

Question
Thuật toán Dijstra dùng để:
Answer
  • Tìm đường đi trong đồ thị không có chu trình
  • Tìm đường đi ngắn nhất trong đồ thị trọng số không âm
  • Tìm đường đi ngắn nhất xuất phát từ một đỉnh
  • Tìm cây khung nhỏ nhất

Question 99

Question
Độ phức tạp tính toán của thuật toán Floyd là
Answer
  • O(n3)
  • O(n2)
  • O(n)
  • O(n4)

Question 100

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t sử dụng thuật toán Dijstra
Answer
  • s-b-c-d-t
  • s-b-a-c-d-t
  • s-a-c-t
  • s-b-d-t

Question 101

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 sử dụng thuật toán Dijstra
Answer
  • 1-3-2-5-7-4-6
  • 1-2-3-5-7-4-6
  • 1-2-3-5-7-6
  • 1-2-3-4-6

Question 102

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh f đến đỉnh c sử dụng thuật toán Dijstra
Answer
  • f-e-d-c
  • f-e-d-h-g-b-c
  • f-a-b-c
  • f-a-b-g-h-d-c

Question 103

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z sử dụng thuật toán Dijstra
Answer
  • a-d-g-k-r-t-z
  • a-d-g-k-r-n-q-p-t-z
  • a-d-g-k-n-p-q-s-z
  • a-c-f-g-k-r-n-q-p-t-z

Question 104

Question
Cho hình vẽ. Tìm đường đi ngắn nhất từ 1 đến các đỉnh còn lại sử dụng thuật toán Ford - Bellman
Answer
  • Đỉnh: 1 2 3 4 5 Độ dài: 0 1 4 3 -1
  • Đỉnh: 1 2 3 4 5 Độ dài: 0 1 4 3 -3
  • Đỉnh: 1 2 3 4 5 Độ dài: 0 1 3 3 -3
  • Đỉnh: 1 2 3 4 5 Độ dài: 0 1 4 3 3

Question 105

Question
Điều kiện cân bằng luồng trên mỗi đỉnh của mạng là:
Answer
  • - Tổng luồng trên các cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v.
  • - Tổng luồng trên các cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v nếu v khác đỉnh phát và v khác đỉnh thu.
  • Tổng luồng trên các cung đi vào đỉnh v nhỏ hơn tổng luồng trên các cung đi ra khỏi đỉnh v nếu v khác đỉnh phát và v khác đỉnh thu.
  • - Tổng luồng trên các cung đi vào đỉnh v lớn hơn tổng luồng trên các cung đi ra khỏi đỉnh v nếu v khác đỉnh phát và v khác đỉnh thu.

Question 106

Question
Mệnh đề nào sau đây không tương đương với 3 mệnh đề còn lại :
Answer
  • - (X,X*) là lát cắt nhỏ nhất.
  • - f là luồng cực đại trong mạng.
  • - Không tìm được đường tăng luồng f
  • - Val(f) = c(X,X*) với một lát cắt (X,X*) nào đó.

Question 107

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất giữa các cặp đỉnh sử dụng thuật toán Floyd Đưa ra ma trận d (độ dài), k (đỉnh trước)
Answer
  • A
  • B
  • C
  • D

Question 108

Question
Độ phức tạp tính toán của thuật toán Ford-Bellman là
Answer
  • O(n)
  • O(n4)
  • O(n3)
  • O(n2)

Question 109

Question
Thuật toán Floyd dùng để:
Answer
  • Tìm đường đi ngắn nhất xuất phát từ một đỉnh
  • Tìm cây khung nhỏ nhất
  • Tìm đường đi ngắn nhất trong đồ thị trọng số không âm
  • Tìm đường đi ngắn nhất giữa mọi cặp đỉnh

Question 110

Question
Độ phức tạp tính toán của thuật toán Dijkstra là
Answer
  • O(n3)
  • O(n2)
  • O(n)
  • O(n4)

Question 111

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 5 sử dụng thuật toán Dijstra
Answer
  • 1-4-6-5
  • 1-3-2-4-6-5
  • 1-4-2-3-6-5
  • 1-2-4-3-6-5

Question 112

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z sử dụng thuật toán Dijstra
Answer
  • a-c-d-e-f-g-z
  • a-b-c-e-d-f-g-z
  • a-b-c-d-e-g-f-z
  • a-b-c-d-e-g-z

Question 113

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất từ đỉnh f đến đỉnh g sử dụng thuật toán Dijstra
Answer
  • f-e-d-c-g
  • f-b-a-c-g
  • f-e-d-h-g
  • f-j-l-k-g

Question 114

Question
Cho đồ thị như hình vẽ. Đường đi ngắn nhất từ đỉnh a đến đỉnh z sử dụng thuật toán Dijstra có độ dài bằng:
Answer
  • 25
  • 18
  • 20
  • 24

Question 115

Question
Mạng là đồ thị có hướng G = (V, E) trong đó:
Answer
  • - Là luồng cực đại trên G
  • - Có duy nhất một đỉnh không có cung vào gọi là đỉnh phát; có duy nhất một đỉnh không có cung đi ra gọi là đỉnh thu và mỗi cung trên E được gán một số thực gọi là khả năng thông qua.
  • - Là một đồ thị con của G
  • - Có duy nhất một đỉnh không có cung vào gọi là đỉnh phát; có duy nhất một đỉnh không có cung đi ra gọi là đỉnh thu và mỗi cung trên E được gán một số không âm gọi là khả năng thông qua.

Question 116

Question
Cho đồ thị có hướng G = (V, E) và e là cung trên E. Khi đó :
Answer
  • - Luồng trên cung e lớn hơn khả năng thông qua của nó.
  • - Luồng trên cung e nhỏ hơn khả năng thông qua của nó
  • - Luồng trên cung e không vượt quá khả năng thông qua của nó
  • - Luồng trên cung e bằng khả năng thông qua của nó.

Question 117

Question
Cho đồ thị như hình vẽ. Tìm đường đi ngắn nhất giữa các cặp đỉnh sử dụng thuật toán Floyd Đưa ra ma trận d (độ dài), k (đỉnh trước) H232.png
Answer
  • A
  • B
  • C
  • D

Question 118

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 2 của đồ thị là:
Answer
  • 3
  • 4
  • 5
  • 6

Question 119

Question
Cho đồ thị vô hướng G = (V, E) có E = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} xác định bằng danh sách cạnh như sau: 1-2; 1-4; 1-5; 2-3; 2-5; 2-6; 3-6; 3-7; 3-8; 4-5; 5-6; 6-8; 7-9 Số đỉnh có bậc bằng 1 của đồ thị là:
Answer
  • 0
  • 1
  • 2
  • 3
Show full summary Hide full summary

Similar

The Digestive System
cian.buckley
Constitutional Law
jesusreyes88
Area, Volume & Perimeter Mind Map
rory.examtime
Essay Writing: My Essay Plan
Andrea Leyden
English Language Techniques
lewis001
AQA Business Unit 1
lauren_binney
GCSE AQA Biology 1 Quiz
Lilac Potato
Pathos in Battle
mouldybiscuit
Carbohydrates
Julia Romanów
Test your Knowledge with Quizzes
daniel.praecox
1PR101 2.test - Část 17.
Nikola Truong