Mục lục bài họcĐang ở d03-b3
Voronoi diagrams, perpendicular bisectors and graph theory
Building a Voronoi diagram
Given sites $A$ and $B$, every point closer to $A$ than to $B$ lies on one side of the perpendicular bisector of $AB$. That single fact generates the whole diagram: each cell is the intersection of half-planes, each edge is part of a perpendicular bisector, and each vertex is equidistant from three sites.
To find the bisector of $A(x_1,y_1)$ and $B(x_2,y_2)$: take the midpoint $M\left(\dfrac{x_1+x_2}{2},\dfrac{y_1+y_2}{2}\right)$, compute $m_{AB}$, then use gradient $-\dfrac{1}{m_{AB}}$ through $M$.
The toxic waste dump problem
"Find the point in the region that is as far as possible from every site." The answer is always either a Voronoi vertex or a point on the boundary of the region. A vertex is the centre of a circle through three sites containing no site inside — the largest empty circle in that neighbourhood. Checking every vertex and comparing radii is the whole method.
Graph theory
An adjacency matrix $M$ records edges. The $(i,j)$ entry of $M^{k}$ counts walks of length exactly $k$ from $i$ to $j$ — walks, so repeated vertices and repeated edges are allowed.
A minimum spanning tree connects all $n$ vertices using $n-1$ edges of least total weight. Kruskal: sort edges by weight, add the cheapest that does not create a cycle. Prim: grow outwards from one vertex, always taking the cheapest edge leaving the tree built so far.
An Eulerian circuit exists exactly when every vertex has even degree; with exactly two odd vertices there is an Eulerian trail between them. The Chinese postman problem repeats the cheapest pairing of odd vertices.
Dựng sơ đồ Voronoi. Cho hai trạm $A$ và $B$, mọi điểm gần $A$ hơn $B$ nằm về một phía của đường trung trực đoạn $AB$. Chỉ một sự kiện ấy sinh ra toàn bộ sơ đồ: mỗi ô là giao của các nửa mặt phẳng, mỗi cạnh là một phần đường trung trực, và mỗi đỉnh cách đều ba trạm.
Tìm trung trực của $A(x_1,y_1)$ và $B(x_2,y_2)$ theo ba bước máy móc: lấy trung điểm $M\left(\dfrac{x_1+x_2}{2},\dfrac{y_1+y_2}{2}\right)$; tính hệ số góc $m_{AB}$; viết đường thẳng qua $M$ với hệ số góc $-\dfrac{1}{m_{AB}}$. Bỏ bước trung điểm là lỗi thường gặp nhất — đường thu được vẫn vuông góc với $AB$ nhưng đi sai chỗ.
Bài toán bãi rác độc hại. Đề hỏi: tìm điểm trong vùng khảo sát xa mọi trạm nhất. Đáp án luôn là một đỉnh Voronoi, hoặc một điểm trên biên vùng khảo sát. Đỉnh Voronoi là tâm một đường tròn đi qua ba trạm mà bên trong không chứa trạm nào — đường tròn rỗng lớn nhất ở lân cận đó. Phương pháp trọn vẹn chỉ gồm: liệt kê mọi đỉnh, tính bán kính từng đỉnh, chọn bán kính lớn nhất.
Lý thuyết đồ thị. Ma trận kề $M$ ghi lại các cạnh. Phần tử $(i,j)$ của $M^{k}$ đếm số đường đi (walk) độ dài đúng bằng $k$ từ $i$ tới $j$ — là walk, nên được phép lặp đỉnh và lặp cạnh. Đây là chỗ hay hiểu sai: câu trả lời không phải số đường đi không lặp.
Cây bao trùm nhỏ nhất nối cả $n$ đỉnh bằng $n-1$ cạnh với tổng trọng số bé nhất. Thuật toán Kruskal: sắp cạnh theo trọng số tăng dần, lần lượt lấy cạnh rẻ nhất nào không tạo chu trình. Thuật toán Prim: mọc dần từ một đỉnh, luôn lấy cạnh rẻ nhất đi ra khỏi cây đang có. Hai thuật toán cho cùng tổng trọng số.
Chu trình Euler tồn tại đúng khi mọi đỉnh có bậc chẵn; có đúng hai đỉnh bậc lẻ thì có đường đi Euler nối hai đỉnh đó. Bài toán người đưa thư Trung Hoa lặp lại cặp ghép rẻ nhất giữa các đỉnh bậc lẻ.
Ba trạm phát sóng đặt tại $A(1,\,2)$, $B(7,\,4)$ và $C(3,\,8)$, đơn vị là km.
(a) Tìm phương trình đường trung trực của $AB$. (b) Xác định toạ độ đỉnh Voronoi chung của ba ô. (c) Một bãi chứa chất thải cần đặt càng xa mọi trạm càng tốt, bên trong tam giác $ABC$. Nêu vị trí và khoảng cách tới trạm gần nhất.
(a) Trung điểm của $AB$ là $M\left(\dfrac{1+7}{2},\dfrac{2+4}{2}\right)=(4,\,3)$. Hệ số góc
$$m_{AB}=\frac{4-2}{7-1}=\frac{2}{6}=\frac{1}{3}\;\Longrightarrow\;m_{\perp}=-3$$$$y-3=-3(x-4)\;\Longrightarrow\;y=-3x+15$$(b) Đỉnh Voronoi cách đều cả ba trạm nên nó nằm trên cả ba đường trung trực; chỉ cần giao hai đường là đủ. Trung trực của $AC$: trung điểm $(2,\,5)$, $m_{AC}=\dfrac{8-2}{3-1}=3$, nên $m_{\perp}=-\dfrac13$ và
$$y-5=-\tfrac13(x-2)\;\Longrightarrow\;y=-\tfrac13 x+\tfrac{17}{3}$$Giải hệ với $y=-3x+15$:
$$-3x+15=-\tfrac13 x+\tfrac{17}{3}\;\Longrightarrow\;-\tfrac83 x=-\tfrac{28}{3}\;\Longrightarrow\;x=3{,}5,\quad y=-3(3{,}5)+15=4{,}5$$Vậy đỉnh là $V(3{,}5\,;\,4{,}5)$.
Bước kiểm bắt buộc: tính cả ba khoảng cách chứ không phải hai.
$$VA=\sqrt{2{,}5^{2}+2{,}5^{2}}=3{,}54,\quad VB=\sqrt{3{,}5^{2}+0{,}5^{2}}=3{,}54,\quad VC=\sqrt{0{,}5^{2}+3{,}5^{2}}=3{,}54$$Ba số bằng nhau xác nhận $V$ đúng là đỉnh chung. Nếu chỉ giao hai đường rồi bỏ qua bước này thì một lỗi số học nhỏ ở phần (a) sẽ đi thẳng tới đáp số cuối.
(c) Bên trong tam giác chỉ có một đỉnh Voronoi, nên bãi rác đặt tại $V(3{,}5\,;\,4{,}5)$, cách mỗi trạm $3{,}54$ km. Đường tròn tâm $V$ bán kính $3{,}54$ đi qua cả ba trạm và rỗng bên trong, nên không điểm nào trong tam giác xa hơn thế.
Chú ý phân biệt với trọng tâm $\left(\dfrac{11}{3},\dfrac{14}{3}\right)\approx(3{,}67\,;\,4{,}67)$ — đây là điểm hay bị chọn nhầm. Khoảng cách từ trọng tâm tới $A$ là $3{,}80$ nhưng tới $B$ chỉ $3{,}40$, tức trạm gần nhất còn gần hơn so với đặt tại $V$. Bài toán này tối đa hoá khoảng cách tới trạm gần nhất, không tối đa hoá tổng khoảng cách.
Năm thôn $A$, $B$, $C$, $D$, $E$ được nối bởi các con đường có chi phí nâng cấp (đơn vị: trăm triệu VND): $AB=6$, $AC=9$, $AD=12$, $BC=5$, $BD=8$, $BE=14$, $CD=7$, $CE=11$, $DE=4$.
(a) Dùng thuật toán Kruskal tìm cây bao trùm nhỏ nhất và tổng chi phí. (b) Giải thích vì sao lời giải phải có đúng $4$ con đường.
(a) Sắp cạnh theo trọng số tăng dần: $DE=4$, $BC=5$, $AB=6$, $CD=7$, $BD=8$, $AC=9$, $CE=11$, $AD=12$, $BE=14$.
| Xét | DE (4) | BC (5) | AB (6) | CD (7) | BD (8) |
|---|---|---|---|---|---|
| Quyết định | nhận | nhận | nhận | nhận | bỏ |
| Lý do | — | — | — | nối được $E$ | tạo chu trình |
Sau khi nhận $DE$, $BC$, $AB$ ta có hai mảnh $\{D,E\}$ và $\{A,B,C\}$. Cạnh tiếp theo là $CD=7$: nó nối hai mảnh khác nhau nên nhận được, và lúc này cả năm thôn đã thông nhau.
$$\text{Tổng}=4+5+6+7=22$$tức $2{,}2$ tỉ VND. Cạnh $BD=8$ bị loại vì $B$ và $D$ khi ấy đã cùng một mảnh, thêm nó vào là tạo chu trình $B\!-\!C\!-\!D\!-\!B$ mà không nối thêm thôn nào.
(b) Cây bao trùm trên $n$ đỉnh luôn có đúng $n-1$ cạnh. Với $n=5$ thì là $4$. Lý do: mỗi cạnh nhận vào giảm số mảnh rời rạc đi đúng một, bắt đầu từ $5$ mảnh và kết thúc ở $1$ mảnh, nên phải nhận đúng $4$ cạnh. Cạnh thứ năm bất kỳ chắc chắn nối hai đỉnh đã thông nhau, tức tạo chu trình.
Sai lầm hay gặp là “nhận cạnh rẻ nhất tại mỗi đỉnh” — làm vậy thường thu được $5$ cạnh và một chu trình, tổng lớn hơn $22$. Điều kiện không tạo chu trình mới là phần làm nên thuật toán, chứ không phải việc sắp xếp theo giá.
Đọc xong rồi — làm thử ngay
Bài tập của chương Geometry and Trigonometry gồm 14 câu trắc nghiệm và 6 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.