Проектирование, виды проектирования в зависимости от степени автоматизации. Проектирование телекоммуникационных сетей на ЭВМ, страница 6

Шаг 3. Произвести сшивание отдельных малых циклов в один эйлеров цикл графовой модели. Выйти из вершины х и пройти по ребру с исходящей стрелкой и наибольшим индексом до следующей вершины. В ней определить по какому ребру идти дальше. Из всех исходящих ребер взять ребро с наибольшим индексом, по которому еще не проходили и так далее от вершины к вершине, пока не вернемся в х.

Примечание 1: если имеется несколько ребер с одинаковыми индексами, то выбрать любое.

Примечание 2: если в графе G построено несколько малых циклов, то для следующего малого цикла можно выбрать новую базовую вершину из имеющихся циклов, соблюдая правило: Новая вершина для будущего малого цикла должна быть смежна с базовой вершиной уже построенного малого цикла.

20.  Атрибуты графовых моделей сетевых структур, их определение и ввод в ЭВМ.

Вес вершины-это какое-то число,которое поставлено в соотв-е данной вершине и может обозначать стоимость,проп.способность,номерную емкость,в зависимости от условий решаемой задачи.

Вес ребра- это число или неск.чисел, могут  обозначать проп.спос-ть, емкость, длину и т.д, в зависимости от усл.решаемой задачи.

Граф взвешан по ребрам(полностью взвешанный)-граф имеет веса вершин и ребер.

Когда выходим из программы сохраняем атрибуты и входя в программу они там уже сохранены.

В ребрах выбирали тип, цвет.

Настраивали имя в Х1. В Х2 ставили вес ребра. Если меняем значение 1 атрибута в графе, меняется то лько оно, остальные остаются без изменений значения.

Можно в 1 значение указать несколько,например, вес ребра и потом стоимотной

21.  Задача о китайском почтальоне (постановка задачи, решение, примеры практического применения)

Общая формулировка задачи: необходимо пройти по всем ребрам графовой модели и вернуться в исходную вершину так, чтобы пройденный суммарный путь был самым коротким из возможных.

Решение: так как граф пути в общем случае является не Эйлеровым, то его в процессе решения задачи искусственно сводят к Эйлерову, удваивая некоторые ребра. Если такие ребра выбраны правильно, то пройденный путь можно найти как путь в сложном Эйлеровом графе по алгоритму Хуанг-Туи. Он действительно будет самым коротким, хотя по некоторым ребрам (удвоенным) такого графа искусственно сведенного к Эйлерову приходится проходить дважды. Выбор ребер графа, которые при решении задачи удваиваются, производится с использованием понятий наименьшего совершенного паросочетания и аргументальной цепи.

22.  Основные понятия и определения теории графов, используемые при компьютерном проектировании телекоммуникационных сетей

Графом G называется совокупность двух множеств(Х,U)и отображение j:XàU(однозначное соответствие,элементы одного множ-ва привязываются к др.мн-ву)),где X=(x1,x2,x3…xn),Х-множество вершин,U-мн-во ребер U=(U1,U2…Um)

Инцидентность –вершина Х инцидентна ребру U,если имеет место соотношение U=(x,xk).Верно и обратное утверждение, что ребро Uинцендентно вершине Х.

Если в графе все элементы множества U изображаются дугами, то такой граф называется ориентированным или орграфом, если ребрами – то неориентированным.

Два ребра называются смежными, если они имеют общий конец.

Вершина х_l и ребро u_l называются инцидентными, если х_l является концом u_l. Таким образом, смежность есть отношение между однородными элементами графа, а инцидентность – отношение между разнородными элементами.

Граф полный-граф,у которого любая пара вершин смежная.

Граф называется связным, если любые его две несовпадающие вершины соединены маршрутом.

Путь – это ориентированный маршрут.

Маршрут в графе,модел.тк сеть-это чередующаяся послед-ть вида х1,u1,x2,u2..Uk-1,uk,в которой любая пара двух соседних элементов инцидентна.

Цепь-в граф.модели-это маршрут,в котором все ребра различны.

Простая цепь-в которой все вершины различны.

Под степенью вершины графа понимается число ребер, инцидентных этой вершине (связанных с ней).

Валентность вершины графа-определяется числом инцидентных данной вершине ребер графа+число инциден-хей петель.

Сеть-наз.любой взвешанный граф(имеющий веса элементов).

Цикл-цепь,у которой начальная и конечная вершины совпадают.

23. Гиперграфы и гиперсети. Примеры использования при проектировании телекоммуникационных сетей.

  первичной сети - конфигурация сетки линий передачи или соединительных линий;

 вторичной сети - конфигурация сетки пучков каналов вторичной сети или каналов электросвязи;

листы А4  и ксерокс

24. Теорема Оре и ее применение.

Теорема Если для любой пары u и v несмежных вершин

графа G порядка n≥3 выполняется неравенство deg u+deg v≥n, то G – гамильтонов

граф.

Граф называется гамильтоновым, если в нем имеется простой цикл, содер-

жащий каждую вершину этого графа. Сам этот цикл также называется гамильто-

новым. Гамильтоновой называют и простую цепь, содержащую каждую вершину

графа.

25.  Связность в графовых моделях телекоммуникационных сетей.

                                           Теорема Менгера

Две вершины S и T явл. к-реберно связными, если между ними существует к-реберно-независимых S,t цепей.

Две вершины S и T явл. к- связными, если между ними существует к- независимых S,t цепей.