Lý thuyết đồ thị

Trong toán học và tin học, lý thuyết đồ thị (tiếng Anh: graph theory) nghiên cứu các tính chất của các đồ thị. Một cách không chính thức, đồ thị là một tập hợp các đối tượng gọi là đỉnh (hoặc nút) kết nối với nhau qua các cạnh (hoặc cung). Các cạnh có thể có hướng hoặc không hướng. Đồ thị thường được biểu diễn dưới dạng một tập hợp các điểm (đỉnh) được nối với nhau bằng các đoạn thẳng (các cạnh).

Đồ thị có thể biểu diễn nhiều cấu trúc khác nhau và nhiều bài toán thực tế có thể được mô tả bằng đồ thị. Ví dụ, cấu trúc liên kết của một trang web có thể được mô tả bằng một đồ thị có hướng như sau: các đỉnh là các trang web hiện có trong trang web, và có một cạnh có hướng từ trang A đến trang B nếu và chỉ nếu trang A có một liên kết đến trang B. Do đó, việc phát triển các thuật toán xử lý đồ thị là một trong những vấn đề quan trọng trong khoa học máy tính.

Cấu trúc của đồ thị có thể được mở rộng bằng cách gán một trọng số cho mỗi cạnh. Đồ thị có trọng số có thể được sử dụng để biểu diễn nhiều khái niệm khác nhau. Ví dụ, nếu đồ thị biểu diễn một mạng lưới giao thông, các trọng số có thể đại diện cho độ dài của mỗi con đường. Một cách khác để mở rộng đồ thị cơ bản là xác định hướng của các cạnh (ví dụ, trong trang web, trang A liên kết đến trang B nhưng không nhất thiết là ngược lại). Loại đồ thị này được gọi là đồ thị có hướng. Một đồ thị có hướng với các cạnh có trọng số được gọi là một mạng.

Lịch sử

Một trong những kết quả đầu tiên trong lý thuyết đồ thị xuất hiện trong bài báo của Leonhard Euler về Bảy cây cầu ở Königsberg, được xuất bản năm 1736. Bài báo này cũng được coi là một trong những thành tựu đầu tiên trong lĩnh vực topo hình học, tức là không phụ thuộc vào bất kỳ độ đo nào. Nó chỉ ra mối quan hệ sâu sắc giữa lý thuyết đồ thị và hình học topo.

Năm 1845, Gustav Kirchhoff đưa ra Định luật Kirchhoff cho mạch điện để tính điện thế và cường độ dòng điện trong mạch điện.

Năm 1852, Francis Guthrie đưa ra bài toán bốn màu về việc liệu có thể sử dụng bốn màu để tô màu một bản đồ bất kỳ sao cho không có hai vùng nào cùng biên giới được tô cùng màu. Bài toán này được coi là bài toán sáng lập cho lý thuyết đồ thị và chỉ được giải quyết sau một thế kỷ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Trong quá trình giải bài toán này, các nhà toán học đã đưa ra nhiều thuật ngữ và khái niệm cơ bản cho lý thuyết đồ thị.

Định nghĩa

Cách vẽ đồ thị

Đồ thị được biểu diễn đồ họa bằng cách vẽ một điểm cho mỗi đỉnh và nối chúng bằng cạnh. Trong trường hợp đồ thị có hướng, sẽ có mũi tên chỉ hướng của cạnh.

Không nên nhầm lẫn giữa đồ họa của đồ thị với bản thân đồ thị (một cấu trúc trừu tượng, không phải đồ họa), vì có nhiều cách khác nhau để xây dựng đồ họa. Vấn đề chính là xác định xem đỉnh nào được nối với đỉnh nào và bằng bao nhiêu cạnh. Trên thực tế, việc xác định liệu hai đồ họa có biểu thị cùng một đồ thị hay không thường rất phức tạp. Cách biểu diễn này phụ thuộc vào từng bài toán và có thể dễ hiểu hơn một cách biểu diễn khác.

Các cấu trúc dữ liệu đồ thị

Có nhiều phương pháp khác nhau để lưu trữ đồ thị trên máy tính. Lựa chọn cấu trúc dữ liệu phụ thuộc vào cấu trúc của đồ thị và thuật toán sử dụng để thao tác trên đồ thị đó. Trong lý thuyết, có thể phân biệt giữa các cấu trúc danh sách và ma trận. Tuy nhiên, trong các ứng dụng cụ thể, việc kết hợp cả hai thường là tối ưu nhất. Danh sách thường được sử dụng cho đồ thị thưa vì tiêu tốn ít bộ nhớ hơn. Ma trận, mặt khác, cho phép truy cập nhanh hơn nhưng yêu cầu bộ nhớ lớn hơn đối với đồ thị lớn.

Các cấu trúc danh sách

• Danh sách liên kết (Incidence list) - Mỗi đỉnh có một danh sách các cạnh mà nó kết nối. Các cạnh của đồ thị có thể được lưu trữ trong một danh sách riêng (có thể dùng mảng hoặc danh sách liên kết động), trong đó mỗi phần tử chứa thông tin về cạnh như cặp đỉnh nối bởi cạnh (nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách cạnh của mỗi đỉnh tham chiếu đến vị trí của các cạnh tương ứng trong danh sách này.
• Danh sách kề (Adjacency list) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề nó (tức là có cạnh nối từ đỉnh này tới mỗi đỉnh kề). Trong đồ thị vô hướng, cấu trúc này có thể dẫn đến các mối quan hệ trùng lặp. Ví dụ, nếu đỉnh 3 nằm trong danh sách kề của đỉnh 2, thì đỉnh 2 cũng phải nằm trong danh sách kề của đỉnh 3. Lập trình viên có thể chọn giải pháp tiêu tốn không gian hoặc chỉ liệt kê mối quan hệ kề cạnh một lần. Cấu trúc này thuận tiện cho việc từ một đỉnh duy nhất tìm ra tất cả các đỉnh kề với nó, do các đỉnh này được liệt kê rõ ràng.

Các cấu trúc ma trận

• Ma trận liên kết (Incidence matrix) - Đồ thị được biểu diễn bằng một ma trận p × q, trong đó p là số đỉnh và q là số cạnh. Mỗi phần tử của ma trận này cho biết mối quan hệ giữa đỉnh v_{i} và cạnh x_{j}. Đơn giản nhất, nếu đỉnh v_{i} là một trong hai đầu của cạnh x_{j}, thì giá trị của phần tử tương ứng trong ma trận là 1; ngược lại là 0.
• Ma trận kề (Adjacency matrix) - Một ma trận N × N, trong đó N là số đỉnh của đồ thị. Phần tử M_{i,j} bằng 1 nếu có cạnh nối từ đỉnh v_{i} tới đỉnh v_{j}, ngược lại là 0. Cấu trúc này thuận lợi cho việc tìm các đồ thị con và phân tích đồ thị.
• Ma trận dẫn nạp (Admittance matrix) hay ma trận Kirchhoff (Kirchhoff matrix) hoặc ma trận Laplace (Laplacian matrix) - là kết quả thu được khi lấy ma trận bậc (degree matrix) trừ đi ma trận kề. Do đó, ma trận này chứa thông tin về cả quan hệ kề (có cạnh nối hay không) giữa các đỉnh lẫn bậc của các đỉnh đó.

Các bài toán liên quan đến đồ thị

Tìm kiếm đồ thị con

Một vấn đề phổ biến là bài toán tìm đồ thị con đồng cấu (subgraph isomorphism problem), tức là tìm các đồ thị con trong một đồ thị đã cho. Nhiều thuộc tính của đồ thị có tính chất di truyền, tức là nếu một đồ thị con có một thuộc tính nào đó, thì toàn bộ đồ thị cũng có thuộc tính đó. Ví dụ, một đồ thị là không phẳng nếu nó chứa một đồ thị hai phía đầy đủ (complete bipartite graph) K_{3,3}, hoặc nếu nó chứa đồ thị đầy đủ K_{5}. Tuy nhiên, bài toán tìm đồ thị con lớn nhất thỏa mãn một thuộc tính nào đó thường là bài toán NP-đầy đủ (NP-complete problem).

['Bài toán liên quan đến đồ thị con cực đại (clique problem) (NP-đầy đủ)','Bài toán tập con độc lập (independent set problem) (NP-đầy đủ)']

Tô màu các đồ thị

['Định lý bốn màu (four-color theorem)','Định lý đồ thị hoàn hảo mạnh (strong perfect graph theorem)','Bài toán giả thuyết Erdős-Faber-Lovász (chưa có ai giải được)','Bài toán giả thuyết tô màu tổng (chưa có ai giải được)','Bài toán giả thuyết tô màu danh sách (chưa có ai giải được)']

Các vấn đề liên quan đến đường đi

['Bài toán bảy cây cầu Euler (Seven Bridges of Königsberg) còn gọi là \'Bảy cây cầu ở Königsberg\'','Cây bao phủ nhỏ nhất (Minimum spanning tree)','Cây Steiner','Bài toán đường đi ngắn nhất','Bài toán người đưa thư Trung Hoa (còn gọi là \'bài toán tìm hành trình ngắn nhất\')','Bài toán người bán hàng (Traveling salesman problem) (NP-đầy đủ) cũng có tài liệu (tiếng Việt) gọi là \'Bài toán người đưa thư\'']

Các vấn đề về luồng

['Định lý luồng cực đại lát cắt cực tiểu','Reconstruction conjecture']

Các vấn đề liên quan đến đồ thị nhìn thấy

['Bài toán lính bảo vệ bảo tàng']

Các vấn đề liên quan đến phủ

'Các vấn đề liên quan đến phủ là các dạng cụ thể của các bài toán tìm đồ thị con. Chúng có mối liên hệ chặt chẽ với bài toán đồ thị con đầy đủ hoặc bài toán tập độc lập.'

['Bài toán phủ tập (Set cover problem)','Bài toán phủ đỉnh (Vertex cover problem)']

Các thuật toán quan trọng

['Thuật toán Bellman-Ford','Thuật toán Dijkstra','Thuật toán Ford-Fulkerson','Thuật toán Kruskal','Thuật toán láng giềng gần nhất','Thuật toán Prim']

Các lĩnh vực toán học liên quan

['Lý thuyết Ramsey','Toán tổ hợp (Combinatorics)']

Ứng dụng

Lý thuyết đồ thị được ứng dụng rộng rãi trong phân tích lưới. Có hai loại phân tích lưới: phân tích cấu trúc mạng lưới như mạng scale-free hay small-world, và phân tích đo đạc như lưu thông xe cộ trong mạng lưới giao thông.

Lý thuyết đồ thị cũng được áp dụng trong nghiên cứu phân tử. Trong vật lý vật chất ngưng tụ, cấu trúc ba chiều phức tạp của các hệ nguyên tử có thể được nghiên cứu bằng cách thu thập thống kê về các tính chất lý thuyết đồ thị, như các vành đường đi ngắn nhất Franzblau.

Các lĩnh vực con của lý thuyết đồ thị

['Lý thuyết đồ thị đại số (Algebraic graph theory)','Lý thuyết đồ thị tô pô (Topological graph theory)','Lý thuyết đồ thị hình học (Geometric graph theory)','Lý thuyết đồ thị cực trị (Extremal graph theory)','Lý thuyết đồ thị mê-tríc (Metric graph theory)','Lý thuyết đồ thị xác suất (Probabilistic graph theory)']

['Lý thuyết đồ thị đại số (Algebraic graph theory)','Lý thuyết đồ thị tô pô (Topological graph theory)','Lý thuyết đồ thị hình học (Geometric graph theory)','Lý thuyết đồ thị cực trị (Extremal graph theory)','Lý thuyết đồ thị mê-tríc (Metric graph theory)','Lý thuyết đồ thị xác suất (Probabilistic graph theory)']

Các nhà lý thuyết đồ thị nổi tiếng

['Frank Harary','Denes König','W.T. Tutte','Sách trắng về lý thuyết đồ thị Lưu trữ 2006-01-11 tại Wayback Machine các nhà lý thuyết đồ thị khác và danh sách ấn bản phẩm của họ.']