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:

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

1. Biểu diễn ma trận kề: 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.

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:

2. Biểu diễn ma trận tỉ lệ: 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 đồ.

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

1. Biểu diễn ma trận kề: 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.

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:

2. Biểu diễn ma trận tỉ lệ: 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ị.

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:

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.

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

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

Leave a Reply

Call now
%d bloggers like this: