Bài tập đồ thị pascal cho học sinh giỏi lớp 9

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ố ui và vi mô tả cạnh thứ i tương ứng với đỉnh ui và vi 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ố).
- Dòng thứ hai ghi hai số x và y
-K hàng tiếp theo hàng thứ i chứa 2 số ui và vi mô tả đừng thứ i tương ứng nối hai thành phố ui và vi .
Kết qủa: Ra màn hình
-Dòng đầu tổng số đường đi.
-Các dòng tiếp theo, mỗi dòng là danh sách các đỉnh trên đường đi, bắt đầu từ x kết thúc tại y.
Bài 3. “ Otomat”. Một máy đổi thẻ giải trí tự động có m cửa dùng để đổi thẻ. Có các thẻ mã số từ 1 đến n. Nếu ta bỏ thẻ có mã i vào 1 cửa nào đó thì máy thu thẻ đó và cho ra 1 thẻ có mã số trong khoãng 1 ... n. Người ta tiết lộ cho bạn biết rằng máy hành động theo thông tin ghi trong tệp văn bản có tên OTOMAT.INP như sau:
- Các giá trị n m (dòng đầu tiên)
- Một bảng kích thước n x m (n dòng m cột)
phần tử nằm trên dòng i, cột j của bảng này là phần tử máy sẽ cho ra nếu ta bỏ thẻ mã i vào cửa j.

Yêu cầu:

a- Với mỗi thẻ số hiệu x cho trước hãy tìm cách nhanh nhất để thu được thẻ có số hiệu lớn nhất.
b- Với mỗi cặp thẻ x, y cho trước hãy tìm cách nhanh nhất (có thể nếu được) để dùng thẻ x thu được thẻ y.

Lời giải cần hiển thị trên màn hình theo mẫu sau:
Bỏ thẻ x vào cửa y sẽ thu được thẻ z
Bỏ thẻ z vào cửa .....

Bài 4. Mạng máy tính:
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 Ui , Vi cho biết kênh thứ i truyền trực tiếp từ máy Ui đến máy Vi ( 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

1