Bài Tập đồ thò Trang 1
Bài tập Thực hành:
Bài 1. Viết một chương trình tìm các thành phần liên thông của đồ thò
+ Yêu cầu:
- Xác đònh tính liên thông
- Các thành phần liên thông
- Minh họa bằng đồ họa
dữ liệu vào: là từ file text có tên DOTHI.INP
-hàng đầu ghi số N (số đỉnh đồ thò), và số K (số cạnh của đồ thò).
-K hàng tiếp theo hàng thứ i chứa 2 số u
i
và v
i
mô tả cạnh thứ i tương ứng với đỉnh u
i
và v
i
của đồ
thò.
Kết qủa : Ra màn hình như sau :
-Dòng đầu : Số thành phần liên thông.
-Các dòng tiếp theo:
+Thành phần thứ 1: x1 x2 .....
+Thành phần thứ 2: x1 x2 .....
+........................
Bài 2.
Có N thành phố đánh số thứ tự tứ 1 đến N, giữa các thành phố có thể có hoặc không có đường đi.
Đường đi có thể là một chiều hoặc hai chiều. Tìm tất cả đường đi từ thành phố x đến thành phố y cho
trước.
dữ liệu vào: là từ file text có tên THPHO.INP
-hàng đầu ghi số N (số thành phố), và số K (số đường đi trực tiếp giữa 2 thành phố).

Bài Tập đồ thò Trang 2
Một mạng máy tính gồm n máy đánh số từ 1 đến n, và m kênh truyền tin một chiều giữa một số cặp
máy được đánh số từ 1 đến m. Mạng máy tính là thông suốt (nghóa là từ một máy bất kỳ có thể truyền tin
đến tất cả các máy còn lại hoặc là theo kênh nối trực tiếp hoặc thông qua các máy trung gian). Một máy
trong mạng được gọi là máy chẳn (máy lẻ) nếu số kênh truyền tin trực tiếp từ đó đến các máy khác trong
mạng là số chẳn (số lẻ).
Giả sử S và T là hai máy lẻ trong mạng. Bằng cách đảo ngược hướng truyền tin một số kênh trong
mạng, hãy biến đổi mạng đã cho thành mạng (không nhất thiết phải thông suốt) mà trong đó 2 máy S và T
trở thành máy chẳn mà không thay đổi tính chẳn lẻ của các máy khác.
Dữ liệu vào được cho trong file kiểu Text có tên NET.INP theo qui cách:
- Dòng đầu tiên chứa 2 số n, m được ghi cách nhau bởi dấu cách ( n < 1 0 1 )
- Dòng thứ hai chứa 2 số nguyên dương S T được ghi cách nhau bởi dấu cách là chỉ số của 2 máy lẻ
trong mạng.
- Dòng thứ i trong số m dòng tiếp theo ghi 2 số nguyên U
i
, V
i
cho biết kênh thứ i truyền trực tiếp từ
máy U
i
đến máy V
i
( i = 1, 2, ... , m )
Kết quả ghi ra màn hình và ra file kiểu Text với tên NET.OUT theo qui cách:
- Dòng đầu ghi số lượng kênh cần thay đổi hướng truyền q
- Mỗi dòng trong số q dòng tiếp theo ghi chỉ số của kênh cần đảo ngược hướng truyền tin.
Ví dụ:
NET.INP NET.OUT
6 9 3
1 6

0 0 0 0 0 Màn của vùng lớn nhất: Đen.
0 0 0 0 0
Bài 6. “ Mạng đường sắt”
Do nhu cầu cấp bách trong xây dựng kinh tế của một quốc gia, người ta cần sửa chữa gấp rút lại
một mạng lưới đường sắt ( hai chiều) đã có sẳn lưu thông giữa N thành phố ( đánh số thứ tự 1,2,...,N). Biết
rằng chi phí cho sữa chữa chỉ phụ thuộc vào chiều dài của đoạn đường củ. Hãy tìm một phương án sữa
chữa ít tốn kém nhất mà vẫn đảm bảo là chỉ sử dụng đường mới sữa mà vẫn lưu thông giữa các thành phố
như trứơc khi sửa.
dữ liệu vào: là từ file text có tên DUONGSAT.INP
-hàng đầu ghi số N (số thành phố), và số K (số đường nối trực tiếp giữa hai thành phố).
-K hàng tiếp theo hàng thứ i chứa 3 số u
i
, v
i
và d
i
mô tả có đường nối thứ i giữa 2 thành phố u
i
và
v
i
với chiều dài là d
i
.
Kết qủa: Ra màn hình.
-Dòng tiên là tổng số chiều dài cần sửa chữa.
-Các dòng tiếp theo là chỉ số của các đường cần sửa.
Bài 7.
Cho một bảng N dòng, M cột các số nguyên không âm. Từ một ô (i,j) ta có thể đi sang ô chung cạnh
nếu giá trò của ô này không lớn hơn giá trò của ô (i,j). Một đường đi từ ô (i,j) tới ô (k,l) theo cách đi trên gọi là

Dữ liệu được cho bởi file TEXT có tên INPUT.DAT trong đó dòng thứ nhất ghi số N, các dòng tiếp
theo mỗi dòng ghi hai số x và y mà (x,y) là tọa độ của đỉnh trái dưới của hình vuông, 0 ≤ x,y ≤ 95.
1. Tìm đường đi ngắn nhất từ (0,0) đến (100,100) theo cách thứ nhất. Kết quả thông báo ra file TEXT
có tên KQ2.DAT các đỉnh lần lượt trên hành trình trong một dòng, dòng tiếp theo thông báo độ dài.
2. Tìm được đi ngắn nhất từ (0,0) đế (100,100) theo cách thứ hai. Kết quả thông báo tiếp ra file TEXT
có tên KQ1.DAT các đỉnh lần lượt trên hành trình trong một dòng, dòng tiếp theo thông báo độ dài.
Bài 9. “Lập lòch bay”
Có N thành phố (N ≤ 50). Hàng ngày từ thành phố i đến thành phố j có các chuyến bay vào các giờ
nào đó, các giờ này tính thống nhất theo một đồng hồ chung cho cả N thành phố. Tại thành phố i, nếu ở lại
đó một giờ thì tốn một lượng tiền nào đó. Một người muốn bay từ thành phố u đến thành phố v và khởi
hành vào giờ T. Thời gian chuyển máy bay xem như không đáng kể.
Dữ liệu được cho bở file TEXT có tên MB.DAT trong đó dòng thứ nhất ghi các số N, u, v, T. Với 1 ≤
i,j ≤ N, dòng thứ (i-1)N+j+1 ghi như sau:
- Nếu i≠j thì số đầu tiên là thời gian bay từ i đến j, số thứ hai là giá vé bay từ i đến j, tiếp theo là
các giờ có chuyến bay từ i đến j, nếu dòng này rỗng có nghóa là không có đường bay từ i đến j.
- Nếu i=j thì ghi chi phí cho 1 giờ tại i.
Tất cả các số đều nguyên dương, số chỉ giờ tính từ 1 đến 24
Hãy tìm cho người đó một hành trình từ u đến v theo các yêu cầu sau đây:
1. Thời gian bay nhanh nhất. Kết quả thông báo ra file TEXT với tên KQ.DAT, các dòng đầu ghi
hành trình, mỗi dòng một chặng theo quy cách như sau (quy ước ngày 1 là ngày khởi hành):
...........................
4 → 3 đi 5 giờ ngày 6 đến 7 giờ ngày 8.
3 → 10 đi 11 giờ ngày 8 đến 15 giờ ngày 8.
...........................
dòng tiếp theo thông báo giờ bay từ u, giờ đến v, thời gian bay (chú ý rằng hành trình có thể kéo dài nhiều
ngày).
2. Chi phí ít nhất. Kết quả thông báo tiếp ra file KQ2.DAT, các dòng cho hành trình tương tự như trên,
dòng tiếp theo ghi chi phí, giờ bay từ u, giờ đến v, thời gian bay.
Bài 10. “Vẽ Đường”
Một lưới giao thông đường hai chiều giữa n đòa điểm được cho bởi ma trận A[i,j] trong đó A[i,j] =1

1 0 1 0 2 1 3 1
0 1 0 1
Bài 12. Lâu đài.
Hình bên dưới là lưới ô vuông kích thước MxN (M=4, N=7) biểu diễn một lâu đài.
Ta gọi một phòng là gồm 1 hoặc nhiều ô vuông chung cạnh được bao chung quanh bởi các bức tường.Hãy
viết chương trình tính :
1. Lâu đài có bao nhiêu phòng ?
2. Phòng lớn nhất là bao nhiêu ô vuông ?
3. Bức tường nào cần loại bỏ để có một phòng càng nhiều ô vuông càng tốt.
1 2 3 4 5 6 7
1
2
3
4
->
Dữ liệu vào: File text tên LAUDAI.INP có cấu trúc như sau:
Biên soan: Võ Viết Trí
đxxđxđxxđxđ
(Mũi tên trong hình chỉ bức tường bò loại
bỏ)