Euler và bảy cây cầu Königsberg: bài toán đi dạo sinh ra lý thuyết đồ thị

Một trò đi dạo ngày Chủ nhật

Thế kỷ 18, Königsberg là một thành phố cảng thịnh vượng của nước Phổ. Dòng sông Pregel chảy qua giữa thành phố, ôm lấy hai hòn đảo, chia mặt đất thành bốn vùng: bờ Bắc, bờ Nam, đảo Kneiphof ở giữa và một hòn đảo phía Đông. Bảy cây cầu nối các vùng ấy với nhau.

Người dân thành phố truyền nhau một câu đố. Có cách nào đi dạo qua cả bảy cây cầu, mỗi cầu đúng một lần, không được lội sông, không được đi một cầu hai lần?

Nghe thì đơn giản. Bạn có thể thử ngay trên Hình 1 bên dưới: đặt ngón tay ở một vùng đất bất kỳ rồi đi. Rất nhanh, bạn sẽ thấy mình luôn bị kẹt lại với một cây cầu chưa đi mà không còn đường tới nó.

Có người bảo câu đố không có lời giải. Nhưng chẳng ai chứng minh được. Biết đâu chỉ là chưa ai thử đủ cách? Bảy cây cầu cho ra hàng nghìn thứ tự đi khác nhau, và không ai muốn thử hết.

Năm 1736, nhà toán học Leonhard Euler trả lời dứt khoát: không thể. Lý do ông đưa ra ngắn đến mức có thể giải thích cho một học sinh tiểu học. Và trên đường đi đến lý do ấy, ông lập ra một ngành toán học mới mà hôm nay chạy trong ứng dụng bản đồ trên điện thoại của bạn.

Đây là tập thứ hai trong loạt bài về các nhà toán học. Mỗi tập kể về một người và một khoảnh khắc của họ.

“Chẳng liên quan mấy tới toán học”

Khi ấy Euler chưa tới 30 tuổi, đang làm việc ở Viện Hàn lâm Khoa học Saint Petersburg nước Nga. Ông sinh ở Basel, Thụy Sĩ, và sau này trở thành một trong những nhà toán học viết nhiều nhất trong lịch sử. Tuyển tập đầy đủ các công trình của ông dài hơn 70 tập sách, phần lớn viết khi thị lực ngày một kém, và nhiều công trình được ông đọc cho người khác chép khi đã gần như mù hoàn toàn.

Bài toán bảy cây cầu đến với Euler qua thư từ. Carl Ehler, thị trưởng thành phố Danzig gần đó, viết thư nhờ ông giải câu đố, thay mặt một người bạn là giáo sư toán ở Danzig. Trong thư trả lời ngày 3 tháng 4 năm 1736, Euler tỏ ra khá hờ hững[2]:

Như ngài thấy đấy, kiểu lời giải này chẳng mấy liên quan tới toán học, và tôi không hiểu sao ngài lại mong một nhà toán học giải nó hơn là bất kỳ ai khác, vì lời giải chỉ dựa vào lý lẽ thông thường.

Euler đã nhầm về đúng một điểm: đây chính là toán học, chỉ là một loại toán học chưa có tên. Trước đó vài tháng, ông đã trình bày lời giải trước Viện Hàn lâm. Bài viết bằng tiếng Latin, có tên tạm dịch là Lời giải một bài toán thuộc hình học vị trí, được in trong tập kỷ yếu năm 1736 của Viện, dù tập sách ấy tới năm 1741 mới thực sự ra mắt[1].

“Hình học vị trí” (geometria situs) là một cái tên Leibniz đã dùng trước đó cho một loại hình học mà ông chỉ mơ hồ hình dung: hình học không quan tâm tới khoảng cách hay góc, chỉ quan tâm cái gì nối với cái gì. Euler nhận ra bài toán bảy cây cầu đúng là thuộc loại ấy.

Vứt bỏ bản đồ

Bước quan trọng nhất của Euler là bỏ đi gần như mọi thứ trên bản đồ.

Hình dạng hòn đảo không quan trọng. Chiều dài cây cầu không quan trọng. Ta đi bộ nhanh hay chậm, rẽ trái hay rẽ phải trên một vùng đất cũng không quan trọng. Thứ duy nhất ảnh hưởng tới câu trả lời là: vùng đất nào nối với vùng đất nào, bằng bao nhiêu cây cầu.

Vậy hãy thu mỗi vùng đất lại thành một chấm, và vẽ mỗi cây cầu thành một đường nối hai chấm. Bản đồ phức tạp của Königsberg biến thành bốn chấm và bảy đường:

bờ Bắc nối với đảo Kneiphof bằng hai cầu;
bờ Nam nối với đảo Kneiphof bằng hai cầu;
bờ Bắc, bờ Nam và đảo Kneiphof, mỗi nơi có một cầu sang đảo phía Đông.

Ngày nay, hình vẽ gồm chấm và đường như thế được gọi là một đồ thị (graph). Chấm là đỉnh, đường là cạnh. Từ “đồ thị” ở đây không phải đồ thị hàm số trong sách giáo khoa, mà là một mạng lưới. Euler không dùng chữ ấy và cũng không vẽ hình theo cách này. Ông lập luận bằng chữ cái và bảng đếm. Nhưng ý tưởng thu gọn thế giới thành một mạng lưới là của ông, và nó là điểm khởi đầu của lý thuyết đồ thị.

Một lý lẽ chỉ cần đếm

Giờ hãy nhìn một vùng đất bất kỳ mà ta đi ngang qua trong chuyến dạo, tức không phải điểm xuất phát, cũng không phải điểm kết thúc. Mỗi lần ghé qua nó, ta dùng đúng hai cây cầu: một cầu để vào, một cầu để ra. Ghé ba lần thì dùng sáu cây cầu. Vì mỗi cầu chỉ được đi một lần, tổng số cầu chạm vào vùng đất ấy phải là một số chẵn.

Số cây cầu chạm vào một vùng đất được gọi là bậc của đỉnh ấy. Lý lẽ trên nói rằng: trong một chuyến đi qua mỗi cầu đúng một lần, mọi vùng đất ở giữa hành trình đều phải có bậc chẵn. Chỉ có điểm xuất phát và điểm kết thúc là được phép có bậc lẻ, vì ở đó có một cây cầu “đi ra” không cần “đi vào”, hoặc ngược lại.

Vậy đếm bậc của Königsberg:

Vùng đất	Số cầu (bậc)
Đảo Kneiphof	5
Bờ Bắc	3
Bờ Nam	3
Đảo phía Đông	3

Cả bốn vùng đất đều có bậc lẻ. Nhưng một chuyến đi chỉ có một điểm xuất phát và một điểm kết thúc, nên tối đa hai vùng bậc lẻ. Bốn vùng lẻ thì chắc chắn có ít nhất hai vùng nằm “ở giữa” hành trình mà lại có bậc lẻ, điều không thể xảy ra. Câu đố vô nghiệm. Không cần thử một thứ tự đi nào cả.

Euler phát biểu kết luận tổng quát cho mọi mạng lưới cầu, ở mọi thành phố:

Nếu có nhiều hơn hai vùng đất bậc lẻ: không có cách đi nào.
Nếu có đúng hai vùng đất bậc lẻ: có cách đi, nhưng phải xuất phát ở một vùng lẻ và kết thúc ở vùng lẻ còn lại.
Nếu không có vùng đất bậc lẻ nào: có cách đi, và có thể quay về đúng chỗ xuất phát.

Euler chứng minh rõ ràng chiều “không thể”: điều kiện bậc chẵn là bắt buộc. Chiều ngược lại, rằng hễ thỏa điều kiện thì chắc chắn tìm được cách đi, ông khẳng định nhưng không chứng minh đầy đủ. Phải hơn một thế kỷ sau, nhà toán học Đức Carl Hierholzer mới chứng minh trọn vẹn. Công trình của ông được in năm 1873, sau khi ông đã qua đời. Ngày nay, một đường đi qua mỗi cạnh đúng một lần được gọi là đường đi Euler.

Hai đồ thị bốn đỉnh. Bên trái là Königsberg năm 1736: đảo Kneiphof bậc 5, bờ Bắc, bờ Nam và đảo phía Đông mỗi nơi bậc 3; cả bốn đỉnh viền vàng vì bậc lẻ, tiêu đề ghi không có đường đi. Bên phải thêm một cầu thứ tám nối thẳng bờ Bắc và bờ Nam: bờ Bắc và bờ Nam thành bậc 4 viền xanh, chỉ còn đảo Kneiphof và đảo phía Đông bậc lẻ, tiêu đề ghi có đường đi. — Hình 1. Königsberg thu gọn thành đồ thị: mỗi vùng đất là một đỉnh (số bên trong là bậc), mỗi cây cầu là một cạnh. Viền vàng là đỉnh bậc lẻ. Bên trái: bốn đỉnh lẻ nên không có cách đi. Bên phải: thêm một cầu giả định nối hai bờ thì chỉ còn hai đỉnh lẻ, và đường đi tồn tại. Hình được vẽ bằng đoạn code ở mục Tự tay đi qua các cây cầu, gần cuối bài.

Cây cầu thứ tám

Quy tắc của Euler còn cho biết cách sửa thành phố. Chỉ cần xây thêm một cây cầu nối thẳng bờ Bắc với bờ Nam (bên phải Hình 1): bờ Bắc và bờ Nam lên bậc 4, chẵn; chỉ còn đảo Kneiphof và đảo phía Đông bậc lẻ. Theo quy tắc số 2, giờ đã có cách đi qua cả tám cây cầu, xuất phát ở một hòn đảo và kết thúc ở hòn đảo kia. Ví dụ:

Kneiphof → đảo Đông → bờ Nam → bờ Bắc → Kneiphof → bờ Nam → Kneiphof → bờ Bắc → đảo Đông.

Đếm lại: tám bước, tám cây cầu, mỗi cầu đúng một lần.

Thật ra Königsberg đã “được sửa”, nhưng không phải bằng một cây cầu mới. Năm 1944, thành phố bị ném bom nặng nề trong Thế chiến II, và hai trong bảy cây cầu bị phá hủy. Sau chiến tranh, thành phố thuộc về Liên Xô và đổi tên thành Kaliningrad, nay là một vùng lãnh thổ của Nga. Hai cây cầu cũ khác về sau bị dỡ bỏ. Hôm nay vùng sông ấy còn năm cây cầu, trong đó chỉ hai cây có từ thời Euler. Với năm cây cầu ấy, chỉ còn hai vùng đất bậc lẻ, nên đi qua mỗi cầu đúng một lần đã trở nên khả thi. Có điều, đường đi phải bắt đầu ở một hòn đảo và kết thúc ở hòn đảo kia, nên không tiện cho khách du lịch muốn quay về khách sạn[5].

Từ câu đố đến một ngành toán học

Trong gần hai thế kỷ, ý tưởng của Euler chủ yếu nằm trong các câu đố giải trí. Người Việt chắc đã gặp một trò như thế từ hồi nhỏ: vẽ một hình bằng một nét, không nhấc bút, không tô lại nét nào. Hình ngôi nhà có mái nhọn và hai đường chéo vẽ được một nét, nhưng phải bắt đầu ở một góc đáy. Còn một hình chữ nhật với hai đường chéo, trông đơn giản hơn, lại không thể vẽ được.

Đó đúng là bài toán bảy cây cầu: giao điểm là đỉnh, nét là cạnh. Đếm số giao điểm có lẻ nét chạm vào. Bằng 0 thì vẽ được và quay về chỗ cũ. Bằng 2 thì vẽ được, nhưng phải bắt đầu ở một điểm lẻ. Nhiều hơn 2 thì đừng mất công thử nữa.

Sang thế kỷ 20, khi con người bắt đầu xây những mạng lưới khổng lồ (đường sắt, điện thoại, máy tính), lý thuyết đồ thị bỗng trở thành một trong những ngành toán học hữu ích nhất.

Ý tưởng ấy ở đâu hôm nay?

Xe rác, xe quét đường và người đưa thư

Một chiếc xe quét đường phải đi qua mọi con phố trong khu vực, rồi về lại bãi xe. Đây gần như đúng là câu hỏi của Euler, chỉ khác ở chỗ được phép đi lại một con phố, nhưng càng ít càng tốt vì mỗi cây số là tiền xăng và thời gian.

Đầu thập niên 1960, nhà toán học Trung Quốc Kwan Mei-Ko đặt bài toán này cho người đưa thư. Ngày nay nó vẫn mang tên “bài toán người đưa thư Trung Hoa” (Chinese postman problem). Lời giải đi thẳng từ quy tắc của Euler: tìm các giao lộ bậc lẻ, ghép chúng thành từng cặp sao cho tổng quãng đường nối các cặp là ngắn nhất, rồi coi như “đi hai lần” những đoạn nối ấy. Khi mọi đỉnh đã thành bậc chẵn, có một vòng đi khép kín qua mọi con phố. Các thành phố dùng cách làm này để lập lộ trình xe thu gom rác, xe quét tuyết và cả người kiểm tra đường ống.

Bản đồ chỉ đường

Khi bạn hỏi ứng dụng bản đồ đường nhanh nhất về nhà, nó không nhìn bản đồ như bạn nhìn. Nó nhìn đúng như Euler nhìn Königsberg: mỗi giao lộ là một đỉnh, mỗi đoạn đường là một cạnh, kèm thêm một con số là thời gian đi qua đoạn ấy. Câu hỏi “đường nào nhanh nhất?” trở thành câu hỏi về đường đi ngắn nhất trên đồ thị. Năm 1959, nhà khoa học máy tính Edsger Dijkstra công bố một thuật toán giải bài toán ấy. Các phiên bản cải tiến của nó vẫn là nền tảng của việc chỉ đường hôm nay.

Ghép lại bộ gen

Máy giải trình tự gen không đọc nổi cả một sợi DNA dài hàng tỷ ký tự. Nó cắt DNA thành hàng triệu mảnh ngắn, đọc từng mảnh, rồi máy tính phải ghép lại các mảnh theo đúng thứ tự, như ghép một bức tranh xếp hình khổng lồ mà nhiều mảnh trông giống hệt nhau.

Năm 2001, Pavel Pevzner, Haixu Tang và Michael Waterman đề xuất một cách nhìn mới: biến bài toán ghép mảnh thành bài toán tìm đường đi Euler trên một đồ thị được dựng từ các đoạn DNA ngắn[4]. Thay vì thử ghép từng cặp mảnh với nhau, việc này cực kỳ chậm, máy tính chỉ cần tìm một đường đi qua mỗi cạnh đúng một lần, đúng loại bài toán mà Euler đã chỉ ra cách nhận biết và Hierholzer đã chỉ ra cách giải. Các phần mềm ghép gen hiện đại phần lớn được xây trên ý tưởng này.

Từ một câu đố đi dạo, tới bộ gen người: khoảng cách là gần ba thế kỷ, nhưng ý tưởng cốt lõi không đổi. Bỏ đi những chi tiết không quan trọng, giữ lại cái gì nối với cái gì, rồi đếm.

Tự tay đi qua các cây cầu

Đoạn Python dưới đây làm hai việc. Nó đếm bậc của từng vùng đất, rồi dùng thuật toán Hierholzer để tìm đường đi qua mỗi cầu đúng một lần, nếu có. Nó cũng vẽ ra Hình 1 ở trên. Chỉ cần cài matplotlib.

from collections import Counter

import matplotlib.pyplot as plt
from matplotlib.patches import FancyArrowPatch

plt.rcParams.update({"figure.facecolor": "#16181c", "text.color": "#d4d7dc", "font.size": 12})

# Bốn vùng đất: Bắc (N), Nam (S), đảo Kneiphof (K), đảo phía đông (E). Mỗi cầu là một cạnh.
BRIDGES = [("N", "K"), ("N", "K"), ("S", "K"), ("S", "K"), ("N", "E"), ("S", "E"), ("K", "E")]


def degrees(edges):
    """Số cầu chạm vào mỗi vùng đất (bậc của đỉnh)."""
    return Counter(v for edge in edges for v in edge)


def euler_path(edges):
    """Thuật toán Hierholzer: trả về một đường đi qua mỗi cầu đúng một lần, hoặc None."""
    deg = degrees(edges)
    odd = [v for v in deg if deg[v] % 2 == 1]
    if len(odd) not in (0, 2):
        return None  # Điều kiện của Euler: phải có 0 hoặc 2 vùng đất bậc lẻ.
    adj = {v: [] for v in deg}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    used, stack, path = set(), [odd[0] if odd else edges[0][0]], []
    while stack:
        v = stack[-1]
        while adj[v] and adj[v][-1][1] in used:
            adj[v].pop()
        if adj[v]:
            w, i = adj[v].pop()
            used.add(i)
            stack.append(w)
        else:
            path.append(stack.pop())
    return path[::-1]


print("Bậc năm 1736:", dict(degrees(BRIDGES)))
print("Đường đi năm 1736:", euler_path(BRIDGES))
EIGHT = BRIDGES + [("N", "S")]  # thêm một cây cầu nối thẳng bờ Bắc và bờ Nam
print("Bậc khi thêm cầu thứ 8:", dict(degrees(EIGHT)))
print("Đường đi với 8 cầu:", " → ".join(euler_path(EIGHT)))

# Vẽ hai đồ thị: 7 cầu (không có đường đi) và 8 cầu (có đường đi).
POS = {"N": (0, 1.6), "S": (0, -1.6), "K": (-1.2, 0), "E": (1.8, 0)}
NAME = {"N": "bờ Bắc", "S": "bờ Nam", "K": "đảo\nKneiphof", "E": "đảo\nphía Đông"}
LABEL = {"N": (0, 0.45), "S": (0, -0.45), "K": (-1.0, 0), "E": (1.05, 0)}
fig, axes = plt.subplots(1, 2, figsize=(12, 5.6))
for ax, edges, title in [(axes[0], BRIDGES, "1736: 7 cầu, cả 4 vùng bậc lẻ → không có đường đi"),
                         (axes[1], EIGHT, "Thêm cầu thứ 8: còn 2 vùng bậc lẻ → có đường đi")]:
    seen = Counter()
    for u, v in edges:
        key = tuple(sorted((u, v)))
        k = seen[key]
        seen[key] += 1
        rad = [0, 0.35, -0.35][k] if key in {("K", "N"), ("K", "S")} else 0
        ax.add_patch(FancyArrowPatch(POS[u], POS[v], connectionstyle=f"arc3,rad={rad}", arrowstyle="-",
                                     color="#d2b48c" if key == ("N", "S") else "#a4a9b2", lw=2.5,
                                     shrinkA=28, shrinkB=28))
    deg = degrees(edges)
    for v, (x, y) in POS.items():
        odd = deg[v] % 2 == 1
        ax.scatter([x], [y], s=1600, color="#16181c", edgecolors="#e8b05a" if odd else "#8fa9c9", linewidths=3, zorder=3)
        ax.text(x, y, str(deg[v]), ha="center", va="center", fontsize=18, zorder=4)
        ax.text(x + LABEL[v][0], y + LABEL[v][1], NAME[v], ha="center", va="center", fontsize=11, color="#a4a9b2")
    ax.set_title(title, color="#d4d7dc", fontsize=12)
    ax.set_xlim(-2.6, 3.2)
    ax.set_ylim(-2.3, 2.3)
    ax.set_aspect("equal")
    ax.axis("off")
fig.savefig("bridges.png", dpi=150, bbox_inches="tight")

Bậc năm 1736: {'N': 3, 'K': 5, 'S': 3, 'E': 3}
Đường đi năm 1736: None
Bậc khi thêm cầu thứ 8: {'N': 4, 'K': 5, 'S': 4, 'E': 3}
Đường đi với 8 cầu: K → E → S → N → K → S → K → N → E

Thuật toán Hierholzer có một ý rất gọn: cứ đi theo bất kỳ cây cầu nào chưa dùng cho tới khi kẹt. Khi kẹt, lùi lại tới vùng đất gần nhất còn cầu chưa đi, đi tiếp một vòng nhỏ từ đó, rồi “chèn” vòng nhỏ ấy vào hành trình. Bạn có thể thử thêm hoặc bớt cầu trong danh sách BRIDGES để xem khi nào đường đi xuất hiện và biến mất.

Quay lại Königsberg

Câu đố của người dân Königsberg vô nghiệm, và lý do chỉ gói trong một câu: mỗi lần đi ngang qua một vùng đất, ta dùng hai cây cầu, nên vùng đất ở giữa hành trình phải có số cầu chẵn, mà Königsberg có tới bốn vùng lẻ.

Euler từng nghĩ lời giải ấy “chẳng mấy liên quan tới toán học”. Thật ra, ông vừa làm một trong những việc toán học nhất có thể: nhìn qua mọi chi tiết bề ngoài để thấy cấu trúc nằm bên dưới. Bỏ đi hình dạng, khoảng cách, màu sắc, chỉ giữ lại những chấm và những đường. Ba thế kỷ sau, cũng những chấm và đường ấy đang dẫn đường cho bạn về nhà mỗi tối.

Tập trước của loạt bài này kể về Pascal, Fermat và ván cược bỏ dở. Tập sau là về Gauss và một tiểu hành tinh bị lạc mất trong ánh Mặt Trời.