[Moscow.pm] Взрыв мозга или занимательная топология

[Kaltashkin Eugene]

Доброе время суток.

Предлагаю некоторую разминку для мозга.
Тема разминки: построение топологических деревьев или сопоставление 
множеств множествам.
Поясню смысл. Тема произошла от задачи построения топологии локальной 
сети с неопределенным количеством узлов коммутации и устройств.
Опишу используемые термины:
устройство - конечное абонентское устройство имеющее фиксированный адрес 
или признак.
узел коммутации - промежуточное устройство содержащее в себе базу 
расположения устройств подключенных непосредственно к узлу коммутации 
или к соседним узлам коммутации или концентрации.
узел концентрации - промежуточное устройство не имеющее в себе базы 
данных устройств подключенных к себе, но объединяющее несколько 
устройств по определенным признакам.
Ярким примером классического топологического дерева является схема 
взаимодействия подразделений внутри любой компании или генеалогическое 
дерево ваших предков.
http://zhecka.323f.net.ru/temp/topology.jpg
На картинке пример обычного дерева, устройства подключены к узлам 
коммутации, узлы в свою очередь подключены друг к другу. Использование 
ветвлений дерева предполагает отсутствие колец(двойных соединений) между 
какими либо двумя устройствами в системе, кроме оговоренных случаев.
Устройство коммутации содержит в себе информацию о подключенных 
устройствах к пронумерованным портам(ветвям - листьям) дерева.
Концентратор1 не знает какие устройства к нему подключены, т.к. он не 
обладает внутренней базой данных. Коммутатор1(в центре)
знает что на его порт1 подключено 2 устройства, на портах 2,3,4,5 
подключено по одному устройству, на порту 8 подключено 4 
устройства(коммутаторы также имеют свой уникальный номер). 
Коммутатор2(справа) знает что к его порту 1 подключены 7 устройств, а 
также по одному устройству на каждом порту.
Необходимо построить путь от любого устройства к любому включая узлы 
коммутации, и определить точки соединения узлов коммутации.

Если честно я решил эту задачу наполовину, но потом впал в ступор. По шагам.
1. это определение public портов на которых имеется куча значений. Эти 
порты могут быть uplink и downlink, uplink это порт к вышестоящему по 
топологии узлу, downlink это порт к нижестоящему по топологии узлу. 2. 
необходимо получить список портов через которые каждое устройство видит 
другие устройства. 3.получить список портов через которые узлы видят 
друг друга. 4. опять прогнать процедуру привязки портов на public и 
5.точно вычислить статусы unlink и downlink для каждого из узлов. Я 
застрял на 4-5 шаге. Может у кого есть какие идеи ? Я иссяк :(