Đâ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)