Graph theory: Basic definitions

Đây là bài thứ hai của tôi về lý thuyết đồ thị. Các bạn có thể xem bài trước ở

[1] https://nttuan.org/2023/08/13/graph01/

Với mỗi tập hợp $X,$ ký hiệu $[X]^2$ là tập gồm tất cả các tập con có $2$ phần tử của $X.$

Định nghĩa 1. Một đồ thị là một cặp $G=(V,E)$ các tập hợp sao cho $E\subset [V]^2.$

Như vậy, các phần tử của $E$ là các tập con có $2$ phần tử của $V.$ Các phần tử của $V$ được gọi là các đỉnh của đồ thị $G,$ các phần tử của $E$ được gọi là các cạnh của $G.$ Đồ thị có tập các đỉnh $V$ được gọi là đồ thị trên $V$ . Cách thông thường để vẽ một đồ thị là mỗi đỉnh biểu thị bởi một dấu chấm và nối hai trong các dấu chấm này bởi một đường cong nếu hai đỉnh tương ứng tạo thành một cạnh.

Trong hình trên ta có một đồ thị trên $V=\{1,2,\ldots,6\}$ với tập cạnh $E=\{\{1;2\},\{2;3\},\{6;5\},\{2;4\}\}.$ Khi vẽ một đồ thị ta không quan tâm các đỉnh hay cạnh được vẽ thế nào, điều quan trọng duy nhất ở đây là hai đỉnh nào được nối với nhau. Tập các đỉnh của một đồ thị $G$ được ký hiệu bởi $V(G),$ trong khi tập cạnh của nó được ký hiệu bởi $E(G).$ Ta thường không phân biệt đồ thị và tập cạnh hoặc tập đỉnh của nó. Chẳng hạn, ta có thể nói đỉnh $v$ thuộc $G$ (thay vì $v\in V(G)),$ một cạnh $e$ của $G,$ …

Số đỉnh của $G$ được gọi là cấp của nó, ký hiệu bởi $\mid G\mid$ . Một đồ thị $G$ được gọi là hữu hạn nếu $V(G)$ và $E(G)$ là hai tập hữu hạn, vô hạn nếu $V(G)$ hoặc $E(G)$ là một tập vô hạn. Trong bài giảng này ta chỉ xét các đồ thị hữu hạn. Khi $\mid G\mid =0$ ta gọi $G$ là đồ thị rỗng, ký hiệu $\emptyset.$ Nếu cấp của $G$ bằng $n$ thì ta cũng nói $G$ là đồ thị trên $n$ đỉnh.

Định nghĩa 2. Cho một đồ thị $G.$ Đỉnh $v$ của $G$ được gọi là đầu mút của một cạnh $e$ của $G$ nếu $v\in e.$ Nếu hai đầu mút của một cạnh $e$ là $x$ và $y$ thì ta nói $e$ nối $x$ và $y,$ hoặc $e$ kề với hai đỉnh $x$ và $y$ .

Một cạnh $\{x;y\}$ thường được viết là $xy$ hoặc $yx.$

Định nghĩa 3. Cho một đồ thị $G$ . Hai đỉnh $x$ và $y$ của $G$ được gọi là kề nhau nếu $\{x;y\}$ là một cạnh của $G.$ Trong trường hợp đó ta nói $x$ và $y$ là láng giềng của nhau.

Với mỗi đỉnh $x,$ tập gồm tất cả các đỉnh kề với $x$ được ký hiệu là $N(x)$ hoặc $N_G(x).$ Hai cạnh phân biệt $e$ và $f$ của $G$ được gọi là kề nhau nếu chúng có chung một đầu mút. Nếu tất cả các đỉnh của $G$ là đôi một kề nhau ta nói $G$ là một đồ thị đầy đủ. Một đồ thị đầy đủ trên $n$ đỉnh được ký hiệu bởi $K_n$ . $K_3$ được gọi là tam giác. Một cặp các đỉnh hay cạnh được gọi là độc lập nếu chúng không kề nhau.

Định nghĩa 4. Cho hai đồ thị $G=(V,E)$ và $G^{\prime}=(V^{\prime},E^{\prime}).$ Một ánh xạ $\varphi: V\to V^{\prime}$ được gọi đồng cấu từ $G$ đến $G^{\prime}$ nếu nó bảo toàn quan hệ kề giữa các đỉnh, nghĩa là $\varphi (x)$ và $\varphi (y)$ kề nhau mỗi khi $x$ và $y$ kề nhau. Nếu đồng cấu $\varphi$ từ $G$ đến $G^{\prime}$ là một song ánh và $\varphi^{-1}$ cũng là một đồng cấu, thì ta nói $\varphi$ là một đẳng cấu hoặc $G$ và $G^{\prime}$ là đẳng cấu.

Ta không phân biệt các đồ thị đẳng cấu, vì thế ta thường viết $G=G^{\prime}$ để chỉ $G$ và $G^{\prime}$ đẳng cấu. Trong một số trường hợp ta cũng nói $G^{\prime}$ là một bản sao của $G$ .

Continue reading →

IMO1986/3

The Pentagon Problem

Một bài viết rất công phu về IMO1986/3.

Trên mỗi đỉnh của một ngũ giác đều có viết một số nguyên, sao cho tổng của chúng là dương. Nếu ba đỉnh liên tiếp được viết lần lượt các số $x$ , $y$ , $z$ , với $y<0$ , thì phép toán sau được phép thực hiện: $x$ , $y$ , $z$ lần lượt được thay bởi $x+y$ , $-y$ , $z+y$ . Thao tác như vậy được thực hiện lặp đi lặp lại miễn là có ít nhất một trong năm số âm. Xác định xem quy trình này có nhất thiết phải kết thúc sau một số hữu hạn bước hay không.

IMO2011/6: Miquel circles and Steiner line

Sau khi giải xong bài IMO2023/6 ([1]) tôi vào topic thảo luận về bài toán đó trên AoPS ([2]) để tham khảo các lời giải khác. Tôi thấy parmenides51 bình luận rằng trong lịch sử IMO thì bài này là bài khó thứ nhì trong các bài hình học, bài khó nhất là bài IMO2011/6. Do tò mò tôi vào trang chủ của IMO ([3]) xem bài toán đó thế nào? Dưới đây là đề bài:

IMO2011/6. Cho tam giác nhọn $ABC$ với đường tròn ngoại tiếp $\Gamma$ . Giả sử $l$ là một tiếp tuyến nào đó của $\Gamma$ . Gọi $l_a$ , $l_b$ , và $l_c$ là những đường thẳng nhận được từ $l$ bằng cách lấy đối xứng qua $BC$ , $CA$ , và $AB$ , tương ứng. Chứng minh rằng đường tròn ngoại tiếp của tam giác tạo bởi ba đường thẳng $l_a$ , $l_b$ , và $l_c$ tiếp xúc với $\Gamma$ .

Trong điều kiện phòng thi thì thống kê chứng tỏ đây là bài hình học khó nhất trong lịch sử IMO! Ảnh sau tôi lấy từ [3], chỉ có $4$ thí sinh làm được bài toán này. Một bài toán rất rất khó!

Chỉ có 4 thí sinh làm được bài IMO2011/6.

Tôi thích bài IMO2023/6 bởi nó khá lạ so với các bài toán hình thường làm, bài IMO2011/6 này hấp dẫn tôi bởi sự giản dị. Không thể tin được là có kết quả này! Tôi quyết định lập một topic trên blog của tôi để làm việc với bài toán mỗi khi có thời gian (công việc chính của tôi là dạy đại số và số học cho các học sinh Chuyên toán bậc THPT), nó có thể lấy của tôi vài ngày hay nhiều tuần. Khi tôi đang gõ dòng này thì topic đang ở trạng thái ĐỢI, giải được bài toán tôi sẽ bấm nút CÔNG BỐ. Ở mỗi thời điểm, có được kết quả mới nào tôi sẽ sửa vào đây. Lời giải được viết theo hình vẽ trong bài, các trường hợp khác được bỏ qua.

Continue reading →

International Mathematical Olympiad: Shortlisted Problems

Trong bài này chúng tôi sẽ dịch đề bài từ các bộ IMO Shortlist sang tiếng Việt.

Các bạn có thể tải các tài liệu khác ở https://nttuan.org/download/ .

IMO2014SL_Vie Download

IMO2015SL_Vie Download

Continue reading →

A proof of Pick’s theorem

Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ $Oxy$ , cho tam giác $ABC.$ Khi đó diện tích của tam giác $ABC$ bằng $\displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|.$ Nói riêng, với mỗi hai điểm $M$ và $N$ ta có diện tích của tam giác $OMN$ bằng $\dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.$

Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng $\dfrac{1}{2}.$

Chứng minh. Giả sử $TAB$ là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem $T$ trùng với gốc tọa độ $O.$ Ta cần chứng minh $\mid x_1y_2-x_2y_1\mid =1,$ với $(x_1;y_1)$ và $(x_2;y_2)$ lần lượt là tọa độ của $A$ và $B.$

Gọi $K$ là điểm sao cho $OAKB$ là hình bình hành. Giả sử $M$ là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho $M$ khác các đỉnh. Khi đó $M$ thuộc tam giác $ABK$ và điểm $N$ đối xứng với $M$ qua tâm hình bình hành là điểm nguyên thuộc tam giác $OAB$ nhưng khác các đỉnh, không thể xảy ra điều này do $OAB$ là một tam giác cơ bản. Như vậy hình bình hành $OAKB$ không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử $P$ là một điểm nguyên bất kỳ. Vì $\overrightarrow{OA}$ và $\overrightarrow{OB}$ là hai vector không cùng phương nên tồn tại cặp số thực $(\alpha,\beta)$ để $\overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}.$ Gọi $P'$ là điểm xác định bởi $\overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}.$ Vì $\{\alpha\}$ và $\{\beta\}$ thuộc $[0;1)$ nên $P'$ thuộc hình bình hành $OAKB$ , nhưng $P'$ lại là một điểm nguyên, suy ra $P'$ phải là một trong bốn đỉnh của hình bình hành. Dễ thấy $P'\equiv O$ và do đó $\alpha$ và $\beta$ là hai số nguyên.

Gọi $\overrightarrow{i}$ và $\overrightarrow{j}$ lần lượt là các vector đơn vị đặt trên $Ox$ và $Oy$ . Khi đó theo lập luận trên, tồn tại các cặp số nguyên $(u,v)$ và $(u',v')$ để $\overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB}$ và $\overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}.$ Từ hai đẳng thức này ta có $\begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases}$ và $\begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases}$ suy ra $\displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D}$ và $\displaystyle v'=\frac{x_1}{D},$ trong đó $D=x_1y_2-x_2y_1\not =0$ do $O,A$ và $B$ không thẳng hàng. Vì $u,$ $v,$ $u'$ và $v'$ là các số nguyên nên $x_1,x_2,y_1$ và $y_2$ đều là bội của $D$ , do đó $D^2\mid D$ và bởi thế, $D=\pm 1.$

Định lí Pick. Cho $P$ là một đa giác đơn có các đỉnh là các điểm nguyên, $I$ là số điểm nguyên nằm trong và $B$ là số điểm nguyên nằm trên biên của $P$ . Khi đó ta có đẳng thức $\displaystyle S_P=I+\frac{1}{2}B-1.$

Chứng minh. Chia $P$ thành $N$ tam giác cơ bản. Gọi $S$ là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính $S$ theo hai cách. Vì số tam giác là $N$ nên $S=N\pi.$

Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong $P$ bằng $2\pi$ , tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của $P$ nhưng không phải đỉnh của $P$ bằng $\pi$ và tổng của tất cả các góc có đỉnh là đỉnh của $P$ bằng $(n-2)\pi$ , ở đây $n$ là số đỉnh của $P$ . Do đó $S=2\pi I+\pi B-2\pi$ , suy ra $N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2$ . Để ý thêm $S_P=\dfrac{1}{2}N$ , ta có điều phải chứng minh.