CHƯƠNG 5: Đồ Thị Và Biểu Diễn Đồ Thị

Đồ thị được sử dụng để giải quyết vấn đề nào sau đây?

• 
  Tăng tốc độ xử lý của CPU
  

• 
  Giảm dung lượng tệp hình ảnh

• Xác định tốc độ mạng Internet

• Tìm đường đi ngắn nhất giữa 2 thành phố

Trong đồ thị vô hướng, tổng bậc của tất cả các đỉnh bằng:

• 2 lần số cạnh

• Số cạnh nhân với số đỉnh

• Tổng trọng số của các cạnh

• Một nửa tổng số cạnh

Trong đồ thị có hướng, tổng bán bậc ra của các đỉnh bằng:

• Số đỉnh chia 2

• Tổng số bậc vào

• Tổng số cung

• Số cạnh trừ đi 1

Trong ma trận kề của đồ thị vô hướng, phần tử a[i][j] có ý nghĩa gì?

• Bằng số lượng đỉnh trong đồ thị

• Bằng trọng số giữa i và j

• Luôn bằng 0

• Bằng 1 nếu có cạnh nối giữa đỉnh i và j

Trong biểu diễn bằng danh sách kề, thông tin nào được lưu cho mỗi đỉnh?

• Tổng số cạnh

• Danh sách các đỉnh kề với nó

• Tổng số đỉnh

• Tên của đồ thị

Ma trận trọng số là:

• Ma trận kề có chứa giá trị trọng số của các cạnh

• Ma trận chứa số lượng các đỉnh

• Danh sách các chu trình

• Danh sách các đường đi

Đồ thị có hướng khác với đồ thị vô hướng ở điểm nào?

• Có ít đỉnh hơn

• Luôn có trọng số

• Không có chu trình

• Các cung có thứ tự định hướng

Đồ thị đơn là gì ?

• Không có trọng số

• Không có cạnh khép kín và không có cạnh lặp

• Chỉ có một đỉnh

• Chỉ có một cạnh

Một chu trình là gì ?

• Đường đi dài nhất

• Đường đi chỉ qua một đỉnh

• Đường đi bắt đầu và kết thúc tại cùng một đỉnh

• Đường đi không có đỉnh lặp

Tính liên thông của đồ thị vô hướng là gì ?

• Số lượng chu trình lớn nhất

• Từ mọi đỉnh đều có thể đi đến các đỉnh khác

• Tổng số cạnh tối đa

• Số lượng đỉnh lẻ