Lý Thuyết đồ Thị – Wikipedia Tiếng Việt

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. (Tìm hiểu cách thức và thời điểm xóa thông báo này)

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 đồ 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à quy đị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.)

Lịch sử

[sửa | sửa mã nguồn]

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ị.

Định nghĩa

[sửa | sửa mã nguồn] Bài chi tiết: Đồ thị (toán học)

Cách vẽ đồ thị

[sửa | sửa mã nguồn] 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.

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

[sửa | sửa mã nguồn] 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.

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

[sửa | sửa mã nguồn]

• 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

[sửa | sửa mã nguồn]

• Ma trận liên thuộc (Incidence matrix) - Đồ thị được biểu diễn bằng một ma trận [ b i j ] {\displaystyle [b_{ij}]} kích thước p × q, trong đó p là số đỉnh và q là số cạnh, b i j = 1 {\displaystyle b_{ij}=1} chứa dữ liệu về quan hệ giữa đỉnh v i {\displaystyle v_{i}} và cạnh x j {\displaystyle x_{j}} . Đơn giản nhất: b i j = 1 {\displaystyle b_{ij}=1} nếu đỉnh v i {\displaystyle v_{i}} là một trong 2 đầu của cạnh x j {\displaystyle 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 i {\displaystyle v_{i}} với đỉnh v j {\displaystyle v_{j}} thì phần tử M i , j {\displaystyle 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 đó.

Các bài toán đồ thị

[sửa | sửa mã nguồn]

Tìm đồ thị con

[sửa | sửa mã nguồn]

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 ) K 3 , 3 {\displaystyle K_{3,3}} hoặc nếu nó chứa đồ thị đầy đủ K 5 {\displaystyle K_{5}} . 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ị

[sửa | sửa mã nguồn] Bài chi tiết: Tô màu đồ 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 Erdős-Faber-Lovász conjecture (hiện chưa ai giải được)
• Bài toán total coloring conjecture (hiện chưa ai giải được)
• Bài toán list coloring conjecture (hiện chưa ai giải được)

Các bài toán đường đi

[sửa | sửa mã nguồn]

• 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

[sửa | sửa mã nguồn]

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

Visibility graph problems

[sửa | sửa mã nguồn]

• Museum guard problem

Các bài toán phủ

[sửa | sửa mã nguồn] Bài chi tiết: 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

[sửa | sửa mã nguồn]

• 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

[sửa | sửa mã nguồn]

• Lý thuyết Ramsey
• Toán tổ hợp (Combinatorics)

Ứng dụng

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

• Frank Harary
• Denes König
• W.T. Tutte
• Sách trắng về lý thuyết đồ thị Lưu trữ ngày 11 tháng 1 năm 2006 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ọ.

Xem thêm

[sửa | sửa mã nguồn]

• Thuật ngữ lý thuyết đồ thị
• Cấu trúc dữ liệu cây có thứ tự – đồ 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

[sửa | sửa mã nguồn]

Liên kết ngoài

[sửa | sửa mã nguồn]

• Sách trực tuyến về Lý thuyết đồ thị
• Hướng dẫn về lý thuyết đồ thị Lưu trữ ngày 16 tháng 1 năm 2012 tại Wayback Machine
• Bài giảng của một môn học về các thuật toán đồ thị Lưu trữ ngày 31 tháng 8 năm 2005 tại Wayback Machine
• 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) Lưu trữ ngày 29 tháng 5 năm 2013 tại Wayback Machine
• Sưu tập ảnh số 1: một số mạng lưới thực
• Các tạp chí lý thuyết đồ thị Lưu trữ ngày 4 tháng 7 năm 2013 tại Wayback Machine

Wikimedia Commons có thêm hình ảnh và phương tiện về Lý thuyết đồ thị.

x t s Toán học
Lịch sử Dòng thời gian Tương lai Đại cương Danh sách Ký hiệu
Nền tảng	Logic toán Lý thuyết hình thái Lý thuyết phạm trù Lý thuyết tập hợp Lý thuyết thông tin Triết học toán học
Đại số	Đa tuyến tính Đồng điều Giao hoán Lý thuyết nhóm Phổ dụng Sơ cấp Trừu tượng Tuyến tính
Giải tích	Giải tích điều hòa Giải tích hàm Giải tích phức Giải tích thực Lý thuyết độ đo Phương trình vi phân Vi tích phân
Rời rạc	Lý thuyết đồ thị Lý thuyết thứ tự Tổ hợp
Hình học	Đại số Euclid Giải tích Hữu hạn Rời rạc Số học Vi phân
Lý thuyết số	Số học Đại số Giải tích Hình học Diophantos
Tô pô	Đại số Hình học Đại cương Vi phân Lý thuyết đồng luân
Ứng dụng	Hóa học Kinh tế Lý thuyết điều khiển tự động Lý thuyết trò chơi Sinh học Tài chính Tâm lý Thống kê toán học Xác suất Thống kê Vật lý
Tính toán	Khoa học máy tính Lý thuyết tính toán Lý thuyết độ phức tạp tính toán Đại số máy tính Giải tích số Tối ưu hóa
Liên quan	Toán học giải trí Toán học và nghệ thuật Giáo dục toán học
Thể loại · Chủ đề · Commons · Dự án

x t s Khoa học máy tính
Chú ý: Bản mẫu này cơ bản dựa trên Hệ thống xếp loại điện toán ACM năm 2012.
Phần cứng	Mạch in Thiết bị ngoại vi Vi mạch Vi mạch tích hợp Hệ thống trên vi mạch (SoC) Tiêu thụ năng lượng (Điện toán xanh) Tự động hóa thiết kế điện tử Tăng tốc phần cứng Bộ xử lý Kích thước / Dạng thức
Tổ chức hệ thống máy tính	Kiến trúc máy tính Độ phức tạp tính toán Độ tin cậy hệ thống Hệ thống nhúng Hệ thống thời gian thực
Mạng máy tính	Kiến trúc mạng Giao thức mạng Phần cứng mạng Bộ lập lịch trình mạng Hiệu suất mạng Dịch vụ mạng
Tổ chức phần mềm	Trình thông dịch Middleware Máy ảo Hệ điều hành Chất lượng phần mềm
Ký pháp và công cụ phần mềm	Mẫu hình lập trình Ngôn ngữ lập trình Trình biên dịch Ngôn ngữ miền chuyên biệt Ngôn ngữ mô hình hóa Khung phần mềm Môi trường phát triển tích hợp Quản lý cấu hình phần mềm Thư viện phần mềm Kho chứa phần mềm
Phát triển phần mềm	Biến điều khiển Quy trình phát triển phần mềm Phân tích yêu cầu Thiết kế phần mềm Xây dựng phần mềm Triển khai phần mềm Công nghệ phần mềm Bảo trì phần mềm Nhóm lập trình Mô hình nguồn mở
Lý thuyết tính toán	Mô hình tính toán Ngẫu nhiên Ngôn ngữ hình thức Lý thuyết Automat Lý thuyết khả tính Lý thuyết độ phức tạp tính toán Logic Ngữ nghĩa
Thuật toán	Thiết kế thuật toán Phân tích thuật toán Hiệu quả thuật toán Thuật toán ngẫu nhiên Hình học tính toán
Toán học về điện toán	Toán học rời rạc Xác suất Thống kê Phần mềm toán học Lý thuyết thông tin Giải tích toán học Giải tích số Khoa học máy tính lý thuyết
Hệ thống thông tin	Hệ quản trị cơ sở dữ liệu Hệ thống lưu trữ thông tin Hệ thống thông tin doanh nghiệp Hệ thống thông tin xã hội Hệ thống thông tin địa lý Hệ thống hỗ trợ ra quyết định Hệ thống điều khiển quá trình Hệ thống thông tin đa phương tiện Khai phá dữ liệu Thư viện số Nền tảng máy tính Tiếp thị kỹ thuật số World Wide Web Truy hồi thông tin
Bảo mật	Mật mã học Các phương pháp hình thức Hacker bảo mật Dịch vụ bảo mật Hệ thống phát hiện xâm nhập Bảo mật phần cứng Bảo mật mạng An toàn thông tin Bảo mật ứng dụng
Tương tác người–máy	Thiết kế tương tác Điện toán xã hội Điện toán khắp nơi Trực quan hóa Khả năng tiếp cận
Tương tranh	Tính toán tương tranh Tính toán song song Điện toán phân tán Đa luồng Đa xử lý
Trí tuệ nhân tạo	Xử lý ngôn ngữ tự nhiên Biểu diễn tri thức và suy luận Thị giác máy tính Lập kế hoạch và lên lịch tự động Phương pháp tìm kiếm Phương pháp điều khiển Triết học về trí tuệ nhân tạo Trí tuệ nhân tạo phân tán
Học máy	Học có giám sát Học không có giám sát Học tăng cường Học đa tác vụ Kiểm chứng chéo
Đồ họa	Hoạt hình Thực tế mở rộng Tăng cường Hỗn hợp Ảo Kết xuất Thao túng hình ảnh Bộ xử lý đồ họa Nén ảnh Mô hình hóa dạng khối
Điện toán ứng dụng	Điện toán lượng tử Thương mại điện tử Phần mềm doanh nghiệp Toán học tính toán Vật lý tính toán Hóa học tính toán Sinh học tính toán Khoa học xã hội tính toán Kỹ thuật tính toán Điện toán khả vi Y tế tính toán Nghệ thuật số Xuất bản điện tử Chiến tranh mạng Bầu cử điện tử Trò chơi video Soạn thảo văn bản Vận trù học Công nghệ giáo dục Quản lý tài liệu
Thể loại Đề cương Thuật ngữ