Sorry all, I have been pre-occupied these few days. Truly thanks for all the help with programming and all. Haven't got much time so I will just list out the results I found manually.
1. Is it possible to connect 9 BSCs altogether? If yes how? If not why?
The answer is impossible, and it can be proved quite easily.
Firstly we have to consider the total number of "registered PDs" (RPDs) on all 9 BSCs. Note that each direct link would account for 2 RPDs (one on each end). Say there are L direct links, then the total number of RPDs would be 2L, which must be an even number.
Now recall that each BSC can hold a maximum of 3 RPDs. If all 9 BSCs were to use the maximum, then the total number of RPDs would be 9*3=27, which would be an odd number, impossible. Therefore at least one BSC (say X) must hold fewer than 3 RPDs, i.e. have a maximum of 2 PDs. In turn these 2 PDs would allow a further 2*2=4 BSCs to have "bridged communication" with X. In total, X can only establish communication with a maximum of 2+4=6 other BSCs, making the remaining two "out of reach" from X's standpoint.
Hence, 9 BSCs cannot be connected altogether. If we need to connect 9 SCs together, at least the GSCs (4 RPDs @) must be used.
2. Is it possible to connect 10 BSCs altogether? If yes how? If not why?
Even though 9 BSCs cannot be connected together, if we add 1 extra BSC, then the situation is totally different. Now the maximum total number of RPDs is 10*3=30 which is even, a possible scenario. The remaining problem is to work out the actual arrangement.
I will introduce a method called the "3 levels assignment" which would be very useful in constructing any connection arrangement.
Firstly we assign one BSC as in level 0, and label it Z, which is like the root in a tree structure.
Z would connect to 3 other BSCs, which we assign in level 1, and label them A,B,C. We can refer to them as "moms".
Each of A,B,C would connect to 2 other BSCs (other than Z), which we assign in level 2, and label them A1,A2,B1,B2,C1,C2. We can refer to them as "kids".
This is a graphical view of the structure:
- Code: Select all
Z
/ | \
A B C
/| / \ |\
A1 A2 B1 B2 C1 C2
It is obvious Z has already establish communication with all other BSCs. All it requires for altogether connection is to do the same of the 9 remaining BSCs.
To do this we need to systematically add direct links among the 6 "kids". Say we adopt the following system:
- Code: Select all
B1 links to A1,C1. B2 links to A2,C2. A1 links to C2. A2 links to C1.
In a nutshell the group B (middle group) kids links to other kids with the same index, while the 2 other groups have links between kids with different indices.
Now we can check the actual situation for each BSC:
For moms (A,B,C), they have direct links to Z and their own kids, and have bridged communication to other moms (via Z) and other kids (via their own kids).
For kids (A1,A2,B1,B2,C1,C2), they have direct links to the their own moms, and 2 kids from other groups, and have bridged communication to Z and the other kids of the same group (via their own moms), as well as other moms and kids (via the 2 other kids they link to).
This is the SCM for this arrangement:
- Code: Select all
Z A B C A1 A2 B1 B2 C1 C2
Z . 1 1 1 . . . . . .
A 1 . . . 1 1 . . . .
B 1 . . . . . 1 1 . .
C 1 . . . . . . . 1 1
A1 . 1 . . . . 1 . . 1
A2 . 1 . . . . . 1 1 .
B1 . . 1 . 1 . . . 1 .
B2 . . 1 . . 1 . . . 1
C1 . . . 1 . 1 1 . . .
C2 . . . 1 1 . . 1 . .
Z A B C A1 A2 B1 B2 C1 C2
Z 0 1 1 1 2 2 2 2 2 2
A 1 0 2 2 1 1 2 2 2 2
B 1 2 0 2 2 2 1 1 2 2
C 1 2 2 0 2 2 2 2 1 1
A1 2 1 2 2 0 2 1 2 2 1
A2 2 1 2 2 2 0 2 1 1 2
B1 2 2 1 2 1 2 0 2 1 2
B2 2 2 1 2 2 1 2 0 2 1
C1 2 2 2 1 2 1 1 2 0 2
C2 2 2 2 1 1 2 2 1 2 0
With some permutations, this SCM can be shown isomorphic to the one I provided earlier, which was attributed to the well known "Petersen Graph".
. Could you confirm this number?
