tailieunhanh - GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG III ĐỒ THỊ_3

Mạng kết nối quan trọng nhất là mạng kiểu siêu khối. Với các mạng loại này số các bộ xử lý là luỹ thừa của 2, n=2m. Các bộ xử lý được gán nhãn là P0, P1, ., | CHƯƠNG III ĐÒ THỊ Mạng kiểu lưới hoặc mảng hai chiều rất hay được dùng cho các mạng liên kết. Trong một mạng như thế số các bộ xử lý là một số chính phương n m2. Các bộ xử lý được gán nhãn P i j 0 i j m-1. Các kết nối hai chiều sẽ nối bộ xử lý P i j với bốn bộ xử lý bên cạnh tức là với P i j 1 và P i 1 j chừng nào các bộ xử lý còn ở trong lưới. Mạng kết nối quan trọng nhất là mạng kiểu siêu khối. Với các mạng loại này số các bộ xử lý là luỹ thừa của 2 n 2m Các bộ xử lý được gán nhãn là Po P1 . Pn-1. Mỗi bộ xử lý có liên kết hai chiều với m bộ xử lý khác. Bộ xử lý Pi nối với bộ xử lý có chỉ số biểu diễn bằng dãy nhị phân khác với dãy nhị phân biểu diễn i tại đúng một bit. Mạng kiểu siêu khối cân bằng số các kết nối trực tiếp của mỗi bộ xử lý và số các kết P4 nối gián tiếp sao cho các bộ xử lý có thể truyền thông được. Nhiều máy tính đã chế tạo theo mạng kiểu siêu khối và nhiều thuật toán đã được thiết kế để sử dụng mạng kiểu siêu khối. Đồ thị lập phương Qm biểu diễn mạng kiểu siêu khối có 2m bộ xử lý. . BIỂU DIỄN ĐÒ THỊ BẰNG MA TRẬN VÀ Sự ĐẲNG CẤU ĐÒ THỊ . Định nghĩa Cho đồ thị G V E vô hướng hoặc có hướng với V v1 v2 . vn . Ma trận liền kề của G ứng với thứ tự các đỉnh v1 v2 . vn là ma trận A aij 1 i j n e M n Z trong đó aij là số cạnh hoặc cung nối từ vi tới vj. Như vậy ma trận liền kề của một đồ thị vô hướng là ma trận đối xứng nghĩa là aij dji trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng. Thí dụ 11 Ma trận liền kề với thứ tự các đỉnh v1 v2 v3 v4 là 0 3 0 2 ì 3 0 1 1 0 1 1 2 2 1 2 0 Ma trận liền kề với thứ tự các đỉnh v1 v2 v3 v4 v5 là Í1 1 0 1 1 ì 0 1 2 1 0 1 0 0 1 0 0 0 2 0 1 1 0 1 0 . Định nghĩa Cho đồ thị vô hướng G V E v1 v2 . vn là các đỉnh và e1 e2 . em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận vỵ n X m Z M mij 1 i w 1 j