Lý thuyết đồ thị- Wikipedia

Bước tới: menu, tìm kiếm
Hình vẽ một đồ thị có 6 đỉnh và 7 cạnh
Mục lục
[ẩn]

1 Lịch sử
2 Định nghĩa
3 Cách vẽ đồ thị
4 Các cấu trúc dữ liệu đồ thị
4.1 Các cấu trúc danh sách
4.2 Các cấu trúc ma trận
5 Các bài toán đồ thị
5.1 Tìm đồ thị con
5.2 Tô màu đồ thị
5.3 Các bài toán đường đi
5.4 Luồng
5.5 Visibility graph problems
5.6 Các bài toán phủ
6 Các thuật toán quan trọng
7 Các lĩnh vực toán học có liên quan
8 Ứng dụng
9 Các lĩnh vực con
10 Các nhà lý thuyết đồ thị quan trọng
11 Xem thêm
12 Liên kết ngoài

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

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

Cấu trúc đồ thị có thể được mở rộng bằng cách gán trọng số cho mỗi cạnh. Có thể sử dụng đồ thị có trọng số để 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 đường giao thông, các trọng số có thể là độ dài của mỗi con đường. Một cách khác để mở rộng đồ thị cơ bản là qui định hướng cho các cạnh của đồ thị (như đối với các trang web, A liên kết tới B, nhưng B không nhất thiết cũng liên kết tới A). 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 lưới.

Các lưới có nhiều ứng dụng trong khía cạnh thực tiễn của lý thuyết đồ thị, chẳng hạn, phân tích lưới có thể dùng để mô hình hoá và phân tích mạng lưới giao thông hoặc nhằm "phát hiện" hình dáng của Internet - (Xem thêm các ứng dụng đưới đây. Mặc dù vậy, cũng nên lưu ý rằng trong phân tích lưới, thì định nghĩa của khái niệm "lưới" có thể khác nhau và thường được chỉ ra bằng một đồ thị đơn giản.)
[sửa] 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, xuất bản năm 1736. Bài báo này cũng được xem như một trong những kết quả topo đầu tiên trong hình học, tức là, nó không hề phụ thuộc vào bất cứ độ đo nào. Nó diễn tả mối liên hệ sâu sắc giữa lí thuyết đồ thị và tôpô học.

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ề vấn đề liệu chỉ với bốn màu có thể tô màu một bản đồ bất kì sao cho không có hai nước nào cùng biên giới được tô cùng màu. Bài toán này được xem như đã khai sinh ra lí thuyết đồ thị, và chỉ được giải sau một thế kỉ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Trong khi cố gắng giải quyết bài toán này, các nhà toán học đã phát minh ra nhiều thuật ngữ và khái niệm nền tảng cho lí thuyết đồ thị.
[sửa] Định nghĩa

Bài chi tiết: Đồ thị (toán học)

[sửa] Cách vẽ đồ thị

Bài chi tiết: Vẽ đồ thị

Đồ thị được biểu diễn đồ họa bằng cách vẽ một điểm cho mỗi đỉnh và vẽ một cung giữa hai đỉnh nếu chúng được nối bởi một cạnh. Nếu đồ thị là có hướng thì hướng được chỉ bởi một mũi tên.

Không nên lẫn lộn giữa một đồ hình của đồ thị với bản thân đồ thị (một cấu trúc trừu tượng, không đồ họa) bởi có nhiều cách xây dựng đồ hình. Toàn bộ vấn đề nằm ở chỗ đỉnh nào được nối với đỉnh nào, và bằng bao nhiêu cạnh. Trong thực hành, thường rất khó để xác định xem hai đồ hình có cùng biểu diễn một đồ thị không. Tùy vào bài toán mà đồ hình này có thể phù hợp và dễ hiểu hơn đồ hình kia.
[sửa] Các cấu trúc dữ liệu đồ thị

Bài chi tiết: Đồ thị (cấu trúc dữ liệu)

Có nhiều cách khác nhau để lưu trữ các đồ thị trong máy tính. Sử dụng cấu trúc dữ liệu nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao tác trên đồ thị đó. Trên lý thuyết, người ta có thể phân biệt giữa các cấu trúc danh sách và các cấu trúc ma trận. Tuy nhiên, trong các ứng dụng cụ thể, cấu trúc tốt nhất thường là kết hợp của cả hai. Người ta hay dùng các cấu trúc danh sách cho các đồ thị thưa (sparse graph), do chúng đòi hỏi ít bộ nhớ. Trong khi đó, các cấu trúc ma trận cho phép truy nhập dữ liệu nhanh hơn, nhưng lại cần lượng bộ nhớ lớn nếu đồ thị có kích thước lớn.
[sửa] Các cấu trúc danh sách

Danh sách liên thuộc (Incidence list) - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng (có thể cài đặt bằng mảng (array) hoặc danh sách liên kết động (linked list)), trong đó mỗi phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các cạnh tương ứng tại danh sách cạnh 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ó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó). Trong đồ thị vô hướng, cấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi đỉnh được nối với nó, do các đỉnh này đã được liệt kê tường minh.

[sửa] Các cấu trúc ma trận

Ma trận liên thuộc (Incidence matrix) - Đồ thị được biểu diễn bằng một ma trận [b_{ij}] kích thước p × q, trong đó p là số đỉnh và q là số cạnh, b_{ij} = 1 chứa dữ liệu về quan hệ giữa đỉnh v_i và cạnh x_j. Đơn giản nhất: b_{ij} = 1 nếu đỉnh v_i là một trong 2 đầu của cạnh x_j, bằng 0 trong các trường hợp khác.

Ma trận kề (Adjaceny matrix) - một ma trận N × N, trong đó N là số đỉnh của đồ thị. Nếu có một cạnh nào đó nối đỉnh v_ivới đỉnh v_j thì phần tử M_{i, j} bằng 1, nếu không, nó có giá trị 0. Cấu trúc này tạo thuận lợi cho việc tìm các đồ thị con và để đảo các đồ thị.

Ma trận dẫn nạp (Admittance matrix) hoặc ma trận Kirchhoff (Kirchhoff matrix) hay ma trận Laplace (Laplacian matrix) - được định nghĩa 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 cả về 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 đó.