bài tập chương 5

Đồ thị là gì trong Tin học?

• Tập hợp các số tự nhiên
  

• Tập hợp các đỉnh và cạnh nối giữa các đỉnh
  

• Tập hợp các chuỗi ký tự

• Mô hình quan hệ giữa cơ sở dữ liệu

Trong đồ thị có hướng, mối liên hệ giữa bán bậc ra và bán bậc vào là:

• Luôn lớn hơn nhau
  

• Bằng số lượng chu trình
  

• Tổng bán bậc ra bằng tổng bán bậc vào và bằng số cung
  

• Không liên quan

Chu trình là gì trong đồ thị?

• Đường đi từ một đỉnh đến chính nó không qua cạnh nào
  

• Đường đi đóng, bắt đầu và kết thúc tại cùng một đỉnh, không lặp đỉnh
  

• Một dạng đặc biệt của ma trận kề
  

• Một danh sách kề có trọng số

Định lý bắt tay cho đồ thị vô hướng phát biểu rằng:

• Tổng bậc các đỉnh bằng 2 lần số cạnh
  

• Tổng bậc bằng số cung

• Bậc của mỗi đỉnh bằng số cạnh trừ đi 1

• Đỉnh có bậc lẻ luôn xuất hiện 2 lần

Mục đích chính của việc dùng đồ thị trong tin học là:

• Tính toán nhanh hơn

• Mô hình hóa các mối quan hệ và tìm đường đi, tối ưu
  

• Giảm bớt bộ nhớ
  

• Lưu trữ dữ liệu đơn giản hơn

Trong đồ thị, hai đỉnh được gọi là kề nhau khi:

• Chúng có cùng bậc

• Chúng nằm trong cùng một chu trình
  

• Có một cạnh nối giữa hai đỉnh đó
  

• Chúng nằm ở hai ma trận kề khác nhau

Đồ thị liên thông là:

• Đồ thị không có đỉnh nào lặp lại
  

• Đồ thị có thể chia làm 2 phần không giao nhau

• 2 cặp đỉnh bất kì luôn có đường đi giữa chúng
  

• Đồ thị chỉ có 1 chu trình

Dạng biểu diễn đồ thị nào phù hợp nhất để tìm đỉnh kề nhanh chóng?

• Ma trận kề

• Ma trận trọng số

• Danh sách cạnh

• Danh sách kề

Khi sử dụng ma trận kề, số phần tử của ma trận là bao nhiêu nếu có n đỉnh?

• n

• n²

• 2n

• n(n-1)/2

.Cho đồ thị có 5 đỉnh và 6 cạnh, tổng bậc của đồ thị là bao nhiêu?

• 6

• 10

• 12

• 5