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.

Square roots are linearly independent

Trong bài này tôi giới thiệu nhiều lời giải cho bài toán quan trọng sau:

Bài toán. Cho $a_1,\ldots,a_k$ là các số nguyên không đồng thời bằng $0$ . Chứng minh rằng nếu $n_1,$ $n_2,\ldots,$ $n_k$ là các số nguyên dương đôi một khác nhau và không có ước chính phương lớn hơn $1$ thì $\sum a_i\sqrt{n_i}\not=0$ .

Lời giải 1. Ta sẽ chứng minh bằng quy nạp theo $N$ , số ước nguyên tố của $\prod n_i$ , khẳng định: Tồn tại tổng $S'=\sum b_i\sqrt{m_i}$ sao cho $SS'$ là số nguyên khác $0$ , ở đây $m_i$ là các số nguyên dương đôi một khác nhau và không có ước chính phương khác $1$ , tập các ước nguyên tố của $\prod m_i$ là tập con của tập các ước nguyên tố của $\prod n_i$ , $b_i$ là các số nguyên, và $S=\sum a_i\sqrt{n_i}$ . Từ đó suy ra $S\not=0$ .

Với $N=0$ ta chọn $S'=1$ .

Với $N=1$ ta chọn $S'=\sqrt{p_1}$ khi $S=a_1\sqrt{p_1}$ , chọn $S'=-a_1\sqrt{p_1}+a_2$ nếu $S=a_1\sqrt{p_1}+a_2$ .

Continue reading →

Combinations

Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Một $k-$ tổ hợp (một tổ hợp chập $k$ ) của $A$ là một tập con $k$ phần tử của $A$ .

Ví dụ 1. Các $3-$ tổ hợp của $A=\{a,b,c,d\}$ là

$\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}.$

Định lí 1. Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Khi đó số $k-$ tổ hợp của $A$ bằng $C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.$

Chứng minh. Sự khác nhau giữa một $k-$ tổ hợp và một $k-$ hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Một $k-$ hoán vị của $A$ có thể hình thành sau hai bước: Đầu tiên, chọn một $k-$ tổ hợp của $A$ ; sau đó xếp $k$ phần tử của tập này thành một hàng. Bởi vì có $C_n^k$ cách để làm bước một, $k!$ cách để làm bước hai nên theo nguyên lý nhân ta có $A_n^k=C_n^k\times k!.$ $\Box$

Ví dụ 2. Có bao nhiêu xâu nhị phân độ dài $7$ mà có đúng ba số $0$ ?

Lời giải. Một xâu nhị phân có tính chất như trong đề bài sẽ được hình thành khi ta chọn $3$ vị trí trong $7$ vị trí để viết số $0.$ Do đó số xâu thỏa mãn là $C_7^3.$ $\Box$

Ví dụ 3. Có bao nhiêu cách có thể thành lập một hội đồng gồm $5$ thành viên từ một nhóm có $11$ người chứa $4$ giáo viên và $7$ học sinh nếu

(1) Không có thêm điều kiện gì?

(2) Hội đồng chứa đúng $2$ giáo viên?

(3) Hội đồng chứa ít nhất $3$ giáo viên?

(4) Giáo viên $A$ và học sinh $B$ không thể cùng nằm trong hội đồng?

Hướng dẫn giải. (1) $C_{11}^5$ . (2) $C_4^2\times C_7^3$ . (3) $3$ hoặc $4$ giáo viên có thể nằm trong hội đồng, đáp số $91$ .

(4) Dùng quy tắc trừ, đáp số $378$ . $\Box$

Ví dụ 4. Cho $n$ là một số nguyên dương và $A$ là một tập có $2n$ phần tử. Có bao nhiêu cách phân hoạch $A$ thành các tập có $2$ phần tử?

Lời giải 1. Đầu tiên, cố định một phần tử $x$ của $A$ và chọn một phần tử trong $2n-1$ phần tử còn lại của $A$ để ghép lại với $x$ tạo thành một khối của phân hoạch; sau đó cố định một phần tử $y$ trong các phần tử còn lại của $A$ và chọn một phần tử trong $2n-3$ phần tử còn lại của $A$ để ghép lại với $y$ tạo thành một khối của phân hoạch; ta cứ làm như vậy cho đến khi còn $2$ phần tử thì đây chính là khối còn lại của phân hoạch. Theo quy tắc nhân, số phân hoạch thoả mãn là $(2n-1)\times (2n-3)\times\cdots\times 1$ . $\Box$

Lời giải 2. Chọn một tập con có $2$ phần tử của $A$ làm khối thứ nhất, sau đó chọn một tập con có $2$ phần tử của tập hợp gồm $2n-2$ phần tử còn lại làm khối thứ hai, ta cứ làm như vậy cho đến khi còn hai phần tử thì đây chính là khối thứ $n$ . Vì thứ tự các khối là không quan trọng nên số các phân hoạch thoả mãn là $\dfrac{C_{2n}^2\times C_{2n-2}^2\times\cdots\times C_2^2}{n!}$ . $\Box$

Lời giải 3. Ta xếp $2n$ phần tử của $A$ thành một hàng vào $2n$ vị trí như hình dưới đây

$\{(1),(2)\},\{(3),(4)\},\cdots,\{(2n-1),(2n)\}$ có $(2n)!$ cách để làm điều này. Vì trong mỗi tập con có $2$ phần tử thứ tự các phần tử là không quan trọng và thứ tự các khối của phân hoạch là không quan trọng nên số phân hoạch thoả mãn là