Математическое моделирование на графах. Часть 1. Берцун В.Н. - 62 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

62 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Например, на рис. 2.18 представлен граф G = G
1
× G
2
.
0
1
UVW
(1, )
U
(1, )
V
(1, )
W
(0, )
U
(0, )
V
(0, )
W
Рис. 2.18
С помощью операции произведения можно рекуррентно ввести
важный класс графов – N-мерные гиперкубы Г
N
12222 2 1
,, ,1.
NN
ГКГ ККГ КГ N
−
==× =× >
Число вершин в таком графе n = 2
N
, число ребер m = N·2
N–1
, а макси-
мальное расстояние между узлами совпадает с N. При увеличении
размерности гиперкуба на единицу количество вершин увеличивает-
ся в 2 раза, а максимальное расстояние между ними увеличивается
только на 1. При этом Г
N
можно разделить на два гиперкуба размер-
ности (N – 1).
Гиперкубовая топология является одной из наиболее эффектив-
ных способов соединения процессоров в МВС и отличается от пол-
ного графа простотой реализации. В этом случае нумерацию процес-
соров можно задать в двоичной системе (0, 1) – векторами длины N,
так, что номера соседних узлов будут отличаться только одним би-
том. Тогда два процессора имеют соединение, если двоичное пред-
ставление их номеров отличается только одним битом. Например, на
рис. 2.19 представлены графы Г
N
связи процессоров в виде гиперку-
ба для различных значений размерности N.
Известно, что передачу информации между узлами по кольцевой
топологии (в выбранном направлении по кольцу) можно осущест-
вить наиболее просто. Если в Г
N
необходимо осуществить цикличе-
ский сдвиг информации, то удобно граф Г
N
отобразить на простой

Страницы