Đồ thị khối Q, (Hình 4) là đồ thị có 8 đỉnh, mỗi đỉnh là một dãy bit độ dài 3, hai đinh có cạnh nối nếu hai dãy bit sai khác nhau đúng một bit...

VẬN DỤNG

Đồ thị khối Q, (Hình 4) là đồ thị có 8 đỉnh, mỗi đỉnh là một dãy bit độ dài 3, hai đinh có cạnh nối nếu hai dãy bit sai khác nhau đúng một bit. 

Em hãy biểu diễn đồ thị bằng ma trận kề và danh sách kề.


Ma trận kề: Ma trận kề sẽ có kích thước 8x8, với mỗi hàng và cột tương ứng với một đỉnh của đồ thị. Nếu hai đỉnh khác nhau đúng một bit, chúng sẽ được nối với nhau và ô tương ứng trong ma trận sẽ được đánh dấu là 1. Còn lại sẽ là 0.

000 001 010 011 100 101 110 111

000   0   1   1   0   1   0   0   0

001   1   0   0   1   0   1   0   0

010   1   0   0   1   0   0   1   0

011   0   1   1   0   0   0   0   1

100   1   0   0   0   0   1   1   0

101   0   1   0   0   1   0   0   1

110   0   0   1   0   1   0   0   1

111   0   0   0   1   0   1   1   0

Danh sách kề: Danh sách kề sẽ liệt kê các đỉnh kề với mỗi đỉnh trong đồ thị.

000: [001, 010, 100]

001: [000, 011, 101]

010: [000, 011, 110]

011: [001, 010, 111]

100: [000, 101, 110]

101: [001, 100, 111]

110: [010, 100, 111]

111: [011, 101, 110]


Bình luận

Giải bài tập những môn khác