Khác biệt giữa bản sửa đổi của “Lý thuyết đồ thị”
Nội dung được xóa Nội dung được thêm vào
n Robot: Sửa đổi hướng |
|||
Dòng 1:
[[Tập tin:6n-graf.svg|nhỏ|phải|Hình vẽ một đồ thị có 6 đỉnh và 7 cạnh]]
{{TOCright}}
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ị (
Đồ 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'' [[tương đương logic|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ị (lý thuyết đồ thị)#các định nghĩa|đồ 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 (toán học)|lưới]].
Dòng 10:
== 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ài toán bảy cây cầu Euler|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ô|tôpô học]].
Năm [[1845]], [[Gustav Robert Kirchhoff|Gustav Kirchhoff]] đưa ra [[Định luật Kirchhoff cho mạch điện]] để tính [[điện thế]] và [[dòng điện#Cường độ dòng điện|cường độ dòng điện]] trong [[mạch điện]].
Năm [[1852]] [[Francis Guthrie]] đưa ra [[định lý bốn màu|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ị.
== Định nghĩa ==
Dòng 41:
* '''[[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 <math>v_i</math>với đỉnh <math>v_j</math> thì phần tử <math>M_{i, j}</math> 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 Laplace|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 đó.
== Các bài toán đồ thị ==
=== Tìm đồ thị con ===
Một bài toán thường gặp, được gọi là [[bài toán đồ thị con đẳng cấu]] (''subgraph isomorphism problem''), là tìm các [[thuật ngữ lý thuyết đồ thị#Đồ thị con|đồ thị con]] trong một đồ thị cho trước. Nhiều tính chất của đồ thị có tính ''di truyền'', nghĩa là nếu một đồ thị con nào đó có một tính chất thì toàn bộ đồ thị cũng có tính chất đó. Chẳng hạn như một đồ thị là [[đồ thị phẳng|không phẳng]] nếu như nó chứa một [[đồ thị hai phía đầy đủ]] (''complete bipartite graph '') <math>K_{3,3}</math> hoặc nếu nó chứa đồ thị đầy đủ <math>K_{5}</math>. Tuy nhiên, bài toán tìm đồ thị con cực đại thỏa mãn một tính chất nào đó thường là [[bài toán NP-đầy đủ]] (''NP-complete problem'').
* Bài toán đồ thị con đầy đủ lớn nhất (''clique problem'') (NP-đầy đủ)
Dòng 68:
* [[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 đây là "Bài toán người đưa thư"
=== [[Luồng
* [[Định lý luồng cực đại lát cắt cực tiểu]]
* [[Reconstruction conjecture]]
Dòng 92:
== Các lĩnh vực toán học có liên quan ==
* [[Lý thuyết Ramsey]]
* [[Toán học tổ hợp|Toán tổ hợp]] (''Combinatorics'')
== Ứng dụng ==
Lý thuyết đồ thị được ứng dụng nhiều trong [[phân tích lưới]]. Có hai kiểu phân tích lưới. Kiểu thứ nhất là phân tích để tìm các tính chất về cấu trúc của một lưới, chẳng hạn nó là một [[scale-free network]] hay là một [[small-world network]]. Kiểu thứ hai, phân tích để đo đạc, chẳng hạn mức độ lưu thông xe cộ trong một phần của [[mạng lưới giao thông]] (''transportation network'').
Lý thuyết đồ thị còn được 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 một cách định lượng bằng cách thu thập [[khoa học Thống kê|thống kê]] về các tính chất lý thuyết đồ thị có liên quan đến cấu trúc [[tô pô]] của các nguyên tử. Ví dụ, các vành đường đi ngắn nhất Franzblau (''Franzblau's shortest-path rings'').
== Các lĩnh vực con ==
| |||