程序代写代做代考 graph C EE6605

EE6605
HW#3 Solutions 2020
3-1
1 e1 e4 4 2
e3 e2
e5
5
(i) Matrices
3
1
0 1 1 0 0
1 0 0 0
0 1 1 0
1 1 0 0, L1 1 2 0 0 0 0 1 1 0 1 0 2 1
1 3 1 1 0 
1 A1 1 0 0 0, M0 0 1 0 0 1 0
1 0 1 1 0
0 0 0 1 0 0 0 0 0 1 0 0 0 1 1
(ii) Cut sets
{e1, e2}, {e1, e3}, {e2, e3}, {e4}, {e5}
(iii) Complementary graph
124
2 1 1 0 0
(iv) Line graph
1,2 2,4
35
1,3
2,3
4,5

EE6605
HW#3 Solutions
2020
(v) Average closeness
01123 10112 11023 21201 32310
C (1)  1 /(1  1  2  3)  0.143 C(2) 1/(111 2)  0.200 C(3)1/(1123)0.143 C ( 4 )  1 / ( 2  1  2  1)  0 . 1 6 7 C ( 5 )  1 / ( 3  2  3  1)  0 . 1 1 1
C 0.153
(vi) Density of the graph:
(vii) Node connectivity = 1
(viii) Edge connectivity = 1
(ix) Closeness of Node 5 = 1/(1+2+3+3) = 1/9 After normalization = 1/9 x (5-1) = 4/9 (x) There are two centre nodes: Node 2 and Node 4
3-2 (a) Girth of Node 5 = 3 (b)
𝜃1=
𝜃2=
𝜃3=
𝜃4=
𝜃5= 𝜃6 =
𝐴=
1 2(2−1)/2 1 3(3−1)/2 1 2(2−1)/2 1
2(2 − 1)/2 1 4(4−1)/2
0
0
1 0 0 0 1 0
Den = 5/10 = 1/2
0 𝑎12 𝑎13 𝑎14 𝑎15 𝑎16 0 𝑎23 𝑎24 𝑎25 𝑎26
0 𝑎34 𝑎35 𝑎36 = 0 𝑎45 𝑎46
0 1 0 0 1 0 01 010
01] [0]0
(𝑎12𝑎23+𝑎12𝑎25+𝑎15𝑎56+0+⋯+0)=1(1+1+1)= 8 𝑆123 𝑆125 𝑆156 5 3 ∞ 15
(𝑎21𝑎12+𝑎21𝑎15+𝑎23𝑎34+𝑎25𝑎56+0+⋯+0)=1(1+1+1+1)= 7 𝑆212 𝑆215 𝑆234 𝑆256 3 ∞ 3 4 ∞ 36
(𝑎32𝑎23 + 𝑎32𝑎25 + 𝑎34𝑎45 + 0 + ⋯ + 0) = 1 ( 1 + 1 + 1) = 1 𝑆323 𝑆325 𝑆345 ∞ 4 4 2
(𝑎43𝑎34 +𝑎45𝑎56 +0+⋯+0)=1(1 + 1)=0 𝑆434 𝑆456 ∞∞
(𝑎51𝑎12+𝑎52𝑎23+0+⋯+0)=1(1+1)= 7 𝑆512 𝑆523 6 3 4 72
𝜃=1(8 + 7 +1+0+ 7 +0)= 53 ≈0.221 615362 72 240
0𝑎56 [
Finally,

EE6605
HW#3 Solutions
2020
3-3
r(G)  4 (bolded path length from node A) diam(G)  7 (dashed path)
There are two centre nodes: A and B
AB
Minimum spanning tree (red) = 4+7+7+8+8+9 = 43 Cable with lowest cost (green) = 11+10+7 = 28
(i)
(ii) (iii)
3-4
13
12
4
8
B
7
9
8
11 97
10
A
11
To find minimum spanning tree:
First, identify edge with length 4, then those with 7, 7, 8, 8, and finally the one with 9