PDF được tạo bằng bộ công cụ mã nguồn mở mwlib. Xem để biết thêm thông tin.
PDF generated at: Wed, 14 May 2014 15:48:20 UTC
Thuật toán đồ thị
Nội dung
Bài
Đại cương
1
Lý thuyết đồ thị 1
Thuật ngữ lý thuyết đồ thị 5
Đồ thị (lý thuyết đồ thị) 12
Ma trận kề 16
Danh sách kề 22
Tìm kiếm trong đồ thị
24
Tìm kiếm theo chiều sâu 24
Tìm kiếm theo chiều rộng 33
Sắp xếp tô pô 35
Tính liên thông của đồ thị vô hướng
38
Thành phần liên thông 38
Thuật toán Karger 40
Tính liên thông của đồ thị có hướng
42
Thành phần liên thông mạnh 42
Thuật toán Kosaraju 43
Đường đi ngắn nhất
44
Bài toán đường đi ngắn nhất 44
Thuật toán Dijkstra 45
Thuật toán Bellman-Ford 47
Giải thuật tìm kiếm A* 53
Chú thích
Nguồn và người đóng góp vào bài 120
Nguồn, giấy phép, và người đóng góp vào hình 121
Giấy phép Bài viết
Giấy phép 124
1
Đại cương
Lý thuyết đồ thị
Hình vẽ một đồ thị có 6 đỉnh và 7 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ị. 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.)
(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 kích thước p × q, trong đó
p là số đỉnh và q là số cạnh, chứa dữ liệu về quan hệ giữa đỉnh và cạnh . Đơn giản nhất:
nếu đỉnh là một trong 2 đầu của cạnh , 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ới đỉnh thì phần tử 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
đó.
Lý thuyết đồ thị
3
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 đồ
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à không phẳng nếu như nó chứa một
đồ thị hai phía đầy đủ (complete bipartite graph ) hoặc nếu nó chứa đồ thị đầy đủ . 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 đủ)
•• 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 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 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 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
•• nguyễn văn lê
•• Frank Harary
•• Denes König
•• W.T. Tutte
• Sách trắng về lý thuyết đồ thị
[1]
4 và 5 có bậc bằng 3, đỉnh 6 có bậc 1.
Nếu tập cạnh E là hữu hạn thì tổng giá trị bậc của
các đỉnh gọi là bậc của đồ thị. Bậc của đồ thị
bằng hai lần số cạnh. Số các đỉnh bậc lẻ luôn là
số chẵn.
Bậc cực đại của đồ thị G, ký hiệu Δ(G), là bậc lớn nhất của các đỉnh trong đồ thị; bậc cực tiểu, δ(G), là bậc
nhỏ nhất của các đỉnh trong đồ thị.
Trong đồ thị có hướng Γ, bậc ngoài d
Γ
+
(v), số cung xuất phát từ đỉnh v, và bậc trong d
Γ
-
(v), số cung đi vào
đỉnh v. Bậc d
Γ
(v) của đỉnh v bằng tổng bậc ngoài và bậc trong của đỉnh đó. Bậc ngoài cực đại và cực tiểu được
ký hiệu Δ
+
(Γ) và δ
+
(Γ); bậc trong cực đại và cực tiểu, Δ
-
(Γ) và δ
-
(Γ). Trong ngữ cảnh rõ ràng, có thể bỏ qua
chỉ số dưới Γ
• Bất biến đồ thị (graph invariant)
là một tính chất của một đồ thị G, thường là một số hoặc một đa thức chỉ phụ thuộc vào lớp đẳng cấu của G. Ví
dụ: bậc của đồ thị.
• Chỉ số độc lập: Chỉ số độc lập của đồ thị G, ký hiệu α(G), là kích thước của tập độc lập lớn nhất của G.
• Chu trình trong đồ thị: là một đường đi đóng trong đồ thị. Đồ thị chỉ gồm một chu trình với n đỉnh được gọi là đồ
thị vòng, ký hiệu C
n
,
• Chu trình bao trùm: là cách gọi khác của chu trình Hamilton.
• Chu trình chẵn: là chu trình có độ dài chẵn.
• Chu trình có hướng: là một chu trình đơn mà mọi cung trong đó đều cùng hướng, nghĩa là mọi đỉnh đều có
bậc trong và bậc ngoài bằng 1. Có thể gọi đơn giản là chu trình khi ngữ cảnh rõ ràng.
• Chu trình đơn: là chu trình đi qua mỗi đỉnh không quá một lần. Trong đồ thị ở hình trên, (1, 5, 2, 1) là một
chu trình đơn. Nếu không chỉ rõ, chu trình thường được hiểu là một chu trình đơn.
• Chu trình Euler: là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần.
• Chu trình lẻ: là chu trình có độ dài lẻ.
• Chu vi nhỏ (girth): Chu vi nhỏ của một đồ thị là độ dài của chu trình đơn ngắn nhất của đồ thị.
• Chu vi lớn (circumference): Chu vi lớn của một đồ thị là độ dài của chu trình đơn dài nhất của đồ thị. Đối với đồ
thị không có chu trình, chu vi lớn và chu vi nhỏ được định nghĩa bằng giá trị vô cùng ∞.
• Chuỗi bậc (degree sequence): là danh sách các bậc của một đồ thị sắp xếp theo thứ tự giảm dần. (ví dụ, d
1
≥ d
2
≥
… ≥ d
n
). Một chuỗi giảm dần các số tự nhiên được coi là hiện thực được (realizable) nếu nó là chuỗi bậc của
Thuật ngữ lý thuyết đồ thị
7
một đồ thị nào đó.
• Cung: là cạnh có hướng.
D
• Dẫn xuất (induced)
• Đồ thị con: Một đồ thị con của đồ thị G là một đồ thị mà tập cạnh và tập đỉnh của nó là các tập con của các
thành phần tướng ứng của G.
• Đồ thị con bao trùm (spanning subgraph): Đồ thị con H là một đồ thị con bao trùm của đồ thị G nếu tập đỉnh
của H trùng với tập đỉnh của G. Ta nói rằng H bao trùm G.
• Đồ thị đầy đủ: Đồ thị đầy đủ bậc n, ký hiệu K
n
, là một đồ thị đơn gồm n đỉnh trong đó hai đỉnh bất kỳ đều
được nối với nhau bởi một cạnh. Có tất cả n(n-1)/2 cạnh. Đồ thị ví dụ không phải đồ thị đầy đủ.
• Đồ thị đơn: là đồ thị không có đa cạnh và không có khuyên.
• Đồ thị Euler có hướng: là một đồ thị có hướng mà mỗi đỉnh đều có bậc trong bằng bậc ngoài.
Thuật ngữ lý thuyết đồ thị
8
• Đồ thị hai phía: là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao
nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.
• Đồ thị hữu hạn: là đồ thị có hữu hạn cạnh và hữu hạn đỉnh. Nếu không được chỉ rõ tính chất, một đồ thị
thường được hiểu là hữu hạn.
• Đồ thị hữu hạn địa phương: là đồ thị vô hạn trong đó mỗi cạnh đều có bậc hữu hạn.
• Đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng Euclid sao cho không có hai cạnh nào cắt nhau. Đồ thị ví
dụ là đồ thị phẳng.
• Đồ thị phi chu trình: là đồ thị không có chu trình. Một đồ thị có hướng là phi chu trình nếu nó không chứa
chu trình có hướng.
• Đồ thị phổ dụng (universal graph): Đồ thị phổ dụng của một lớp đồ thị K là một đồ thị đơn nhỏ nhất mà mọi
đồ thị là phần tử của K đều là đồ thị con của nó.
• Đồ thị rỗng: là đồ thị không có cạnh và không có đỉnh. Hoặc, nó là một đồ thị không có cạnh nhưng có một số
đỉnh bất kỳ, khi đó, nó được gọi là đồ thị rỗng đỉnh. (Không có sự thống nhất giữa các tài liệu).
• Đồ thị vòng: là đồ thị chứa một chu trình duy nhất đi qua tất cả các đỉnh, mỗi đỉnh đều có bậc đúng bằng 2.
• Đồ thị vô hạn: là đồ thị có vô hạn cạnh hoặc vô hạn đỉnh hoặc cả hai.
• Đồ thị vô hướng: là đồ thị gồm toàn các cạnh không có hướng.
•• Độ dài
Độ dài của một đường đi là số cạnh mà nó đi qua. Đường đi P
• Đường đi đơn:là đường đi trong đó mỗi đỉnh chỉ được đi qua nhiều nhất một lần.
• Đường đi Euler (Eulerian path): là đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần. Đồ thị ví dụ không
có đường đi Euler.
Thuật ngữ lý thuyết đồ thị
9
• Đường đi Hamilton (Hamiltonian path): là đường đi đơn qua tất cả các đỉnh trong đồ thị. Đồ thị ví dụ có
đường đi Hamilton.
G
• Gắn nhãn đồ thị (graph labelling)
Việc gán các nhãn phân biệt (thường là các số) cho các cạnh và đỉnh của đồ thị.
•• Gốc
xem Đỉnh gốc.
K
•• Kề
Hai đỉnh u và v được coi là kề nhau, kí hiệu u ↓ v, nếu có một cạnh nối chúng. Trong đồ thị ví dụ, các đỉnh 1 và 2 kề
nhau, nhưng các đỉnh 2 và 4 không kề.
•• Khoảng cách
Khoảng cách d
G
(u, v) giữa hai đỉnh (không nhất thiết phân biệt u và v trong đồ thị G là độ dài đường đi ngắn
nhất giữa chúng. Có thể bỏ chỉ số dưới G nếu không sợ hiểu nhầm. Khi u và v là một, khoảng cách giữa chúng
bằng 0. Khi giữa u và v không có đường đi, khoảng cách giữa chúng là vô cùng ∞.
• Khuyên (loop)
Cạnh có hai đầu trùng nhau (cùng một đỉnh).
•• Kích thước của đồ thị
Kích thước của một đồ thị là số cạnh của nó, nghĩa là |E(G)|.
L
•• Lá
Xem Đỉnh lá.
•• Lát cắt đỉnh
• Nút (knot)
trong một đồ thị có hướng, nút là một tập các đỉnh và cung với tính chất: mọi đỉnh trong nút đều có cung từ đó
đi ra, và mọi cung xuất phát từ các đỉnh trong nút đều có đích là các đỉnh nằm trong nút. Do đó, không thể ra
khỏi nút nếu đi theo hướng của các cung.
Trong trường hợp đồ thị là sơ đồ sử dụng tài nguyên (general resource graph), một nút là điều kiện đủ cho
deadlock.
• Nút (node)
Trong một số ngữ cảnh, một đỉnh của đồ thị cũng được gọi là một nút. Chẳng hạn, các đỉnh trong một cây có
gốc thường được gọi là nút.
P
• Phản cạnh (anti-edge)
Là một cạnh "không tồn tại".
Cho hai đỉnh và , là một phản cạnh của đồ thị nếu không phải là cạnh của .
Nghĩa là: hoặc không có cạnh nào nối hai đỉnh, hoặc chỉ có một cung từ tới nếu là đồ thị có
hướng.
• Phần bù (complement)
Phần bù của một đồ thị G là một đồ thị có cùng tập đỉnh như G nhưng lại có tập cạnh thỏa mãn điều kiện:
xy là một cạnh của khi và chỉ khi xy không phải là cạnh của G.
Thuật ngữ lý thuyết đồ thị
11
Q
•• Quan hệ liên thuộc
Quan hệ giữa cạnh và đỉnh là một trong hai đầu của cạnh đó.
R
•• Rừng
là hợp của các cây; tương đương với một đồ thị phi chu trình.
S
•• Sắc số
Sắc số χ(G) của một đồ thị G là số nhỏ nhất các màu cần thiết để tô màu đồ thị đó, nghĩa là tô màu các đỉnh
của nó sao cho hai đỉnh kề nhau có màu khác nhau.
đường đi đến mọi đỉnh khác.
•• Thống trị
Thuật ngữ lý thuyết đồ thị
12
Đỉnh v thống trị đỉnh u nếu có một cạnh từ v tới u. Một tập đỉnh V thống trị một tập đỉnh U khác nếu mọi
đỉnh trong U đều thuộc V hoặc kề với một đỉnh nào đó trong V. Kích thước của tập thống trị nhỏ nhất được gọi
là chỉ số thống trị γ(G).
Tập đỉnh S được gọi là thống trị ngoài (out-dominating) nếu mọi đỉnh ngoài S đều bị thống trị bởi một đỉnh
nào đó thuộc S; gọi là thống trị trong (in-dominating) nếu mọi đỉnh thuộc S đều bị thống trị bởi một đỉnh nào
đó không thuộc S.
•• Trọng số
là các giá trị thường được gán cho các cạnh của đồ thị. Trọng số thường là các số thực. Chúng có thể bị giới
hạn trong phạm vi số hữu tỷ hoặc số nguyên. Một số thuật toán có thể đòi hỏi các giới hạn khác đối với trọng
số. Chẳng hạn, thuật toán Dijkstra chỉ dùng được cho các trọng số dương. Trọng số của đường đi hoặc trọng
số của cây trong một đồ thị có trọng số là tổng trọng số của các cạnh được chọn. Đôi khi một cạnh không tồn
tại được gán một trọng số đặc biệt để biểu diễn giá trị vô cùng. Từ chi phí đôi khi được dùng để chỉ trọng số.
Tham khảo
• Bollobás, Béla (1998). Modern Graph Theory. New York: Springer-Verlag. ISBN 0-387-98488-7. [Nhiều chủ đề
nâng cao kèm thêm tổng quan về quá trình phát triển tai cuối mỗi chương.]
• West, Douglas B. (2001). Introduction to Graph Theory (2ed). Upper Saddle River: Prentice Hall. ISBN
0-13-014400-2. [Nhiều minh họa, tham khảo, và bài tập. Hướng dẫn hoàn chỉnh nhất về chủ đề này.]
• Eric W. Weisstein. "Graph." From MathWorld—A Wolfram Web Resource. http:/ / mathworld. wolfram. com/
Graph. html
• Zaslavsky, Thomas. Glossary of signed and gain graphs and allied areas. Electronic Journal of Combinatorics,
Dynamic Surveys in Combinatorics, # DS 8. http:/ / www. combinatorics. org/ Surveys/
Đồ thị (lý thuyết đồ thị)
Bài này chỉ viết về các định nghĩa cơ bản. Để hiểu rộng hơn, xin xem lý thuyết đồ thị. Về ý nghĩa biểu diễn
hàm số trên hệ tọa độ, xem đồ thị hàm số.
Một đồ thị vô hướng với 6 đỉnh (nút) và 7 cạnh.
Trong toán học và tin học, đồ thị là đối tượng nghiên cứu cơ bản của
hướng, trong đó, nếu x và y là hai đỉnh thì đồ thị được phép có cả hai cung (x, y) và (y, x).Đồ thị đơn có hướng
(hoặc Đơn đồ thị có hướng) là một đồ thị có hướng, trong đó, nếu x và y là hai đỉnh thì đồ thị chỉ được phép có tối
đa một trong hai cung (x, y) hoặc (y, x).
Quiver thường được coi là một đồ thị có hướng. Nhưng trong thực hành, nó là một đồ thị có hướng với các không
gian vector (vector space) gắn với các đỉnh và các biến đổi tuyến tính gắn với các cung.
Đồ thị hỗn hợp
Đồ thị hỗn hợp G là một bộ ba có thứ tự G:= (V,E,A) với V, E và A được định nghĩa như trên.
Các định nghĩa khác
Như đã được định nghĩa ở trên, các cạnh của đồ thị vô hướng có hai đầu là hai đỉnh phân biệt; E và A là các tập hợp
(với các phần tử phân biệt). Nhiều ứng dụng cần các khái niệm rộng hơn, và các thuật ngữ cũng khác nhau. Một
khuyên (loop) là một cạnh (vô hướng hoặc có hướng) nối từ một đỉnh về chính nó; Kiểu cạnh này có được chấp nhận
hay không là tùy ở ứng dụng. Trong ngữ cảnh này, một cạnh nối hai đỉnh phân biệt được gọi là một liên kết (link).
Đôi khi, E và A được phép là các đa tập hợp (multiset), khi đó giữa hai đỉnh có thể có nhiều hơn một cạnh. Có thể
cho phép giữa hai đỉnh có nhiều cạnh bằng cách cho E là một tập hợp độc lập với V, và xác định các điểm đầu của
mỗi cạnh bằng một quan hệ liên thuộc (incidence relation) giữa V và E. Đối với đồ thị có hướng, ta áp dụng tương tự
cho tập hợp cạnh có hướng A, tuy nhiên, phải có hai quan hệ liên thuộc, một cho đỉnh đầu và một cho đỉnh cuối của
mỗi cung. Trong các sách, tùy theo ý của tác giả hoặc theo yêu cầu của chủ đề cụ thể mà từ "đồ thị" có thể hàm ý
cho phép hoặc không cho phép khuyên hay đa cạnh. Nếu đồ thị không cho phép đa cạnh (và không cho phép khuyên
nếu là đồ thị có hướng), đồ thị được gọi là đồ thị đơn. Mặt khác, nếu cho phép đa cạnh (và đôi khi cả khuyên), đồ
thị được gọi là đa đồ thị. Đôi khi, từ giả đồ thị (pseudograph) còn được dùng để hàm ý cả đa cạnh và khuyên đều
Đồ thị (lý thuyết đồ thị)
14
được phép. Trong các trường hợp đặc biệt, thậm chí còn cần đến các cạnh chỉ có một đỉnh, được gọi là nửa cạnh
(halfedge), hoặc không có đỉnh nào, (cạnh rời). Xem ví dụ tại signed graph.
Các định nghĩa khác
Xem thêm thuật ngữ lý thuyết đồ thị.
Hai cạnh của một đồ thị được coi là kề nhau nếu chúng có chung một đỉnh. Tương tự, hai đỉnh được coi là kề nhau
nếu chúng được nối với nhau bởi một cạnh. Một cạnh và đỉnh nằm trên cạnh đó được coi là liên thuộc với nhau.
Đồ thị chỉ có một đỉnh và không có cạnh nào được gọi là đồ thị tầm thường. Đồ thị không có cả đỉnh lẫn cạnh được
gọi là đồ thị rỗng
• Đồ thị đường (Line graph) (tạo đồ thị mới bằng cách chuyển cạnh thành đỉnh và tạo các cạnh tương ứng)
• Đồ thị đối ngẫu (Dual graph) (tạo đồ thị mới từ một đồ thị phẳng bằng cách tạo một đỉnh cho mỗi miền mặt phẳng
và các cạnh được nối giữa hai đỉnh tương ứng với hai miền kề nhau)
• Đồ thị bù (Complement graph)
Các phép toán hai ngôi
• Tích Đề-các của đồ thị (Cartesian product of graphs)
• Tích Ten-xơ của đồ thị (Tensor product of graphs)
Các suy rộng
Trong siêu đồ thị (hypergraph), một cạnh có thể nối nhiều hơn hai đỉnh.
Một đồ thị vô hướng có thể được coi là một phức đơn hình (simplicial complex) bao gồm các đơn hình 1 chiều (các
cạnh) và các đơn hình 0 chiều (các đỉnh). Như vậy, đa hình là suy rộng của đồ thị do chúng cho phép các đơn hình
nhiều chiều hơn.
Mỗi đồ thị đều cho một matroid, nhưng nói chung, không thể tạo lại đồ thị từ matroid của nó, do đó, matroid không
phải là suy rộng của đồ thị.
Trong lý thuyết mô hình (model theory), một đồ thị chỉ là một cấu trúc. Nhưng khi đó, không có giới hạn về số cạnh:
nó có thể là một số đếm bất kỳ.
Ma trận kề
16
Ma trận kề
Trong Toán học và Khoa học máy tính, ma trận kề (tiếng Anh: adjacency matrix) cho một đồ thị hữu hạn G gồm n
đỉnh là một ma trận n × n, trong đó, các ô không nằm trên đường chéo chính a
ij
là số cạnh nối hai đỉnh i và j, còn ô
nằm trên đường chéo chính a
ii
là hai lần số khuyên tại đỉnh i, hoặc chỉ là số khuyên tại đỉnh đó (bài này chọn cách
thứ nhất, các đồ thị có hướng luôn theo cách thứ hai). Mỗi đồ thị có duy nhất một ma trận kề, các đồ thị khác nhau có
các ma trận kề khác nhau. Trong trường hợp đặc biệt của đồ thị đơn hữu hạn, ma trận kề là một ma trận (0,1) với các
giá trị 0 nằm trên đường chéo chính. Nếu đồ thị là vô hướng, ma trận kề là ma trận đối xứng.
Đối với đồ thị thưa, nghĩa là đồ thị có ít cạnh, người ta thường chọn dùng danh sách kề hơn do nó chiếm ít bộ nhớ
• 2 và 6 có cạnh nối =>
• 3 và 4 có cạnh nối =>
• 3 và 5 có cạnh nối =>
• 3 và 7 có cạnh nối =>
• 4 và 6 có cạnh nối =>
• 4 và 5 có cạnh nối =>
• 5 và 6 có cạnh nối =>
• Còn lại các cặp đỉnh không có cạnh nối với nhau => = = 0
•• Kết quả sau khi biểu diễn đồ thị G sang ma trận kề:
Ma trận kề
18
Đồ thị G
• Trong đó dòng và cột màu vàng là danh sách các đỉnh của đồ thị vô hướng G.
Biểu diễn đồ thị có hướng
Cho đồ thị G có hướng (4 đỉnh):
Đồ thị G
•• Gọi A là ma trận kề biểu diễn đồ thị G.
•• Từ đồ thị G, ta thấy:
• 1 và 2 có cạnh nối và 1 đi vào 2 =>
Ma trận kề
19
• 2 và 3 có cạnh nối và 2 đi vào 3 =>
• 3 và 1 có cạnh nối và 3 đi vào 1 =>
• 4 và 1 có cạnh nối và 4 đi vào 1 =>
• Còn lại các cặp đỉnh không có cạnh nối thì
•• Kết quả sau khi biểu diễn đồ thị G sang ma trận kề:
Đồ thị G
Tính chất
•• Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là:
Ngược lại, mỗi (0,1)-ma trận đối xứng cấp n sẽ tương ứng, chính xác đến cách đánh số đỉnh (còn nói là: chính xác
PA
1
P
Ì−1
= A
2
.
Cụ thể là A
1
và A
2
là các ma trận đồng dạng và do đó có cùng đa thức cực tiểu (minimal polynomial), đa thức đặc
trưng (characteristic polynomial), các giá trị riêng, định thức (determinant) và vết của ma trận (trace). Do đó chúng
có thể được dùng như các bất biến đẳng cấu của đồ thị. Cho trước hai ma trận kề, có thể xây dựng lại ma trận hoán vị
đã được sử dụng: xem chi tiết tại Ma trận hoán vị.
Tuy nhiên, cần lưu ý rằng điều ngược lại không đúng: hai đồ thị có thể có bộ giá trị riêng giống nhau nhưng chúng
không đẳng cấu. Phép nhân với ma trận hoán vị có thể được coi là việc gắn nhãn mới cho các cạnh.
Nếu A là ma trận kề của đồ thị có hướng hoặc vô hướng G, thì ma trận A
n
(ma trận tích của n lần A) có một ý nghĩa
thú vị: ô tại hàng i và cột j cho biết số đường đi (có hướng hoặc vô hướng) có độ dài n từ đỉnh i tới đỉnh j.
Ma trận I − A (trong đó I ký hiệu ma trận đơn vị n×n) là nghịch đảo được khi và chỉ khi đồ thị G không có chu trình
có hướng. Khi đó, ma trận nghịch đảo (I − A)
−1
có ý nghĩa sau: ô tại hàng i và cột j cho biết số đường đi có hướng từ
đỉnh i tới đỉnh j (giá trị này luôn hữu hạn nếu đồ thị không có chu trình có hướng). Điều này có thể được giải thích
bằng cấp số nhân (geometric series) của các ma trận:
(I − A)
−1
= I + A + A
21
Mặt khác, khi dùng cho đồ thị thưa, danh sách kề lại thắng thế, do chúng không lưu trữ các cạnh không tồn tại. Sử
dụng cài đặt danh sách liên kết đơn giản trên một máy tính 32-bit, một danh sách kề cho một đồ thị vô hướng cần
khoảng 16e byte, trong đó e là số cạnh của đồ thị.
Lưu ý rằng một đồ thị có thể có nhiều nhất n
2
cạnh (kể cả các khuyên). Giả sử d = e/n
2
ký hiệu mật độ của đồ thị. Ta
có: 16e > n
2
/8, có nghĩa là danh sách kề chiếm nhiều không gian hơn khi d > 1/128. Do đó, chỉ nên dùng danh sách
kề với đồ thị thưa.
Bên cạnh thỏa hiệp về không gian bộ nhớ, các cấu trúc dữ liệu khác nhau còn tạo thuận lợi cho các thao tác dữ liệu
khác nhau. Với một danh sách kề, ta dễ dàng tìm mọi đỉnh kề với một đỉnh cho trước; ta chỉ cần đọc danh sách kề
của đỉnh đó. Với một ma trận kề, ta phải duyệt toàn bộ một hàng, việc đó cần thời gian O(n). Còn nếu ta lại muốn
biết giữa hai đỉnh cho trước có cạnh nối hay không, điều này có thể được xác định ngay lập tức với một ma trận kề,
trong khi đó với một danh sách kề, việc này đòi hỏi thời gian tỷ lệ thuận với bậc nhỏ nhất của các đỉnh trong đồ thị.
Tham khảo
[1][1] CHUNG, Fan RK. Spectral Graph Teory. Amer Mathematical Society, 1997.
[2] Trần Đan Thư - Dương Anh Đức, Lý Thuyết Đồ Thị, Đại Học Khoa Học Tự Nhiên - DHQGTP.HCM, thánh 9 năm 2008
[3] Chartrand, G.,http:/ / www. amazon. com/ exec/ obidos/ ASIN/ 0486247759/ ref=nosim/ weisstein-20/ [Introductory Graph Theory], New
York: Dover, p. 218, 1985.
Tài liệu
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms,
Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 22.1: Representations of graphs,
pp.Ì527–531.
Các chủ đề chính trong toán học
Nền tảng toán học | Đại số | Giải tích | Hình học | Lý thuyết số | Toán học rời rạc | Toán học ứng dụng
|
2
ký hiệu mật độ của đồ thị. Ta
có: 16e > n
2
/8, có nghĩa là danh sách kề chiếm nhiều không gian hơn khi d > 1/128. Do đó, chỉ nên dùng danh sách
kề với đồ thị thưa.
Bên cạnh thỏa hiệp về không gian bộ nhớ, các cấu trúc dữ liệu khác nhau còn tạo thuận lợi cho các thao tác dữ liệu
khác nhau. Với một danh sách kề, ta dễ dàng tìm mọi đỉnh kề với một đỉnh cho trước; ta chỉ cần đọc danh sách kề
của đỉnh đó. Với một ma trận kề, ta phải duyệt toàn bộ một hàng, việc đó cần thời gian O(n). Còn nếu ta lại muốn
biết giữa hai đỉnh cho trước có cạnh nối hay không, điều này có thể được xác định ngay lập tức với một ma trận kề,
trong khi đó với một danh sách kề, việc này đòi hỏi thời gian tỷ lệ thuận với bậc nhỏ nhất của các đỉnh trong đồ thị.
Copyright: Tài liệu đại học ©