Bipartite graph

Một đồ thị $G$ được gọi là hai phần (hay lưỡng phân) nếu $V(G)$ có thể phân hoạch thành hai tập con $X$ và $Y$ , sao cho mỗi phần tử của $E(G)$ có một đầu mút trong $X$ và đầu mút còn lại trong $Y$ . Khi đó $X$ và $Y$ được gọi là các phần của đồ thị lưỡng phân. Ta ký hiệu đồ thị lưỡng phân với hai phần $X$ và $Y$ bởi $G[X,Y]$ . Nếu trong $G[X,Y]$ , mọi đỉnh thuộc $X$ được nối với mọi đỉnh của $Y$ thì $G[X,Y]$ được gọi là đồ thị lưỡng phân đầy đủ.

Ví dụ 1. Gọi $X$ và $Y$ lần lượt là tập các cầu thủ bóng đá và tập các câu lạc bộ trong một thành phố. Khi đó ta có đồ thị lưỡng phân $G[X,Y]$ , ở đây $x\in X$ được nối với $y\in Y$ khi và chỉ khi $x$ đã từng chơi cho $y$ .

Ví dụ 2 (Bài toán tối ưu trong đường sắt). Giả sử ta có một lịch trình các chuyến tàu cùng các điểm dừng của chúng, và cần tìm một tập hợp các ga tàu càng nhỏ càng tốt sao cho mọi chuyến tàu ghé thăm ít nhất một trong các ga đã chọn. Bài toán này có thể được mô hình hóa như một bài toán trên đồ thị lưỡng phân có các phần là tập các chuyến tàu và tập các ga tàu, mỗi chuyến tàu nối với ga mà nó sẽ dừng.

Bây giờ chúng tôi sẽ giới thiệu một số kết quả cơ bản về đồ thị hai phần.

Định lý 1. Cho đồ thị lưỡng phân $G[X,Y]$ không có đỉnh cô lập và thỏa mãn $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ). Khi đó $\mid X\mid \leq \mid Y\mid$ . Đẳng thức xảy ra khi và chỉ khi $\deg (x)= \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ).

Chứng minh. Vì $G$ không có đỉnh cô lập nên với mỗi $(x,y)\in X\times Y$ , ta có

$\displaystyle \sum_{y^{\prime}\in N(x)}\frac{1}{\deg (x)}=\sum_{x^{\prime}\in N(y)}\frac{1}{\deg (y)}=1.$

Suy ra

$\displaystyle \mid X\mid =\sum_{x\in X}\sum_{y\in N(x)}\frac{1}{\deg (x)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg x},$

và

$\displaystyle \mid Y\mid =\sum_{y\in Y}\sum_{x\in N(y)}\frac{1}{\deg (y)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg y}.$

Kết hợp với giả thiết $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ) ta có những điều cần chứng minh. $\Box$

Định lý 2. Một đồ thị là lưỡng phân khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Chứng minh. Nếu một đồ thị là lưỡng phân thì dọc theo một chu trình của nó, các đỉnh thuộc hai phần sẽ xuất hiện luân phiên. Vì thế, mỗi chu trình trong đồ thị lưỡng phân phải có độ dài là số chẵn. Bây giờ xét một đồ thị $G$ không chứa chu trình với độ dài là số lẻ. Ta chỉ cần xét tình huống $G$ là một đồ thị liên thông.

Gọi $T$ là một cây bao trùm trong $G$ (nó tồn tại theo [1]), và chọn một đỉnh $r$ làm gốc của cây này. Gọi $C$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn, và $L$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn. Khi đó $V(G)$ được phân hoạch thành hai phần $C$ và $L$ .

Ta sẽ chứng minh $G$ là đồ thị lưỡng phân với các phần là $L$ và $C$ . Xét hai đỉnh kề nhau $x$ và $y$ của $G$ . Nếu $xy\in T$ thì độ dài của $rTx$ và độ dài của $rTy$ khác tính chẵn-lẻ, do đó trong hai đỉnh $x$ , $y$ có một đỉnh thuộc $C$ và đỉnh còn lại thuộc $L$ . Nếu $xy\not \in T$ , từ giả thiết ta thấy chu trình $xTy\cup xy$ có độ dài chẵn. Theo phần chứng minh trước thì mỗi cạnh khác $xy$ thuộc chu trình này có các đầu mút thuộc hai phần khác nhau của phân hoạch, suy ra $x$ và $y$ thuộc hai phần khác nhau của phân hoạch. $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2024/08/02/tree/

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)$ .

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.

Tài liệu tham khảo

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

[2] https://nttuan.org/2023/09/01/graph02/

[3] https://nttuan.org/2024/06/04/graph03/

International Mathematics Tournament of the Towns, Spring 2024

Kỳ thi Toán quốc tế giữa các thành phố là một kỳ thi học sinh giỏi môn Toán có quy mô quốc tế được tổ chức lần đầu tiên tại Nga vào năm 1980. Cho đến nay, mỗi năm, kỳ thi được tổ chức tại hơn 100 thành phố ở hơn 25 quốc gia trên toàn thế giới. Điều đặc biệt của kỳ thi là học sinh được làm bài tại thành phố của mình, do đó giảm thiểu tối đa các chi phí phát sinh. Bài làm của các thí sinh sẽ được Ban tổ chức tại địa phương chấm và gửi kết quả về Ban tổ chức Trung ương tại Nga. Mỗi năm, có hơn 1000 thí sinh đạt tiêu chuẩn được cấp Bằng chứng nhận từ Viện Hàn lâm Khoa học Nga (Russian Academy of Sciences).

Nhằm thúc đẩy phong trào dạy và học Toán theo xu hướng hội nhập quốc tế, năm 2015, kỳ thi ITOT được tổ chức lần đầu tiên tại Việt Nam do Trung tâm Nghiên cứu và Ứng dụng Khoa học Giáo dục, Trường Đại học Giáo dục, Đại học Quốc gia Hà Nội làm đại diện chính thức của kỳ thi tại Việt Nam.

Từ năm 2024, Công ty TNHH Giáo dục VSO là đơn vị đại diện chính thức phối hợp với Viện Hàn lâm Khoa học Nga để tổ chức các kỳ thi ITOT tại Việt Nam. Kỳ thi được tổ chức hằng năm, mỗi năm hai vòng vào mùa thu (khoảng tháng mười) và mùa xuân (khoảng tháng ba). Học sinh có thể tham gia vào một trong hai hoặc cả hai vòng, tùy theo điều kiện địa phương.

1. Mục đích của kỳ thi

Kỳ thi Toán quốc tế giữa các thành phố giúp cho học sinh có cơ hội tham gia một kỳ thi chuẩn quốc tế. Mục đích chính của kỳ thi là góp phần nâng cao chất lượng dạy và học toán, đồng thời phát hiện và bồi dưỡng các học sinh có năng khiếu. Bên cạnh đó, kỳ thi còn cung cấp cho giáo viên và những người tổ chức địa phương một nguồn tài liệu chất lượng cao.

2. Cơ quan tổ chức:

Công ty TNHH Giáo dục VSO

Đơn vị triển khai: Vietnam Math Circle

3. Thời gian, địa điểm tổ chức kỳ thi ITOT45 mùa xuân

– Thời gian: Ngày thi cấp độ O: 23/03/2024

Ngày thi cấp độ A: 24/03/2024

– Địa điểm: Trường Tiểu học, THCS và THPT Thực nghiệm Khoa học Giáo dục, 50 P. Liễu Giai, Cống Vị, Ba Đình, Hà Nội

4. Đối tượng dự thi

– Cấp THCS: Học sinh khối lớp 7, 8 và 9;

– Cấp THPT: Học sinh khối lớp 10, 11 và 12.

5. Hình thức thi

Thí sinh thi tập trung tại điểm thi. Thông tin về các phòng thi và danh sách học sinh sẽ được ban tổ chức công bố trên website trước ngày 22/03/2024.

Nguồn: https://www.mathcircle.edu.vn/ITOTSpring2024