Formal power series

Định nghĩa 1. Một chuỗi lũy thừa hình thức là một biểu diễn có dạng

$a_0+a_1x+a_2x^2+a_3x^3+\ldots,$

hay gọn hơn $\displaystyle\sum_{k=0}^{\infty}a_kx^k.$ Trong đó $(a_n)_{n\geq 0}$ là một dãy các số phức. Các $a_i$ được gọi là các hệ số của chuỗi lũy thừa hình thức, $a_0$ được gọi là hệ số tự do của chuỗi lũy thừa hình thức.

Từ “hình thức” trong định nghĩa trên có nghĩa là ta không bận tâm đến việc cho $x$ các giá trị đặc biệt, ta cũng không quan tâm đến tính hội tụ hay phân kỳ của chuỗi. Tập tất cả các chuỗi lũy thừa hình thức với hệ số thuộc một tập hợp $A$ được ký hiệu bởi $A[[x]]$ . Với một chuỗi lũy thừa hình thức $a(x)$ , ta ký hiệu hệ số của $x^n$ trong chuỗi này bởi $[x^n]a(x)$ .

Nếu $a_i=0$ với mọi $i>m$ thì để cho gọn, chuỗi $\sum_{n=0}^{\infty}a_nx^n$ sẽ được viết là

$a_0+a_1x+\ldots+a_mx^m.$

Chuỗi lũy thừa hình thức với tất cả các hệ số bằng $0$ được gọi là chuỗi không, ký hiệu là $0$ . Tổng và tích của hai chuỗi lũy thừa hình thức $\displaystyle\sum_{n=0}^{\infty}a_nx^n$ và $\displaystyle\sum_{n=0}^{\infty}b_nx^n$ được định nghĩa bởi

$\displaystyle\sum_{n=0}^{\infty}a_nx^n+\sum_{n=0}^{\infty}b_nx^n=\sum_{n=0}^{\infty}(a_n+b_n)x^n$

và

$\displaystyle\left(\sum_{n=0}^{\infty}a_nx^n\right)\left(\sum_{n=0}^{\infty}b_nx^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n.$

Với hai phép toán này thì $\mathbb{C}[[x]]$ là một vành giao hoán có đơn vị là chuỗi đơn vị $1+0x^1+0x^2+0x^3+\ldots,$ ký hiệu là $1$ .

Tương tự như với các số phức, ta có kết quả sau:

Định lý 1. Nếu $a$ và $b$ là các phần tử khác không của $\mathbb{C}[[x]]$ , thì chuỗi tích $ab$ cũng khác chuỗi không.

Chứng minh. Gọi $m$ là số tự nhiên nhỏ nhất sao cho $[x^m]a\not=0$ , và $n$ là số tự nhiên nhỏ nhất sao cho $[x^n]b\not=0$ . Khi đó

$[x^{m+n}](ab)=([x^m]a)([x^n]b)\not=0,$

suy ra $ab$ khác chuỗi không. $\Box$

Khác với phép nhân trong tập các số phức, không phải mọi chuỗi khác không đều có nghịch đảo. Chẳng hạn, khi $a(x)=0+x+0x^2+0x^3+\ldots,$ (chuỗi này thường được viết là $a(x)=x$ ) thì $a(x)\not=0$ nhưng không có chuỗi $b(x)$ để $a(x)b(x)=1$ .

Định lý 2. Chuỗi $a(x)$ có nghịch đảo khi và chỉ khi $[x^0]a(x)\not=0$ .

Chứng minh. Giả sử chuỗi $a(x)$ có nghịch đảo, và $b(x)$ là nghịch đảo của nó. Khi đó

$1=[x^0](ab)=([x^0]a)([x^0]b),$

suy ra $[x^0]a(x)\not=0$ .

Bây giờ giả sử $\displaystyle a(x)=\sum_{n=0}^{\infty}a_nx^n$ là một chuỗi lũy thừa hình thức có $a_0=[x^0]a(x)\not=0$ . Chuỗi lũy thừa hình thức $\displaystyle b(x)=\sum_{n=0}^{\infty}b_nx^n$ là nghịch đảo của $a(x)$ khi và chỉ khi $a_0b_0=1$ và

$\displaystyle\sum _{k=0}^na_kb_{n-k}=0,\quad\forall n\geq 1.$

Từ hệ này ta có thể xác định $b(x)$ bởi $b_0=1/a_0$ và

$\displaystyle b_n=-\frac{1}{a_0}\sum _{k=1}^na_kb_{n-k},\quad\forall n\geq 1.$ $\Box$

Khi $a$ là một chuỗi có nghịch đảo thì ta ký hiệu chuỗi nghịch đảo của nó bởi $a^{-1}$ . Tích của chuỗi $b$ và chuỗi $a^{-1}$ thường được viết là $\frac{b}{a}$ .

Ví dụ. Chuỗi lũy thừa hình thức $1-x$ có nghịch đảo là chuỗi

$\displaystyle \frac{1}{1-x}=1+x+x^2+x^3+\ldots$

Định nghĩa 2. Dãy các chuỗi lũy thừa hình thức với hệ số phức $\{S_n(x)\}_{n\geq 1}$ được gọi là hội tụ đến chuỗi lũy thừa hình thức với hệ số phức $S(x)$ , ký hiệu $\displaystyle\lim_{n\to\infty} S_n(x)=S(x)$ , nếu với mỗi $n\geq 0$ có số nguyên dương $N$ sao cho $[x^n]S_i(x)=[x^n]S(x)$ mỗi khi $i\geq N$ . Trong trường hợp này ta nói $\{S_n(x)\}_{n\geq 1}$ là một dãy hội tụ.

Khi $\displaystyle A(x)=\sum_{n\geq 0}a_nx^n$ là một phần tử khác không của $\mathbb{C}[[x]]$ , ta gọi bậc của $A(x)$ , ký hiệu $\deg A(x)$ , là số $n$ nhỏ nhất sao cho $a_n\not=0$ . Dễ thấy nếu $B(x)$ và $C(x)$ là các phần tử khác không của $\mathbb{C}[[x]]$ thì $B(x)C(x)$ cũng là một phần tử khác không của $\mathbb{C}[[x]]$ , và

$\deg B(x)C(x)=\deg B(x)+\deg C(x).$

Ta quy ước $\deg 0=\infty$ . Sử dụng bậc của một chuỗi lũy thừa hình thức ta có một định nghĩa khác của tính hội tụ của dãy các chuỗi lũy thừa hình thức.

Continue reading →

Discrete random variables

Ta thường không quan tâm đến thí nghiệm mà chỉ quan tâm đến một số hệ quả từ thí nghiệm đó. Chẳng hạn, những tay cờ bạc chỉ quan tâm đến số tiền họ được hay mất, không quan tâm mấy đến trò chơi. Nhiều hệ quả từ thí nghiệm có thể được biểu diễn bằng một hàm trên không gian mẫu của thí nghiệm.

Định nghĩa 1. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ . Một biến ngẫu nhiên là một hàm $X:\Omega\to\mathbb{R}$ sao cho với mỗi $x\in\mathbb{R}$ , $\{\omega\in\Omega\mid X(\omega)\leq x\}\in\mathcal{F}.$

Một biến ngẫu nhiên được gọi là rời rạc nếu nó chỉ nhận giá trị trong một tập hợp đếm được.

Không khó khăn lắm để thấy rằng nếu $X$ và $Y$ là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc) thì $X+Y$ , $XY$ , và $\alpha X$ ( $\alpha\in\mathbb{R}$ ) cũng là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc).

Định nghĩa 2. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến ngẫu nhiên $X:\Omega\to\mathbb{R}$ . Hàm phân bố của biến ngẫu nhiên $X$ là hàm $F_X:\mathbb{R}\to [0;1]$ xác định bởi

$F_X(x)=\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\}),\quad\forall x\in\mathbb{R}.$

Để cho gọn, ta viết sự kiện $\{\omega\in\Omega\mid X(\omega)\leq x\}$ bởi $\{ X\leq x\}$ . Khi đó xác suất $\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\})$ sẽ được viết là $\mathbb{P}( X\leq x)$ .

Ví dụ 1. Tung một đồng xu hai lần. Không gian mẫu của phép thử là $\Omega =\{NN,SS,SN,NS\}$ . Xét biến ngẫu nhiên $X$ , số mặt ngửa, xác định bởi

$X(NN)=2, X(SS)=0, X(SN)=1, X(NS)=1.$

Hàm phân bố của $F_X:\mathbb{R}\to [0;1]$ của $X$ xác định bởi

$F_X(x)=\begin{cases}0,\quad x<0\\ 1/4,\quad 0\leq x<1\\ 3/4,\quad 1\leq x<2\\ 1,\quad x\geq 2.\end{cases}$

Ví dụ 2. Xét không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến cố $A$ . Hàm chỉ báo của $A$ là hàm $I_A: \Omega\to \mathbb{R}$ xác định bởi

$I_A(\omega)=\begin{cases}1,\quad \omega\in A\\ 0,\quad \omega\not\in A.\end{cases}$

Ta thấy $I_A$ là một biến ngẫu nhiên rời rạc với hàm phân bố $F:\mathbb{R}\to [0;1]$ xác định bởi

$F(x)=\begin{cases}0,\quad x<0\\ 1-\mathbb{P}(A),\quad 0\leq x<1\\ 1,\quad x\geq 1. \end{cases}$

Nếu $\{A_i\}_{i\in I}$ là một họ các biến cố đôi một rời nhau sao cho $\displaystyle A\subset \bigcup_{i\in I} A_i$ thì

$I_A(\omega)=\sum_{i\in I}I_{A\cap A_i}(\omega),\quad \forall \omega\in \Omega.$ $\Box$

Định lý 1. Hàm phân bố $F_X$ của biến ngẫu nhiên $X$ có các tính chất sau

(a) với mỗi số thực $x_1$ và $x_2$ , nếu $x_1<x_2$ thì $F_X(x_1)\leq F_X(x_2)$ .

(b) $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ và $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ .

(c) $F_X$ liên tục phải tại mọi điểm.

Chứng minh. Xét hai số thực $x_1$ và $x_2$ với $x_1<x_2$ . Biến cố $\{X\leq x_2\}$ là hợp của hai biến cố rời nhau $\{X\leq x_1\}$ và $\{x_1<X\leq x_2\}$ nên

$F_X(x_2)=\mathbb{P}(X\leq x_2)=\mathbb{P}(X\leq x_1)+\mathbb{P}(x_1<X\leq x_2)\geq \mathbb{P}(X\leq x_1)=F_X(x_1).$

Ta có $\{X\leq n\}_{n\geq 1}$ là một dãy tăng các sự kiện có hợp bằng $\Omega$ , theo định lý 1 trong [1], ta có

$1=\mathbb{P}(\Omega)=\mathbb{P}\left(\bigcup_{n=1}^{+\infty}\{X\leq n\}\right)=\lim_{n\to +\infty}\mathbb{P}(X\leq n),$

kết hợp với tính đơn điệu của $F_X$ ta được $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ . Tính chất $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ được chứng minh theo cách tương tự.

Bây giờ xét một số thực $x_0$ . Ta thấy $\{x_0<X\leq x_0+\frac{1}{n}\}_{n\geq 1}$ là một dãy giảm các sự kiện có giao bằng rỗng, theo định lý 2 trong [1], ta có

$0=\mathbb{P}\left(\bigcap_{n=1}^{+\infty}\left\{x_0<X\leq x_0+\frac{1}{n}\right\}\right)=\lim_{n\to +\infty}\left(F_X\left(x_0+\frac{1}{n}\right)-F_X(x_0)\right),$

kết hợp với tính đơn điệu của $F_X$ ta có $F_X$ liên tục phải tại $x_0$ . $\Box$

Continue reading →

Tree

Một đồ thị không chứa chu trình được gọi là một rừng. Một rừng liên thông được gọi là một cây.

Ví dụ 1. Cho $G$ là một cây trên $n>1$ đỉnh. Chứng minh rằng $G$ có ít nhất hai lá, và nếu $v$ là một lá thì $G\setminus\{v\}$ là một cây.

Hướng dẫn. Trong các đường đi của $G$ , quan tâm đến một đường đi dài nhất. Chứng minh hai đầu của nó là lá. Chỉ ra $G\setminus\{v\}$ là một rừng liên thông. $\Box$

Định lý 1. Với một đồ thị $G$ , các khẳng định sau là tương đương:

(1) $G$ là một cây;

(2) Mỗi hai đỉnh của $G$ được nối với nhau bởi một đường đi duy nhất trong $G$ ;

(3) $G$ là đồ thị liên thông và với mỗi cạnh $e$ , đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ không phải là đồ thị liên thông;

(4) $G$ không chứa chu trình và với mỗi hai đỉnh không kề nhau $x$ và $y$ , đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình.

Chứng minh. Giả sử $G$ là một cây và $x$ , $y$ là hai đỉnh của $G$ . Vì $G$ là đồ thị liên thông nên có một đường đi nối $x$ và $y$ , ký hiệu là $\alpha$ . Nếu có một đường đi khác đường đi này nối $x$ và $y$ , ký hiệu là $\beta$ , gọi $z$ là đỉnh chung gần $x$ nhất của hai đường đi. Đường đi từ $x$ đến $z$ dọc theo $\alpha$ hợp với đường đi từ $z$ đến $x$ dọc theo $\beta$ tạo thành một chu trình, vô lý. Vậy ta đã chứng minh $(1)\Rightarrow (2)$ .

Xét một cạnh $e=xy$ của $G$ . Nếu đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ là đồ thị liên thông, thì trong $G$ có một đường đi nối $x$ và $y$ mà không chứa $e$ . Đường đi này cùng với $e$ là hai đường đi nối $x$ và $y$ . Vậy ta đã chứng minh $(2)\Rightarrow (3)$ , vì nếu có $(2)$ thì đồ thị phải là đồ thị liên thông.

Bây giờ giả sử có $(3)$ . Trước tiên ta thấy $G$ không chứa chu trình, vì nếu không ta bỏ đi một cạnh của chu trình thì đồ thị mới vẫn liên thông, vô lý. Xét hai đỉnh không kề nhau $x$ và $y$ . Vì $G$ là đồ thị liên thông nên có đường đi nối $x$ và $y$ . Thêm cạnh $xy$ vào đường đi này ta có một chu trình trong đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ . Vậy ta có $(4)$ .

Cuối cùng, ta giả sử có $(4)$ . Xét hai đỉnh phân biệt $x$ và $y$ . Nếu $x$ và $y$ kề nhau thì có đường đi nối $x$ và $y$ , là $xy$ chẳng hạn. Nếu $x$ và $y$ không kề nhau thì đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình. Vì $G$ không chứa chu trình nên chu trình này chứa $xy$ , bỏ $xy$ ra khỏi nó ta có đường đi trong $G$ nối $x$ và $y$ . Vậy ta có $(1)$ . $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh là một cây khi và chỉ khi nó có $n-1$ cạnh.

Chứng minh. Giả sử $G$ là một cây trên $n$ đỉnh. Vì $G$ là đồ thị liên thông nên theo định lý 1 trong [4], ta có thể đánh số các đỉnh của $G$ là $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$ . Do $G$ là một cây nên mỗi $G_i$ là một cây. Giả sử $G_i$ có $i-1$ cạnh với mọi chỉ số $i<k$ ( $k$ là một số nguyên dương sao cho $k\leq n$ ). Vì $G_k$ là liên thông nên với mỗi $i<k$ , có đường đi trong $G_k$ nối $v_i$ và $v_k$ . Trong tất cả các đường đi như thế, xét đường đi ngắn nhất và giả sử nó nối $v_1$ và $v_k$ . Đường đi này phải có độ dài bằng $1$ , hay $v_k$ và $v_1$ kề nhau trong $G$ . Vì $G$ không có chu trình nên trong $G_{k-1}$ , chỉ có đúng một đỉnh kề với $v_k$ , suy ra $G_k$ có $k-2+1=k-1$ cạnh. Theo nguyên lý quy nạp toán học, $G=G_n$ có $n-1$ cạnh.

Ngược lại, giả sử $G$ là một đồ thị liên thông trên $n$ đỉnh và có $n-1$ cạnh. Gọi $T$ là một đồ thị con bao trùm liên thông cực tiểu của $G$ . Do tính cực tiểu, khi bỏ mỗi cạnh ra khỏi $T$ thì đồ thị thu được không liên thông, suy ra theo định lý 1 thì $T$ là một cây. Cây này có số cạnh bằng $n-1$ theo phần đầu của chứng minh, do đó $T=G$ . $\Box$

Trong một số vấn đề, việc xét một cây với gốc sẽ rất thuận tiện. Giả sử có một cây $T$ và một đỉnh cố định $r$ , gọi là gốc của cây. Với hai đỉnh $x$ và $y$ của $T$ , có đúng một đường đi nối $x$ và $y$ , ta ký hiệu nó là $xTy$ . Với $a,b\in T$ , ta viết $a\leq_T b$ (hoặc $a\leq b$ khi không sợ nhầm lẫn) nếu $a\in rTb$ . Ta thấy $\leq_T$ là một quan hệ thứ tự bộ phận trên $T$ , gọi là thứ tự cây. Khi $a<b$ ta nói $b$ nằm trên $a$ , hay $a$ nằm dưới $b$ . Theo quan hệ thứ tự này thì $r$ là phần tử nhỏ nhất của $T$ , mỗi lá là phần tử cực đại. Hai đầu mút của mỗi cạnh của $T$ là so sánh được.

Ví dụ 2. Cho số nguyên $n$ lớn hơn $1$ và một cây trên $n$ đỉnh. Các đỉnh của cây được viết các số thực $x_1$ , $x_2$ , $\ldots$ , $x_n$ . Mỗi cạnh của cây được viết tích của hai số được viết trên các đầu mút của cạnh, gọi $S$ là tổng tất cả các số này. Chứng minh rằng

$\displaystyle\sqrt{n-1}\left(x_1^2+x_2^2+\dots+x_n^2\right)\geq 2S.$

Lời giải. Giả sử tập các đỉnh của cây là $V=\{v_1, v_2, \ldots, v_n\}$ sao cho với mỗi $i$ , số được viết trên $v_i$ là $x_i$ . Với hai đỉnh kề nhau $v_i$ và $v_j$ , gọi $P(i,j)$ là tập các đỉnh của cây không nối được đến $v_i$ bởi một đường đi sau khi xóa khỏi cây cạnh $v_iv_j$ . Ta có ngay $1\leq \mid P(i,j)\mid \leq n-1$ mỗi khi $v_i$ và $v_j$ kề nhau.

Nhận xét 1. Nếu $v_i$ và $v_j$ kề nhau thì $\mid P(i,j)\mid +\mid P(j,i)\mid=n$ .

Chứng minh. Gọi $v$ là một đỉnh của cây, và xem nó là gốc. Ta có $v_i$ và $v_j$ là so sánh được theo thứ tự cây. Nếu $v_i<v_j$ thì $v\in P(j,i)$ , nếu $v_j<v_i$ thì $v\in P(i,j)$ , nhưng không thể có cả hai. Như vậy $V$ được phân hoạch thành $P(i,j)$ và $P(j,i)$ , từ đây ta có điều cần chứng minh. $\Box$

Nhận xét 2. Với mỗi $i$ ,

$\displaystyle \sum_{v_j\in N(v_i)}\mid P(i,j)\mid =n-1$ .

Chứng minh. Cố định một chỉ số $i$ . Do mỗi đỉnh đều nối đến $v_i$ bởi một đường đi duy nhất và cây không có chu trình nên các $P(i,j)$ với $v_j\in N(v_i)$ làm thành một phân hoạch của $V\setminus\{v_i\}$ , từ đây ta có điều cần chứng minh. $\Box$

Bây giờ với mỗi cạnh $v_iv_j$ , theo nhận xét 1 ta có

$\displaystyle \mid P(i,j)\mid .\mid P(j,i)\mid=\frac{n^2-(\mid P(i,j)\mid -\mid P(j,i)\mid)^2}{4}\geq n-1,$

suy ra

$\displaystyle\frac{\mid P(i,j)\mid}{\sqrt{n-1}}x_i^2+\frac{\mid P(j,i)\mid}{\sqrt{n-1}}x_j^2\geq 2\sqrt{\frac{\mid P(i,j)\mid .\mid P(j,i)\mid}{n-1}}|x_ix_j|\geq 2x_ix_j.$

Mỗi cạnh cho ta một bất đẳng thức có dạng như trên, cộng theo vế các bất đẳng thức này ta có bất đẳng thức trong đề bài. $\Box$

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/

[4] https://nttuan.org/2024/07/01/connected-graph/

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.