Автоматизированное проектирование телекоммуникационных сетей. Контрольная работа. 3-й вариант

1. Сделать теоретико-множественное представление графа.
2. Найти матрицу расстояний графа сети связи по выбранному варианту
3. Построить двойственный граф.
4.  Построить оптимальную сеть проводного вещания.
5. Найти оптимальное место расположение РАТС при минимизации капитальных затрат на линейные сооружения. (Медиана графа).
6.  Найти границу между двумя телефонными районами и оптимальные места расположения двух РАТС.
1.Теоретико-множественное представление.
Теоретико-множественное представление графа G(V,E) задается явным перечислением множеств V,E и отображения инциденции f.
Вершины:
а1,а2,а3,а4,а5,а6,а7,а8,а9,а10,а11,а12,а13,а14,а15,а16
Ребра:
u1,u2,u3,u4,u5,u6,u7,u8,u9,u10,u11,u12,u13,u14,u15,u16,u17,u18,u19,u20,u21,
u22
u1→a1a2 u9→a4a8 u17→a9a13
u2→a2a3 u10→ a8a9 u18→a13a14
u3→a1a4 u11→a5a9 u19→a11a14
u4→a4a5 u12→a9a10 u20→a12a15
u5→a2a5 u13→a10a11 u21→a13a15
u6→a5a6 u14→a7a11 u22→a15a16
u7→a6a7 u15→a8a12 u23→a14a16
u8→a3a7 u16→a12a13
3.Построим двойственный граф.

Граф G' называется (геометрически) двойственным для плоского графа G, если выполняются два следующих условия:
1) Каждой грани h графа G соответствует единственная вершина v' графа G'.
2) Если вершины v1' и v2' в G' соответствуют граням h1 и h2 в G, то каждому ребру e графа G, инцидентному граням h1 и h2, соответствует единственное ребро e' графа G', инцидентное вершинам v1' и v2'.

2011, зачет