Rate this post

Có hai cách chính để biểu diễn đồ thị G với ma trận, tức là, ma trận kề và biểu diễn ma trận tỷ lệ.

Các bài viết liên quan:

Tóm tắt nội dung

Biểu diễn Đồ thị vô hướng:

Biểu diễn ma trận kề vô hướng:

Nếu đồ thị vô hướng G bao gồm n đỉnh thì ma trận kề của đồ thị là ma trận n x n A = [aij] và được xác định bởi

Nếu tồn tại một cạnh giữa đỉnh vi và vj, trong đó i là hàng và j là cột thì giá trị của aij = 1.

Nếu không có cạnh nào giữa đỉnh vi và vj thì giá trị của aij = 0.

Cách biểu diễn ma trận kề vô hướng:

Để biểu diễn ma trận kề vô hướng (undirected adjacency matrix) trong đồ thị, bạn có thể làm theo các bước sau:

Chuẩn bị ma trận: Xác định số lượng đỉnh của đồ thị và tạo ma trận vuông có kích thước tương ứng. Mỗi hàng và cột của ma trận sẽ đại diện cho một đỉnh trong đồ thị.
Đặt giá trị cho ma trận: Với mỗi cạnh trong đồ thị, đặt giá trị 1 tại vị trí tương ứng trong ma trận. Vì đồ thị vô hướng, nếu có cạnh nối giữa hai đỉnh A và B, ta sẽ đặt giá trị 1 ở cả hai vị trí tương ứng trong ma trận (tức là ma trận là đối xứng qua đường chéo chính). Nếu không có cạnh nối, đặt giá trị 0.
Hiển thị ma trận: Sử dụng các ký hiệu và định dạng phù hợp để hiển thị ma trận kề vô hướng. Ví dụ, bạn có thể sử dụng các số hoặc ký hiệu đặc biệt để biểu thị các cạnh hoặc quan hệ giữa các đỉnh.

Lưu ý rằng ma trận kề vô hướng là một cách phổ biến để biểu diễn đồ thị vô hướng. Tuy nhiên, nếu đồ thị có hướng (đồ thị có các cạnh chỉ đi từ một đỉnh đến một đỉnh khác), bạn cần sử dụng ma trận kề có hướng (directed adjacency matrix) để đại diện cho quan hệ hướng của các đỉnh.

Ví dụ: Tìm ma trận kề MA của đồ thị G trong hình:

Giải: Vì đồ thị G gồm bốn đỉnh. Do đó, ma trận kề sẽ là ma trận 4 x 4. Ma trận kề như sau trong hình:

Biểu diễn ma trận tỉ lệ vô hướng:

Nếu một đồ thị vô hướng G bao gồm n đỉnh và m cạnh, thì ma trận tỉ lệ là ma trận n x m C = [cij] và được xác định bởi

Có một hàng cho mọi đỉnh và một cột cho mọi cạnh trong ma trận sự cố.

Số lượng đơn vị trong ma trận tỷ lệ của đồ thị vô hướng (không có vòng lặp) bằng tổng các bậc của tất cả các đỉnh trong một biểu đồ.

Để biểu diễn ma trận tỉ lệ vô hướng (undirected proportion matrix) trong đồ thị, bạn có thể làm theo các bước sau:

Chuẩn bị ma trận: Xác định số lượng đỉnh của đồ thị và tạo ma trận vuông có kích thước tương ứng. Mỗi hàng và cột của ma trận sẽ đại diện cho một đỉnh trong đồ thị.
Đặt giá trị cho ma trận: Với mỗi cạnh trong đồ thị, đặt giá trị tỉ lệ tương ứng trong khoảng từ 0 đến 1. Vì đồ thị vô hướng, nếu có cạnh nối giữa hai đỉnh A và B với giá trị tỉ lệ p, ta sẽ đặt giá trị p ở cả hai vị trí tương ứng trong ma trận (tức là ma trận là đối xứng qua đường chéo chính). Nếu không có cạnh nối, đặt giá trị 0.
Hiển thị ma trận: Sử dụng các định dạng và ký hiệu phù hợp để hiển thị ma trận tỉ lệ vô hướng. Bạn có thể sử dụng các số thập phân hoặc ký hiệu đặc biệt để biểu thị mức độ tỉ lệ hoặc tương quan giữa các đỉnh.

Lưu ý rằng biểu diễn ma trận tỉ lệ vô hướng thường được sử dụng trong các bài toán liên quan đến mạng lưới, mạng xã hội, hoặc các hệ thống tương tác khác. Việc hiểu và đọc ma trận tỉ lệ vô hướng sẽ phụ thuộc vào ngữ cảnh và mục đích của bạn.

Ví dụ: Hãy xem xét đồ thị vô hướng G như trong hình. Tìm ma trận tỷ lệ MI của nó.

Giải: Đồ thị vô hướng bao gồm bốn đỉnh và năm cạnh. Do đó, ma trận tỷ lệ là ma trận 4 x 5, được thể hiện trong Hình:

Biểu diễn Đồ thị có hướng

Biểu diễn ma trận kề có hướng:

Nếu đồ thị có hướng G bao gồm n đỉnh thì ma trận kề của đồ thị là ma trận n x n A = [aij] và được xác định bởi

Nếu tồn tại một cạnh giữa đỉnh Vi và Vj, với Vi là đỉnh ban đầu và Vj là đỉnh cuối cùng, thì giá trị của aij = 1.

Nếu không có cạnh nào giữa đỉnh Vi và Vj thì giá trị của aij = 0.

Số đơn vị trong ma trận kề của đồ thị có hướng bằng số cạnh.

Cách biểu diễn ma trận kề có hướng

Để biểu diễn ma trận kề có hướng (directed adjacency matrix) trong đồ thị, bạn có thể làm theo các bước sau:

Chuẩn bị ma trận: Xác định số lượng đỉnh của đồ thị và tạo ma trận vuông có kích thước tương ứng. Mỗi hàng và cột của ma trận sẽ đại diện cho một đỉnh trong đồ thị.
Đặt giá trị cho ma trận: Với mỗi cạnh trong đồ thị, đặt giá trị 1 tại vị trí tương ứng trong ma trận. Nếu đồ thị có hướng, khi có một cạnh từ đỉnh A đến đỉnh B, ta chỉ đặt giá trị 1 tại vị trí (A, B) trong ma trận. Còn các vị trí khác, ta đặt giá trị 0.
Hiển thị ma trận: Sử dụng các ký hiệu và định dạng phù hợp để hiển thị ma trận kề có hướng. Ví dụ, bạn có thể sử dụng các số hoặc các mũi tên để biểu thị hướng của các cạnh.

Lưu ý rằng ma trận kề có hướng là một cách phổ biến để biểu diễn đồ thị có hướng. Nếu đồ thị là vô hướng (không có hướng), bạn có thể sử dụng ma trận kề vô hướng như đã trình bày trước đó.

Ví dụ: Hãy xem xét đồ thị có hướng hiển thị trong hình. Xác định ma trận kề của nó MA.

Giải: Vì đồ thị có hướng nên G gồm năm đỉnh. Do đó, ma trận kề sẽ là ma trận 5 x 5. Ma trận kề của các đồ thị có hướng như sau:

Xem thêm Cách tạm thời vô hiệu hóa Face ID trên iPhone

Biểu diễn ma trận tỉ lệ có hướng

Nếu một đồ thị có hướng G gồm n đỉnh và m cạnh, thì ma trận tỉ lệ là ma trận n x m C = [cij] và được xác định bởi

Số lượng đơn vị trong ma trận tỷ lệ bằng số cạnh trong đồ thị.

Cách biểu diễn ma trận tỉ lệ có hướng

Để biểu diễn ma trận tỉ lệ có hướng (directed proportion matrix) trong đồ thị, bạn có thể làm theo các bước sau:

Chuẩn bị ma trận: Xác định số lượng đỉnh của đồ thị và tạo ma trận vuông có kích thước tương ứng. Mỗi hàng và cột của ma trận sẽ đại diện cho một đỉnh trong đồ thị.
Đặt giá trị cho ma trận: Với mỗi cạnh trong đồ thị, đặt giá trị tỉ lệ tương ứng trong khoảng từ 0 đến 1. Nếu có một cạnh từ đỉnh A đến đỉnh B với giá trị tỉ lệ p, ta sẽ đặt giá trị p tại vị trí (A, B) trong ma trận. Nếu không có cạnh nối, đặt giá trị 0.
Hiển thị ma trận: Sử dụng các định dạng và ký hiệu phù hợp để hiển thị ma trận tỉ lệ có hướng. Bạn có thể sử dụng các số thập phân hoặc ký hiệu đặc biệt để biểu thị mức độ tỉ lệ hoặc tương quan giữa các đỉnh.

Lưu ý rằng biểu diễn ma trận tỉ lệ có hướng thường được sử dụng trong các bài toán liên quan đến mạng lưới, mạng xã hội, hoặc các hệ thống tương tác khác mà hướng của các quan hệ giữa các đỉnh là quan trọng. Việc hiểu và đọc ma trận tỉ lệ có hướng sẽ phụ thuộc vào ngữ cảnh và mục đích của bạn.

Ví dụ: Xét đồ thị có hướng G như trong hình. Tìm ma trận tỷ lệ MI của nó.

Giải: Đồ thị có hướng gồm bốn đỉnh và năm cạnh. Do đó, ma trận tỷ lệ là ma trận 4 x 5 được hiển thị trong hình:

Xem thêm Kiểm tra giả thuyết trong SAS

Biểu diễn đồ thị Multigraph

Chỉ được biểu diễn bằng biểu diễn ma trận kề.

(i) Biểu diễn ma trận kề của đa đồ thị: Nếu đa đồ thị G bao gồm các đỉnh, thì ma trận kề của đồ thị là ma trận n x n A = [aij] và được xác định bởi

Nếu tồn tại một hoặc nhiều hơn một cạnh giữa đỉnh vi và vj thì aij = N, trong đó là số cạnh giữa vi và vj.

Nếu không có cạnh nào giữa vi và vj.

Cách biểu diễn đồ thị Multigraph

Để biểu diễn đồ thị Multigraph, bạn có thể sử dụng các phương pháp sau:

Ma trận kề: Sử dụng ma trận kề (adjacency matrix) để biểu diễn đồ thị Multigraph. Trong ma trận này, các phần tử của ma trận sẽ đại diện cho số lượng cạnh giữa các cặp đỉnh. Ví dụ, nếu có nhiều cạnh nối cùng một cặp đỉnh, giá trị tại vị trí tương ứng trong ma trận sẽ là số lượng cạnh đó. Nếu không có cạnh nối giữa hai đỉnh, giá trị tương ứng sẽ là 0.
Danh sách cạnh: Sử dụng danh sách cạnh (edge list) để liệt kê tất cả các cạnh trong đồ thị Multigraph. Mỗi cạnh sẽ được biểu diễn bằng một cặp đỉnh kề nhau, và nếu có nhiều cạnh giữa cùng một cặp đỉnh, chúng sẽ được liệt kê thành các phần tử riêng biệt trong danh sách.
Danh sách kề: Sử dụng danh sách kề (adjacency list) để liệt kê tất cả các đỉnh kề với mỗi đỉnh trong đồ thị Multigraph. Mỗi đỉnh sẽ có một danh sách các đỉnh kề, và nếu có nhiều cạnh giữa cùng một cặp đỉnh, chúng sẽ được liệt kê thành các phần tử riêng biệt trong danh sách.

Lưu ý rằng đồ thị Multigraph là loại đồ thị cho phép có nhiều cạnh nối giữa cùng một cặp đỉnh. Vì vậy, các biểu diễn trên sẽ phải xác định được số lượng cạnh giữa các cặp đỉnh để phản ánh chính xác đồ thị Multigraph.

Ví dụ: Hãy xem xét đa đồ thị được hiển thị trong Hình, Xác định ma trận kề của nó.