Trong toán rời rạc, đồ thị là một cấu trúc gồm các đỉnh và các cạnh nối từng cặp đỉnh, dùng để mô tả quan hệ giữa các đối tượng; nó không phải đồ thị hàm số y theo x. Đỉnh có thể là thành phố, con người, trang web, trạm biến áp; cạnh là con đường, quan hệ quen biết, liên kết, đường dây. Lý thuyết đồ thị nghiên cứu những tính chất chỉ phụ thuộc vào việc cái gì nối với cái gì, bỏ qua vị trí và hình dáng.
Ngành này thường được kể là bắt đầu từ năm 1736, khi Leonhard Euler giải bài toán bảy cây cầu ở thành phố Königsberg. Bài đi qua các khái niệm nền, định lý bắt tay, lời giải của Euler, các loại đồ thị hay gặp, cách lưu đồ thị trên máy tính, và cách dùng AI để luyện mà không bị dẫn sai bởi một hình vẽ tưởng tượng.
Đỉnh, cạnh, bậc: bộ từ vựng tối thiểu
Một đồ thị G gồm tập đỉnh V và tập cạnh E, mỗi cạnh nối hai đỉnh. Hai đỉnh có cạnh nối gọi là kề nhau. Bậc của một đỉnh, ký hiệu deg(v), là số cạnh chạm vào đỉnh đó. Đường đi là dãy đỉnh liên tiếp kề nhau; chu trình là đường đi quay về đỉnh xuất phát. Đồ thị liên thông khi giữa hai đỉnh bất kỳ luôn có đường đi.
Ví dụ giả định: một nhóm năm người An, Bình, Chi, Dũng, Em; cạnh nối hai người đã từng làm chung dự án. An làm chung với Bình, Chi, Dũng; Bình làm chung với Chi; Dũng làm chung với Em. Đồ thị có năm đỉnh và năm cạnh. Bậc lần lượt là An 3, Bình 2, Chi 2, Dũng 2, Em 1. Đồ thị liên thông vì từ Em đi qua Dũng, qua An, tới được mọi người. Chu trình An, Bình, Chi, An có độ dài 3.
Cần phân biệt đồ thị đơn, giữa hai đỉnh có nhiều nhất một cạnh và không có cạnh nối một đỉnh với chính nó, với đa đồ thị, cho phép nhiều cạnh song song. Bài toán cầu Königsberg ở mục sau cần đa đồ thị, vì có những vùng đất nối với nhau bằng hai cây cầu. Hình vẽ của một đồ thị không quan trọng: hai hình trông khác hẳn nhau nhưng cùng đỉnh, cùng cách nối thì là cùng một đồ thị.
Định lý bắt tay: tổng các bậc luôn chẵn
Định lý đầu tiên của lý thuyết đồ thị: tổng bậc của mọi đỉnh bằng hai lần số cạnh. Lý do rất gọn: mỗi cạnh có hai đầu, nên khi cộng bậc của các đỉnh, mỗi cạnh được đếm đúng hai lần. Trong ví dụ năm người, tổng bậc là 3 + 2 + 2 + 2 + 1 = 10, đúng bằng 2 nhân 5 cạnh. Tên gọi đến từ hình ảnh một buổi gặp mặt: tổng số lần bắt tay mà từng người kể lại luôn gấp đôi số cái bắt tay thực sự.
Hệ quả ngay: số đỉnh bậc lẻ luôn là số chẵn. Tổng mọi bậc là số chẵn, phần đóng góp của các đỉnh bậc chẵn cũng chẵn, nên tổng các bậc lẻ phải chẵn, điều chỉ xảy ra khi số số hạng lẻ là chẵn. Hệ quả này giải ngay những câu đố dạng “có thể có một nhóm 7 người mà mỗi người quen đúng 3 người khác không?”. Câu trả lời là không, vì khi đó có 7 đỉnh bậc lẻ, một số lẻ.
Định lý bắt tay cũng là công cụ kiểm nhanh khi bạn tự đếm hoặc khi AI đưa ra một đồ thị: cộng các bậc, nếu ra số lẻ thì chắc chắn có chỗ đếm sai. Đây là kiểu kiểm tốn ít công nên làm theo thói quen, giống như kiểm tổng các cột trong bảng tính. Với đồ thị có hướng, phiên bản tương ứng là tổng bậc vào bằng tổng bậc ra và cùng bằng số cạnh.
Bảy cây cầu Königsberg: Euler giải thế nào
Thành phố Königsberg thế kỷ 18 có dòng sông chia đất thành bốn vùng: hai bờ sông và hai cù lao, nối với nhau bằng bảy cây cầu. Câu hỏi của người dân: có thể đi dạo qua mỗi cây cầu đúng một lần không? Lập luận của Euler, viết lại bằng ngôn ngữ hiện đại:
- Bỏ hết chi tiết địa lý: mỗi vùng đất thành một đỉnh, mỗi cây cầu thành một cạnh. Được một đa đồ thị bốn đỉnh, bảy cạnh.
- Đếm bậc: cù lao trung tâm nối với năm cầu, ba vùng còn lại mỗi vùng nối với ba cầu. Bậc là 5, 3, 3, 3; tổng 14, đúng bằng 2 nhân 7.
- Nhận xét then chốt: trong một cuộc đi dạo, mỗi lần đi ngang qua một vùng ở giữa hành trình, ta vào bằng một cầu và ra bằng một cầu khác, dùng hết hai cầu. Vậy mọi vùng không phải điểm đầu hay điểm cuối phải có số cầu chẵn.
- Chỉ điểm đầu và điểm cuối được phép có bậc lẻ, nên một đường đi qua mỗi cạnh đúng một lần chỉ tồn tại khi có 0 hoặc 2 đỉnh bậc lẻ. Königsberg có 4 đỉnh bậc lẻ, nên không có cách đi nào.
Chiều ngược lại, rằng đồ thị liên thông có 0 hoặc 2 đỉnh bậc lẻ thì luôn có đường đi như vậy, được chứng minh chặt chẽ muộn hơn. Ngày nay đường đi qua mọi cạnh đúng một lần gọi là đường đi Euler; nếu quay về điểm xuất phát thì gọi là chu trình Euler, tồn tại khi đồ thị liên thông và mọi đỉnh có bậc chẵn.
Ý nghĩa lớn hơn của bài toán nằm ở cách nhìn: Euler bỏ đi khoảng cách, hình dáng, chỉ giữ lại quan hệ nối, và chính sự trừu tượng hoá đó mở ra cả một ngành. Bài toán người đưa thư đi qua mọi con phố, hay xe quét đường đi hết các tuyến, đều là hậu duệ trực tiếp của câu hỏi về bảy cây cầu.
Các loại đồ thị hay gặp và ví dụ thực tế
Mỗi bài toán thực tế cần một loại đồ thị phù hợp. Chọn sai loại ngay từ đầu, ví dụ dùng đồ thị vô hướng cho đường một chiều, là lỗi mô hình hoá khó phát hiện về sau.
| Loại | Đặc điểm | Ví dụ |
|---|---|---|
| Vô hướng | Cạnh không có chiều, A nối B cũng là B nối A | Quan hệ quen biết, đường dây điện giữa hai trạm |
| Có hướng | Cạnh có chiều, đi được từ A tới B không kéo theo đi được từ B về A | Đường một chiều trong phố, quan hệ theo dõi trên mạng xã hội, môn học tiên quyết |
| Có trọng số | Mỗi cạnh mang một con số: độ dài, thời gian, chi phí | Bản đồ đường kèm số km, mạng chuyển phát kèm thời gian giao |
| Cây | Liên thông, không có chu trình; n đỉnh thì đúng n − 1 cạnh | Sơ đồ tổ chức, cây thư mục, cây gia phả theo một dòng |
| Hai phía | Đỉnh chia hai nhóm, cạnh chỉ nối giữa hai nhóm | Ứng viên và vị trí tuyển dụng, sinh viên và môn học đăng ký |
| Đầy đủ | Mọi cặp đỉnh đều nối nhau; n đỉnh có n(n − 1)/2 cạnh | Lịch thi đấu vòng tròn một lượt |
Dòng cuối cho một phép tính tiện: giải đấu vòng tròn 10 đội cần 10 nhân 9 chia 2 bằng 45 trận. Các loại có thể kết hợp: bản đồ giao thông thường là đồ thị có hướng và có trọng số. Đồ thị hai phía có một dấu hiệu nhận biết đẹp: một đồ thị là hai phía khi và chỉ khi nó không có chu trình độ dài lẻ.
Lưu đồ thị trên máy tính: ma trận kề hay danh sách kề
Có hai cách lưu chính. Ma trận kề là bảng vuông n nhân n, ô hàng i cột j bằng 1 nếu đỉnh i nối đỉnh j, bằng 0 nếu không; với đồ thị có trọng số thì ghi trọng số thay cho số 1. Danh sách kề lưu, với mỗi đỉnh, danh sách các đỉnh kề với nó. Trong ví dụ năm người, danh sách kề của An là Bình, Chi, Dũng; của Em chỉ có Dũng.
Mỗi cách mạnh ở một chỗ. Ma trận kề trả lời câu “i có nối j không” ngay lập tức, nhưng tốn n bình phương ô nhớ dù đồ thị có ít cạnh. Danh sách kề tốn bộ nhớ tỷ lệ với số đỉnh cộng số cạnh và duyệt các đỉnh kề của một đỉnh rất nhanh, nhưng kiểm một cặp cụ thể phải dò danh sách. Đồ thị thực tế như mạng đường phố hay mạng xã hội thường rất thưa: một triệu đỉnh mà mỗi đỉnh chỉ nối vài chục đỉnh khác. Khi đó ma trận kề cần một nghìn tỷ ô, gần như toàn số 0, nên danh sách kề là lựa chọn mặc định.
Ma trận kề còn có một ý nghĩa đại số đáng biết: luỹ thừa bậc k của ma trận kề cho số đường đi độ dài k giữa mọi cặp đỉnh. Đây là cầu nối giữa lý thuyết đồ thị và đại số tuyến tính, và là ý tưởng nằm sau nhiều phương pháp xếp hạng trang web hay phân tích mạng lưới. Người học AI sẽ gặp lại ý này khi đọc về mạng nơ-ron đồ thị.
Dùng AI luyện lý thuyết đồ thị: đưa danh sách cạnh, đừng tả hình
Chatbot dạng chữ không nhìn thấy hình bạn vẽ và hay mô tả sai hình nó tự tưởng tượng, nên làm việc với đồ thị qua AI an toàn nhất là qua danh sách cạnh. Quy trình:
- Chuyển hình vẽ thành danh sách cạnh trước khi hỏi, ví dụ “A–B, A–C, A–D, B–C, D–E”. Danh sách cạnh không thể bị đọc nhầm như hình vẽ.
- Câu lệnh mẫu: “Đây là danh sách cạnh của một đồ thị vô hướng. Liệt kê bậc từng đỉnh, rồi cho biết có đường đi Euler không và vì sao. Trình bày từng bước.”
- Kiểm câu trả lời bằng định lý bắt tay: tổng bậc AI liệt kê phải bằng hai lần số cạnh bạn đưa vào. Lệch là AI đếm sai.
- Nếu AI đưa ra một đường đi cụ thể, tự dò lại trên hình của mình: mỗi bước có đúng là cạnh có thật không, có cạnh nào bị đi hai lần không.
- Khi muốn xem hình, nhờ AI chuyển danh sách cạnh sang một định dạng mô tả đồ thị mà phần mềm vẽ đồ thị đọc được, rồi tự mở bằng phần mềm đó để đối chiếu.
Nếu đồ thị mô tả dữ liệu thật của đơn vị bạn, ví dụ quan hệ giữa khách hàng hay nhân viên, đổi tên người thành mã trước khi đưa vào AI. Cấu trúc đồ thị vẫn giữ nguyên, còn thông tin cá nhân thì không đi ra ngoài.
Câu hỏi thường gặp
Đồ thị trong toán rời rạc khác đồ thị hàm số thế nào?
Đồ thị hàm số là tập điểm biểu diễn quan hệ giữa x và y trên mặt phẳng toạ độ. Đồ thị trong toán rời rạc là cấu trúc gồm đỉnh và cạnh, không cần toạ độ, chỉ quan tâm cái gì nối với cái gì. Tiếng Anh phân biệt graph of a function với graph trong graph theory; tiếng Việt dùng chung một chữ nên dễ nhầm.
Cây là gì và vì sao n đỉnh thì có n − 1 cạnh?
Cây là đồ thị liên thông không có chu trình. Có thể dựng mọi cây bằng cách bắt đầu từ một đỉnh rồi lần lượt thêm từng đỉnh mới, mỗi lần nối nó với đúng một đỉnh đã có, vì nối bằng hai cạnh sẽ tạo chu trình. Thêm n − 1 đỉnh thì dùng đúng n − 1 cạnh. Lập luận này viết chặt lại chính là một chứng minh quy nạp.
Bài toán bốn màu liên quan gì tới lý thuyết đồ thị?
Định lý bốn màu nói mọi bản đồ phẳng đều tô được bằng bốn màu sao cho hai vùng chung biên khác màu. Chuyển sang đồ thị: mỗi vùng là một đỉnh, chung biên là một cạnh. Định lý được Appel và Haken chứng minh năm 1976 với sự trợ giúp của máy tính, một trong những chứng minh lớn đầu tiên cần máy kiểm hàng loạt trường hợp.
Lý thuyết đồ thị được dùng trong những ngành nào?
Rất rộng: định tuyến giao thông và mạng máy tính, xếp lịch thi tránh trùng môn bằng tô màu đồ thị, phân tích mạng xã hội, sinh học với mạng tương tác protein, hoá học với cấu trúc phân tử, và trí tuệ nhân tạo với đồ thị tri thức. Trong lập trình, các thuật toán duyệt đồ thị là nội dung gần như bắt buộc.
Đường đi Euler và đường đi Hamilton khác nhau thế nào?
Đường đi Euler đi qua mọi cạnh đúng một lần, kiểm tồn tại rất dễ bằng cách đếm số đỉnh bậc lẻ. Đường đi Hamilton đi qua mọi đỉnh đúng một lần, nghe tương tự nhưng khó hơn hẳn: chưa ai biết thuật toán hiệu quả cho mọi đồ thị, và bài toán thuộc lớp NP-đầy đủ. Hai bài toán trông gần nhau mà độ khó cách xa là một bài học hay của ngành.