Tag Archives: Tổ hợp

Phương pháp chứng minh quy nạp – Các dạng khác

Leave a reply

Trong bài này, chúng ta tiếp tục tìm hiểu thêm và phương pháp quy nạp. Ngoài dạng quy nạp như đã biết ta còn một số dạng quy nạp khác như: Quy nạp mạnh, quy nạp bước nhảy, quy nạp lùi.

Quy nạp mạnh được phát biểu như sau: Để chứng minh mệnh đề $P(n)$ đúng với mọi số tự nhiên $n$, ta thực hiện theo hai bước sau:

  • Chứng minh $P(n)$ đúng với $n=1$.
  • Giả sử $P(n)$ đúng với $1, 2, \cdots, n$. Chứng minh $P(n+1)$ đúng.

Ví dụ 1. Cho $x$ thỏa $x+\dfrac{1}{x}$ là số nguyên. Chứng minh rằng $x^n+\dfrac{1}{x^n}$ là số nguyên với mọi $n$.

Lời giải. 

  • Ta có $x + \dfrac{1}{x}$ là số nguyên  đúng (theo giả thiết).
  • Giả sử $x^k + \dfrac{1}{x^k}$ là số nguyên với mọi $k = \overline{1,n}$. Ta cần chứng minh $x^{n+1} + \dfrac{1}{x^{n+1}}$.
    • $(x^{n+1} + \dfrac{1}{x^{n+1}} = (x+\dfrac{1}{x})(x^n + \dfrac{1}{n})  – (x^{n-1}+\dfrac{1}{x^{n-1}})$.
    • Theo giả thiết quy nạp thì $x^{n+1} + \dfrac{1}{x^{n+1}}$ là số nguyên.
  • Vậy ta có $x^n + \dfrac{1}{x^n}$ là số nguyên với mọi $n$.

 

Dạng kế tiếp là Quy nạp bước nhảy  được phát biểu như sau: Chứng minh mệnh đề $P(n)$ đúng với mọi $n$, ta làm như sau:

  • Chứng minh $P(1), P(2), \cdots, P(k)$ đúng.
  • Giả sử $P(n)$ đúng. Ta chứng minh $P(n+k)$ đúng.

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên $M$ tồn tại số tự nhiên $n$ và cách chọn các dấu $+$ hoặc $-$ sao cho

$M = \pm 1^2 \pm 2^2 \cdots \pm n^2$.

Lời giải.

  • Khi $M = 1, 2, 3, 4$ ta có $1 = 1^2$, $2 = -1^2-2^2-3^2+4^2$, $3 = -1^2+2^2$ và $4 = 1^2-2^2-3^2+4^2$.
  • Giả sử đúng với $M$, tức là tồn tại $n$ thỏa $M = \pm 1^2 \pm 2^2 \cdots \pm n^2$, khi đó $M + 4 = \pm 1^2 \pm 2^2 \cdots \pm n^2 +(n+1)^2-(n+2)^2-(n+3)^2 + (n+4)^2$.

Ví dụ 3.  Chứng minh rằng với mọi số tự nhiên $n$ thì phương trình $a^2 + b^2 = c^n$ luôn có nghiệm trong tập các số nguyên dương.

Lời giải. 

  • Rõ ràng nếu $n=1, 2$ thì phương trình luông có nghiệm nguyên dương.
  • Giả sử phương trình có nghiệm nguyên dương là $a, b, c$ với $n$ nào đó, tức là $a^2 + b^2 = c^n$.
    • Khi đó với $n+2$ thì xét $(ac), (bc), c$: $(ac)^2+(bc)^2 = c^2 (a^2+b^2) = c^{n+2}$.
    • $(ac, bc, c$ là nghiệm.
  • Vậy phương trình luôn có nghiệm với mọi $n$.

Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:

  • Chứng minh $P(a_i)$ đúng với dãy $(a_i)$ là dãy con tăng thực sự của tập các số tự nhiên.
  • Giả sử $P(n)$ đúng, chứng minh $P(n-1)$ đúng.

Ví dụ 4. 

a) Hãy chỉ ra cách sắp 8 số nguyên dương đầu tiên 1, 2, …, 8 thành một dãy $a_1, a_2 ,…, a_8$ sao cho 2 số $a_i, a_j$ bất kì $(i < j)$ thì mọi số trong dãy nằm giữa $a_i$ và $a_j$ đều khác $\dfrac{a_i + a_j}{2}$.
b) Chứng minh rằng với $N$ số nguyên dương đầu tiên $1, 2, …, N$ luôn tìm được cách sắp thành dãy $a_1, a_2, …, a_N$ sao cho dãy thỏa mãn điều kiện như câu a).
Lời giải.

a) Một cách xếp thỏa đề bài là 26481537.\
b)

Bước 1.Ta chứng minh bằng quy nạp với $n = 2^k$ thì luôn tồn tại một cách xếp thỏa đề bài.

  • Nếu $k = 1$, hiển nhiên đúng.
    Giả sử luôn tồn tại một cách xếp thỏa đề bài với $n = 2^k$, cách xếp đó là $a_1, a_2, …, a_n$.
    Ta chứng minh tồn tại một cách xếp với $n = 2^{k+1}$.
    Thật vậy xét hoán vị $(2a_1, 2a_2,…, 2a_n, 2a_1-1, 2a_2-1, …, 2a_n-1)$ là một hoán vị của $1, 2, …, 2^{k+1}$. Ta chứng minh hoán vị trên thỏa đề bài.

    • Ta có nếu $a_i, a_j \in \{2a_1, 2a_2, …, 2a_n\}$ theo giả thiết quy nạp không có số nào nằm giữa $a_i, a_j$ bằng $\dfrac{1}{2}(a_i+a_j)$.
    • Nếu $a_i \in \{2a_1, …, 2a_n\}, a_j \in \{2a_1-1, 2a_2-1, …, 2a_n-1\}$ thì $\dfrac{1}{2}(a_i +a_j)$ không phải số nguyên.
    • Nếu $a_i, a_j \in \{2a_1-1, 2a_2-1, …, 2a_n-1\}$ theo giả thiết quy nạp thì cũng có số nào nằm giữa $a_i, a_j$ bằng $\dfrac{1}{2}(a_i + a_j)$.

Vậy bài toán đúng với $n = 2^k$.(1)
Bước 2. Nếu bài toán đúng với $n$, ta chứng minh bài toán đúng với $n-1$.

Xét các số $a_1, a_2, …, a_n$ là một hoán vị thỏa đề bài của $1,2,…,n$.

Khi đó nếu xóa bất kì số nào trong các số $a_1, …, a_n$ thì dãy còn lại vẫn thỏa điều kiện. (2)
Từ (1) và (2) ta có điều cần chứng minh.

Quy nạp lùi cũng là một trong những cách chứng minh bất đẳng thức Cauchy tổng quát: $\dfrac{a_1+a_2 + \cdots+a_n}{n} \geq \sqrt[n]{a_1a_2\cdots a_n}$.

Các bạn tự làm thử nhé.

Trên đây là một số dạng quy nạp thường gặp trong chứng minh toán. Tùy theo tình huống mà ta sử dụng cho phù hợp, các bạn cần làm thêm nhiều bài tập để rèn luyện.

Bài tập rèn luyện.

Bài 1. Ta gọi tổng các số tự nhiên từ 1 đến n là số tam giác. Chứng minh rằng tồn tại vô hạn các số tam giác đồng thời là số chính phương.

Bài 2. (Chọn đội tuyển PTNK 2014)Tìm số nguyên dương $n$ lớn nhất thỏa mãn các điều kiện sau:

  • $n$ không chia hết cho 3;
  • Bảng vuông $n \times n$ ô không thể được phủ kín bằng 1 quân tetramino $1 \times 4$ và các quân trimino kích thước $1 \times 3$. Trong phép phủ các quân tetramino và trimino được phép quay dọc nhưng không được phép chườm lên nhau hoặc nằm ngoài ra bảng vuông.

Bài 3. Có $n$ số tự nhiên từ 1 đến $n$ được viết thành một dòng theo một thứ tự nào đó. Mỗi bước thực hiện biến đổi như sau: nếu số đầu tiên là $k$ thì $k$ số đầu tiên sẽ được viết theo thứ tự ngược lại. Chứng minh rằng sau hữu hạn bước thì số đầu tiên của dòng là số 1.

Bài 4. Trong cuộc họp có $2n$ ($n \geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có $n$ bộ ba, mà mỗi bộ ba đôi một bắt tay nhau.

Bài 5. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số nguyên $x, y, z$ phân biệt sao cho $x^2+y^2+z^2 = 14^n$.

Bài 6. Trong một giải đấu tennis có 10 người tham dự, hai đối thủ gặp nhau đúng một trận. Chứng minh rằng, sau khi kết thúc giải có thể sắp xếp các tay vợt thành một hàng mà người đứng trước thắng người đứng sau.

Phương pháp chứng minh quy nạp – P2

Leave a reply

Trong phần trước ta đã làm quen với phương pháp chứng minh quy nạp và áp dụng vào chứng minh một vài đẳng thức, bất đẳng thức hay các bài toán chia hết. Bài này tiếp tục là ứng dụng của quy nạp trong việc chứng minh các bài toán khác, trong cái đề thi học sinh giỏi hay tuyển sinh.

Ví dụ 1. Người ta lát nền nhà hình vuông kích thước $n \times n$ ô bằng các viên gạch như hình vẽ dưới sao cho còn chừa lại một ô không lát.
a) Hãy chỉ ra một cách lát như trên với nền nhà kích thước $4 \times 4$ và $8 \times 8$.
b) Hãy chứng minh rằng luôn tồn tại một cách lát nền nhà có kích thước $2^k \times 2^k$ (k nguyên dương) với ô trống còn lại nằm ở vị trí $(i,j)$ bất kì.

Lời giải

a) Các bạn tự làm.
b) Ta chứng minh bằng quy nạp.

  • Với $k = 2$ hiển nhiên đúng.
  • Giả sử với $k$ thì nền $2^k \times 2^k$ bỏ ô $(i;j)$ bất kì thì luôn phủ được. Ta chứng minh đúng với $k+1$.
    Với nền nhà $2^{k+1} \times 2^{k+1}$ ta chia thành 4 hình vuông $2^k \times 2^k$. Khi đó ô bỏ đi thuộc một trong 4 hình vuông đó, ta phủ được hình vuông này theo giả thiết quy nạp. Tiếp tục,theo giả thiết quy nạp, với 3 hình vuông còn lại, bỏ đi ô ở góc (hình vẽ) thì ta có thể phủ được. Khi đó 3 ô ở góc ta phủ tiếp bằng một viên gạch.
  • Với cách thực hiện đó thì ta có thể phủ được nền nhà $2^{k+1} \times 2^{k+1}$ khi bỏ ô bất kì.

Ví dụ 2. Trong cuộc họp có $2n$ ($n \geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có 3 người đôi một bắt tay nhau.

Lời giải
  • Rõ ràng bài toán đúng khi $n=2$.
  • Giả sử bài toán đúng với $n$, ta chứng minh bài toán đúng với $n+1$. Xét hai người $A, B$ bắt tay.
    Nếu số bắt tay của $A$ và $B$ với $2n$ người còn lại không vượt quá $2n$ thì $n$ người kia có $n^2+1$ cái bắt tay, ta có điều cần chứng minh.
    Nếu số người bắt tay với $A, B$ là hơn $2n$ cái.
  • Do đó trong $2n$ người kia thì sẽ có ít nhất một người bắt tay với cả $A$ và $B$, ta có điều cần chứng minh.

Ví dụ 3.  a) Cho bốn số nguyên dương $a_1, a_2, a_3, a_4$ sao cho $1 \leq a_k \leq k$ với mọi $ k= 1,2, 3, 4$ và tổng $S = a_1 + a_2 + a_3 + a_4$ là một số chẵn. Chứng minh rằng có ít nhất một trong các số dạng $\pm a_1 \pm a_2 \pm a_3 \pm a_4$ có giá trị bằng 0.
b) Cho 1000 số nguyên dương $a_1, a_2,…, a_{1000}$ sao cho $1 \leq a_k \leq k$ với $k = 1, 2, …, 1000$ và tổng $S = a_1 + a_2 + …+a_{1000}$ là một số chẵn.\
Hỏi trong các số có dạng $\pm a_1 \pm a_2 … \pm a_{1000}$ có số nào bằng 0 hay không? Giải thích vì sao?

Lời giải

a) Ta có $4 \leq S \leq 10$ và $S$ chẵn, suy ra $S = 4, 6, 8, 10$. Xét các trường hợp sau:

  • $S = 4$, suy ra $a_1 = a_2 = a_3 = a_4 = 1$. Suy ra $- 1 – 1+ 1 + 1 = 0$.
  • $S = 6$ ta có $6 = 1 + 1 + 1 + 3 = 1 + 1 + 2 + 2$, suy ra có một cách thỏa đề bài.
  • $S = 8$ ta có $8 = 1 + 1 + 2 + 4 = 1 + 1 + 3 + 3 = 1 + 2 + 2 + 3 = 2 + 2 + 2 + 2$. Suy ra mỗi cách đều tồn tại một cách chọn dấu $ + , – $ thỏa đề bài.
  • $S = 10 = 1 + 2 + 3 + 4$. Suy ra có một cách thỏa đề bài.

a) Ta chứng minh bằng quy nạp mệnh đề sau: Cho $n$ các số nguyên dương thỏa $1 \leq a_k \leq k$ thỏa $S_n = a_1 + …+a_n$ chẵn. Khi đó tồn tại số có dạng $\pm a_1 \pm a_2 … \pm a_{n}$ bằng 0.

  • Khi $n = 2$ ta có $a_1 + a_2$ chẵn, suy ra $a_1 = a_2 = 1$. Suy ra $a_1 – a_2 = 0$.
  • Giả sử bài toán đúng với $k\leq n$. Ta chứng minh bài toán đúng với $n + 1$. Ta có $S_{n+1} = a_1 + …+a_{n} + a_{n+1}$ chẵn. Ta có $0\leq |a_{n} – a_{n+1}| \leq n$.
    • Nếu $a_n – a_{n+1} = 0$ ta áp dụng giả thiết quy nạp với $n-1$ số $a_1, …, a_{n-1}$ ta có điều cần chứng minh.
    • Nếu $a_n – a_{n+1} \neq 0$. Áp dụng giả thiết quy nạp với $n$ số $a_1, a_2, …, a_{n-1}, |a_n-a_{n+1}|$ ta thấy $a_1 + …+a_{n+1}$ chẵn nên $a_1 + …+a_{n-1} + |a_n – a_{n+1}|$ chẵn.
    • Suy ra tồn tại số có dạng $\pm a_1 \pm a_2 … \pm |a_{n}-a_{n+1}| = \pm a_1 \pm a_2 … \pm a_{n+1}$ bằng 0.

 

Ví dụ 4. (USAMO 2002) Cho tập S có 2002 phần tử, số tự nhiên $k$ thỏa $0 \leq k \leq 2^{2002}$ chứng minh rằng tồn tại cách tô màu các tập con của S bằng hai màu xanh và đỏ thỏa:
a)  Có đúng $k$ tập được tô màu đỏ.
b) Hợp của hai tập đỏ là một tập đỏ.
c) Hợp của hai tập xanh là một tập xanh.

Lời giải
  • Ta chứng minh bài toán đúng với tập $S$ có số phần tử $n$ bất kì bằng quy nạp.

    Rõ ràng bài toán đúng với $n=1$, $S=\{1\}$. Nếu $k=0$ tô màu xanh cả hai tập con. Nếu $k=1$ tô màu đỏ tập $S$, xanh tập rỗng. Nếu $k=2$ thì tô $S$ và rỗng đều màu đỏ.

  • Giả sử $S$ có $n$ phần tử thì với mọi $k$ đều tồn tại cách tô thỏa đề bài.
    Ta chứng minh bài toán đúng với $S$ có $n+1$ phần tử.
    Giả sử $S = \{1, 2, \cdots, n, n+1\}$, $0 \leq k \leq 2^{n+1}$.

    • Nếu $k \leq 2^n$.Theo giả thiết quy nạp các tập con của $\{1, 2, \cdots, n\}$ được tô thỏa đề bài và các tập con chứa $n+1$ ta tô màu xanh. Rõ ràng cách tô này thỏa đề bài.
    • Nếu $ 2^n < k \leq 2^{n+1}$. Thì ta chỉ cần đổi màu các tập tô như trường hợp trên, tập nào tô màu xanh thì đổi thì màu đỏ và ngược lại. Rõ ràng thỏa đề bài.

Trên đây là một vài ví dụ khá hay về áp dụng của Quy nạp, tất nhiên còn nhiều bài tập khác cũng hấp dẫn không kém, các bạn tự tìm hiểu nhé. Chúng ta sẽ trở lại trong bài viết sau về một số dạng quy nạp thường gặp.

Bài tập rèn luyện. 

Bài 1. Lúc đầu có $n$ lít nước để vào một số lu, mỗi lu chứa đúng một số nguyên dương lít nước, ta thực hiện cách đong nước như sau: nếu số nước ở lu $A$ nhỏ hơn hoặc bằng lu $B$ thì ta có thể cho hết nước của $B$ vào $A$ một lượng bằng lượng nước lu $A$ đang có.
a) Nếu có 3 lu nước chứa lần lượt $2, 3, 8$ thì có thể đưa về hai lu không? Tại sao?
b) Nếu $n=1024 $. Chứng minh rằng ta có thể đưa số nước hết về một lu. Giả sử lu này là lu lớn, chứa đủ số nước đã có.
Bài 2. Cho $n$ đội bóng, $n$ là số chẵn lớn hơn 2.  Mỗi một lượt, các đội chia cặp để đấu với nhau một trận. Chứng minh rằng sau hai lượt thì có thể tìm được $\dfrac{n}{2}$ đội mà không có hai đội nào đấu với nhau.

Bài 3. Cho $n = 2^k$, chứng minh rằng người ta có thể chọn $n$ số nguyên từ $2n-1$ số nguyên để tổng của chúng chia hết cho $n$.

Bài 4. Gọi $x_1, x_2$ là nghiệm của phương trình $x^2 + 2017 x – 1 = 0$. Đặt $S_n = x_1^2+x_2^n$. Chứng minh rằng $S_n$ và $S_{n+1}$ là nguyên tố cùng nhau với mọi $n$.

Phương pháp chứng minh quy nạp – P1

Leave a reply

Phương pháp chứng minh quy nạp là một trong những phương pháp chứng minh quan trọng trong toán học. Trong bài viết nhỏ này dành cho các bạn THCS chúng tôi xin trình bày một số dạng của phương pháp này trong việc chứng minh các bài toán ở các lĩnh vực như: Đại số, số học, tổ hợp. Hy vọng các em có thể nắm bắt vận dụng phù hợp trong các tình huống cụ thể.

Để chứng minh một mệnh đề $P(n)$ là đúng với mọi số nguyên dương $n$, ta thực hiện các bước sau:

  • Bước cơ sở:      Chứng minh $P(1)$ đúng.
  • Bước quy nạp: Giả sử $P(n)$ đúng với $n$ nào đó (giả thiết quy nạp), chứng minh $P(n+1)$ đúng.

Ví dụ 1. Chứng minh rằng với mọi số nguyên dương $n$ thì $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

Lời giải. 

  • Khi $n=1$ rõ ràng : $1 = \dfrac{1(1+1)}{2}$.
  • Giả sử đẳng thức đúng với $n$, ta chứng minh đẳng thức đúng với $n+1$.
    • Thật vậy áp dụng giả thiết quy nạp ta có: $1+2+\cdots+n+n+1 = \dfrac{n(n+1)}{2} + n+1 = \dfrac{(n+1)(n+2)}{2}$.
  • Vậy đẳng thức đúng với mọi $n$.

Ví dụ 2. Chứng minh $n^3+11n$ chia hết cho 6 với mọi số tự nhiên $n$.

Lời giải. 

  • Khi $n = 0$ ta có $0^3+11\cdot 0 = 0$ chia hết cho 6.
  • Giả sử $n^3+11n$ chia hết cho 6, ta chứng minh $(n+1)^3+11(n+1$ chia hết cho 6.
    • Thật vậy $(n+1)^3 + 11(n+1) = n^3 + 11n + 3n(n+1)+12$.
    • Theo giả thiết quy nạp thì $n^3+11n$ chia hết cho 6, và $3n(n+1), 12$ cũng chia hết cho 6 nên $(n+1)^3+11n$ chia hết cho 6.
  • Vậy $n^3+11n$ chia hết cho 6 với mọi $n$.

Trong một số trường hợp ta cần chứng minh $P(n)$ đúng với mọi số tự nhiên $n \geq n_o$ nào đó, ta cũng làm tương tự, chỉ thay bước cơ sở thành: Chứng minh $P(n_o)$ đúng.

Ví dụ 3. Chứng minh rằng $2^n > n^2$ với mọi $n \geq 5$.

Lời giải. 

  • Khi $n = 5$ ta có $2^5 > 5^2 $( đúng)
  • Giả sử $2^n > n^2$ với $n> 5$. Ta cần chứng minh $2^{n+1} > (n+1)^2$.
    • Thật vậy áp dụng giả thiết quy nạp ta có $2^{n+1} = 2\cdot 2^n > 2n^2$.
    • Mà $2n^2 > (n+1)^2 \Leftrightarrow  n^2-2n+1 > 0$ (đúng với $n > 5$).
    • Do đó $2^{n+1} > (n+1)^2$.
  • Vậy $2^n > n^2$ với mọi $n \geq 5$.

Bài tập rèn luyện.

Bài 1. Chứng minh các đẳng thức sau:

a) $1^2 + 2^2 + …+ n^2 = \dfrac{n(n+1)(2n+1)}{6}.$

b) $1^3 + 2^3 + …+n^3 = \dfrac{n^2(n+1)^2}{4}$.

c) $\dfrac{1}{1.2.3} + \dfrac{1}{2.3.4} + …+ \dfrac{1}{n(n+1)(n+2)} = \dfrac{n(n+3)}{4(n+1)(n+2)}$.

Bài 2.

a) Chứng minh rằng $n! > 3^n$ với mọi $n > 7$.

b) Chứng minh rằng với số thực $a > – 1$, thì với mọi số tự nhiên $n$ ta có $(1+a)^n \geq 1+ na$.

Bài 3. Chứng minh rằng với mọi số tự nhiên $n$ thì:

a) $5^{2n+1}+2^{n+4} + 2^{n+1}$ chia hết cho 23.

b) Với $ n $ là số tự nhiên chẵn, chứng minh rằng: $$ (20^n+16^n-3^n-1)\ \vdots \ 323. $$

Mở đầu về lý thuyết đồ thị (P1)

Leave a reply

Đây là phần mở đầu cho một loạt bài viết về lý thuyết đồ thị và ứng dụng trong việc giải các bài toán thuộc chương trình THPT chuyên. Các chủ đề được cấu trúc như sau:

1/ Các khái niệm cơ bản: đỉnh, cạnh, bậc, đường đi, liên thông, chu trình…

2/ Cây, đường đi Euler, đường đi Hamilton.

3/ Cực trị đồ thị. Định lý Turan.

4/ Các vấn đề về cặp ghép. Định lý Hall và biến thể.

5/ Một số vấn đề khác và bài toán bổ sung.

Phần 1,2 cần đặc biệt quan tâm, vì đó là những phần căn bản đồng thời hỗ trợ rất nhiều về suy luận; trong các bài toán khó, những định lý sẵn có tỏ ra kém tác dụng. Học sinh cần đọc kỹ lý thuyết để hiểu rõ các ý tưởng và kỹ thuật chứng minh.

I. Mở đầu

Lúc còn học cấp 2, thầy giáo dạy toán đố tôi một câu như sau:

“Trong thành phố có 3 khu dân cư và 3 nhà máy. Người ta muốn xây dựng đường từ mỗi khu đến mỗi nhà máy sao cho hai con đường bất kỳ không cắt nhau. Em vẽ hình thử xem được không ?”

Nghe thì rất dễ dàng, nhưng khi vẽ thì không cách nào thực hiện được, dù tôi đã thử “uốn lượn” những con đường (bạn hãy thử xem !) Một cảm giác vừa kỳ lạ, vừa thích thú khi không chứng minh được những gì thấy ngay trước mắt.

Có một bài toán khác về “đường đi”, nhưng nguồn gốc rõ ràng hơn, như sau: ở thế kỷ 18, tại vương quốc Phổ, thành phố Königsberg có bảy cây cầu nối giữa các phần khác nhau. Khi dẫn người ngoại quốc du lịch, người dân thấy rằng thế nào cũng phải đi qua một cây cầu nào đó ít nhất hai lần. Vậy liệu có đường đi nào để tham quan được toàn bộ thành phố, đi qua toàn bộ các cây cầu chỉ một lần duy nhất hay không ?

Cả hai vấn đề đều rất “hình học”, nhưng khó có thể giải quyết bằng hình học thông thường.  Để giải quyết, ta cần một công cụ mới: lý thuyết đồ thị.

II. Các định nghĩa cơ bản

Ta bắt đầu bằng một định nghĩa tương đối hình thức nhưng chính xác.

Định nghĩa 1: Một bộ $G=(V,E)$ gồm hai tập hợp $V, E$ được gọi là một đồ thị hữu hạn (finite graph) nếu:

  • $V$ và $E$ là hai tập hợp hữu hạn.
  • Cho mỗi phần tử $e\in E$, tồn tại hai phần tử $x,y\in V$ sao cho ta có tương ứng $e=(x,y)$ hoặc $e=\{x,y\}$. Với $e=(x,y)$ hay $e=\{x,y\}$, ta gọi $e$ là cạnh (edge) của $G$ và $x,y$ là đỉnh (vertex) của cạnh $e$. Hai tương ứng trên cho biết cạnh $e$ là có hướng (từ $x$ đến $y$) hay vô hướng.

Với định nghĩa trên, giữa hai đỉnh của một đồ thị có thể xuất hiện rất nhiều cạnh, hoặc có thể tồn tại một cạnh mà hai đầu mút cùng là một đỉnh. Hơn nữa, tuỳ vào ý muốn, ta có thể phân biệt điểm đầu – điểm cuối của một cạnh hoặc không.

Định nghĩa 2: Một đồ thị gồm tất cả các cạnh vô hướng được gọi là một đồ thị vô hướng (undirected graph). Ngược lại, nếu tất cả các cạnh đều có hướng, ta gọi là đồ thị có hướng (directed graph). Đồ thị gồm cả cạnh vô hướng và có hướng được gọi là đồ thị hỗn hợp (mixed graph).

Định nghĩa 3: Một cạnh nối một đỉnh với chính nó được gọi là khuyên (loop).

Định nghĩa 4: Một đồ thị $G$ được gọi là đồ thị đơn (simple graph) nếu như $G$ không chứa khuyên và giữa hai đỉnh bất kỳ có không quá một cạnh nối. Ngược lại, nếu $G$ chứa khuyên hoặc tồn tại hai đỉnh của $G$ mà có ít nhất hai cạnh nối giữa chúng, ta gọi $G$ là đồ thị kép (multigraph).

Để tránh việc quá trừu tượng, nhu cầu biểu diễn đồ thị một cách trực quan nảy sinh rất tự nhiên. Ta thường biểu diễn đồ thị trên mặt phẳng như sau: các đỉnh được biểu diễn bởi các điểm (thường được tô đậm cho dễ thấy), còn các cạnh được biểu diễn bởi các đoạn thẳng (hoặc tổng quát hơn là đường liên tục) giữa các điểm tô đậm. Các cạnh có hướng được định hướng bằng mũi tên.

Dưới đây là một ví dụ minh họa:

Ta sẽ nhắc đến vấn đề biểu diễn đồ thị một cách chi tiết hơn ở các phần sau.

Khi tìm hiểu về đồ thị, dĩ nhiên ta quan tâm đến cấu trúc và các mối liên hệ của đỉnh – cạnh. Một số khái niệm và mối liên hệ cơ bản về các đối tượng đó được trình bày ở phần tiếp theo như sau:

Định nghĩa 5: Với đồ thị $G$, nếu $u$ là cạnh có hai đỉnh là $x,y$, ta nói rằng cạnh $u$ kề (incident) với hai đỉnh $x,y$. Ta cũng nói rằng $x,y$ là hai đỉnh kề nhau.

Định nghĩa 6: Với đồ thị $G$, bậc (degree) của đỉnh $v$ là tổng của số cạnh kề $v$ và hai lần số khuyên có đỉnh là $v$. Ta ký hiệu bậc của $v$ trong $G$ bởi $d_G(v)$. Nếu không xảy ra nhầm lẫn, ta có thể viết là $d(v)$ hay $\deg(v)$.

Có thể hình dung trực quan qua biểu diễn đồ thị như sau: nếu xem mỗi cạnh là một sợi dây, số “đầu dây” “cắm” vào đỉnh $u$ chính là bậc của $u$. Bạn đọc hãy chứng minh các kết quả sau:

Định lý 1: Cho đồ thị $G(V,E)$. Khi đó $\sum_{v\in V}deg(v)=2|E|$. Từ đó trong một đồ thị bất kỳ, số đỉnh có bậc lẻ luôn là số chẵn.

Định lý 2: Nếu $G$ là đồ thị đơn có hướng, gọi $\deg^+(v)$ và $\deg^-(v)$ lần lượt là số cạnh xuất phát và kết thúc tại $v$. Khi đó $\deg^+(v)+\deg^-(v)=\deg(v)$.

Với đồ thị $G(V,E)$, ký hiệu bậc lớn nhất của $G$ là $\Delta(G)=\max \{\deg(v)\mid v\in V\}$ và bậc nhỏ nhất của $G$ là $\delta(G)=\min \{\deg(v)\mid v\in V\}$.

Định nghĩa 7: Một đỉnh được gọi là đỉnh cô lập (isolated vertex) nếu như có bậc bằng 0, và được gọi là đỉnh treo (pendant vertex / leaf vertex) nếu có bậc bằng $1$.

(còn tiếp phần 2)