Đồ thị trong toán học không phải là biểu đồ đường hay biểu đồ cột, mà là một tập các đỉnh (chấm) nối với nhau bằng các cạnh (đường). Bậc của một đỉnh là số cạnh đi ra từ nó. Chỉ với ba khái niệm đó, người ta mô tả được bản đồ xe buýt, mạng bạn bè, sơ đồ điện, quan hệ giữa các trang web — và giải những bài toán thực tế mà không cần một con số đo đạc nào.
Ba khái niệm nền
- Đỉnh (vertex): một vật, một nơi, một người. Ví dụ: các bến xe buýt, các học sinh trong lớp, các thành phố.
- Cạnh (edge): một mối nối giữa hai đỉnh. Ví dụ: tuyến xe nối hai bến, hai học sinh là bạn thân, con đường nối hai thành phố.
- Bậc (degree): số cạnh gặp nhau ở một đỉnh. Bến xe có 4 tuyến đi qua là đỉnh bậc 4.
Điều quan trọng: trong đồ thị, vị trí và hình dáng không quan trọng. Vẽ đỉnh ở đâu, cạnh cong hay thẳng, dài hay ngắn — đều là cùng một đồ thị, miễn là các cặp nối với nhau không đổi. Bản đồ tàu điện ngầm ở nhiều thành phố là ví dụ đẹp: nó vẽ sai khoảng cách thật, nhưng đúng thứ tự ga và chỗ đổi tuyến — đúng thứ hành khách cần.
Định lý bắt tay
Trong một bữa tiệc, mỗi người bắt tay một số người. Cộng số lần bắt tay của từng người lại, kết quả luôn là số chẵn. Vì sao? Mỗi cái bắt tay có hai người, được đếm hai lần.
Trong ngôn ngữ đồ thị: tổng bậc của mọi đỉnh bằng hai lần số cạnh. Hệ quả bất ngờ: số người bắt tay một số lẻ lần luôn là số chẵn. Không bao giờ có một bữa tiệc mà đúng ba người bắt tay số lẻ lần. Đây là lý do số điểm lẻ trong một hình vẽ luôn chẵn.
Các loại đồ thị hay gặp
| Loại | Đặc điểm | Ví dụ đời thường |
|---|---|---|
| Vô hướng | Cạnh không có chiều | Quan hệ bạn bè: A là bạn B thì B là bạn A |
| Có hướng | Cạnh có mũi tên | Đường một chiều; theo dõi ai trên mạng xã hội |
| Có trọng số | Mỗi cạnh có một con số | Đường đi kèm số km hoặc số phút |
| Cây | Liên thông, không có vòng | Gia phả, sơ đồ thư mục máy tính |
| Đầy đủ | Mọi cặp đỉnh đều nối | Giải đấu vòng tròn: ai cũng gặp ai |
| Hai phía | Đỉnh chia hai nhóm, cạnh chỉ nối khác nhóm | Học sinh và câu lạc bộ học sinh tham gia |
Đường đi, chu trình, liên thông
Đường đi là một dãy đỉnh nối nhau bằng cạnh: từ nhà → ngã tư → trường. Chu trình là đường đi quay về chỗ xuất phát. Đồ thị liên thông nếu từ đỉnh nào cũng đi tới mọi đỉnh khác được.
Hai kiểu đường đi nổi tiếng:
- Đường đi Euler: đi qua mọi cạnh đúng một lần. Có quy tắc đơn giản: đếm đỉnh bậc lẻ (0 hoặc 2 là được).
- Đường đi Hamilton: đi qua mọi đỉnh đúng một lần. Nghe giống, nhưng khó hơn nhiều — không có quy tắc đơn giản nào để biết có hay không. Đây là gốc của bài toán người du lịch.
Sự chênh lệch giữa hai bài toán "na ná" này là một trong những bài học sâu sắc nhất của toán học: đổi một chữ trong đề, bài toán từ dễ thành cực khó.
Biểu diễn đồ thị trên giấy và trong máy
Trên giấy, ta vẽ chấm và đường. Trong máy tính, người ta thường lưu đồ thị theo hai cách:
- Danh sách kề: với mỗi đỉnh, ghi danh sách các đỉnh nối với nó. "Bến A: B, C, F." Gọn khi đồ thị thưa.
- Ma trận kề: một bảng vuông, hàng và cột là các đỉnh, ô ghi 1 nếu hai đỉnh nối nhau, 0 nếu không. Tiện khi đồ thị dày.
Học sinh có thể thử: vẽ đồ thị bạn bè của năm người trong nhóm, rồi lập ma trận kề. Đường chéo chính toàn số 0 (không ai là bạn của chính mình), và bảng đối xứng qua đường chéo (vì tình bạn hai chiều).
Đồ thị quanh ta
- Bản đồ dẫn đường: giao lộ là đỉnh, đoạn phố là cạnh, thời gian đi là trọng số.
- Mạng điện, nước: trạm và nút là đỉnh, đường dây, đường ống là cạnh.
- Mạng xã hội: người là đỉnh, quan hệ là cạnh.
- Trang web: mỗi trang là đỉnh, mỗi liên kết là cạnh có hướng. Các công cụ tìm kiếm từng dùng cấu trúc này để đánh giá trang nào quan trọng.
- Phân tử hoá học: nguyên tử là đỉnh, liên kết là cạnh.
- Kế hoạch công việc: việc là đỉnh, "việc này phải xong trước việc kia" là cạnh có hướng.
Góc nhìn hôm nay: vẽ đồ thị của chính mình
Một bài tập năm phút: vẽ các nơi bạn hay đến trong tuần (nhà, trường hoặc chỗ làm, chợ, nhà ông bà, quán quen) thành đỉnh. Nối hai nơi nếu bạn thường đi thẳng giữa chúng. Ghi số phút lên mỗi cạnh. Bạn vừa vẽ một đồ thị có trọng số. Nhìn vào đó, hỏi: nơi nào có bậc cao nhất (trung tâm cuộc sống của bạn)? Có vòng nào đi từ nhà, qua ba nơi rồi về nhà không? Bắt đầu từ những câu hỏi như thế, các nhà toán học đã xây nên cả một ngành.
Câu hỏi thường gặp
Đồ thị trong toán học là gì?
Là một tập các đỉnh nối với nhau bằng các cạnh, dùng để mô tả quan hệ nối giữa các vật. Nó khác với biểu đồ đường hay biểu đồ cột dùng để vẽ số liệu.
Bậc của một đỉnh là gì?
Là số cạnh gặp nhau tại đỉnh đó. Một bến xe có bốn tuyến đi qua là đỉnh bậc bốn; một đầu mút cụt là đỉnh bậc một.
Định lý bắt tay nói gì?
Tổng bậc của mọi đỉnh luôn bằng hai lần số cạnh, nên luôn là số chẵn. Vì vậy số đỉnh có bậc lẻ trong bất kỳ đồ thị nào cũng luôn là số chẵn.
Đườ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 và có quy tắc đơn giản để kiểm tra. Đường đi Hamilton đi qua mọi đỉnh đúng một lần, khó hơn nhiều và không có quy tắc đơn giản.
Lý thuyết đồ thị được dùng ở đâu?
Trong bản đồ dẫn đường, thiết kế mạng điện và nước, mạng xã hội, công cụ tìm kiếm, hoá học, xếp lịch và lập kế hoạch công việc.