Mạng với nhiều điểm phát và nhiều điểm thu | Bài giảng môn Phương pháp tính và matlab CTTT | Đại học Bách khoa hà nội

Mạng với nhiều điểm phát và nhiều điểm thu. Tài liệu trắc nghiệm môn Phương pháp tính và matlab CTTT giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Bài tập Luồng trên mạng
Trần Vĩnh Đức
HUST
Ngày 21 tháng 11 năm 2019
1 / 19
Tài liệu Tham khảo
Nguyễn Đức Nghĩa, Slides Toán rời rạc, Fall 2005.
Je Erickson, Algorithms, 2015.
2 / 19
Tìm luồng cực đại lát cắt cực tiểu
3 / 19
Tìm luồng cực đại lát cắt cực tiểu 2
4 / 19
Tìm luồng cực đại lát cắt cực tiểu 3
5 / 19
Mạng với nhiều điểm phát nhiều điểm thu
Mạng với p điểm phát s
1
, . . . , s
p
q điểm thu t
1
, . . . , t
q
.
Tìm luồng cực đại từ các điểm phát đến các điểm thu.
6 / 19
Tìm ghép cặp cực đại trên đồ thị hai phần
7 / 19
Tìm tập đỉnh phủ tối tiểu của đồ thị hai phần
Tập đỉnh phủ một tập đỉnh C V sao cho mọi cạnh của đồ thị
đều ít nhất một đầu mút trong C.
8 / 19
Phủ bàn cờ
Cho bàn cờ n × n đã bị xóa đi một số ô.
Tìm thuật toán để xác định xem liệu thể phủ kín bàn cờ
y bằng các quân dominos biết rằng mỗi quân domino chỉ
phủ đúng hai ô trên bàn cờ.
9 / 19
Tìm số đường đi không chung cạnh lớn nhất
Cho đồ thị hướng G = (V, E) hai đỉnh s, t. Hãy tìm số lượng
lớn nhất các đường đi không chung cạnh từ s đến t.
10 / 19
Bài toán vượt ngục
Cho một lưới m × n m đỉnh phân biệt
(x
1
, y
1
), (x
2
, y
2
), · · · , (x
m
, y
m
).
y xác định xem liệu hay không m đường đi không chung đỉnh
nối m điểm y với các biên.
11 / 19
Xếp lịch thi học kỳ
Mỗi học kỳ n lớp học, r phòng học t ca thi.
Bạn danh sách hai danh sách
E[i] : số sinh viên đăng học lớp i
S[j] : số chỗ ngồi của phòng j
Lớp i thể thi phòng j nếu E[i] < S[j].
Trong mỗi ca thi, mỗi phòng chỉ một lớp thi.
y tả thuật toán ghép phòng ca thi cho từng lớp.
12 / 19
Đặt camera
Người ta muốn đặt camera quan sát lên một một số ô màu
trắng trên lưới n × n. Hãy tả thuật toán xác định liệu thể
đặt camera sao cho mỗi hàng đúng một camera mỗi cột
đúng một camera.
13 / 19
Biến đổi ma trận
Cho một ma trận thực không âm A[1..m][1..n]. Ta muốn làm
tròn thành ma trận nguyên bằng cách thay mỗi phần tử x
bởi x hoặc x
không thay đổi tổng mỗi hàng hay tổng mỗi cột.
y thiết kế thuật toán để làm tròn ma trận A hoặc thông
báo không thể.
1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.5
1 4 2
4 4 2
8 1 1
14 / 19
Sắp xếp ma trận
Cho ma trận n × n với các phần tử chỉ 0 hoặc 1.
Ma trận được gọi sắp xếp được nếu thể hoán đổi một số
lần hàng hoặc cột của ma trận để được ma trận các phần
tử trên đường chéo đều bằng 1.
y tìm thuật toán sắp xếp ma trận hoặc thông báo ma trận
không thể sắp xếp được.
0 1 1
1 1 0
1 0 1
1 0 1
1 1 0
0 1 1
15 / 19
Đánh golf
Sân golf một đa giác khép kín bao bởi m đoạn thẳng ngang
n đoạn thẳng dọc.
Trên sân đánh dấu n điểm n lỗ.
y tìm thuật toán ghép cặp mỗi điểm với một lỗ sao cho
người chơi thể đánh bóng theo đường thẳng từ mỗi điểm
tới lỗ tương ứng không ra ngoài biên.
16 / 19
mối
m chàng trai, n gái k mối. Mỗi mối p một
danh sách L
p
gồm các chàng trai gái khách hàng của
ta.
mối p thể se duyên cho bất cứ cặp trai-gái nào khách
hàng của ta, nhưng không đủ sức tổ chức quá d
p
đám cưới.
y xây dựng thuật toán căn cứ vào danh sách L
p
, d
p
đưa ra
cách tổ chức nhiều nhất các đám cưới giữa m chàng trai n
gái với sự giúp đỡ của các mối.
17 / 19
Phủ đường
Cho đồ thị hướng phi chu trình G = (V, E). Một phủ
đường một tập P các đường đi không chung đỉnh phủ hết
các đỉnh của G. Đường đi thể bắt đầu bất cứ đâu, kể cả
đường độ dài 0.
y tìm phủ đường gồm ít đường đi nhất.
18 / 19
Nhát cắt cực tiểu duy nhất
y tìm thuật toán quyết định xem liệu nhát cắt cực tiểu của
mạng cho trước duy nhất không.
19 / 19
| 1/19

Preview text:

Bài tập Luồng trên mạng Trần Vĩnh Đức HUST Ngày 21 tháng 11 năm 2019 1 / 19 Tài liệu Tham khảo
▶ Nguyễn Đức Nghĩa, Slides Toán rời rạc, Fall 2005.
▶ Jeff Erickson, Algorithms, 2015. 2 / 19
Tìm luồng cực đại và lát cắt cực tiểu 3 / 19
Tìm luồng cực đại và lát cắt cực tiểu 2 4 / 19
Tìm luồng cực đại và lát cắt cực tiểu 3 5 / 19
Mạng với nhiều điểm phát và nhiều điểm thu
▶ Mạng với p điểm phát s1, . . . , sp q điểm thu t1, . . . , tq.
▶ Tìm luồng cực đại từ các điểm phát đến các điểm thu. 6 / 19
Tìm ghép cặp cực đại trên đồ thị hai phần 7 / 19
Tìm tập đỉnh phủ tối tiểu của đồ thị hai phần
Tập đỉnh phủ là một tập đỉnh C ⊆ V sao cho mọi cạnh của đồ thị
đều có ít nhất một đầu mút trong C. 8 / 19 Phủ bàn cờ
▶ Cho bàn cờ n × n đã bị xóa đi một số ô.
▶ Tìm thuật toán để xác định xem liệu có thể phủ kín bàn cờ
này bằng các quân dominos biết rằng mỗi quân domino chỉ
phủ đúng hai ô trên bàn cờ. 9 / 19
Tìm số đường đi không chung cạnh lớn nhất
Cho đồ thị có hướng G = (V, E) và hai đỉnh s, t. Hãy tìm số lượng
lớn nhất các đường đi không chung cạnh từ s đến t. 10 / 19 Bài toán vượt ngục
Cho một lưới m × n m đỉnh phân biệt
(x1, y1), (x2, y2), · · · , (xm, ym).
Hãy xác định xem liệu có hay không m đường đi không chung đỉnh
nối m điểm này với các biên. 11 / 19 Xếp lịch thi học kỳ
▶ Mỗi học kỳ có n lớp học, có r phòng học và t ca thi.
▶ Bạn có danh sách hai danh sách
E[i] : số sinh viên đăng ký học lớp i
S[j] : số chỗ ngồi của phòng j
▶ Lớp i có thể thi ở phòng j nếu
E[i] < S[j].
▶ Trong mỗi ca thi, mỗi phòng chỉ có một lớp thi.
▶ Hãy mô tả thuật toán ghép phòng và ca thi cho từng lớp. 12 / 19 Đặt camera
Người ta muốn đặt camera quan sát lên một một số ô có màu
trắng trên lưới n × n. Hãy mô tả thuật toán xác định liệu có thể
đặt camera sao cho mỗi hàng có đúng một camera và mỗi cột có đúng một camera. 13 / 19 Biến đổi ma trận
▶ Cho một ma trận thực không âm A[1..m][1..n]. Ta muốn làm
tròn nó thành ma trận nguyên bằng cách thay mỗi phần tử x
bởi ⌈x⌉ hoặc ⌊x ⌋
▶ mà không thay đổi tổng mỗi hàng hay tổng mỗi cột.
▶ Hãy thiết kế thuật toán để làm tròn ma trận A hoặc thông báo là không thể.     1.2 3.4 2.4 1 4 2
 3.9 4.0 2.1  −→  4 4 2  7.9 1.6 0.5 8 1 1 14 / 19 Sắp xếp ma trận
▶ Cho ma trận n × n với các phần tử chỉ là 0 hoặc 1.
▶ Ma trận được gọi là sắp xếp được nếu có thể hoán đổi một số
lần hàng hoặc cột của ma trận để được ma trận mà các phần
tử trên đường chéo đều bằng 1.
▶ Hãy tìm thuật toán sắp xếp ma trận hoặc thông báo ma trận
không thể sắp xếp được.     0 1 1 1 0 1
 1 1 0  −→  1 1 0  1 0 1 0 1 1 15 / 19 Đánh golf
▶ Sân golf là một đa giác khép kín bao bởi m đoạn thẳng ngang
n đoạn thẳng dọc.
▶ Trên sân có đánh dấu n điểm và có n lỗ.
▶ Hãy tìm thuật toán ghép cặp mỗi điểm với một lỗ sao cho
người chơi có thể đánh bóng theo đường thẳng từ mỗi điểm
tới lỗ tương ứng mà không ra ngoài biên. 16 / 19 Bà mối
▶ Có m chàng trai, n cô gái và k bà mối. Mỗi bà mối p có một
danh sách Lp gồm các chàng trai và cô gái là khách hàng của bà ta.
▶ Bà mối p có thể se duyên cho bất cứ cặp trai-gái nào là khách
hàng của bà ta, nhưng không đủ sức tổ chức quá dp đám cưới.
▶ Hãy xây dựng thuật toán căn cứ vào danh sách Lp, dp đưa ra
cách tổ chức nhiều nhất các đám cưới giữa m chàng trai và n
cô gái với sự giúp đỡ của các bà mối. 17 / 19 Phủ đường
▶ Cho đồ thị có hướng phi chu trình G = (V, E). Một phủ
đường là một tập P các đường đi không chung đỉnh phủ hết
các đỉnh của G. Đường đi có thể bắt đầu ở bất cứ đâu, kể cả đường độ dài 0.
▶ Hãy tìm phủ đường gồm ít đường đi nhất. 18 / 19
Nhát cắt cực tiểu duy nhất
Hãy tìm thuật toán quyết định xem liệu nhát cắt cực tiểu của
mạng cho trước có duy nhất không. 19 / 19