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
Không có tóm lược sửa đổi
xóa lượng lớn thông tin có ích mà không qua thảo luận trước
Dòng 1:
{{chú thích trong bài}}
==Tổng quan về Lý thuyết đồ thị==
[[Tập tin:6n-graf.svg|nhỏ|phải|Hình vẽ một đồ thị có 6 đỉnh và 7 cạnh]]
===Định nghĩa đồ thị===
{{TOCright}}
Định nghĩa: Đồ thị là một tập hợp rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó.
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ị (lý thuyết đồ thị)|đồ 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 [[đồ thị (lý thuyết đồ thị)|đỉnh]] (hoặc nút) nối với nhau bởi các [[đồ thị (lý thuyết đồ thị)|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ị có hướng.====
Một đồ thị có hướng G = (X, U) được định nghĩa bởi:
* Tập hợp X ≠ Ø được gọi là tập các đỉnh của đồ thị;
* Tập hợp U là tập các cạnh của đồ thị;
* Ánh xạ liên kết cạnh đỉnh: mỗi cạnh u ∈ U được liên kết với một cặp đỉnh có thứ tự (i, j) ∈ X2.
====Đồ thị vô hướng====
Nếu chúng ta không phân biệt thứ tự của cặp đỉnh liên kết với mỗi cạnh thì sẽ có được đồ thị vô hướng. Đồ thị vô hướng G = (X, E) được định nghĩa bởi:
* Tập hợp X ≠ Ø được gọi là tập các đỉnh của đồ thị;
* Tập hợp E là tập các cạnh của đồ thị;
* Ánh xạ liên kết cạnh đỉnh: mỗi cạnh e∈E được liên kết với một cặp đỉnh {i, j} ⊆X không phân biệt thứ tự.
====Một số từ ngữ và quy ước====
Khi một cạnh u được liên kết với cặp đỉnh (i, j):
* Ta nói cạnh u kề với đỉnh i và kề với đỉnh j (hay cũng nói đỉnh i và đỉnh j kề với cạnh u);
* Ta viết tắt u = (i, j), như vậy có lúc ta viết u = (i, j) và v = (i, j) nhưng lại hiểu u ≠ v;
* Nếu đồ thị vô hướng, ta nói hai đỉnh i và j được nối với nhau, nếu đồ thị có hướng (tức cặp đỉnh (i, j) được tôn trọng thứ tự) ta nói đỉnh i được nối tới đỉnh j.
* Nếu đồ thị có hướng ta nói cạnh u bắt đầu từ đỉnh i và kết thúc tại đỉnh j, ta cũng nói cạnh u đi ra khỏi đỉnh i và đi vào từ đỉnh j.
* Ngoài ra, trong giáo trình này chúng ta chỉ làm việc với trường hợp các đồ thị có tập đỉnh và cặp cạnh hữu hạn. Để cho chính xác thì phải nhấn mạnh là ĐỒ THỊ HỮU HẠN, tuy nhiên để ngắn gọn ta chỉ dùng thuật ngữ ĐỒ THỊ và hiểu ngầm đó là đồ thị hữu hạn.
====Khuyên và cạnh song song====
*Trong đồ thị có một cạnh nối từ đỉnh đó tới chính nó được gọi là khuyên.
* Tại hai đỉnh bất kỳ của đồ thị tồn tại nhiều hơn một cạnh nối giữa hai đỉnh đó được gọi là cạnh song song.
===Các dạng đồ thị đặc biệt===
====Đồ thị đơn====
Đồ thị đơn là đồ thị không có khuyên và không có cạnh song song.
====Đồ thị đủ====
Đồ thị đủ là một đồ thị vô hướng, đơn mà giữa hai đỉnh bất kỳ đều có một cạnh nối chúng.
* Đồ thị đủ n đỉnh được ký hiệu là K<sub>n</sub>.
* Đồ thị đủ n đỉnh sẽ có (n(n-1))/2 cạnh.
====Đồ thị phân đôi====
Cho G = (X, E) là một đồ thị. Đồ thị G được gọi là đồ thị phân đôi nếu có thể chia tập đỉnh X thành hai tập con X_1 và X_2sao cho:
* Hai tập X_1và X_(2 )phân hoạch X, nghĩa là: X_1 ≠ Ø ≠ X_2, X_1∩X_2 = Ø, và X = X_1∪X_2;
* Hai đỉnh bất ky trong X_1không được nối với nhau bởi cạnh của đồ thị; hai đỉnh bất kỳ trong X_2 cũng không được nối với nhau bởi cạnh nào của đồ thị.
====Đồ thị phân đôi đủ====
Cho G = (X, E) là một đồ thị phân đôi, vô hướng với hai tập X_1 và X_2 định nghĩa như trên. G được gọi là đồ thị phân đôi đủ nếu:
* G đơn và mọi cặp đỉnh (i, j) mà i∈X_1 và j∈X_(2 )thì có đúng một cạnh của G nối i và j.
* Nếu | X_1| = n và | X_2| = m thì G có mxn cạnh được ký hiệu là K<sub>(m,n)</sub>.
==== Đồ thị chu trình đơn====
Đồ thị chu trình đơn n đỉnh (ký hiệu C_n) là một đa giác khép kín gồm n đỉnh.
====Đồ thị bù====
Cho G = (X, E) là một đồ thị vô hướng gồm n đỉnh. Đồ thị bù của G, ký hiệu là G ̅, là đồ thị:
* Có tập đỉnh là X, Với mọi x
Với mọi <math>x,y \in X</math> thì có cạnh của G ̅ nối x, y khi và chỉ khi x ≠ y và trong G không có cạnh nối x, y.
===Bậc của đỉnh===
====Bậc====
Bậc của đỉnh x trong đồ thị là tổng số các cạnh kề với đỉnh x, qui ước là mỗi khuyên phải được tính hai lần.Bậc của đỉnh x trong đồ thị G được ký hiệu là d_G(x) (hay d(x) nếu đã xác định đó là đồ thị nào).
====Bậc đỉnh trong đồ thị có hướng====
Xét đồ thị G = (X, E) và đỉnh x ∈ X.
* Nửa bậc ngoài của đỉnh x: ký hiệu <math>d_G^+(x)</math> là số các cạnh đi ra khỏi đỉnh x (hay khởi đầu từ đỉnh x).
* Nửa bậc trong của đỉnh x: ký hiệu <math>d_G^-(x)</math> là số các cạnh đi vào đỉnh x (hay kết thúc tại đỉnh x).
* Bậc của đỉnh x: tổng hai nửa bậc tại đỉnh x:
<math>d_G(x) = d_G^+(x) + d_G^-(x)</math>
 
Đồ 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]].
====Đỉnh treo, đỉnh cô lập====
* Đỉnh treo là đỉnh có bậc bằng 1.
* Đỉnh cô lập là đỉnh có bậc bằng 0.
 
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]].
====Công thức liên hệ giữa bậc và số cạnh====
* a/ Xét đồ thị có hướng G = (X, U). Ta có:
<math>\sum_{x=X} { d^+(x) } = \sum_{x=X} { d^-(x) }</math>=|U|
* b/ Xét đồ thị G = (X, E) bất kỳ (có hướng hay vô hướng). Ta có:
∑_(x∈X)▒〖d(x)=2|E| 〗
 
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 [[#Ứng dụng|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.)
Hệ quả: Số lượng các đỉnh có bậc lẻ trong một đồ thị là một số chẵn.
 
===Biểu diễn đồ thị bằng ma trận===
== Lịch sử ==
* Xét đồ thị G = (X, U) (có hướng hay vô hướng).
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]].
* Giả sử tập X gồm n đỉnh được sắp thứ tự X= {x_1, x_2, …, x_n} và tập U gồm n cạnh được sắp thứ tự U = {u_1, u_2, …, u_m}.
 
====Ma trận kề====
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]].
Ma trận kề của đồ thị G, ký hiệu B(G), là một ma trận nhị phân cấp n x n được định nghĩa là B = (B_ij) với:
 
* B_ij = 1 nếu có cạnh nối x_itới x_j.
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ị.
* B_ij = 0 nếu ngược lại.
 
====Ma trận liên thuộc (ma trận liên kết)====
== Định nghĩa ==
* Nếu G là đồ thị vô hướng, ma trận liên thuộc của đồ thị G, ký hiệu A(G), là ma trận nhị phân cấp n x m được định nghĩa là A = (A_ij) với:
{{Chính|Đồ thị (toán học)}}
**A<sub>ij</sub> = 1 nếu đỉnh x_i kề với cạnh u_j.
 
**A<sub>ij</sub> = 0 nếu ngược lại.
== Cách vẽ đồ thị ==
*Nếu G là đồ thị có hướng không có khuyên, ma trận liên thuộc của đồ thị G, ký hiệu A(G), là ma trận n x m được đinh nghĩa là A = (A_ij) với:
{{Chính|Vẽ đồ thị}}
**A<sub>ij</sub> = 1 nếu cạnh u_j hướng ra khỏi đỉnh x<sub>i</sub>,
 
**A<sub>ij</sub> = -1 nếu cạnh u_j hướng vào đỉnh x<sub>i</sub>,
Đồ 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.
**A<sub>ij</sub> = 0 nếu cạnh u_j không kề đỉnh x<sub>i</sub>.
 
====Ma trận bậc====
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.
*Ma trận bậc (degree matrix) là một ma trận đường chéo chứa thông tin về bậc của mỗi đồ thị.
 
*Định nghĩa
== Các cấu trúc dữ liệu đồ thị ==
Cho một đồ thị G, ma trận bậc D của đồ thị G mà một ma trận vuông n x n được định nghĩa như sau:
{{Chính|Đồ thị (cấu trúc dữ liệu)}}
* d_(i,j) = deg (v_i) khi i = j
 
* d_(i,j) = 0 khi i ≠ j.
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 (toán họ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.
 
* Tính chất:
=== Các cấu trúc danh sách ===
Ma trận bậc của đồ thị chính quy bậc k có một đường chéo chứa toàn các hằng sốk.
* '''[[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.
 
=== 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 (toán học)|ma trận]] <math>[b_{ij}]</math> kích thước ''p'' × ''q'', trong đó ''p'' là số đỉnh và ''q'' là số cạnh, <math>b_{ij} = 1</math> chứa dữ liệu về quan hệ giữa đỉnh <math>v_i</math> và cạnh <math>x_j</math>. Đơn giản nhất: <math>b_{ij} = 1</math> nếu đỉnh <math>v_i</math> là một trong 2 đầu của cạnh <math>x_j</math>, 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 <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 đủ)
* Bài toán tập con độc lập (''independent set problem'') (NP-đầy đủ)
 
=== Tô màu đồ thị ===
{{Chính|Tô màu đồ thị}}
 
* [[Định lý bốn màu]] (''four-color theorem'')
* [[Đồ thị hoàn hảo|Định lý đồ thị hoàn hảo mạnh]] (''strong perfect graph theorem'')
* Bài toán [[Erdős-Faber-Lovász conjecture]] (hiện chưa ai giải được)
* Bài toán [[total coloring|total coloring conjecture]] (hiện chưa ai giải được)
* Bài toán [[list edge-coloring|list coloring conjecture]] (hiện chưa ai giải được)
 
=== Các bài toá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 trùm 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 đây là "Bài toán người đưa thư"
 
=== [[Luồng trên mạng|Luồng]] ===
* [[Định lý luồng cực đại lát cắt cực tiểu]]
* [[Reconstruction conjecture]]
 
=== [[Visibility graph]] problems ===
* [[Visibility graph|Museum guard problem]]
 
=== Các bài toán phủ ===
{{Chính|Phủ (lý thuyết đồ thị)}}
 
Các bài toán phủ là các thể hiện cụ thể của các bài toán tìm đồ thị con. Chúng có quan 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 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 ==
Lý thuyết đồ thị rất đa dạng và có nhiều [[Danh sách các chủ đề lý thuyết đồ thị|lĩnh vực con]]. Trong đó có:
 
* [[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ị quan trọng ==
* [[Paul Erdős]]
* [[Frank Harary]]
* [[Denes König]]
* [[W.T. Tutte]]
* [http://www1.cs.columbia.edu/~sanders/graphtheory/people/alphabetic.html Sách trắng về lý thuyết đồ thị] các nhà lý thuyết đồ thị khác và danh sách ấn bản phẩm của họ.
 
== Xem thêm ==
* [[Thuật ngữ lý thuyết đồ thị]]
* [[Cây (cấu trúc dữ liệu)|Cấu trúc dữ liệu cây có thứ tự]]&nbsp;– đồ thị có hướng phi chu trình, cây nhị phân, và các dạng đồ thị đặc biệt khác.
* [[Đồ thị phẳng]]
 
==Tham khảo==
{{tham khảo}}
 
== Liên kết ngoài ==
* [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Sách trực tuyến về Lý thuyết đồ thị]
* [http://www.utm.edu/departments/math/graph/ Hướng dẫn về lý thuyết đồ thị]
* [http://www.cs.wpi.edu/~dobrush/cs507/presentation/2001/Project10/ppframe.htm Bài giảng của một môn học về các thuật toán đồ thị]
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Dữ liệu test chuẩn cho các bài toán đồ thị con đầy đủ lớn nhất (Maximum Clique), tập con độc lập lớn nhất (Maximum Independent Set), phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô mầu đỉnh (Vertex Coloring)]
* [http://www.nd.edu/~networks/gallery.htm Sưu tập ảnh số 1: một số mạng lưới thực]
* [http://www1.cs.columbia.edu/~sanders/graphtheory/writings/journals.html Các tạp chí lý thuyết đồ thị]
 
{{Commonscat|Graph theory}}
{{Toán}}
 
[[Thể loại:Lý thuyết đồ thị|*]]
[[Thể loại:Toán học rời rạc]]
 
{{Liên kết chọn lọc|nl}}