Bài tập lý thuyết đồ thị

Chương 1. ĐẠI CƯƠNG VỀ ĐỒ THỊ

1. Loại đồ thị nào được dùng để mô hình hệ thống các đường cao tốc giữa các thành phố lớn trong các trường hợp sau:
a. Nếu giữa hai thành phố có đường cao tốc thì giữa chúng sẽ được nối bởi một cạnh.b. Mỗi cạnh biểu thị cho mỗi đường cao tốc giữa các thành phố.
c. Mỗi cạnh biểu thị cho mỗi đường cao tốc giữa các thành phố và ngoài ra có thêm khuyên để biểu diễn cho đường cao tốc bao quanh một thành phố nào đó.

2. Hãy xây dựng đồ thị lấn tổ cho cả 6 loài chim trong đó chim hét cạnh tranh với chim cổ đỏ và chim giẻ cùi xanh, chim cổ đỏ cũng cạnh tranh với chim nhại, chim nhại cạnh tranh với chim giẻ cùi và chim bổ hạt cạnh tranh với chim gõ kiến.

3. Nếu cần phải dùng đồ biểu diễn cho kết quả thắng – thua của các trận đấu bóng chuyền giữa các đội theo thể thức vòng tròn hai lượt (mỗi đội gặp nhau 2 lần) thì cần phải dùng đồ thị gì? Đồ thị này sẽ có bao nhiêu cạnh nếu số đội là n đội?

4. Hãy xây dựng đồ thị ưu tiên trước sau cho chương trình sau:
a. x := 0;
b. x := x+1;
c. y := 2;
d. z := y;
e. x := x + 2;
f. y := y + z;
g. z := 4;