TOÁN 11–12 · LÝ THUYẾT ĐỒ THỊ — Chỉ giữ "ai nối với ai": bậc, liên thông, Euler, Hamilton, cây khung và đường đi ngắn nhất
Bài khái niệm lí thuyết đồ thị (chuyên đề Toán 11): đỉnh, cạnh, bậc và bổ đề bắt tay; đường đi, chu trình, liên thông; đường đi và chu trình Euler; chu trình…
TOÁN 11–12 · LÝ THUYẾT ĐỒ THỊ · LUKATO AI · BÀI KHÁI NIỆM
Chỉ giữ "ai nối với ai": đỉnh, cạnh và những câu hỏi về đường đi
Bậc và bổ đề bắt tay, liên thông, đi hết mọi cạnh (Euler), thăm hết mọi đỉnh (Hamilton), cây khung, đường đi ngắn nhất theo kiểu "sóng lan", và ranh giới giữa bài toán dễ với bài toán khó
Bản đồ tàu điện ngầm vẽ sai hết khoảng cách: ga xa vẽ gần, đường cong vẽ thẳng. Vậy mà hành khách vẫn đi đúng, vì bản đồ giữ lại đúng một thứ cần thiết: ga nào nối với ga nào . Toán học gọi thứ còn lại ấy là một đồ thị . Bài này cho thấy chỉ với "ai nối với ai", ta đã trả lời được những câu hỏi rất thật: có đi qua mọi đoạn đường đúng một lần được không, có ghé thăm mọi điểm đúng một lần được không, đường nào ngắn nhất, và vì sao có câu hỏi trả lời trong chớp mắt còn có câu hỏi làm khó mọi máy tính. Có sơ đồ, câu "em thử xem" và ba phòng thí nghiệm. Mọi tình huống và con số tự đặt đều là hư cấu.
12 SƠ ĐỒ TỰ DỰNG 3 PHÒNG THÍ NGHIỆM THUẦN KHÁI NIỆM 8 CÂU TRẮC NGHIỆM TỰ SOẠN
BẢN ĐỒ BÀI
Bản đồ tàu điện ngầm: bỏ hình dáng, giữ kết nối
Hãy giữ trong đầu một tấm bản đồ tàu điện ngầm suốt bài. Mỗi ga là một đỉnh , mỗi chặng nối thẳng hai ga là một cạnh . Độ dài, độ cong, vị trí trên giấy đều bị bỏ đi. Câu hỏi trung tâm của bài: chỉ với thông tin "ai nối với ai", ta trả lời được những gì, và câu hỏi nào dễ, câu hỏi nào khó?
Vuốt ngang để xem hết sơ đồ
Hình 1. Bản đồ bài: từ bản đồ thật (đường cong, sông, khoảng cách) chỉ giữ lại kết nối để được một đồ thị; sáu mục của bài là sáu cách đọc đồ thị ấy.
Câu hỏi · Đọc "ai nối với ai" thế nào? · Ở mục
Một nhóm 7 bạn, có thể nào mỗi bạn quen đúng 3 bạn khác trong nhóm? · Cộng các bậc: tổng luôn bằng 2 × số cạnh · 1
Mạng lưới có "đứt" thành nhiều mảnh không? Bao nhiêu cạnh thì chắc chắn liền một khối? · Thành phần liên thông; thêm một cạnh thì chuyện gì xảy ra · 2
Xe quét đường có đi qua mỗi đoạn phố đúng một lần được không? · Đếm số đỉnh bậc lẻ (định lí Euler) · 3
Người giao hàng có ghé mỗi điểm đúng một lần rồi về được không? · Chu trình Hamilton: không có điều kiện gọn như Euler · 4
Nối mọi trạm bằng ít đoạn nhất; đi từ ga này tới ga kia nhanh nhất? · Cây khung; đường đi ngắn nhất bằng "sóng lan" (Dijkstra) · 5
Vì sao có câu hỏi máy trả lời tức thì, có câu hỏi thử mãi không hết? · Tồn tại hay tối ưu; dễ hay khó; bùng nổ tổ hợp · 6
Vuốt ngang để xem hết bảng
Công cụ A · Đếm hai lần
Đếm đầu cạnh theo từng đỉnh rồi theo từng cạnh: tổng các bậc = 2 × số cạnh.
Công cụ B · Đỉnh lẻ và liên thông
Đi hết mọi cạnh đúng một lần ⇔ các cạnh liền một khối và có 0 hoặc 2 đỉnh bậc lẻ.
Công cụ C · Sóng lan
Chốt dần các đỉnh theo khoảng cách tăng dần; cập nhật nhãn d(u) bằng min(d(u), d(v) + w).
Giả định của bài (dùng suốt bài). (a) Đồ thị hữu hạn, vô hướng : cạnh không có chiều. (b) Mặc định là đơn đồ thị : không có khuyên (cạnh nối một đỉnh với chính nó), không có hai cạnh cùng nối một cặp đỉnh; khi cần cạnh bội (như bài toán bảy cây cầu ở mục 3) bài ghi rõ "đa đồ thị". (c) Trọng số (độ dài, thời gian) luôn không âm. (d) Tên gọi "đường đi", "chu trình" có thể khác nhau đôi chút giữa các sách; bài nêu định nghĩa ngay khi dùng, em luôn đọc định nghĩa trước. (e) Lí thuyết đồ thị thuộc chuyên đề học tập Toán 11 (chương trình 2018): khái niệm cơ bản, đường đi Euler và Hamilton, bài toán đường đi ngắn nhất. Phần vượt ngoài chuyên đề mang nhãn MỞ RỘNG .
Về chữ "hư cấu". Mọi mạng lưới, số trạm, số đường nối, trọng số (phút, km) và tình huống mẫu trong bài đều do bài tự đặt, được kiểm bằng máy tính, và mang nhãn hư cấu . Các định lí, định nghĩa và dữ kiện lịch sử (bài toán bảy cây cầu) là thật. Thư viện đã có một bài riêng về trải phẳng đa diện và đồ thị Euler; ở đây chỉ dựng nền khái niệm, không lặp kĩ thuật của bài ấy.
MỤC 1 · ĐỈNH, CẠNH, BẬC
Mỗi cái bắt tay có hai bàn tay
Một đồ thị chỉ có hai loại thành phần: các đỉnh và các cạnh nối từng cặp đỉnh. Từ hai thứ đơn sơ ấy đã có một định lí đầu tiên rất mạnh, chứng minh chỉ bằng một ý: đếm cùng một thứ theo hai cách.
1.1 Đồ thị là gì, và cái gì KHÔNG thuộc đồ thị
Một đồ thị G gồm một tập đỉnh V và một 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 . Kí hiệu: |V| = n là số đỉnh, |E| = m là số cạnh. Đỉnh có thể là ga tàu, người, trạm phát sóng, môn thi; cạnh có thể là chặng tàu, quan hệ quen biết, đường cáp, "hai môn có chung thí sinh".
Tên gọi · Nghĩa · Ví dụ trong đời sống (hư cấu)
Đơn đồ thị · Không có khuyên, mỗi cặp đỉnh có nhiều nhất một cạnh · Mạng quen biết: hai người hoặc quen, hoặc không
Đa đồ thị · Cho phép nhiều cạnh nối cùng một cặp đỉnh (cạnh bội) · Hai bờ sông nối bằng hai cây cầu khác nhau
Khuyên · Cạnh nối một đỉnh với chính nó · Một tuyến xe buýt vòng quanh rồi về đúng bến cũ
Đồ thị có hướng · Mỗi cạnh có chiều (gọi là cung) · Đường một chiều; "A theo dõi B" trên mạng xã hội
Đồ thị đầy đủ K n · n đỉnh, mọi cặp đỉnh đều kề nhau · n kho hàng, kho nào cũng có đường thẳng tới mọi kho khác
Vuốt ngang để xem hết bảng
Đồ thị không phải là hình vẽ. Cùng một đồ thị có vô số cách vẽ: đặt đỉnh ở đâu, nét thẳng hay cong, dài hay ngắn đều không quan trọng. Chỗ hai nét vẽ cắt nhau không phải là đỉnh, vì không có ga nào ở đó; giống như cầu vượt bắc ngang qua đường bên dưới. Muốn biết hai hình vẽ có cùng một đồ thị hay không, hãy so danh sách cạnh , đừng so hình.
Vuốt ngang để xem hết sơ đồ
Hình 2. Hai hình vẽ của cùng một đồ thị đầy đủ K 4 : hình trái có hai nét cắt nhau (giao điểm không phải đỉnh), hình phải không có nét nào cắt và chia mặt phẳng thành 4 miền.
MỞ RỘNG Đồ thị phẳng và công thức Euler V − E + F = 2. Một đồ thị vẽ được trên mặt phẳng mà không có hai cạnh nào cắt nhau gọi là đồ thị phẳng . Nếu đồ thị phẳng liên thông được vẽ như vậy, với V đỉnh, E cạnh và F miền (đếm cả miền ngoài vô hạn) thì luôn có V − E + F = 2. Với K 4 ở hình 2: 4 − 6 + 4 = 2. Hệ quả: một đơn đồ thị phẳng có V ≥ 3 đỉnh thì E ≤ 3V − 6. Đồ thị K 5 có V = 5, E = 10 > 3 · 5 − 6 = 9, nên không thể vẽ phẳng ; dù vậy nó vẫn là một đồ thị hoàn toàn bình thường, chỉ là mọi hình vẽ của nó đều phải có chỗ cắt nhau.
1.2 Bậc của đỉnh và bổ đề bắt tay
Bậc của đỉnh v, kí hiệu deg(v), là số cạnh có một đầu ở v (một khuyên tính 2, vì cả hai đầu đều ở v). Trong đơn đồ thị n đỉnh, bậc của mỗi đỉnh nằm trong khoảng từ 0 tới n − 1.
Bổ đề bắt tay. Trong mọi đồ thị, tổng các bậc bằng hai lần số cạnh: deg(v 1 ) + deg(v 2 ) + … + deg(v n ) = 2m.
Vì sao? Hãy đếm số "đầu cạnh" (trong hình 3 là các chấm cam). Đếm theo đỉnh: mỗi đỉnh v có đúng deg(v) đầu cạnh, cộng lại được tổng các bậc. Đếm theo cạnh: mỗi cạnh có đúng hai đầu, được 2m. Cùng một số lượng chấm, đếm hai cách phải ra cùng một kết quả. Tên gọi đến từ hình ảnh một buổi gặp mặt: mỗi cái bắt tay cần đúng hai bàn tay, nên tổng số "lần bắt tay" mà mọi người kể lại luôn gấp đôi số cái bắt tay.
Vuốt ngang để xem hết sơ đồ
Hình 3. Đồ thị 6 đỉnh, 7 cạnh: mỗi cạnh có hai đầu (chấm cam). Đếm theo đỉnh được 3 + 2 + 3 + 3 + 2 + 1 = 14; đếm theo cạnh được 7 × 2 = 14. Bốn đỉnh bậc lẻ: một số chẵn.
Hệ quả 1: số đỉnh bậc lẻ luôn là số chẵn. Tổng các bậc là số chẵn 2m. Tổng các bậc chẵn đã là số chẵn, nên phần còn lại (tổng các bậc lẻ) cũng chẵn; mà tổng của các số lẻ chỉ chẵn khi có một số chẵn số hạng. Ví dụ (hư cấu): một nhóm 7 bạn không thể nào mỗi bạn quen đúng 3 bạn khác trong nhóm, vì khi đó tổng các bậc là 7 × 3 = 21, một số lẻ.
Hệ quả 2: số cạnh của K n . Trong K n , mỗi đỉnh bậc n − 1, nên 2m = n(n − 1) và m = n(n − 1)/2. Chẳng hạn K 6 có 15 cạnh: đó chính là 15 nút cạnh có thể bật trong Phòng A. Đây cũng là số cạnh tối đa của một đơn đồ thị n đỉnh.
Hệ quả 3 (thú vị). Trong một đơn đồ thị có n ≥ 2 đỉnh, luôn có hai đỉnh cùng bậc. Lí do: các bậc nằm trong 0, 1, …, n − 1 (n giá trị), nhưng 0 và n − 1 không thể cùng xuất hiện (một đỉnh nối với mọi đỉnh khác thì không đỉnh nào bậc 0). Vậy n đỉnh chỉ có n − 1 giá trị bậc khả dĩ, theo nguyên lí Dirichlet phải có hai đỉnh trùng bậc. Trong mọi buổi gặp mặt, luôn có hai người quen số người bằng nhau.
Chốt ý mục 1: tổng các bậc = 2 × số cạnh ⇒ số đỉnh bậc lẻ luôn chẵn Đồ thị chỉ là "ai nối với ai": cách vẽ, độ dài, chỗ cắt nhau không thuộc đồ thị. Đơn đồ thị n đỉnh có nhiều nhất n(n − 1)/2 cạnh, đạt khi là K n .
Có đồ thị nào (hư cấu, cho phép cả cạnh bội) gồm 5 đỉnh với các bậc 4, 4, 3, 2, 2 không?
Cộng các bậc trước khi thử vẽ.
Giải thích. Tổng các bậc là 4 + 4 + 3 + 2 + 2 = 15, một số lẻ, trong khi tổng các bậc của mọi đồ thị phải bằng 2m (số chẵn). Vậy không tồn tại, dù cho phép cạnh bội hay khuyên. Không cần thử vẽ: phép cộng đã trả lời.
MỤC 2 · ĐƯỜNG ĐI, CHU TRÌNH, LIÊN THÔNG
Những hòn đảo trong mạng lưới
Trên bản đồ tàu, câu hỏi đầu tiên của hành khách là: từ ga này có tới được ga kia không? Câu hỏi ấy chia mọi đồ thị thành những "hòn đảo". Và có một quan sát nhỏ mà cả mục 5 sẽ dựa vào: mỗi cạnh mới chỉ có thể làm một trong hai việc.
2.1 Đường đi và chu trình
Một đường đi từ u tới v là một dãy đỉnh u = v 0 , v 1 , …, v k = v, trong đó hai đỉnh liên tiếp luôn kề nhau; số cạnh k là độ dài (số chặng) của đường đi. Đường đi không lặp lại đỉnh nào gọi là đường đi đơn (có sách gọi là đường đi sơ cấp, và dùng chữ "đơn" cho đường không lặp cạnh). Một chu trình là đường đi khép kín (v k = v 0 ; k ≥ 3 với đơn đồ thị, còn đa đồ thị có thể có chu trình 2 cạnh qua hai cạnh bội) không đi lại cạnh nào; chu trình không lặp đỉnh nào (trừ đỉnh đầu trùng đỉnh cuối) gọi là chu trình đơn .
Trên đồ thị 5 ga ở hình 1 (các cạnh 1–2, 2–3, 1–4, 2–5, 4–5): 3 – 2 – 5 là đường đi độ dài 2; 1 – 2 – 5 – 4 – 1 là một chu trình độ dài 4; còn 1 – 3 không phải đường đi vì 1 và 3 không kề nhau (phải đi 1 – 2 – 3).
2.2 Liên thông và thành phần liên thông
Đồ thị liên thông nếu giữa hai đỉnh bất kì luôn có đường đi. Nếu không, nó tách thành các thành phần liên thông : những "hòn đảo" mà bên trong mỗi đảo đi lại được, còn giữa hai đảo thì không có cạnh nào. Một đỉnh không có cạnh nào (bậc 0) là một đảo riêng.
Vuốt ngang để xem hết sơ đồ
Hình 4. Trên: một đồ thị 8 đỉnh, 7 cạnh nhưng có 3 thành phần liên thông; thêm một cạnh chỉ có hai khả năng. Dưới: 6 đỉnh, 10 cạnh vẫn rời (5 đỉnh nối đầy đủ cộng một đỉnh lẻ loi), trong khi 6 đỉnh, 5 cạnh đã liên thông.
Quan sát then chốt: thêm một cạnh uv thì chỉ có hai khả năng. (a) u và v ở hai đảo khác nhau: cạnh mới nối hai đảo làm một, số thành phần giảm đúng 1. (b) u và v cùng một đảo: đã có sẵn đường đi từ u tới v, cạnh mới khép đường ấy thành một chu trình, số thành phần giữ nguyên. Không có khả năng thứ ba.
Hệ quả. Xuất phát từ n đỉnh rời nhau (n thành phần), thêm lần lượt m cạnh, mỗi cạnh giảm số thành phần nhiều nhất 1. Vậy đồ thị n đỉnh, m cạnh có ít nhất n − m thành phần; nói cách khác, đồ thị có k thành phần thì m ≥ n − k . Riêng đồ thị liên thông (k = 1) cần ít nhất n − 1 cạnh .
2.3 Nhiều cạnh có chắc liên thông không?
Điều kiện "m ≥ n − 1" chỉ là điều kiện cần . Một đồ thị có thể dồn rất nhiều cạnh vào một góc mà vẫn bỏ rơi một đỉnh: lấy n − 1 đỉnh nối đầy đủ với nhau (K n−1 , có (n − 1)(n − 2)/2 cạnh) và để một đỉnh lẻ loi. Ngược lại, có thể chứng minh: đơn đồ thị n đỉnh có nhiều hơn (n − 1)(n − 2)/2 cạnh thì chắc chắn liên thông . Lí do: nếu đồ thị rời thành hai nhóm a và b đỉnh (a + b = n, không có cạnh giữa hai nhóm), số cạnh tối đa là a(a − 1)/2 + b(b − 1)/2, và biểu thức này lớn nhất khi một nhóm chỉ có 1 đỉnh.
Số đỉnh n · 4 · 5 · 6 · 7
Ít nhất để có thể liên thông: n − 1 cạnh · 3 · 4 · 5 · 6
Nhiều nhất mà vẫn có thể rời: (n − 1)(n − 2)/2 cạnh (máy vét cạn mọi đơn đồ thị xác nhận) · 3 · 6 · 10 · 15
Chắc chắn liên thông khi số cạnh ≥ · 4 · 7 · 11 · 16
Vuốt ngang để xem hết bảng
Khoảng giữa hai dòng đầu là "vùng không chắc": số cạnh như nhau, đồ thị có thể liền, có thể rời. Muốn biết chắc, phải nhìn cấu trúc (đi thử từ một đỉnh xem chạm được bao nhiêu đỉnh), không chỉ đếm cạnh.
Chốt ý mục 2: thêm một cạnh thì hoặc nối hai đảo (số thành phần giảm 1), hoặc khép một chu trình Đồ thị n đỉnh có k thành phần thì có ít nhất n − k cạnh; liên thông cần ít nhất n − 1 cạnh. Nhưng nhiều cạnh chưa chắc liên thông: chỉ khi vượt (n − 1)(n − 2)/2 cạnh (đơn đồ thị) mới chắc chắn.
Một mạng 10 trạm (hư cấu) có 36 đường nối, không có hai đường nối cùng một cặp trạm. Có chắc mọi trạm thông nhau không?
So 36 với (n − 1)(n − 2)/2 khi n = 10.