Conditional probability

Bạn đọc nên xem lại hai bài sau

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

—

Nhiều phát biểu về cơ hội có dạng: Nếu $B$ xảy ra thì xác suất để $A$ xảy ra là $p$ . Trong bài này ta sẽ quan tâm đến các phát biểu như vậy.

Ví dụ 1. Giả sử một lớp học có $n$ học sinh, trong đó có $n_1$ bạn giỏi toán và $n_2$ bạn nữ. Chọn ngẫu nhiên một học sinh trong lớp. Gọi $A$ là biến cố học sinh được chọn giỏi toán, và $B$ là biến cố học sinh được chọn là nữ. Khi đó theo định nghĩa ngây thơ của xác suất, $\mathbb{P}(A)=n_1/n$ và $\mathbb{P}(B)=n_2/n$ . Bây giờ ta tập trung vào nhóm các bạn học sinh nữ trong lớp. Xác suất để em được chọn trong nhóm này mà giỏi toán bằng $m/n_2$ , ở đây $m$ là số học sinh nữ trong lớp giỏi toán. Nếu kí hiệu $\mathbb{P}(A\mid B)$ là xác suất này, thì

$\displaystyle \mathbb{P}(A\mid B)=\frac{m}{n_2}=\frac{m/n}{n_2/n}=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}.$ $\Box$

Ta có định nghĩa hình thức sau

Định nghĩa 1. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và hai biến cố $\displaystyle A$ , $\displaystyle B$ với $\displaystyle \mathbb{P}(B)>0$ . Xác suất của $\displaystyle A$ biết $\displaystyle B$ đã xảy ra, cũng được gọi là xác suất của $\displaystyle A$ với điều kiện $\displaystyle B$ , kí hiệu $\displaystyle \mathbb{P}(A\mid B)$ , được định nghĩa bởi

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}.$

Chú ý rằng $\displaystyle\mathbb{P}(A\mid B)$ là xác suất của $\displaystyle A$ khi biết $\displaystyle B$ xảy ra, nó không phải là xác suất của biến cố $\displaystyle A\mid B$ , không có biến cố $\displaystyle A\mid B$ . Nếu $\displaystyle \mathbb{P}(A)>0$ thì $\displaystyle \mathbb{P}(A\mid A)=1$ .

Ví dụ 2. Xét phép thử ngẫu nhiên: Tung lần lượt hai con xúc xắc cân đối. Biết rằng con xúc xắc đầu hiện $\displaystyle 3$ chấm, xác suất để tổng số chấm lớn hơn $\displaystyle 6$ là bao nhiêu?

Lời giải. Không gian mẫu của phép thử là $\displaystyle \Omega=\{1,2,3,4,5,6\}^2$ . Như quy ước đối với không gian xác suất rời rạc, $\displaystyle \mathcal{F}$ là họ tất cả các tập con của $\displaystyle \Omega$ . Cuối cùng, $\displaystyle \mathbb{P}(A)=\mid A\mid / 36$ với mỗi $\displaystyle A \subset \Omega$ .

Bây giờ gọi $\displaystyle B$ là biến cố con đầu ra $\displaystyle 3$ chấm, và $\displaystyle A$ là biến cố tổng các chấm lớn hơn $\displaystyle 6$ . Khi đó

$\displaystyle B=\{(3, b): 1 \leq b \leq 6\}, \quad A=\{(a, b): a+b>6\},$ $\displaystyle \quad A \cap B=\{(3,4),(3,5),(3,6)\}.$ Suy ra

$\displaystyle \mathbb{P}(A \mid B)=\frac{\mathbb{P}(A \cap B)}{\mathbb{P}(B)}=\frac{|A \cap B|}{|B|}=\frac{3}{6}=\frac{1}{2}.$ $\Box$

Ví dụ 3. Rút ngẫu nhiên hai quân bài từ một bộ bài cho trước, mỗi lần rút một quân và không trả lại. Gọi $\displaystyle A$ là sự kiện quân bài thứ nhất mang chất cơ và $\displaystyle B$ là sự kiện quân bài thứ hai có màu đỏ. Tính $\displaystyle \mathbb{P}(A\mid B)$ và $\displaystyle \mathbb{P}(B\mid A)$ .

Lời giải. Không gian xác suất được xây dựng theo cách tự nhiên. Với không gian xác suất này, $\displaystyle \mathbb{P}(A)=1/4$ , $\displaystyle \mathbb{P}(B)=1/2$ , và $\displaystyle\mathbb{P}(A\cap B)=\frac{25}{204}.$ Từ đây ta thu được

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}=\frac{25}{102}\approx 0,25$

và

$\displaystyle\mathbb{P}(B\mid A)=\frac{\mathbb{P}(B\cap A)}{\mathbb{P}(A)}=\frac{25}{51}\approx 0,49.$ $\Box$

Từ định nghĩa của xác suất có điều kiện ta có

Định lý 1 (Công thức Bayes). Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và hai biến cố $\displaystyle A$ , $\displaystyle B$ với $\displaystyle \mathbb{P}(A)\mathbb{P}(B)>0$ . Khi đó

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(B\mid A)\mathbb{P}(A)}{\mathbb{P}(B)}.$

Định lý 2 (Công thức xác suất toàn phần). Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Giả sử $\displaystyle A_1$ , $\displaystyle A_2$ , $\displaystyle \ldots$ , $\displaystyle A_n$ là một phân hoạch của $\displaystyle\Omega$ sao cho $\displaystyle \mathbb{P}(A_i)>0$ với mọi $\displaystyle i$ . Khi đó với mỗi biến cố $\displaystyle B$ ,

$\displaystyle\mathbb{P}(B)=\sum_{i=1}^n\mathbb{P}(B\mid A_i)\mathbb{P}(A_i).$

Công thức xác suất toàn phần cho một liên hệ giữa xác suất có điều kiện và xác suất không điều kiện. Để tính một xác suất, ta có thể dùng công thức này để chia bài toán thành các bài toán đơn giản hơn, và nó thường được sử dụng cùng với công thức Bayes.

Ví dụ 4. Có hai chiếc hộp, $\displaystyle \alpha$ và $\displaystyle \beta$ , đựng các viên bi xanh và đỏ. Hộp $\displaystyle \alpha$ chứa hai viên bi đỏ và ba viên bi xanh, hộp $\displaystyle \beta$ chứa ba viên bi đỏ và bốn viên bi xanh. Một viên bi được lấy ngẫu nhiên từ hộp $\displaystyle \alpha$ và bỏ vào hộp $\displaystyle \beta$ . Sau đó, lấy ngẫu nhiên một viên bi trong hộp $\displaystyle \beta$ và kiểm tra màu của nó. Xác suất để nó có màu xanh là bao nhiêu?

Lời giải. Không gian xác suất được mô tả theo cách tự nhiên. Gọi $\displaystyle A$ là biến cố viên bi lấy sau mang màu xanh, và $\displaystyle B$ là biến cố viên bi lấy trước mang màu xanh. Tính toán đơn giản ta được $\displaystyle \mathbb{P}(B)=3/5>0$ và $\displaystyle\mathbb{P}(\overline{B})=2/5>0$ , do đó theo công thức xác suất toàn phần, ta có

$\displaystyle\mathbb{P}(A)=\mathbb{P}(A\mid B)\mathbb{P}(B)+\mathbb{P}(A\mid \overline{B})\mathbb{P}(\overline{B}).$

Mà ta lại có $\displaystyle \mathbb{P}(A\mid B)=5/8$ và $\displaystyle \mathbb{P}(A\mid \overline{B})=1/2$ , suy ra $\displaystyle \mathbb{P}(A)=23/40= 0,575.$ $\Box$

Ví dụ 5. Có hai nhà máy sản xuất cốc, nhà máy I và nhà máy II. Biết rằng $\displaystyle 20\%$ số cốc từ nhà máy I và $\displaystyle 5\%$ từ nhà máy II bị lỗi. Mỗi tuần, I sản xuất số lượng cốc gấp đôi II. Xác suất để một chiếc cốc được chọn ngẫu nhiên trong một tuần sản xuất đạt yêu cầu là bao nhiêu? Nếu chiếc cốc được chọn bị lỗi thì khả năng nó được sản xuất bởi I là bao nhiêu?

Lời giải. Gọi $\displaystyle A$ là biến cố mà chiếc cốc được chọn là đạt yêu cầu, và gọi $\displaystyle B$ là biến cố nó được sản xuất tại $\displaystyle I$ . Khi đó

$\displaystyle\mathbb{P}(A)=\mathbb{P}(A\mid B)\mathbb{P}(B)+\mathbb{P}(A\mid \overline{B})\mathbb{P}(\overline{B})$

$=\frac{4}{5}\cdot\frac{2}{3}+\frac{19}{20}\cdot\frac{1}{3}=\frac{51}{60}\approx 0,85.$

Nếu chiếc cốc được chọn bị lỗi thì khả năng nó được sản xuất bởi I, theo công thức Bayes, là

$\displaystyle \mathbb{P}(B\mid \overline{A})=\frac{\mathbb{P}(\overline{A}\mid B)\mathbb{P}(B)}{\mathbb{P}(\overline{A})}=\frac{\frac{1}{5}\cdot \frac{2}{3}}{1-\frac{51}{60}}=\frac{8}{9}\approx 0,889.$ $\Box$

Ví dụ 6. Có một đồng xu công bằng và một đồng xu không công bằng với xác suất hiện mặt sấp khi tung là $\displaystyle 3/4$ . Chọn ngẫu nhiên một trong hai đồng xu và tung nó ba lần. Nó hiện mặt sấp cả ba lần. Tính xác suất để đồng xu được chọn là đồng xu công bằng.

Lời giải. Gọi $\displaystyle A$ là biến cố đồng xu được chọn đều hiện mặt sấp khi tung ba lần, và $\displaystyle B$ là biến cố đồng xu được chọn là đồng xu công bằng. Theo công thức Bayes và công thức xác suất toàn phần, ta có

$\displaystyle \mathbb{P}(B \mid A)=\frac{\mathbb{P}(A \mid B) \mathbb{P}(B)}{\mathbb{P}(A)}=\frac{\mathbb{P}(A \mid B) \mathbb{P}(B)}{\mathbb{P}(A \mid B) \mathbb{P}(B)+\mathbb{P}\left(A \mid \overline{B}\right) \mathbb{P}\left(\overline{B}\right)}$

$=\frac{(1 / 2)^3 \cdot 1 / 2}{(1 / 2)^3 \cdot 1 / 2+(3 / 4)^3 \cdot 1 / 2}\approx 0.23$ . $\Box$

Ví dụ 7. Xét một trò chơi trong đó một người chơi phải chọn một trong ba cánh cửa. Một trong ba cánh cửa giấu một giải thưởng có giá trị là một chiếc ô tô mới, trong khi mỗi một trong hai cánh cửa còn lại giấu một chiếc bút chì. Sau khi người chơi lựa chọn, người dẫn chương trình (biết xe ở đâu) sẽ mở một trong hai cánh cửa mà người chơi không chọn và cho biết phía sau cánh cửa đó có một cái bút chì. Vào thời điểm này, người chơi phải lựa chọn giữa hai cánh cửa còn lại. Người chơi nên giữ nguyên lựa chọn hay thay đổi?

Lời giải. Bởi vì còn hai cách cửa, một chứa ô tô và cánh còn lại chứa bút chì, nên nhiều người cho rằng chọn lại hay giữ nguyên thì khả năng là như nhau. Đây là câu trả lời sai.

Gọi $\displaystyle A_i$ là biến cố giải thưởng ô tô nằm sau cánh cửa $\displaystyle i$ . Giả sử người chơi đã chọn cánh cửa $\displaystyle 1$ . Gọi $\displaystyle B$ là sự kiện người dẫn chương trình mở ra cánh cửa số $\displaystyle 2$ có giải thưởng là cái bút chì. Theo định nghĩa của xác suất có điều kiện và công thức xác suất toàn phần,

$\displaystyle \mathbb{P}\left(A_1 \mid B\right)=\frac{\mathbb{P}\left(A_1 \cap B\right)}{\mathbb{P}(B)}=\frac{\mathbb{P}\left(B \mid A_1\right)\mathbb{P}\left(A_1\right)}{\mathbb{P}\left(B \mid A_1\right) \mathbb{P}\left(A_1\right)+\mathbb{P}\left(B \mid A_2\right) \mathbb{P}\left(A_2\right)+\mathbb{P}\left(B \mid A_3\right) \mathbb{P}\left(A_3\right)}.$

Bây giờ lập luận đơn giản cho ta $\displaystyle\mathbb{P}(A_i)=1/3$ với mọi $\displaystyle i$ , $\displaystyle \mathbb{P}\left(B \mid A_1\right)=1 / 2$ , $\displaystyle P\left(B \mid A_2\right)=0$ , và $\displaystyle \mathbb{P}\left(B \mid A_3\right)=1$ . Suy ra $\displaystyle \mathbb{P}\left(A_1 \mid B\right)=1/3\approx 0,333.$ Như vậy người chơi nên thay đổi lựa chọn của mình. $\Box$

Từ đầu cho đến thời điểm hiện tại ta đã thấy nhiều ví dụ mà $\displaystyle \mathbb{P}(A\mid B)\not=\mathbb{P}(B)$ , nghĩa là khi ta bổ sung thông tin $\displaystyle B$ thì khả năng xảy ra $\displaystyle A$ thay đổi. Nếu khi bổ sung $\displaystyle B$ mà khả năng xảy ra $\displaystyle A$ không thay đổi ta nói $\displaystyle A$ và $\displaystyle B$ là độc lập.

Định nghĩa 2. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Một họ các biến cố $\displaystyle \{A_i\}_{i\in I}$ được gọi là độc lập nếu với mỗi tập con hữu hạn $\displaystyle J$ của $\displaystyle I$ ,

$\displaystyle\mathbb{P}\left(\bigcap_{j\in J}A_j\right)=\prod_{j\in J}\mathbb{P}(A_j).$

Từ định nghĩa này ta thấy nếu $\displaystyle A$ và $\displaystyle B$ là hai sự kiện độc lập với $\displaystyle \mathbb{P}(A)\mathbb{P}(B)>0$ thì $\displaystyle \mathbb{P}(A\mid B)=\mathbb{P}(A)$ và $\displaystyle \mathbb{P}(B\mid A)=\mathbb{P}(B)$ .

IMO Shortlist 2022: Number theory

N1. Một số nguyên dương được gọi là số Na Uy nếu nó có ba ước dương phân biệt có tổng bằng $2022$ . Xác định số Na Uy nhỏ nhất.

N2. Tìm tất cả các số nguyên dương $n>2$ sao cho

$\displaystyle n! \mid \prod_{ p<q\le n,\quad p,q\in\mathbb{P}} (p+q).$

N3. Cho $a > 1$ là một số nguyên dương và $d > 1$ là một số nguyên dương nguyên tố cùng nhau với $a$ . Đặt $x_1=1$ và với $k\geq 1$ , $x_{k+1} = x_k + d$ nếu không chia hết $x_k$ , $=x_k/a$ nếu $a$ chia hết $x_k$ . Tìm, theo $a$ và $d$ , số nguyên dương $n$ lớn nhất mà tồn tại chỉ số $k$ sao cho $x_k$ chia hết cho $a^n$ .

N4. Tìm tất cả các bộ ba số nguyên dương $(a,b,p)$ sao cho $p$ là số nguyên tố và $a^p=b!+p.$

(IMO2022/5)

N5. Đối với mỗi $i\in [9]$ và $T\in\mathbb{N}^*$ , ký hiệu $d_i(T)$ là số lần chữ số $i$ xuất hiện khi tất cả các bội của $1829$ trong $[T]$ được viết ra theo cơ số $10$ . Chứng minh rằng có vô số $T\in\mathbb{N}^*$ sao cho có đúng hai giá trị phân biệt trong các số $d_1(T)$ , $d_2(T)$ , $\dots$ , $d_9(T)$ .

N6. Cho $Q$ là một tập hợp không nhất thiết hữu hạn các số nguyên tố. Đối với một số nguyên dương $n$ , xét phân tích ra thừa số nguyên tố của nó: gọi $p(n)$ là tổng của tất cả các số mũ và $q(n)$ là tổng của các số mũ tương ứng với các số nguyên tố trong $Q$ . Số nguyên dương $n$ được gọi là đặc biệt nếu $p(n)+p(n+1)$ và $q(n)+q(n+1)$ đều là số nguyên chẵn. Chứng minh rằng tồn tại một hằng số $c>0$ không phụ thuộc $Q$ sao cho với mọi số nguyên dương $N>100$ , số các số nguyên đặc biệt trong $[N]$ ít nhất là $cN$ .

N7. Gọi $k$ là một số nguyên dương và $S$ là một tập hữu hạn các số nguyên tố lẻ. Chứng minh rằng có nhiều nhất một cách (sai khác phép quay và đối xứng) để đặt các phần tử của $S$ xung quanh một đường tròn sao cho tích của hai số cạnh nhau bất kỳ có dạng $x^2+x+k$ với một số nguyên dương $x$ .

(IMO2022/3)

N8. Chứng minh rằng với mỗi số nguyên dương $n$ , số $5^n-3^n$ không chia hết cho số $2^n+65$ .

—

Các phần khác đã được đăng ở

Đại số: https://nttuan.org/2024/05/06/isl2022-algebra/

Hình học: https://nttuan.org/2023/09/08/isl2022-geometry/

Tổ hợp: https://nttuan.org/2023/09/29/isl2022-combinatorics/

Bản pdf của IMO SL từ 2014 đến 2021: https://nttuan.org/2023/07/02/isl/

Sau khi sửa một vài chỗ, bản pdf của IMO SL 2022 sẽ được đăng trong link trên.

IMO 2024: Problems and results

Ngày thi thứ nhất (16/7/2024)

Bài 1. https://artofproblemsolving.com/community/c6h3358923

Tìm tất cả các số thực $\alpha$ sao cho với mỗi số nguyên dương $n$ , số

$[\alpha]+[2\alpha]+\cdots+[n\alpha]$

chia hết cho $n$ .

Bài 2. https://artofproblemsolving.com/community/c6h3358926

Tìm tất cả các cặp số nguyên dương $(a,b)$ sao cho tồn tại các số nguyên dương $g$ và $N$ thỏa mãn

$\gcd (a^n+b,b^n+a)=g$

với mọi số nguyên $n\geq N$ .

Bài 3. https://artofproblemsolving.com/community/c6h3358932

Cho dãy vô hạn các số nguyên dương $(a_n)_{n\geq 1}$ và số nguyên dương $N$ . Giả sử với mọi số nguyên $n>N$ , $a_n$ bằng số lần xuất hiện của $a_{n-1}$ trong dãy số $a_1$ , $a_2$ , $\ldots$ , $a_{n-1}$ . Chứng minh rằng một trong hai dãy số $(a_{2n-1})_{n\geq 1}$ và $(a_{2n})_{n\geq 1}$ là tuần hoàn kể từ lúc nào đó.

Ngày thi thứ hai (17/7/2024)

Bài 4. https://artofproblemsolving.com/community/c6h3359767

Cho $ABC$ là một tam giác với $AB < AC < BC$ . Gọi tâm đường tròn nội tiếp và đường tròn nội tiếp của tam giác $ABC$ lần lượt là $I$ và $\omega$ . Gọi $X$ là điểm trên đường thẳng $BC$ , khác $C$ , sao cho đường thẳng qua $X$ song song với $AC$ tiếp xúc với $\omega$ . Tương tự, gọi $Y$ là điểm trên đường thẳng $BC$ , khác $B$ , sao cho đường thẳng qua $Y$ song song với $AB$ tiếp xúc với $\omega$ . Đường thẳng $AI$ cắt lại đường tròn ngoại tiếp tam giác $ABC$ tại $P$ . Gọi $K$ và $L$ lần lượt là trung điểm của $AC$ và $AB$ . Chứng minh rằng $\angle KIL + \angle YPX = 180^{\circ}$ .

Bài 5. https://artofproblemsolving.com/community/c6h3359777

Ốc sên Turbo chơi trò chơi sau trên một bảng ô vuông cỡ $2024\times 2023$ . Trong $2022$ ô vuông con nào đó, có các con quỷ nấp ở đó. Ban đầu, Turbo không biết ô nào có quỷ, nhưng nó biết rằng trên mỗi hàng có đúng một con quỷ, trừ hàng đầu tiên và hàng cuối cùng, và trên mỗi cột có không quá một con quỷ.

Turbo thực hiện một dãy các phép thử để tìm cách đi từ hàng đầu đến hàng cuối của bảng. Tại mỗi lần thử, nó được quyền chọn một ô bất kỳ trên hàng đầu để xuất phát, sau đó liên tục di chuyển giữa các ô, mỗi bước từ một ô sang một ô có chung cạnh với ô mà nó đang đứng (nó được phép đến các ô đã từng đi qua). Nếu nó tới một ô có quỷ thì lần thử này dừng lại và nó được đưa trở lại hàng đầu để thực hiện một lần thử khác. Những con quỷ không di chuyển, và Turbo nhớ mỗi ô mà nó ghé qua có quỷ hay không. Nếu nó tới được một ô bất kỳ trên hàng cuối thì trò chơi kết thúc.

Xác định giá trị nhỏ nhất của $n$ sao cho Turbo luôn có chiến lược đảm bảo tới được hàng cuối cùng sau không quá $n$ lần thử, cho dù các con quỷ có nấp ở đâu.

Bài 6. https://artofproblemsolving.com/community/c6h3359771

Một hàm số $f:\mathbb{Q}\to\mathbb{Q}$ được gọi là đẹp nếu với mỗi số hữu tỷ $x$ và $y$ , $f(x+f(y))=f(x)+y$ hoặc $f(f(x)+y)=x+f(y)$ . Chứng minh rằng tồn tại số nguyên $c$ sao cho với mọi hàm số đẹp $f$ , có không quá $c$ số hữu tỷ có dạng $f(r)+f(-r)$ , với số hữu tỷ $r$ nào đó. Tìm giá trị nhỏ nhất của các số $c$ có tính chất này.

Ban tổ chức quyết định điểm xếp giải như sau:

HCV: $\geq 29$ , HCB: $\geq 22$ , HCĐ: $\geq 16$ .

Đội tuyển Việt Nam được 2 HCB và 3 HCĐ. Đội đứng thứ 33 về tổng điểm.

Top 10 đội có điểm cao nhất. Đội tuyển Trung Quốc đứng thứ hai, sau nhiều năm đứng thứ nhất.

Top 10 thí sinh có điểm cao nhất. Haojia Shi lần thứ hai đạt 42/42 điểm. 🙂

Nguồn ảnh: https://www.imo-official.org/

Connected graph

Một đồ thị (xem lại [2]) khác rỗng $G$ được gọi là liên thông nếu mỗi hai đỉnh của nó được nối với nhau bởi một đường đi (xem lại [3]).

Định lý 1. Các đỉnh của một đồ thị liên thông $G$ có thể đánh số $v_1$ , $v_2$ , $\ldots$ , $v_n$ sao cho $G_i:=G[v_1,v_2,\ldots,v_i]$ là đồ thị liên thông với mọi $i$ .

Chứng minh. Lấy một đỉnh $v_1$ , và giả sử đã đánh số được các đỉnh $v_1$ , $v_2$ , $\ldots$ , $v_i$ thỏa mãn tính chất trong định lý, ở đây $i<\mid G\mid.$ Giả sử $v$ là một đỉnh khác tất cả các đỉnh đã được đánh số. Vì $G$ là đồ thị liên thông nên tồn tại đường đi $P$ nối $v$ với $v_1$ . Chọn $v_{i+1}$ là đỉnh cuối của $P$ mà không thuộc $G_i$ , khi đó $v_{i+1}$ có một láng giềng trong $G_i$ và $G_{i+1}$ liên thông. $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh sẽ có ít nhất $n-1$ cạnh.

Chứng minh. Quy nạp theo $n$ và dùng định lý 1. Bạn đọc tự chứng minh xem như một bài tập. $\Box$

Cho đồ thị $G=G(V,E)$ . Một đồ thị con liên thông cực đại (cực đại theo nghĩa không có đồ thị con liên thông chứa và khác nó, xem lại [2]) của $G$ được gọi là thành phần liên thông của $G$ . Đương nhiên, các thành phần liên thông là các đồ thị con cảm sinh (xem lại [2]) của $G$ , và tập các đỉnh của chúng lập thành một phân hoạch của $V$ . Một đồ thị là liên thông nếu và chỉ nếu nó có đúng một thành phần liên thông.

Ví dụ 1. Cho $G$ là một đồ thị với $m$ cạnh và $p$ thành phần liên thông. Chứng minh rằng $m+p\geq \mid G\mid$ .

Lời giải. Gọi $n_i$ là số đỉnh của thành phần liên thông thứ $i$ . Khi đó số cạnh của thành phần liên thông thứ $i$ không bé hơn $n_i-1$ , do đó

$m\geq \sum (n_i-1)=-p+\sum n_i=\mid G\mid -p,$

và bài toán được giải. $\Box$

Ví dụ 2. Cho $G$ là một đồ thị con không liên thông của $K_n$ . Chứng minh rằng $\overline{G}$ là một đồ thị con liên thông của $K_n$ .

Lời giải. Gọi $G^{\prime}$ là một thành phần liên thông của $G$ . Vì $G$ không liên thông nên $G\setminus G^{\prime}$ khác rỗng. Do tính cực đại của thành phần liên thông, không có cạnh nào của $G$ nối một đỉnh của $G^{\prime}$ với một đỉnh của $G\setminus G^{\prime}$ . Suy ra trong $\overline{G}$ , mỗi đỉnh của $G^{\prime}$ sẽ nối với mỗi đỉnh của $G\setminus G^{\prime}$ .

Vậy muốn chứng minh $\overline{G}$ liên thông, ta chỉ cần chứng minh hai đỉnh cùng thuộc $G^{\prime}$ hoặc $G\setminus G^{\prime}$ được nối với nhau. Nếu hai đỉnh cùng thuộc $G^{\prime}$ thì ta nối chúng với nhau qua một đỉnh của $G\setminus G^{\prime}$ , và ngược lại. $\Box$

Cho số tự nhiên $k$ . Một đồ thị $G=(V,E)$ được gọi là $k-$liên thông nếu $k<\mid G\mid$ và $G\setminus X$ vẫn là đồ thị liên thông với mọi $X\subset V$ mà $\mid X\mid<k$ . Số $k$ lớn nhất sao cho $G$ là $k-$ liên thông được gọi là chỉ số liên thông của $G$ , ký hiệu $k(G)$ .

Ví dụ 3. $k(K_n)=n-1$ với mỗi số nguyên dương $n$ .

Lời giải. Bạn đọc tự giải xem như bài tập. $\Box$

Định lý 2 (Whitney, 1932). Cho đồ thị $G=(V,E)$ với $\mid G\mid\geq 3$ . Khi đó $G$ là $2-$ liên thông khi và chỉ khi với hai đỉnh phân biệt bất kỳ của $G$ , tồn tại hai đường đi rời nhau nối chúng (hai đường đi được gọi là rời nhau nếu chúng không có đỉnh trong chung).

Chứng minh. Khẳng định đúng hiển nhiên khi $\mid G\mid =3$ . Bây giờ ta xét $\mid G\mid >3$ . Đầu tiên, giả sử với hai đỉnh phân biệt bất kỳ của $G$ tồn tại hai đường đi rời nhau nối chúng. Gọi $w$ là một đỉnh bất kỳ và $u,v$ là hai đỉnh khác nhau của $G\setminus\{w\}$ . Giữa $u$ và $v$ sẽ có hai đường đi rời nhau nối chúng, $w$ sẽ không thuộc một trong hai đường này, ký hiệu $P$ . Ta có $P$ là một đường trong $G\setminus\{w\}$ nối $u$ và $v$ . Suy ra $G\setminus\{w\}$ liên thông, do đó $G$ là $2-$ liên thông.

Bây giờ giả sử $G$ là $2-$ liên thông và tồn tại hai đỉnh phân biệt $u$ và $v$ mà không có hai đường đi rời nhau. Vì $\mid G\mid >3$ nên tồn tại ít nhất hai đường đi nối $u$ và $v$ . Gọi $P$ và $Q$ là hai đường đi nối $u$ và $v$ mà có tập đỉnh chung $S$ có ít phần tử nhất có thể. Lấy $w\in S\setminus \{u,v\}$ và $P_1$ , $P_2$ là phần của $P$ từ $u$ đến $w$ , $w$ đến $v$ . Tương tự ta định nghĩa $Q_1$ và $Q_2$ .

Vì $G$ là $2-$ liên thông, ta có thể lấy một đường đi $R$ ngắn nhất từ một đỉnh $x$ thuộc $(P_1\cup Q_1)\setminus \{w\}$ đến một đỉnh $y$ thuộc $(P_2\cup Q_2)\setminus \{w\}$ mà không qua $w$ . Giả sử mà không làm mất tính tổng quát rằng $x\in P_1$ và $y\in Q_2$ . Gọi $T$ là đường đi nối $u$ với $v$ được hình thành bởi phần $P_1$ nối $u$ với $x$ , và phần $Q_2$ nối $y$ với $v$ , cùng với $R$ . Do cách chọn $R$ , hai đường đi $T$ và $Q_1\cup P_2$ cùng nối $u$ với $v$ nhưng có tập các đỉnh chung là tập con của $S\setminus \{w\}$ , vô lý. $\Box$

Cho một đồ thị $G$ . Đường đi $P$ (không nhất thiết trong $G$ ) được gọi là $G-$ đường nếu $\mid P\mid >1$ và $P\cap G$ chỉ chứa hai đầu mút của $P$ . Kết quả sau cho ta biết cấu trúc của các đồ thị $2-$ liên thông.

Định lý 3. Một đồ thị là $2-$ liên thông khi và chỉ khi nó có thể được dựng từ một chu trình bằng cách bổ sung liên tiếp các $H-$ đường vào các đồ thị $H$ đã được dựng.