SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Sat Mar 23, 2019 9:37 am

All times are UTC




Post new topic Reply to topic  [ 13 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Wed Feb 02, 2011 6:18 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
During the cold war era, the Soviet scientists used to develop a certain genre of secret communication devices for KGB agents to use within enemy territories.

(Note this was way before the evolution of modern cell phones and handheld computers.)


These devices (for convenience just call them "Secret Communicators" or SCs) had these properties:

1. Each SC had a unique identifier burnt in the internal chip (not unlike the CPU of modern computers).

2. Each SC, depending on their versions, had different capacities to register the identifiers of a number of "partner devices" (PDs). A white SC could register 2 PDs, a blue one 3, a green one 4 and a red SC, the most advanced version, could register up to 5 PDs. Only SCs of the same version could become PDs of each other.

3. Each SC could establish anytime anywhere (within a range of 3000 km) communication to any of its PDs in a special frequency based on the 2 identifiers on each side, which made the communication totally secured from outside parties. Again only SCs of the same version could communicate with each other.

4. Beside the direct communication between 2 PDs, each SC also had the special feature which allowed it to become a "bridge" for any 2 of its registered PDs to communicate with each other. This "bridged communication" must use a single SC as the "bridge", and the 2 communicating SCs must be PDs of that bridge.


Essentially these were the basic properties of those SCs. In every KGB mission, depending on the number of participants, all agents would all carry the same version of SCs with them. It was normally a requirement for each paricipant of a mission to be able to establish direct or bridged communication to all other participants.

After a while it became a subject of interest for KGB to determine how many participants of a mission would each SC version able to support. For example, white SCs (with a limit of 2 PDs) were known to be able to support 5 agents in any given mission. To demonstrate this, one could draw up the "Secret Communicator Matrix" (SCM) like this:


Say 5 agents are A,B,C,D,E, we arrange them as a full circle and each agent will have his immediate neighbours' SCs as PDs of his own SC. So say A can have direct communication with B,E while C can have it with B,D. Then we use "+" to represent a direct communication relationship (and "." as blanks):

Code:
  A B C D E
A . + . . +
B + . + . .
C . + . + .
D . . + . +
E + . . + .


Next, we have to work out the bridged communication relationship. For example, because the SCs of B,E are PDs of A's SC, B,E can have bridged communication with each other. We use "*" to represent this relationship. Also, we use "-" to represent a "self relationship" between each agent and himself:

Code:
  A B C D E
A - + * * +
B + - + * *
C * + - + *
D * * + - +
E + * * + -


As one can see, when the SCM is filled up, it means all participants of the mission can communicate to each other. Otherwise if there are holes, it means a participant cannot communicate to another one, then a higher version of SCs would be necesary to be used in the mission.


To make another demonstration, let's try 8 agents (A,B,C,D,E,F,G,H). This time we show that the blue SCs (with a limit of 3 PDs) are enough to establish communications among everyone. The method is to arrange them in a full circle again and have the SCs of each agent register the SCs of his immediate neighbours as well as his directly opposite agent:

Code:
  A B C D E F G H
A . + . . + . . +
B + . + . . + . .
C . + . + . . + .
D . . + . + . . +
E + . . + . + . .
F . + . . + . + .
G . . + . . + . +
H + . . + . . + .


Then we fill in the bridged communication and self relationships:

Code:
  A B C D E F G H
A - + * * + * * +
B + - + * * + * *
C * + - + * * + *
D * * + - + * * +
E + * * + - + * *
F * + * * + - + *
G * * + * * + - +
H + * * + * * + -


Once again, the SCM is filled up, so everyone can communicate to everyone.


Is it possible to work out all the possible numbers of agents each SC version can support?


Top
 Profile  
Reply with quote  
PostPosted: Thu Feb 03, 2011 4:56 am 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
I will start on the white SCs (WSCs), with a limit of 2 PDs each. As previously demonstrated, WSCs can support 5 agents, and obviously any number lower than 5.

However, it can be proved that WSCs cannot support 6 or more agents. Here is the proof:

For any particular agent, say A, his WSC gives him direct communications to 2 other agents. Each of these 2 agents can have no more than 1 other PD on their WSCs, so A can have bridged communications to a maximum of 2 more other agents. Therefore a WSC only allows A to establish communications with 4 other agents in total. If there are 6 or more agents, at least 1 agent will be "out of reach" from A's standpoint.

Conclusion: WSCs can support communications for 2 to 5 agents but no more.

Also, generalizing this result, SCs with a limit of N PDs can support no more than 1 + N + N*(N-1) = 1+N^2 agents. Therefore:
  • White SCs (WSCs) can support no more than 1+2^2=5 agents.
  • Blue SCs (BSCs) can support no more than 1+3^2=10 agents.
  • Green SCs (GSCs) can support no more than 1+4^2=17 agents.
  • Red SCs (RSCs) can support no more than 1+5^2=26 agents.

However, these are just the upper bounds. In practice is it really possible for say, GSCs to support 17 agents? It will need to be explored.


Top
 Profile  
Reply with quote  
PostPosted: Fri Feb 04, 2011 6:05 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
Last time I did the SCMs for 5 WSCs (2 PDs @) and 8 BSCs (3 PDs @). Let me quickly do 6 BSCs and 7 BSCs:

(From now on I will use "0","1","2" to replace "-","+","*" for easier manipulation.)

For 6 BSCs, arrange them in a circle and each BSC links directly to the two neighbours and the opposite one:

Code:
  A B C D E F
A . 1 . 1 . 1
B 1 . 1 . 1 .
C . 1 . 1 . 1
D 1 . 1 . 1 .
E . 1 . 1 . 1
F 1 . 1 . 1 .


Code:
  A B C D E F
A 0 1 2 1 2 1
B 1 0 1 2 1 2
C 2 1 0 1 2 1
D 1 2 1 0 1 2
E 2 1 2 1 0 1
F 1 2 1 2 1 0


For 7 BSCs, arrange 6 of them (A to F) in a circle like before and then put the remaining one (G) at the centre. A to F links directly to the two neighbours, B,C,E,F links to the opposite one while A,D boih links to G:

Code:
  A B C D E F G
A . 1 . . . 1 1
B 1 . 1 . 1 . .
C . 1 . 1 . 1 .
D . . 1 . 1 . 1
E . 1 . 1 . 1 .
F 1 . 1 . 1 . .
G 1 . . 1 . . .


Code:
  A B C D E F G
A 0 1 2 2 2 1 1
B 1 0 1 2 1 2 2
C 2 1 0 1 2 1 2
D 2 2 1 0 1 2 1
E 2 1 2 1 0 1 2
F 1 2 1 2 1 0 2
G 1 2 2 1 2 2 0


Think this is easy? Now try to answer the following 2 questions:

1. Is it possible to connect 9 BSCs altogether? If yes how? If not why?

2. Is it possible to connect 10 BSCs altogether? If yes how? If not why?


Top
 Profile  
Reply with quote  
PostPosted: Sun Feb 13, 2011 7:50 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
Quote:
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.


Quote:
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:
        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:
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:
    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


Top
 Profile  
Reply with quote  
PostPosted: Sun Feb 13, 2011 7:54 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
I will go out on a limb and list out all the possible scenarios that I know of. And then given time I will list out their arrangements in detail in the future. Hopefully the programming experts can get there before me (I really hope so). Then perhaps we can explore the problem for larger sizes (e.g. SCs with 6, 7 or even more direct links each).

WSCs (2 direct links each) can support communications for 2,3,4,5 agents.

BSCs (3 direct links each) can support communications for 6,7,8,10 agents (as well as 2-5).

GSCs (4 direct links each) can support communications for 9,11,12,13,14,15 agents (as well as 2-8,10).

RSCs (5 direct links each) can support communications for 16,17,18,20,21,22,24 agents (as well as 2-15).

The possibility of RSCs supporting 19 agents has not been determined yet.

(It has been proven mathematically that GSCs cannot support 16,17 agents and RSCs cannot support 23,25,26 agents.)


Top
 Profile  
Reply with quote  
PostPosted: Sun Feb 13, 2011 7:57 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
On to GSCs (max 4 links):


To connect 9 GSCs altogether, just divide them into 3 groups: A1,A2,A3,B1,B2,B3,C1,C2,C3. All GSCs with same letter or same index are directly linked. Here is the SCM:

Code:
   A1 A2 A3 B1 B2 B3 C1 C2 C3
A1  .  1  1  1  .  .  1  .  .
A2  1  .  1  .  1  .  .  1  .
A3  1  1  .  .  .  1  .  .  1
B1  1  .  .  .  1  1  1  .  .
B2  .  1  .  1  .  1  .  1  .
B3  .  .  1  1  1  .  .  .  1
C1  1  .  .  1  .  .  .  1  1
C2  .  1  .  .  1  .  1  .  1
C3  .  .  1  .  .  1  1  1  .

   A1 A2 A3 B1 B2 B3 C1 C2 C3
A1  0  1  1  1  2  2  1  2  2
A2  1  0  1  2  1  2  2  1  2
A3  1  1  0  2  2  1  2  2  1
B1  1  2  2  0  1  1  1  2  2
B2  2  1  2  1  0  1  2  1  2
B3  2  2  1  1  1  0  2  2  1
C1  1  2  2  1  2  2  0  1  1
C2  2  1  2  2  1  2  1  0  1
C3  2  2  1  2  2  1  1  1  0



To connect 11 GSCs altogether, arrange them in a circle. Then each GSC is directly linked to its immediate neighbour, plus the 4th & 7th away (from both directions). Here is the SCM:

Code:
  A B C D E F G H I J K
A . 1 . . 1 . . 1 . . 1
B 1 . 1 . . 1 . . 1 . .
C . 1 . 1 . . 1 . . 1 .
D . . 1 . 1 . . 1 . . 1
E 1 . . 1 . 1 . . 1 . .
F . 1 . . 1 . 1 . . 1 .
G . . 1 . . 1 . 1 . . 1
H 1 . . 1 . . 1 . 1 . .
I . 1 . . 1 . . 1 . 1 .
J . . 1 . . 1 . . 1 . 1
K 1 . . 1 . . 1 . . 1 .

  A B C D E F G H I J K
A 0 1 2 2 1 2 2 1 2 2 1
B 1 0 1 2 2 1 2 2 1 2 2
C 2 1 0 1 2 2 1 2 2 1 2
D 2 2 1 0 1 2 2 1 2 2 1
E 1 2 2 1 0 1 2 2 1 2 2
F 2 1 2 2 1 0 1 2 2 1 2
G 2 2 1 2 2 1 0 1 2 2 1
H 1 2 2 1 2 2 1 0 1 2 2
I 2 1 2 2 1 2 2 1 0 1 2
J 2 2 1 2 2 1 2 2 1 0 1
K 1 2 2 1 2 2 1 2 2 1 0



To connect 12 GSCs altogether, first divide them into 2 groups of 6: A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6. Each group is arranged in a circle, with links between neighbours. Then add links across the 2 groups between GSCs with the same index (mod 3). For example, A1 is linked to A2,A6,B1,B4. B5 is linked to B4,B6,A2,A5. Here is the SCM:

Code:
   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6
A1  .  1  .  .  .  1  1  .  .  1  .  .
A2  1  .  1  .  .  .  .  1  .  .  1  .
A3  .  1  .  1  .  .  .  .  1  .  .  1
A4  .  .  1  .  1  .  1  .  .  1  .  .
A5  .  .  .  1  .  1  .  1  .  .  1  .
A6  1  .  .  .  1  .  .  .  1  .  .  1
B1  1  .  .  1  .  .  .  1  .  .  .  1
B2  .  1  .  .  1  .  1  .  1  .  .  .
B3  .  .  1  .  .  1  .  1  .  1  .  .
B4  1  .  .  1  .  .  .  .  1  .  1  .
B5  .  1  .  .  1  .  .  .  .  1  .  1
B6  .  .  1  .  .  1  1  .  .  .  1  .

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6
A1  0  1  2  2  2  1  1  2  2  1  2  2
A2  1  0  1  2  2  2  2  1  2  2  1  2
A3  2  1  0  1  2  2  2  2  1  2  2  1
A4  2  2  1  0  1  2  1  2  2  1  2  2
A5  2  2  2  1  0  1  2  1  2  2  1  2
A6  1  2  2  2  1  0  2  2  1  2  2  1
B1  1  2  2  1  2  2  0  1  2  2  2  1
B2  2  1  2  2  1  2  1  0  1  2  2  2
B3  2  2  1  2  2  1  2  1  0  1  2  2
B4  1  2  2  1  2  2  2  2  1  0  1  2
B5  2  1  2  2  1  2  2  2  2  1  0  1
B6  2  2  1  2  2  1  1  2  2  2  1  0



Next time I will show how GSCs can support 13,14,15 agents.

Or if you guys want, try to work them out yourself. They are nice mental exercises (for human brains or computers)!


Top
 Profile  
Reply with quote  
PostPosted: Wed Feb 16, 2011 4:54 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
To connect 13 GSCs altogether, first divide them into 2 groups of 6: A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6, and label the remaining one C. Each group is arranged in a circle, with links between neighbours. The 1,4 of each group links to C directly while the 2,3,5,6 links to the GSCs in the other group with the same index (mod 3).

For example, A1 links to A2,A6,C. B5 links to B4,B6,A2,A5.

Here is the SCM:

Code:
   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C
A1  .  1  .  .  .  1  .  .  .  .  .  .  1
A2  1  .  1  .  .  .  .  1  .  .  1  .  .
A3  .  1  .  1  .  .  .  .  1  .  .  1  .
A4  .  .  1  .  1  .  .  .  .  .  .  .  1
A5  .  .  .  1  .  1  .  1  .  .  1  .  .
A6  1  .  .  .  1  .  .  .  1  .  .  1  .
B1  .  .  .  .  .  .  .  1  .  .  .  1  1
B2  .  1  .  .  1  .  1  .  1  .  .  .  .
B3  .  .  1  .  .  1  .  1  .  1  .  .  .
B4  .  .  .  .  .  .  .  .  1  .  1  .  1
B5  .  1  .  .  1  .  .  .  .  1  .  1  .
B6  .  .  1  .  .  1  1  .  .  .  1  .  .
C   1  .  .  1  .  .  1  .  .  1  .  .  .

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C
A1  0  1  2  2  2  1  2  2  2  2  2  2  1
A2  1  0  1  2  2  2  2  1  2  2  1  2  2
A3  2  1  0  1  2  2  2  2  1  2  2  1  2
A4  2  2  1  0  1  2  2  2  2  2  2  2  1
A5  2  2  2  1  0  1  2  1  2  2  1  2  2
A6  1  2  2  2  1  0  2  2  1  2  2  1  2
B1  2  2  2  2  2  2  0  1  2  2  2  1  1
B2  2  1  2  2  1  2  1  0  1  2  2  2  2
B3  2  2  1  2  2  1  2  1  0  1  2  2  2
B4  2  2  2  2  2  2  2  2  1  0  1  2  1
B5  2  1  2  2  1  2  2  2  2  1  0  1  2
B6  2  2  1  2  2  1  1  2  2  2  1  0  2
C   1  2  2  1  2  2  1  2  2  1  2  2  0


Note there is not as much redundancy as in the scenario for 12 GSCs - which leads to a simple accomodation for the 14 GSCs scenario:



To connect 14 GSCs altogether, first divide them into 2 groups of 6: A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6, and label the remaining two C,D. Each group is arranged in a circle, with links between neighbours. The 1,4 of each group links to C,D directly while the 2,3,5,6 links to the GSCs in the other group with the same index (mod 3).

For example, A1 links to A2,A6,C,D. B5 links to B4,B6,A2,A5.

Here is the SCM:

Code:
   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C  D
A1  .  1  .  .  .  1  .  .  .  .  .  .  1  1
A2  1  .  1  .  .  .  .  1  .  .  1  .  .  .
A3  .  1  .  1  .  .  .  .  1  .  .  1  .  .
A4  .  .  1  .  1  .  .  .  .  .  .  .  1  1
A5  .  .  .  1  .  1  .  1  .  .  1  .  .  .
A6  1  .  .  .  1  .  .  .  1  .  .  1  .  .
B1  .  .  .  .  .  .  .  1  .  .  .  1  1  1
B2  .  1  .  .  1  .  1  .  1  .  .  .  .  .
B3  .  .  1  .  .  1  .  1  .  1  .  .  .  .
B4  .  .  .  .  .  .  .  .  1  .  1  .  1  1
B5  .  1  .  .  1  .  .  .  .  1  .  1  .  .
B6  .  .  1  .  .  1  1  .  .  .  1  .  .  .
C   1  .  .  1  .  .  1  .  .  1  .  .  .  .
D   1  .  .  1  .  .  1  .  .  1  .  .  .  .

   A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6  C  D
A1  0  1  2  2  2  1  2  2  2  2  2  2  1  1
A2  1  0  1  2  2  2  2  1  2  2  1  2  2  2
A3  2  1  0  1  2  2  2  2  1  2  2  1  2  2
A4  2  2  1  0  1  2  2  2  2  2  2  2  1  1
A5  2  2  2  1  0  1  2  1  2  2  1  2  2  2
A6  1  2  2  2  1  0  2  2  1  2  2  1  2  2
B1  2  2  2  2  2  2  0  1  2  2  2  1  1  1
B2  2  1  2  2  1  2  1  0  1  2  2  2  2  2
B3  2  2  1  2  2  1  2  1  0  1  2  2  2  2
B4  2  2  2  2  2  2  2  2  1  0  1  2  1  1
B5  2  1  2  2  1  2  2  2  2  1  0  1  2  2
B6  2  2  1  2  2  1  1  2  2  2  1  0  2  2
C   1  2  2  1  2  2  1  2  2  1  2  2  0  2
D   1  2  2  1  2  2  1  2  2  1  2  2  2  0




The scenario for 15 GSCs is much more complicated, I will show it next time.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 22, 2011 7:28 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
I have drawn up some "text graphics" for a few of the scenarios:

Code:
10 BSCs (10 nodes, max 3 links each):

+---+     +---+     +---+
| B1|-----| B |-----| B2|
+---+     +---+     +---+
  |  \      |      /  |
  |   \   +---+   /   |
  |    \  | Z |  /    |
  |     \ +---+ /     |
  |      X     X      |
+---+   / \   / \   +---+
| A1|--/---\-/---\--| C2|
+---+ /     X     \ +---+
  |  /     / \     \  |
+---+ +---+   +---+ +---+
| A |-| A2|---| C1|-| C |
+---+ +---+   +---+ +---+


Code:
12 GSCs (12 nodes, max 4 links each):

       +---+       +---+
       | B6|-------| B5|
       +---+\_   _/+---+
      /  |    \ /    |  \
     /   |     X     |   \
    /    |   _/ \_   |    \
   /     | _/     \_ |     \
+---+    |/  +---+  \|    +---+
| A6|----/---| A1|---\----| A2|
+---+   /|   +---+   |\   +---+
  |\   / |  /     \  | \   /|
  | \ /+---+       +---+\ / |
  |  X | B1|       | B4| X  |
  | / \+---+       +---+/ \ |
  |/   \ |  \     /  | /   \|
+---+   \|   +---+   |/   +---+
| A5|----\---| A4|---/----| A3|
+---+    |\_ +---+ _/|    +---+
   \     |  \_   _/  |     /
    \    |    \ /    |    /
     \   |     X     |   /
      \  |   _/ \_   |  /
       +---+/     \+---+
       | B2|-------| B3|
       +---+       +---+


Code:
13 GSCs (13 nodes, max 4 links each):

       +---+       +---+
       | B6|-------| B5|
       +---+\_   _/+---+
      /  |    \ /    |  \
     /   |     X     |   \
    /    |   _/ \_   |    \
   /     | _/     \_ |     \
+---+    |/  +---+  \|    +---+
| A6|----/---| A1|---\----| A2|
+---+   /|   +---+   |\   +---+
  |\   / |     |     | \   /|
  | \ /+---+ +---+ +---+\ / |
  |  X | B1|-| C |-| B4| X  |
  | / \+---+ +---+ +---+/ \ |
  |/   \ |     |     | /   \|
+---+   \|   +---+   |/   +---+
| A5|----\---| A4|---/----| A3|
+---+    |\_ +---+ _/|    +---+
   \     |  \_   _/  |     /
    \    |    \ /    |    /
     \   |     X     |   /
      \  |   _/ \_   |  /
       +---+/     \+---+
       | B2|-------| B3|
       +---+       +---+


Code:
14 GSCs (14 nodes, max 4 links each):

       +---+         +---+
       | B5|---------| A2|
       +---+\       /+---+
      /  |   \     /   |  \
     /   |    \   /    |   \
+---+    |     \ /     |    +---+
| B6|----+------X------+----| A3|
+---+    | +---+ +---+ |    +---+
  |  \   | | A1| | B4| |   /  |
  |   \  | +---+ +---+ |  /   |
  |    \ | / |  X  | \ | /    |
  |     \|/+---+ +---+\|/     |
  |      X | C | | D | X      |
  |     /|\+---+ +---+/|\     |
  |    / | \ |  X  | / | \    |
  |   /  | +---+ +---+ |  \   |
  |  /   | | B1| | A4| |   \  |
+---+    | +---+ +---+ |    +---+
| A6|----+------X------+----| B3|
+---+    |     / \     |    +---+
     \   |    /   \    |   /
      \  |   /     \   |  /
       +---+/       \+---+
       | A5|---------| B2|
       +---+         +---+


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 22, 2011 7:28 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
15 GSCs (15 nodes, max 4 links each):

Divide them into 3 different groups of 5: A1,A2,A3,A4,A5, B1,B2,B3,B4,B5, C1,C2,C3,C4,C5. Arrange each group into a circle, linking the neighbours.

Next, order the groups in the following cyclic manner A->B->C->A->B, so each group has a previous and a next (e.g. C's previous is B, its next is A).

Then we link each GSC to the next group's GSC with double the index (mod 5). Say B4, double the index (mod 5) is 8 (mod 5), which is 3. So we link B4 to C3. Starting from A1, we have the following 12 elements cycle:

A1-B2-C4-A3-B1-C2-A4-B3-C1-A2-B4-C3-A1

Also, A5,B5,C5 are linked together as a triangle, which also follows the previous rule as 5 (mod 5) & 5*2 (mod 5) are both equal to 0 (mod 5).

Now to verify this works. We use group B as an example because all groups are rotationally symmetric now. All groups are already interconnected via the circles, so we just need to demonstrate the cross-group connections.

For B1, it is directly linked to A3,C2,B2,B5. A3 bridges to A2,A4, C2 bridges to C1,C3, B2 bridges to A1,C4, B5 bridges to A5,C5.
For B2, it is directly linked to A1,C4,B1,B3. A1 bridges to A2,A5, C4 bridges to C3,C5, B1 bridges to A3,C2, B3 bridges to A4,C1.
For B3, it is directly linked to A4,C1,B2,B4. A4 bridges to A3,A5, C1 bridges to C2,C5, B2 bridges to A1,C4, B4 bridges to A2,C3.
For B4, it is directly linked to A2,C3,B3,B5. A2 bridges to A1,A3, C3 bridges to C2,C4, B3 bridges to A4,C1, B5 bridges to A5,C5.
For B5, it is directly linked to A5,C5,B1,B4. A5 bridges to A1,A4, C5 bridges to C1,C4, B1 bridges to A3,C2, B4 bridges to A2,C3.


As shown all GSCs are connected to all others. This is the SCM:

Code:
   A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5
A1  .  1  .  .  1  .  1  .  .  .  .  .  1  .  .
A2  1  .  1  .  .  .  .  .  1  .  1  .  .  .  .
A3  .  1  .  1  .  1  .  .  .  .  .  .  .  1  .
A4  .  .  1  .  1  .  .  1  .  .  .  1  .  .  .
A5  1  .  .  1  .  .  .  .  .  1  .  .  .  .  1
B1  .  .  1  .  .  .  1  .  .  1  .  1  .  .  .
B2  1  .  .  .  .  1  .  1  .  .  .  .  .  1  .
B3  .  .  .  1  .  .  1  .  1  .  1  .  .  .  .
B4  .  1  .  .  .  .  .  1  .  1  .  .  1  .  .
B5  .  .  .  .  1  1  .  .  1  .  .  .  .  .  1
C1  .  1  .  .  .  .  .  1  .  .  .  1  .  .  1
C2  .  .  .  1  .  1  .  .  .  .  1  .  1  .  .
C3  1  .  .  .  .  .  .  .  1  .  .  1  .  1  .
C4  .  .  1  .  .  .  1  .  .  .  .  .  1  .  1
C5  .  .  .  .  1  .  .  .  .  1  1  .  .  1  .

   A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5
A1  0  1  2  2  1  2  1  2  2  2  2  2  1  2  2
A2  1  0  1  2  2  2  2  2  1  2  1  2  2  2  2
A3  2  1  0  1  2  1  2  2  2  2  2  2  2  1  2
A4  2  2  1  0  1  2  2  1  2  2  2  1  2  2  2
A5  1  2  2  1  0  2  2  2  2  1  2  2  2  2  1
B1  2  2  1  2  2  0  1  2  2  1  2  1  2  2  2
B2  1  2  2  2  2  1  0  1  2  2  2  2  2  1  2
B3  2  2  2  1  2  2  1  0  1  2  1  2  2  2  2
B4  2  1  2  2  2  2  2  1  0  1  2  2  1  2  2
B5  2  2  2  2  1  1  2  2  1  0  2  2  2  2  1
C1  2  1  2  2  2  2  2  1  2  2  0  1  2  2  1
C2  2  2  2  1  2  1  2  2  2  2  1  0  1  2  2
C3  1  2  2  2  2  2  2  2  1  2  2  1  0  1  2
C4  2  2  1  2  2  2  1  2  2  2  2  2  1  0  1
C5  2  2  2  2  1  2  2  2  2  1  1  2  2  1  0


This cyclic approach can also be used for larger scenarios to ensure easy verification.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 22, 2011 7:29 pm 
Offline
Master
Master
User avatar

Joined: Thu Oct 07, 2010 3:21 pm
Posts: 170
Now immediately on to the RSCs (max 5 links each):


16 RSCs (16 nodes, max 5 links each):

Divide them into 4 groups of 4 (ABCD x 1234). Each group (ABCD) is linked as a circle. Also RSCs with the same index (e.g. A1,B1,C1,D1) are also linked as circles. Finally, RSCs two groups and two indices apart are linked together, e.g. A1-C3, B4-D2. Since all nodes are symmetrically linked, just verify using B2 as an example:

B2 is directly linked to B1,B3,A2,C2,D4.
B4 is bridged from B1 or B3.
D2 is bridged from A2 or C2.
A1,A3 are bridged from A2.
C1,C3 are bridged from C2.
D1,D3,A4,C4 are bridged from D4.

Hence all other 15 RSCs are connected to B2. Ditto for the rest. This is the SCM:

Code:
   A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 D1 D2 D3 D4
A1  .  1  .  1  1  .  .  .  .  .  1  .  1  .  .  .
A2  1  .  1  .  .  1  .  .  .  .  .  1  .  1  .  .
A3  .  1  .  1  .  .  1  .  1  .  .  .  .  .  1  .
A4  1  .  1  .  .  .  .  1  .  1  .  .  .  .  .  1
B1  1  .  .  .  .  1  .  1  1  .  .  .  .  .  1  .
B2  .  1  .  .  1  .  1  .  .  1  .  .  .  .  .  1
B3  .  .  1  .  .  1  .  1  .  .  1  .  1  .  .  .
B4  .  .  .  1  1  .  1  .  .  .  .  1  .  1  .  .
C1  .  .  1  .  1  .  .  .  .  1  .  1  1  .  .  .
C2  .  .  .  1  .  1  .  .  1  .  1  .  .  1  .  .
C3  1  .  .  .  .  .  1  .  .  1  .  1  .  .  1  .
C4  .  1  .  .  .  .  .  1  1  .  1  .  .  .  .  1
D1  1  .  .  .  .  .  1  .  1  .  .  .  .  1  .  1
D2  .  1  .  .  .  .  .  1  .  1  .  .  1  .  1  .
D3  .  .  1  .  1  .  .  .  .  .  1  .  .  1  .  1
D4  .  .  .  1  .  1  .  .  .  .  .  1  1  .  1  .

   A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 D1 D2 D3 D4
A1  0  1  2  1  1  2  2  2  2  2  1  2  1  2  2  2
A2  1  0  1  2  2  1  2  2  2  2  2  1  2  1  2  2
A3  2  1  0  1  2  2  1  2  1  2  2  2  2  2  1  2
A4  1  2  1  0  2  2  2  1  2  1  2  2  2  2  2  1
B1  1  2  2  2  0  1  2  1  1  2  2  2  2  2  1  2
B2  2  1  2  2  1  0  1  2  2  1  2  2  2  2  2  1
B3  2  2  1  2  2  1  0  1  2  2  1  2  1  2  2  2
B4  2  2  2  1  1  2  1  0  2  2  2  1  2  1  2  2
C1  2  2  1  2  1  2  2  2  0  1  2  1  1  2  2  2
C2  2  2  2  1  2  1  2  2  1  0  1  2  2  1  2  2
C3  1  2  2  2  2  2  1  2  2  1  0  1  2  2  1  2
C4  2  1  2  2  2  2  2  1  1  2  1  0  2  2  2  1
D1  1  2  2  2  2  2  1  2  1  2  2  2  0  1  2  1
D2  2  1  2  2  2  2  2  1  2  1  2  2  1  0  1  2
D3  2  2  1  2  1  2  2  2  2  2  1  2  2  1  0  1
D4  2  2  2  1  2  1  2  2  2  2  2  1  1  2  1  0


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group