Lý thuyết đồ thị
Những điểm và các đường nối giữa chúng: đồ thị chỉ có vậy. Thế nhưng cùng một hình vẽ ấy có thể mô tả bản đồ đường sá, mạng lưới bạn bè, một phân tử hay cả internet, và những câu hỏi đặt ra về nó, từ việc cần bao nhiêu màu cho đến việc có vẽ được bằng một nét hay không, đã khiến các nhà toán học bận rộn từ năm 1736.
Đỉnh và cạnh
Một đồ thị gồm các đỉnh, còn gọi là nút, và các cạnh, mỗi cạnh nối hai đỉnh. Vị trí vẽ các đỉnh không quan trọng, chỉ cần biết cặp nào được nối, nên cùng một đồ thị có thể trông rất khác nhau trên giấy. Đồ thị trong sân chơi là đồ thị đơn: không có cạnh nối một đỉnh với chính nó, và giữa hai đỉnh có nhiều nhất một cạnh. Với n đỉnh thì có nhiều nhất n(n − 1) / 2 cạnh; đồ thị có đủ tất cả các cạnh đó gọi là đồ thị đầy đủ, và K5 là đồ thị đầy đủ năm đỉnh.
Bậc và bổ đề bắt tay
Bậc của một đỉnh là số cạnh gắn với đỉnh đó. Cộng tất cả các bậc lại, bạn được đúng gấp đôi số cạnh, vì mỗi cạnh có hai đầu và được đếm một lần ở mỗi đầu. Đó là bổ đề bắt tay: trong một nhóm người bất kỳ, nếu đếm số lần bắt tay của từng người rồi cộng lại thì được gấp đôi số cái bắt tay. Điều đó cũng có nghĩa là số đỉnh bậc lẻ luôn là số chẵn. Đồ thị mà mọi đỉnh đều có cùng bậc k được gọi là đồ thị chính quy bậc k.
Đồ thị liên thông, cây và chu trình
Đồ thị liên thông khi từ mỗi đỉnh bạn có thể đi theo các cạnh tới mọi đỉnh khác; nếu không, nó tách thành nhiều mảnh, gọi là các thành phần liên thông. Chu trình là một vòng đi quay về điểm xuất phát mà không qua đỉnh nào hai lần, và độ dài của chu trình ngắn nhất là chu vi (girth) của đồ thị. Đồ thị liên thông không có chu trình là một cây, và cây có n đỉnh luôn có đúng n − 1 cạnh: bớt một cạnh thì nó rời ra, thêm một cạnh thì nó có chu trình. Mọi đồ thị liên thông đều chứa một cây khung, tức một cây đi tới mọi đỉnh mà chỉ dùng một phần các cạnh.
Đồ thị hai phía và tô màu
Hãy tô màu các đỉnh sao cho không có cạnh nào nối hai đỉnh cùng màu. Số màu ít nhất làm được điều đó là sắc số. Chỉ khi không có cạnh nào thì một màu mới đủ. Hai màu là đủ đúng khi đồ thị là hai phía: các đỉnh chia thành hai phía và mọi cạnh đều nối phía này với phía kia. Năm 1936, Dénes Kőnig chỉ ra rằng điều này tương đương với việc không có chu trình độ dài lẻ, vì một chu trình lẻ không thể tô luân phiên bằng hai màu. Với ba màu trở lên thì chưa biết phép kiểm tra đơn giản nào như vậy: quyết định xem ba màu có đủ hay không là bài toán NP-đầy đủ, nên các chương trình phải tìm kiếm, như sân chơi này vẫn làm.
Một ví dụ: đồ thị Petersen
Lấy một ngũ giác A–B–C–D–E và một ngôi sao năm cánh F–H–J–G–I nằm bên trong, rồi nối mỗi góc của ngũ giác với một đầu cánh sao: A–F, B–G, C–H, D–I và E–J. Đó là đồ thị Petersen, với 10 đỉnh và 15 cạnh. Mọi đỉnh đều có bậc 3, nên tổng các bậc là 30, gấp đôi 15. Chu trình ngắn nhất có độ dài 5, nên nó không có tam giác, nhưng ngũ giác là một chu trình lẻ, nên nó không phải đồ thị hai phía và cần 3 màu. Hai đỉnh bất kỳ cách nhau nhiều nhất 2 cạnh, nên đường kính của nó là 2. Cả mười bậc đều lẻ, nên nó không có đường Euler, và không thể vẽ nó mà không có cạnh cắt nhau.
Đường đi Euler và bài toán bảy cây cầu Königsberg
Thành phố Königsberg có bảy cây cầu nối bốn vùng đất, và người ta tự hỏi liệu có thể đi qua mỗi cây cầu đúng một lần hay không. Năm 1736, Leonhard Euler chứng minh rằng điều đó là không thể, và lý thuyết đồ thị ra đời. Mỗi lần đi ngang qua một vùng đất, ta dùng hai cây cầu, nên chỉ vùng xuất phát và vùng kết thúc mới được có số cầu lẻ, trong khi cả bốn vùng đất của Königsberg đều có số cầu lẻ. Ngày nay, một đường đi qua mỗi cạnh đúng một lần được gọi là đường đi Euler, hay chu trình Euler nếu nó kết thúc tại nơi bắt đầu. Năm 1873, Carl Hierholzer chứng minh rằng điều kiện này cũng là đủ: nếu mọi cạnh nằm trong một mảnh và có nhiều nhất hai bậc lẻ thì đường đó tồn tại, và phương pháp ghép nối các vòng đi của ông đến nay vẫn được dùng để tìm ra nó.
Khoảng cách, đường kính và đồ thị bù
Khoảng cách giữa hai đỉnh là số cạnh ít nhất trên một đường đi nối chúng, còn đường kính là khoảng cách lớn nhất trong đồ thị; với đồ thị không liên thông, đường kính là vô cùng. Mạng xã hội có đường kính nhỏ, đó là ý tưởng đằng sau thuyết sáu độ phân cách. Đồ thị bù của một đồ thị có cùng tập đỉnh và nối đúng những cặp đỉnh trước đó chưa được nối. Giữa một đồ thị và đồ thị bù của nó, luôn có ít nhất một đồ thị liên thông.
Tự khám phá
Sân chơi mở ra với đồ thị Petersen được tô bằng ba màu. Nhấp Bậc và kiểm chứng bổ đề bắt tay, nhấp Hai phía để thấy một chu trình lẻ, rồi tải hình lập phương và xem hai phía hiện ra. Tải ngôi nhà và nhấp Đường Euler để xem nét vẽ duy nhất phải bắt đầu từ đâu. Hãy vẽ đồ thị của riêng bạn và thêm từng cạnh một: xem chu trình ngắn nhất ngắn lại, đường kính giảm xuống, và sắc số tăng lên khi cạnh cuối cùng của K4 được thêm vào.
Câu hỏi thường gặp
Đường đi sơ cấp, đường đi đơn và hành trình khác nhau thế nào?
Hành trình (walk) là một dãy đỉnh bất kỳ nối với nhau bằng các cạnh, có thể lặp lại cả đỉnh lẫn cạnh. Đường đi đơn (trail) có thể lặp lại đỉnh nhưng không lặp lại cạnh, vì thế đường Euler có thể đi qua một đỉnh nhiều lần. Đường đi sơ cấp (path) không lặp lại cả hai.
Định lý bốn màu là gì?
Định lý này nói rằng mọi đồ thị vẽ được trên giấy mà không có cạnh cắt nhau đều có thể tô bằng nhiều nhất bốn màu, nên mọi bản đồ đều chỉ cần tối đa bốn màu. Định lý được Kenneth Appel và Wolfgang Haken chứng minh năm 1976 với sự trợ giúp của máy tính, và là định lý lớn đầu tiên được chứng minh theo cách đó.
Chu trình Hamilton là gì?
Là chu trình đi qua mỗi đỉnh đúng một lần, thay vì mỗi cạnh. Nghe giống bài toán Euler, nhưng chưa ai biết phép kiểm tra đơn giản nào cho nó: quyết định xem một đồ thị có chu trình Hamilton hay không là bài toán NP-đầy đủ. Đồ thị Petersen có đường đi Hamilton nhưng không có chu trình Hamilton.
Lý thuyết đồ thị được dùng ở đâu?
Các ứng dụng chỉ đường tìm kiếm trên đồ thị đường sá, công cụ tìm kiếm xếp hạng trang web dựa trên các liên kết, trình biên dịch tô màu đồ thị để chia sẻ thanh ghi của bộ xử lý, việc lập thời khóa biểu tránh trùng lịch bằng cách tô màu đồ thị xung đột, các nhà hóa học đếm phân tử dưới dạng đồ thị, còn mạng máy tính, lưới điện và mạng lưới bạn bè đều được nghiên cứu như những đồ thị.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở Sân chơi lý thuyết đồ thị