Copiar y Editar

Lí thuyết đồ thị

Descripción

Các nghiên cứu máy tính Test sobre Lí thuyết đồ thị , creado por Thần Hoàng el 23/09/2016.
Thần Hoàng
Test por Thần Hoàng, actualizado hace más de 1 año
Thần Hoàng
Creado por Thần Hoàng hace más de 7 años
2318
2
0

Resumen del Recurso

Pregunta 1

Pregunta
Số đỉnh bán bậc ra của d tức deg+(d) bằng bao nhiêu ?
Image:
e9782979-6427-457c-9b6d-9e5e3925bc79 (image/png)
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 2

Pregunta
Hai đỉnh u và v gọi là kề nhau nếu?
Respuesta
  • 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

Pregunta 3

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

Pregunta 4

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

Pregunta 5

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

Pregunta 6

Pregunta
Đồ thị liên thông là đồ thị?
Respuesta
  • 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

Pregunta 7

Pregunta
Đồ thị đầy đủ là đồ thị vô hướng mà :
Respuesta
  • 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

Pregunta 8

Pregunta
Cho đồ thị có hướng theo hình vẽ sau. Hãy chỉ ra đường đi từ đỉnh a đến đỉnh f:
Image:
1c744f4b-d2b5-4c18-9920-9643d0c0dfe6 (image/png)
Respuesta
  • a - d - e - f
  • a-d-b-f
  • a-b-e-f
  • a-d-c-f

Pregunta 9

Pregunta
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à:
Respuesta
  • 4
  • 3
  • 2
  • 1

Pregunta 10

Pregunta
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à
Image:
7972a1de-13da-438a-99ef-83f68a9f4e0b (image/png)
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 11

Pregunta
Đồ thị theo hình sau là đồ thị:
Image:
9edbfc8c-4d22-4be4-b10b-5e8554fe1ce8 (image/png)
Respuesta
  • Phẳng
  • Đầy Đủ
  • Không Phải Phẳng

Pregunta 12

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

Pregunta 13

Pregunta
Bậc của đỉnh v trong đồ thị vô hướng G là?
Respuesta
  • 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)

Pregunta 14

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

Pregunta 15

Pregunta
Số đỉnh bán bậc vào của c là?
Image:
2d4f4fea-6247-477c-b0ec-c2e29d010c0b (image/png)
Respuesta
  • 1
  • 2
  • 3

Pregunta 16

Pregunta
Cho đồ thị theo hình sau. Cho biết đường đi từ đỉnh a sang đỉnh f là ?
Image:
bac960f2-e88e-41bd-9f9c-b53d8d92c05a (image/png)
Respuesta
  • a-d-b-f
  • a-b-d-f
  • a-e-b-d-f
  • a-d-c-b-f

Pregunta 17

Pregunta
Chu trình trong đồ thị vô hướng là một dãy các :
Respuesta
  • 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

Pregunta 18

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 19

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 20

Pregunta
Cho đồ thị vô hướng theo hình sau. Cho biết số đỉnh treo của đồ thị bằng ?
Image:
c3eb7994-967d-4ed6-af8f-5189f88140ef (image/png)
Respuesta
  • 6
  • 8
  • 7
  • 9

Pregunta 21

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

Pregunta 22

Pregunta
Số đỉnh bán bậc ra của d tức deg+(d) bằng bao nhiêu ?
Image:
c81851a0-583a-4054-84b3-eb79d8cea766 (image/png)
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 23

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 24

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 25

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 26

Pregunta
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à:
Respuesta
  • 0
  • 1
  • 2
  • 3

Pregunta 27

Pregunta
Số đỉnh bậc lẻ của đồ thị (theo hình vẽ) là
Image:
10887fba-c21c-47f2-b722-4659793542ad (image/png)
Respuesta
  • 8
  • 9
  • 10
  • 11

Pregunta 28

Pregunta
Số đỉnh bậc lẻ của đồ thị (theo hình vẽ) là
Image:
33b31137-f45d-4fc0-aee7-22f82babf528 (image/png)
Respuesta
  • 0
  • 1
  • 2
  • 3

Pregunta 29

Pregunta
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à:
Respuesta
  • 18
  • 38
  • 25
  • 40

Pregunta 30

Pregunta
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à:
Respuesta
  • 3
  • 4
  • 5
  • 6

Pregunta 31

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 32

Pregunta
Số đỉnh bán bậc vào của c là?
Image:
8a6c8527-7cbe-4d5d-9b59-62b29ab8198c (image/png)
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 33

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 34

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 35

Pregunta
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à:
Respuesta
  • 0
  • 2
  • 1
  • 3

Pregunta 36

Pregunta
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à
Image:
530086af-5b53-4212-89ec-7b323549c2b0 (image/png)
Respuesta
  • 2
  • 3
  • 4
  • 5

Pregunta 37

Pregunta
Số bậc của đỉnh m bằng
Image:
4b94444f-889f-49ae-aa82-f7714d945fe5 (image/png)
Respuesta
  • 6
  • 5
  • 7
  • 8

Pregunta 38

Pregunta
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à:
Respuesta
  • 2
  • 3
  • 4
  • 5

Pregunta 39

Pregunta
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à:
Respuesta
  • 0
  • 1
  • 2
  • 3

Pregunta 40

Pregunta
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à:
Respuesta
  • 01001 10101 01010 00101 11110
  • 01001 10001 01011 00101 11110
  • 01001 10101 01011 00101 11110
  • 01001 10101 01011 00101 11111

Pregunta 41

Pregunta
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à:
Respuesta
  • 01001 10001 01011 00101 11110
  • 01001 10101 01010 00101 01110
  • 01001 10101 01011 00101 11111
  • 01001 10101 01011 00101 11110

Pregunta 42

Pregunta
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à:
Respuesta
  • 01111 10110 11010 11101 10010
  • 01110 10110 11010 11101 10010
  • 01111 10111 11010 11101 10010
  • 01001 10101 01011 00101 11110

Pregunta 43

Pregunta
Cho đồ thị vô hướng theo hình sau. Biểu diễn ma trận kề của đồ thị là
Image:
00238281-aef5-49bd-b036-09603b0d0857 (image/png)
Respuesta
  • 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

Pregunta 44

Pregunta
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à:
Respuesta
  • 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.

Pregunta 45

Pregunta
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à:
Respuesta
  • 3-5-2-1-4
  • 3-2-5-4-1
  • 3-2-4-5-1
  • 3-1-2-4-5

Pregunta 46

Pregunta
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à:
Respuesta
  • 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

Pregunta 47

Pregunta
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à:
Respuesta
  • 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

Pregunta 48

Pregunta
Cho đồ thị có hướng theo hình sau. Biểu diễn đồ thị dưới dạng danh sách cung là
Image:
ac5c743e-5cde-4490-b569-f526c4f29d00 (image/png)
Respuesta
  • 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

Pregunta 49

Pregunta
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à:
Respuesta
  • 2-3-1-5-4
  • 2-1-3-4-5
  • 2-3-5-4-1
  • 2-3-4-1-5

Pregunta 50

Pregunta
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à:
Respuesta
  • 1-2-3-4-5
  • 1-4-5-2-3
  • 1-2-4-5-3
  • 1-2-5-3-4

Pregunta 51

Pregunta
Cho đồ thị vô hướng theo hình sau. Biểu diễn đồ thị dưới dạng danh sách cạnh là
Image:
9d701581-8cfb-4203-8994-df7e6b113112 (image/png)
Respuesta
  • 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

Pregunta 52

Pregunta
Cho đồ thị có hướng theo hình sau. Biểu diễn đồ thị dưới dạng ma trận kề như sau:
Image:
19a047d1-4103-4768-b195-af92065b6af7 (image/png)
Respuesta
  • 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

Pregunta 53

Pregunta
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à:
Respuesta
  • 1-2-4-3-6-5
  • 1-2-3-5-4-6
  • 1-2-4-3-5-6
  • 1-3-4-2-6-5

Pregunta 54

Pregunta
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à:
Respuesta
  • 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

Pregunta 55

Pregunta
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à
Respuesta
  • 52
  • 104
  • 33
  • 60

Pregunta 56

Pregunta
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à :
Respuesta
  • 46
  • 92
  • 180
  • 60

Pregunta 57

Pregunta
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
Respuesta
  • 40
  • 20
  • 18
  • 17

Pregunta 58

Pregunta
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à:
Respuesta
  • 3
  • 5
  • 6
  • 4

Pregunta 59

Pregunta
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à:
Respuesta
  • 0
  • 1
  • 2
  • 3

Pregunta 60

Pregunta
bán bậc ra của đỉnh b là :
Image:
55e7d76b-f7b8-4bde-b826-ca00e58df744 (image/png)
Respuesta
  • 0
  • 1
  • 2
  • 3

Pregunta 61

Pregunta
Cho đồ thị có hướng theo hình vẽ sau. Hãy chỉ ra đường đi từ đỉnh b đến đỉnh a
Image:
f1926001-3517-410f-9175-1733e058c7d2 (image/png)
Respuesta
  • b-e-d-a
  • b-f-c-a
  • b-c-d-a
  • b-e-c-a

Pregunta 62

Pregunta
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à:
Image:
97adc799-042e-4ab7-aad2-04e669ec1640 (image/png)
Respuesta
  • 2
  • 3
  • 4
  • 5

Pregunta 63

Pregunta
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à :
Respuesta
  • 25
  • 55
  • 88
  • 100

Pregunta 64

Pregunta
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à:
Respuesta
  • 17
  • 35
  • 30
  • 20

Pregunta 65

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 66

Pregunta
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à :
Respuesta
  • 180
  • 46
  • 108
  • 64

Pregunta 67

Pregunta
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à:
Respuesta
  • 1
  • 2
  • 3
  • 4

Pregunta 68

Pregunta
Số đỉnh bậc chẵn của đồ thị (theo hình vẽ) là
Image:
de44def1-36f0-466b-b03b-ab25d307627b (image/png)
Respuesta
  • 10
  • 9
  • 13
  • 11

Pregunta 69

Pregunta
Cho đồ thị vô hướng như hình vẽ. Đường đi Euler của đồ thị là:
Image:
31feb2f5-d756-4b73-ab41-4ed3472eea4f (image/png)
Respuesta
  • 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

Pregunta 70

Pregunta
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à:
Respuesta
  • 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

Pregunta 71

Pregunta
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à:
Respuesta
  • bacde
  • acedb
  • abcde
  • aebcda

Pregunta 72

Pregunta
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à:
Respuesta
  • 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

Pregunta 73

Pregunta
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à :
Respuesta
  • 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

Pregunta 74

Pregunta
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à :
Respuesta
  • 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

Pregunta 75

Pregunta
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?
Image:
0d4b83bb-98bd-49c0-8a4f-cae4c51d255f (image/png)
Respuesta
  • Yes !
  • No !

Pregunta 76

Pregunta
Cho đồ thị vô hướng như hình vẽ. Chu trình Hamilton của đồ thị là:
Image:
810a0377-3f1f-456f-b56c-3cfdda028cf9 (image/png)
Respuesta
  • aebdca
  • abedca
  • deabcd
  • bacdeb

Pregunta 77

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

Pregunta 78

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

Pregunta 79

Pregunta
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ị:
Respuesta
  • 1-3-4-2-5-6
  • 1-2-6-3-5-4
  • 1-2-3-6-4-5
  • 1-2-6-4-3-5

Pregunta 80

Pregunta
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ị:
Respuesta
  • 1-3-4-2-5-6
  • 1-6-2-3-4-5
  • 1-2-6-5-4-3
  • 1-2-3-4-5-6

Pregunta 81

Pregunta
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à :
Respuesta
  • (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)

Pregunta 82

Pregunta
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à :
Respuesta
  • (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)

Pregunta 83

Pregunta
Thuật toán Kruskal
Respuesta
  • 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

Pregunta 84

Pregunta
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à:
Respuesta
  • 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

Pregunta 85

Pregunta
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à:
Respuesta
  • aebca
  • aebdc
  • abedcb
  • bacdeb

Pregunta 86

Pregunta
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à:
Respuesta
  • 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

Pregunta 87

Pregunta
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à:
Respuesta
  • 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

Pregunta 88

Pregunta
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à :
Respuesta
  • 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

Pregunta 89

Pregunta
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?
Image:
7621e8e0-4ea9-411e-9e4e-4648421abf9c (image/png)
Respuesta
  • yes !
  • no !

Pregunta 90

Pregunta
Cho đồ thị vô hướng như hình vẽ. Đồ thị có tồn tại chu trình Euler hay không?
Image:
492a6ea2-44a3-471a-bbc1-d5accc9a6ccb (image/png)
Respuesta
  • Yes
  • No

Pregunta 91

Pregunta
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à :
Respuesta
  • 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

Pregunta 92

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

Pregunta 93

Pregunta
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à :
Image:
7d28d2de-cee5-43e2-ab36-3224895d615f (image/png)
Respuesta
  • (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)

Pregunta 94

Pregunta
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ị:
Respuesta
  • 1-2-6-4-3-5
  • 1-2-3-6-4-5
  • 1-2-3-6-5-4
  • 1-3-4-2-5-6

Pregunta 95

Pregunta
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à :
Respuesta
  • (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)

Pregunta 96

Pregunta
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à :
Respuesta
  • (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)

Pregunta 97

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

Pregunta 98

Pregunta
Thuật toán Dijstra dùng để:
Respuesta
  • 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

Pregunta 99

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

Pregunta 100

Pregunta
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
Image:
09591f5d-60ad-48c8-8032-a1059fe57b5d (image/png)
Respuesta
  • s-b-c-d-t
  • s-b-a-c-d-t
  • s-a-c-t
  • s-b-d-t

Pregunta 101

Pregunta
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
Image:
5c8b9b2e-eb85-4b91-bbb5-e7fec44f7ef8 (image/png)
Respuesta
  • 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

Pregunta 102

Pregunta
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
Image:
f67a15fb-db01-4ec9-8945-c3fa8bbabb42 (image/png)
Respuesta
  • f-e-d-c
  • f-e-d-h-g-b-c
  • f-a-b-c
  • f-a-b-g-h-d-c

Pregunta 103

Pregunta
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
Image:
2503cd5d-f403-45bf-9161-78cf3b9499af (image/png)
Respuesta
  • 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

Pregunta 104

Pregunta
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
Image:
b943e7a8-8ab4-47f1-9e6f-fbd1e61b9c5c (image/png)
Respuesta
  • Đỉ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

Pregunta 105

Pregunta
Điều kiện cân bằng luồng trên mỗi đỉnh của mạng là:
Respuesta
  • - 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.

Pregunta 106

Pregunta
Mệnh đề nào sau đây không tương đương với 3 mệnh đề còn lại :
Respuesta
  • - (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 đó.

Pregunta 107

Pregunta
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)
Image:
c6d59dfa-66a8-42db-a0a0-db1916a7d7de (image/png)
Respuesta
  • A
  • B
  • C
  • D

Pregunta 108

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

Pregunta 109

Pregunta
Thuật toán Floyd dùng để:
Respuesta
  • 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

Pregunta 110

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

Pregunta 111

Pregunta
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
Image:
b3c02842-ce23-49d6-a661-00e85e90b158 (image/png)
Respuesta
  • 1-4-6-5
  • 1-3-2-4-6-5
  • 1-4-2-3-6-5
  • 1-2-4-3-6-5

Pregunta 112

Pregunta
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
Image:
9798f792-dc6b-4cb0-91f7-1ffad824bbfb (image/png)
Respuesta
  • 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

Pregunta 113

Pregunta
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
Image:
66689c0b-96c4-4713-923a-6b8cac6c15f5 (image/png)
Respuesta
  • f-e-d-c-g
  • f-b-a-c-g
  • f-e-d-h-g
  • f-j-l-k-g

Pregunta 114

Pregunta
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:
Image:
4106ca76-5040-4158-bdd7-34162c57ec84 (image/png)
Respuesta
  • 25
  • 18
  • 20
  • 24

Pregunta 115

Pregunta
Mạng là đồ thị có hướng G = (V, E) trong đó:
Respuesta
  • - 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.

Pregunta 116

Pregunta
Cho đồ thị có hướng G = (V, E) và e là cung trên E. Khi đó :
Respuesta
  • - 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ó.

Pregunta 117

Pregunta
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
Image:
f2b1576a-2a83-4d7e-a786-ca2ba74cc3c7 (image/png)
Respuesta
  • A
  • B
  • C
  • D

Pregunta 118

Pregunta
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à:
Respuesta
  • 3
  • 4
  • 5
  • 6

Pregunta 119

Pregunta
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à:
Respuesta
  • 0
  • 1
  • 2
  • 3
Mostrar resumen completo Ocultar resumen completo

¿Quieres crear tus propios Tests gratis con GoConqr? Más información.

Similar

Modelo de Examen de Inglés - Selectividad
juanmadj
Primera Guerra Mundial
juanmadj
8 Frases de Ánimo que te Motivarán en la Vuelta a Clase
maya velasquez
Arte Prerromano
maya velasquez
LITERATURA MEDIEVAL
sanzjavier14
Sociales
David Andrino
Marketing Digital
Diego Santos
Métodos anticonceptivos
Sara Donado
Cómo Usar Fichas para Mejorar el Aprendizaje de tus Alumnos
Diego Santos
Sistema de procesamiento en Bases de datos
jhonatanandresce
¿Conozco las herramientas de diseño AutoCAD?
Sonia Rojas Barbosa
Explorar la Librería