Null Graph
Đồ thị rỗng được định nghĩa là đồ thị chỉ bao gồm các đỉnh cô lập.
Null Graph, còn được gọi là Graph rỗng, là một khái niệm trong lý thuyết đồ thị. Nó là một đồ thị không có đỉnh (vertex) và không có cạnh (edge).
Dưới đây là một số điểm đặc trưng và thuộc tính của Null Graph:
- Không có đỉnh: Null Graph không có bất kỳ đỉnh nào. Điều này có nghĩa là không có bất kỳ điểm nào trong đồ thị để tạo thành các liên kết hoặc quan hệ.
- Không có cạnh: Null Graph cũng không có bất kỳ cạnh nào. Vì không có đỉnh, nên không có cách nào để tạo ra các kết nối hoặc liên kết giữa các đỉnh.
- Số lượng đỉnh và cạnh: Null Graph có số lượng đỉnh và cạnh bằng 0. Điều này làm cho nó trở thành một đồ thị rỗng hoàn toàn.
- Trạng thái đồ thị: Null Graph được coi là một trạng thái đặc biệt của đồ thị. Nó không có nội dung hoặc cấu trúc và thường được sử dụng để đại diện cho một trường hợp đặc biệt hoặc trạng thái không hợp lệ trong lý thuyết đồ thị.
- Ứng dụng: Null Graph không có ứng dụng rõ ràng trong các vấn đề thực tế về đồ thị. Tuy nhiên, trong lý thuyết đồ thị, nó có thể được sử dụng trong một số tình huống đặc biệt, ví dụ như trong phân tích lý thuyết hoặc để minh họa khái niệm đồ thị rỗng.
- Đặc điểm toán học: Null Graph là một đồ thị đơn đơn giản nhất. Nó không có thông tin hoặc cấu trúc nào để phân tích hoặc xử lý.
Như vậy, Null Graph là một trạng thái đặc biệt trong lý thuyết đồ thị, mô tả một đồ thị không có đỉnh và không có cạnh.
Ví dụ: Đồ thị trong hình là đồ thị rỗng và các đỉnh là các đỉnh cô lập.
Undirected Graphs
Undirected Graphs, hay còn được gọi là đồ thị vô hướng, là một loại đồ thị trong lý thuyết đồ thị. Trong đồ thị vô hướng, các cạnh không có hướng, có nghĩa là một cạnh nối hai đỉnh cho phép di chuyển theo cả hai hướng.
Dưới đây là một số điểm đặc trưng và thuộc tính của đồ thị vô hướng:
- Đỉnh (Vertex): Đồ thị vô hướng bao gồm một tập hợp các đỉnh, đại diện cho các điểm trong đồ thị. Mỗi đỉnh có thể kết nối với các đỉnh khác thông qua các cạnh.
- Cạnh (Edge): Các cạnh trong đồ thị vô hướng không có hướng. Điều này có nghĩa là một cạnh nối hai đỉnh cho phép di chuyển theo cả hai hướng. Cặp đỉnh liên kết bởi một cạnh được gọi là “đối tác” của nhau.
- Độ mạnh (Degree): Độ mạnh của một đỉnh trong đồ thị vô hướng là số lượng cạnh kết nối với đỉnh đó. Nó biểu thị sự kết nối của đỉnh với các đỉnh khác trong đồ thị.
- Đồ thị liên thông: Một đồ thị vô hướng được gọi là liên thông nếu có đường đi trực tiếp hoặc gián tiếp giữa bất kỳ cặp đỉnh nào trong đồ thị. Điều này có nghĩa là từ một đỉnh bất kỳ, ta có thể đến được tất cả các đỉnh khác trong đồ thị.
- Vòng (Cycle): Một vòng trong đồ thị vô hướng là một chuỗi các đỉnh mà đỉnh đầu tiên và đỉnh cuối cùng là cùng một đỉnh, và các đỉnh trong chuỗi không trùng nhau.
- Cây (Tree): Một cây là một đồ thị vô hướng không chứa chu trình. Nó có thể được coi là một dạng đặc biệt của đồ thị vô hướng, trong đó có một đỉnh gốc và các đỉnh còn lại được kết nối với đỉnh gốc thông qua các cạnh.
Đồ thị vô hướng có nhiều ứng dụng trong nhiều lĩnh vực như mạng máy tính, lập lịch, tối ưu hóa, truy vấn dữ liệu và phân tích xã hội
Ví dụ: Cho V = {1, 2, 3, 4} và E = {(1, 2), (1, 4), (3, 4), (2, 3)}. Vẽ đồ thị.
Giải pháp: Biểu đồ có thể được vẽ theo một số cách.
Hai trong số đó như sau:
Xem thêm Computation graph trong Deep learning với Python
Multigraph
Multigraph, hay còn được gọi là đồ thị đa cạnh, là một loại đồ thị trong lý thuyết đồ thị. Trái ngược với đồ thị đơn, một multigraph cho phép có nhiều cạnh nối cùng một cặp đỉnh.
Dưới đây là một số điểm đặc trưng và thuộc tính của multigraph:
- Đỉnh (Vertex): Multigraph bao gồm một tập hợp các đỉnh, đại diện cho các điểm trong đồ thị. Mỗi đỉnh có thể kết nối với các đỉnh khác thông qua các cạnh.
- Cạnh (Edge): Multigraph cho phép có nhiều cạnh nối cùng một cặp đỉnh. Điều này có nghĩa là hai đỉnh có thể được kết nối bởi nhiều cạnh khác nhau.
- Độ mạnh (Degree): Độ mạnh của một đỉnh trong multigraph là số lượng cạnh kết nối với đỉnh đó. Nó biểu thị sự kết nối của đỉnh với các đỉnh khác trong đồ thị. Trong multigraph, một đỉnh có thể có một độ mạnh lớn hơn 1 nếu có nhiều cạnh nối tới cùng một đỉnh.
- Đồ thị liên thông: Một multigraph được gọi là liên thông nếu có đường đi trực tiếp hoặc gián tiếp giữa bất kỳ cặp đỉnh nào trong đồ thị. Điều này có nghĩa là từ một đỉnh bất kỳ, ta có thể đến được tất cả các đỉnh khác trong đồ thị dựa trên các cạnh có sẵn.
- Vòng (Cycle): Một vòng trong multigraph là một chuỗi các đỉnh mà đỉnh đầu tiên và đỉnh cuối cùng là cùng một đỉnh, và các đỉnh trong chuỗi không trùng nhau. Trong multigraph, có thể có nhiều cạnh khác nhau nối các đỉnh trong vòng.
- Ứng dụng: Multigraphs có thể được sử dụng để mô hình hệ thống hoặc quan hệ có khả năng xảy ra nhiều sự kết nối hoặc tương tác giữa các thành phần. Chúng có thể được áp dụng trong mô hình hóa mạng giao thông, mô phỏng mạng xã hội, phân tích dữ liệu, và nhiều lĩnh vực khác.
Directed Graphs
Directed Graphs, hay còn được gọi là đồ thị có hướng, là một loại đồ thị trong lý thuyết đồ thị. Trong đồ thị có hướng, các cạnh có hướng, có nghĩa là chúng chỉ cho phép di chuyển theo một hướng duy nhất từ đỉnh nguồn tới đỉnh đích.
Dưới đây là một số điểm đặc trưng và thuộc tính của đồ thị có hướng:
- Đỉnh (Vertex): Đồ thị có hướng bao gồm một tập hợp các đỉnh, đại diện cho các điểm trong đồ thị. Mỗi đỉnh có thể có cạnh đi vào và cạnh đi ra đến các đỉnh khác.
- Cạnh (Edge): Các cạnh trong đồ thị có hướng chỉ cho phép di chuyển từ đỉnh nguồn tới đỉnh đích. Một cạnh được biểu diễn bởi một cặp đỉnh (nguồn, đích) và có thể được gán một hướng duy nhất.
- Độ ra (Outdegree) và độ vào (Indegree): Độ ra của một đỉnh là số lượng cạnh đi ra từ đỉnh đó. Độ vào của một đỉnh là số lượng cạnh đi vào đỉnh đó. Điều này cho phép đánh giá mức độ kết nối của một đỉnh trong đồ thị.
- Đồ thị liên thông: Một đồ thị có hướng được gọi là liên thông nếu có đường đi từ một đỉnh bất kỳ đến bất kỳ đỉnh khác trong đồ thị. Điều này có nghĩa là từ một đỉnh bất kỳ, ta có thể đến được tất cả các đỉnh khác trong đồ thị thông qua các cạnh có hướng.
- Chu trình (Cycle): Một chu trình trong đồ thị có hướng là một chuỗi các đỉnh mà ta có thể đi từ đỉnh đầu tiên đến đỉnh cuối cùng thông qua các cạnh có hướng.
- Ứng dụng: Đồ thị có hướng được sử dụng rộng rãi trong nhiều lĩnh vực như mạng máy tính, hệ thống định tuyến, thuật toán đồ thị, xử lý ngôn ngữ tự nhiên và phân tích mạng xã hội. Chúng giúp mô phỏng các quan hệ không đối xứng, sự tương tác hướng một chiều và luồng dữ liệu trong các hệ thống phức tạp.
Ví dụ: Xét đồ thị G = (V, E) như hình bên. Xác định tập đỉnh và tập cạnh của đồ thị G.
Lời giải: Tập hợp đỉnh và cạnh của đồ thị G = (V, E) như sau
G = {{1,2,3}, {(1,2), (2,1), (2,2), (2,3), (1,3)}}.
Xem thêm Phân tích dữ liệu Uber – trực quan hóa dữ liệu
Undirected Complete Graph
Đồ thị không định hướng hoàn chỉnh, hay còn được gọi là đồ thị hoàn chỉnh không định hướng, là một loại đồ thị trong đó mọi cặp đỉnh khác nhau đều được nối với nhau bằng một cạnh không định hướng.
Dưới đây là một số đặc điểm và thuộc tính chính của đồ thị không định hướng hoàn chỉnh:
- Đỉnh: Đồ thị không định hướng hoàn chỉnh bao gồm một tập hợp các đỉnh, đại diện cho các điểm trong đồ thị. Mỗi đỉnh được nối với tất cả các đỉnh khác trong đồ thị.
- Cạnh: Trong đồ thị không định hướng hoàn chỉnh, mỗi cặp đỉnh khác nhau đều được nối với nhau bằng một cạnh không định hướng. Điều này có nghĩa là các cạnh không có hướng và có thể đi qua hai đỉnh theo cả hai hướng.
- Độ: Độ của một đỉnh trong đồ thị không định hướng hoàn chỉnh là số lượng cạnh mà nó kết nối với các đỉnh khác trong đồ thị. Vì mọi cặp đỉnh khác nhau đều được nối với nhau, độ của mỗi đỉnh là tổng số đỉnh trừ đi 1.
- Liên thông: Một đồ thị không định hướng hoàn chỉnh được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh trong đồ thị. Điều này có nghĩa là từ một đỉnh bất kỳ, ta có thể đến được tất cả các đỉnh khác trong đồ thị thông qua các cạnh không định hướng.
- Chu trình: Trong đồ thị không định hướng hoàn chỉnh, có thể tạo ra chu trình của mọi độ dài. Một chu trình là một đường đi đóng trong đồ thị, bắt đầu và kết thúc tại cùng một đỉnh, đi qua một chuỗi các đỉnh khác nhau.
- Ứng dụng: Đồ thị không định hướng hoàn chỉnh được sử dụng rộng rãi trong nhiều lĩnh vực như mạng máy tính, hệ thống giao thông, lý thuyết đồ thị và truyền thông. Chúng cung cấp một mô hình cho các hệ thống hoàn chỉnh và giúp nghiên cứu tính chất của các hệ thống kết nối đầy
Ví dụ: Vẽ đồ thị hoàn chỉnh vô hướng k4 và k6.
Giải pháp: Đồ thị hoàn chỉnh vô hướng của k4 được hiển thị trong hình 1 và của k6 được hiển thị trong hình 2.
Connected và Disconnected Graph:
Đồ thị liên thông là một loại đồ thị trong đó có một đường đi giữa mọi cặp đỉnh. Nghĩa là từ bất kỳ hai đỉnh nào trong đồ thị, ta có thể đi từ đỉnh này đến đỉnh kia thông qua một chuỗi các cạnh.
Dưới đây là một số đặc điểm và thuộc tính chính của đồ thị liên thông:
- Đỉnh: Một đồ thị liên thông bao gồm một tập hợp các đỉnh, đại diện cho các điểm trong đồ thị. Mỗi đỉnh có thể kết nối với một hoặc nhiều đỉnh khác trong đồ thị.
- Cạnh: Trên đồ thị liên thông, các cạnh có thể đi từ một đỉnh đến đỉnh khác, tạo thành một đường đi giữa chúng. Điều này có thể là cạnh trực tiếp nối hai đỉnh hoặc có thể đi qua một số đỉnh trung gian.
- Liên thông: Một đồ thị được gọi là liên thông nếu có ít nhất một đường đi giữa mọi cặp đỉnh. Điều này có nghĩa là từ một đỉnh bất kỳ, ta có thể đến được tất cả các đỉnh khác trong đồ thị thông qua các cạnh.
- Thành phần liên thông: Trong một đồ thị không liên thông, có thể tồn tại nhiều thành phần liên thông. Mỗi thành phần liên thông là một tập hợp các đỉnh mà giữa chúng có ít nhất một đường đi, nhưng không có đường đi nối với các đỉnh nằm ngoài thành phần đó.
- Bậc liên thông: Bậc liên thông của một đỉnh trong đồ thị liên thông là số lượng các đỉnh kết nối trực tiếp với nó. Điều này thể hiện mức độ kết nối của mỗi đỉnh trong đồ thị.
- Ứng dụng: Đồ thị liên thông được áp dụng rộng rãi trong nhiều lĩnh vực như mạng máy tính, giao thông, xử lý ngôn ngữ tự nhiên và phân tích mạng xã hội. Chúng giúp xác định tính kết nối, tìm kiếm đường đi và phân tích sự lan truyền trong các hệ thống phức tạp.
Xem thêm Các thay đổi về Graph API của Facebook
Ví dụ: Hãy xem xét biểu đồ được hiển thị trong hình. Xác định xem các đồ thị có
(a) Đồ thị ngắt kết nối
(b) Đồ thị được kết nối.
Ngoài ra, hãy viết các thành phần được kết nối của chúng.
(i) Biểu đồ được hiển thị trong hình là một Đồ thị ngắt kết nối và các thành phần được kết nối của nó là
{V1, V2, V3, V4}, {V5, V6, V7, V8} và {V9, V10}.
(ii) Đồ thị được hiển thị trong hình là Đồ thị ngắt kết nối và các thành phần được kết nối của nó là
{V1, V2}, {V3, V4}, {V5, V6}, {V7, V8}, {V9, V10} và {V11, V12}.
(iii) Đồ thị trong hình là đồ thị liên thông.
- Connected Component: Một đồ thị con của đồ thị G được gọi là thành phần liên thông của G, nếu nó không được chứa trong bất kỳ đồ thị con nào lớn hơn của G, đồ thị được kết nối. Nó được xác định bằng cách liệt kê các đỉnh của nó.
Ví dụ: Hãy xem xét biểu đồ được hiển thị trong hình. Xác định các thành phần được kết nối của nó.
Giải: Các thành phần liên thông của đồ thị này là {a, b, c}, {d, e, f}, {g, h, i} và {j}.
Xem thêm Thuật toán Dijkstra
Directed Complete Graph:
Đồ thị có hướng hoàn chỉnh, còn được gọi là đồ thị hoàn chỉnh có hướng, là một loại đồ thị trong đó mọi cặp đỉnh khác nhau đều được nối với nhau bằng một cạnh có hướng.
Dưới đây là một số đặc điểm và thuộc tính chính của đồ thị có hướng hoàn chỉnh:
- Đỉnh: Đồ thị có hướng hoàn chỉnh bao gồm một tập hợp các đỉnh, đại diện cho các điểm trong đồ thị. Mỗi đỉnh có cạnh đi vào và cạnh đi ra đến tất cả các đỉnh khác trong đồ thị.
- Cạnh: Trong đồ thị có hướng hoàn chỉnh, mỗi cặp đỉnh khác nhau đều được nối với nhau bằng một cạnh có hướng. Cạnh có hướng chỉ cho phép di chuyển từ đỉnh xuất phát đến đỉnh đích theo một hướng nhất định.
- Bậc ra và bậc vào: Bậc ra của một đỉnh trong đồ thị có hướng hoàn chỉnh là số lượng cạnh đi ra từ đỉnh đó, trong khi bậc vào là số lượng cạnh đi vào đỉnh đó. Trong đồ thị có hướng hoàn chỉnh, mỗi đỉnh có cùng bậc vào và bậc ra, bằng tổng số đỉnh trừ 1.
- Chu trình: Trong đồ thị có hướng hoàn chỉnh, có thể tạo ra chu trình của mọi độ dài. Một chu trình là một đường đi đóng trong đồ thị, bắt đầu và kết thúc tại cùng một đỉnh, đi qua một chuỗi các đỉnh khác nhau.
- Liên thông: Một đồ thị có hướng hoàn chỉnh không phải là một đồ thị liên thông, vì có thể tồn tại các đỉnh không thể tiếp cận từ một số đỉnh khác. Điều này do các cạnh có hướng chỉ cho phép di chuyển theo một hướng nhất định.
- Ứng dụng: Đồ thị có hướng hoàn chỉnh được sử dụng trong nhiều lĩnh vực như mạng máy tính, hệ thống giao thông, lập lịch và quy hoạch. Chúng cung cấp một mô hình cho các hệ thống có quy luật di chuyển theo hướng cụ thể và được sử dụng để tối ưu hóa quá trình định tuyến, xử lý dữ liệu và
Ví dụ: Vẽ đồ thị hoàn chỉnh có hướng K3 và K5.
Giải pháp: Đặt số lượng đỉnh vào vị trí thích hợp và sau đó vẽ một mũi tên từ mỗi đỉnh đến mọi đỉnh khác như trong hình:
Complementary Graph:
Đồ thị bù, còn được gọi là đồ thị phụ hoặc đồ thị bù đối, là một loại đồ thị được tạo ra từ một đồ thị ban đầu bằng cách đảo hướng các cạnh có và không có trong đồ thị ban đầu.
Dưới đây là một số đặc điểm và thuộc tính chính của đồ thị bù:
- Đồ thị gốc: Đồ thị ban đầu là một đồ thị có các đỉnh và cạnh. Nó có thể là một đồ thị có hướng hoặc không có hướng.
- Đồ thị bù: Đồ thị bù được tạo ra từ đồ thị gốc bằng cách đảo hướng các cạnh. Các cạnh có trong đồ thị gốc không có trong đồ thị bù, và ngược lại, các cạnh không có trong đồ thị gốc được thêm vào đồ thị bù.
- Đỉnh và cạnh: Đồ thị bù có cùng tập hợp đỉnh như đồ thị gốc. Điều này có nghĩa là mọi đỉnh trong đồ thị gốc đều có mặt trong đồ thị bù. Tuy nhiên, các cạnh trong đồ thị bù là đảo ngược của các cạnh trong đồ thị gốc.
- Đồ thị đối xứng: Đồ thị bù của một đồ thị không có hướng là một đồ thị đối xứng. Điều này có nghĩa là nếu có một cạnh đi từ đỉnh A đến đỉnh B trong đồ thị gốc, thì cũng có một cạnh từ đỉnh B đến đỉnh A trong đồ thị bù.
- Đặc điểm bù: Đồ thị bù thường được sử dụng để phân tích các thuộc tính và tính chất của đồ thị gốc. Các thuộc tính như liên thông, đồ thị con, đường đi, chu trình và bậc của các đỉnh có thể được nghiên cứu trong đồ thị bù.
- Ứng dụng: Đồ thị bù được sử dụng trong nhiều lĩnh vực như mạng máy tính, lý thuyết đồ thị, lập lịch và quy hoạch. Chúng cung cấp một công cụ hữu ích để phân tích và tìm hiểu các thuộc tính của đồ thị gốc và có thể được sử dụng để giải quyết các vấn đề liên quan đến mạng, tối ưu hóa và phân tích dữ liệu.
Ví dụ: Hãy xem xét đồ thị G được hiển thị trong hình. Tìm phần bù của đồ thị này.
Giải: Phần bù của đồ thị trên được biểu diễn trong Hình:
Labeled Graphs:
Đồ thị có nhãn, còn được gọi là đồ thị có nhãn đỉnh và nhãn cạnh, là một loại đồ thị mà các đỉnh và/hoặc cạnh được gán nhãn, tức là mỗi đỉnh và/hoặc cạnh có một giá trị nhãn riêng biệt.
Dưới đây là một số đặc điểm và thuộc tính chính của đồ thị có nhãn:
- Đỉnh có nhãn: Trong đồ thị có nhãn, mỗi đỉnh được gán một giá trị nhãn riêng biệt. Nhãn của đỉnh có thể là các giá trị số, ký tự, chuỗi, hoặc bất kỳ loại dữ liệu nào khác. Nhãn của đỉnh thường được sử dụng để đại diện cho thông tin hoặc thuộc tính của đỉnh đó.
- Cạnh có nhãn: Đồng thời, các cạnh trong đồ thị cũng có thể được gán nhãn. Nhãn của cạnh có thể là các giá trị tương tự như nhãn của đỉnh. Nhãn cạnh thường được sử dụng để biểu thị mối quan hệ hoặc thuộc tính đặc biệt giữa hai đỉnh kết nối.
- Mô hình dữ liệu: Đồ thị có nhãn cung cấp một mô hình dữ liệu linh hoạt, cho phép biểu diễn và lưu trữ thông tin phức tạp. Bằng cách gán nhãn cho đỉnh và cạnh, ta có thể mô hình hóa các mối quan hệ phức tạp và thuộc tính của các đối tượng trong thế giới thực.
- Tìm kiếm và truy vấn: Các đồ thị có nhãn cung cấp khả năng tìm kiếm và truy vấn dựa trên nhãn. Ta có thể tìm kiếm đỉnh hoặc cạnh có một giá trị nhãn cụ thể, hoặc thực hiện các truy vấn phức tạp hơn như tìm kiếm các đường đi qua các đỉnh có nhãn nhất định.
- Ứng dụng: Đồ thị có nhãn được sử dụng trong nhiều lĩnh vực như cơ sở dữ liệu, mạng xã hội, hệ thống thông tin địa lý, trí tuệ nhân tạo và ngôn ngữ tự nhiên xử lý. Chúng giúp mô hình hóa và xử lý thông tin phức tạp
Ví dụ: Đồ thị trong hình là đồ thị có nhãn.
G = {{a, b, c, d}, {e1, e2, e3, e4}}
Weighted Graphs:
Đồ thị có trọng số, còn được gọi là đồ thị có cạnh có trọng số, là một loại đồ thị mà mỗi cạnh được gán một giá trị trọng số riêng biệt. Trọng số thường biểu thị một thuộc tính hoặc thông tin liên quan đến cạnh, chẳng hạn như độ dài, chi phí, thời gian, hoặc khả năng.
Dưới đây là một số đặc điểm và thuộc tính chính của đồ thị có trọng số:
- Cạnh có trọng số: Mỗi cạnh trong đồ thị có trọng số được gán một giá trị trọng số riêng biệt. Trọng số có thể là một giá trị số dương hoặc số thực, và thường đại diện cho một thuộc tính như độ dài, chi phí, thời gian, hay khả năng.
- Độ dài đường đi: Trọng số của các cạnh được sử dụng để tính toán độ dài của đường đi giữa các đỉnh trong đồ thị. Khi tìm kiếm đường đi ngắn nhất, thuật toán sẽ sử dụng trọng số của các cạnh để tìm ra đường đi có tổng trọng số nhỏ nhất.
- Mô hình dữ liệu: Đồ thị có trọng số cung cấp một cách biểu diễn dữ liệu linh hoạt cho các vấn đề thực tế. Chúng cho phép mô hình hóa mối quan hệ và thông tin phức tạp giữa các đối tượng và thực hiện tính toán dựa trên các trọng số.
- Tối ưu hóa: Đồ thị có trọng số rất hữu ích trong các bài toán tối ưu hóa, như tìm kiếm đường đi ngắn nhất, lập lịch công việc, quy hoạch vận tải, và nhiều bài toán khác. Trọng số của các cạnh được sử dụng để xác định phương án tối ưu dựa trên các tiêu chí như chi phí, thời gian, hay hiệu suất.
- Ứng dụng: Đồ thị có trọng số được áp dụng rộng rãi trong nhiều lĩnh vực như mạng lưới, hệ thống giao thông, kế hoạch sản xuất, quản lý dự án, và trí tuệ nhân tạo.
Ví dụ: Đồ thị trong hình là Đồ thị có Trọng số.