Torus is a Subgraph of Same-Size Hypercube Try to give a proof in another way without using "product graph Fa2010 Parallel Processing, Low-Diameter Architectures Slide 14
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 14 Torus is a Subgraph of Same-Size Hypercube Try to give a proof in another way without using “product graph
Embedding Trees in the Hypercube The( 2q-1)-node complete binary tree even weight is not a subgraph of the q-cube odd weights ○○. Q. even weights Proof by contradiction based on the parity of node label weights(number of 1s in the labels) The 2q-node double-rooted complete even weights binary tree is a subgraph of the g-cube odd weights lew roots NC(NEx) Fig 13.6 The 2q-node N(N fx) double-rooted 入△八 complete binary tree is a subgraph of 2q-node double-rooted Double-rooted tree Double-rooted tree the g-cube plete bi n the ((q-1 ube O n the((q-1)cube Fa2010 Parallel Processing, Low-Diameter Architectures Slide 15
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 15 Embedding Trees in the Hypercube The (2 q – 1)-node complete binary tree is not a subgraph of the q-cube even weight odd weights even weights odd weights even weights Proof by contradiction based on the parity of node label weights (number of 1s in the labels) The 2 q -node double-rooted complete binary tree is a subgraph of the q-cube Fig. 13.6 The 2q -node double-rooted complete binary tree is a subgraph of the q-cube. New Roots x N (N (x)) N (N (x)) 2 -node double-rooted complete binary tree q Double-rooted tree in the (q?)-cube 0 Double-rooted tree in the (q?)-cube 1 N (x) c N (x) b N (x) a b c c b N (N (x)) N (N (x)) c a a c （q -1） （q -1）
14.5 Broadcasting on a Hypercube Flooding: applicable to any network with all-port communication 00000 Source node 00001,00010,00100,01000,10000 Neighbors of source 00011,00101,01001,10001,00110,01010,10010,01100,10100,11000 Distance2 nodes 00111,01011.10011,01101,10101,11001,01110,10110.11010.11100 Distance-3 nodes 01111410111,11011,11101,11110 Distance- 4 nodes 11111 Distance-5 node Binomial broadcast tree with single-port communication 00000 Time Fig. 14.9 l0000 The binomial 01000 l1000 broadcast tree 01100 l1100 for a 5-cube 00010 00001 2345 Fa2010 Parallel Processing, Low-Diameter Architectures Slide 16
Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 16 14.5 Broadcasting on a Hypercube Flooding: applicable to any network with all-port communication 00000 Source node 00001, 00010, 00100, 01000, 10000 Neighbors of source 00011, 00101, 01001, 10001, 00110, 01010, 10010, 01100, 10100, 11000 Distance-2 nodes 00111, 01011, 10011, 01101, 10101, 11001, 01110, 10110, 11010, 11100 Distance-3 nodes 01111, 10111, 11011, 11101, 11110 Distance-4 nodes 11111 Distance-5 node Binomial broadcast tree with single-port communication 0 1 2 3 4 5 Time 00000 10000 01000 11000 00100 01100 10100 11100 00001 00010 Fig. 14.9 The binomial broadcast tree for a 5-cube