ТЕОРЕМА ГРАФОВ КАК ОСНОВА ПОСТРОЕНИЯ СИСТЕМ СВЯЗИ

АННОТАЦИЯ

Теория графов является основанием для построения всех видов сетей связи и может обеспечить их качественный анализ и классификацию. Современное понимание построения сетей и их топология не возможна без теоретико-графовых моделей программ и систем, включая системы переписывания графов и графовые грамматики. Теория графов является одной из основных описательных моделей построения специфических и не специфических сетей связи. 

ABSTRACT

Graph theory is the basis for the construction of all kinds of communication networks and can provide their qualitative analysis and classification. Modern understanding of network construction and their topology is not possible without theoretical and graph models of programs and systems, including graph rewriting systems and graph grammars. Graph theory is one of the main descriptive models for constructing specific and non-specific communication networks.

Ключевая слова: теорема графов; дискретная математика; топология систем сети; матрица сети; дуга; ребро; обобщенная стоимость;матрица информационных тяготений.

Keywords: graph theorem; Discrete Math; topology of network systems; network matrix; arc; edge; generalized cost; informational gravity matrix.

Введение

Первое упоминание Теории Графов приходится на 1736 год. Эммануил Кант разгуливая по улицам Кёнигсберга, в настоящее время именуемый Калининградом, задался вопросом: « Как пройти по всем мостам, не проходя по нему дважды, и вернуться в исходную точку?» Многие ученые того времени пытались решить эту математическую задачу, но теоретические и практические исследования не привели к решению.

Петербуржская академия наук славилась своими достижениями в области математики, а именно выделялись работы Леонарда Эйлера. В марте 1736 года, в своем письме итальянскому инженеру Мариони, Эйлер пишет о необходимости найти маршрут, чтобы пройти от одного участка суши до другого единожды. Таким образом, ученый доказал, что невозможно пройти по 7 мостам и вернуться в исходную точку не проходя мост дважды.

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

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

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

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

1. Основные понятия теории графов.

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

Рисунок 1. Наглядный пример построения графа

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

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

Таблица 1.

Типология графов

На основании таблицы 1 мы видим, что теория графов является основанием для построения всех видов сетей связи и может обеспечить их качественный анализ и классификацию.

Для понимания топологии сетей связи необходимо отдельно выделить понятия Абстрактных и семантических графовых сетей. Наглядно представить посторенние сетей можно на Рисунке 2.

Рисунок 2. Схема построения абстрактной и семантической графовой сети

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

2. Теория графов как основа анализа систем связи.

Структура сети (её морфологическая модель) задается неориентированным графом , где [32, 36–39, 94]:

 – множество вершин (узлов связи – УС), декомпозируемых на совокупность узлов доступа и узлов магистральной сети и характеризуемых координатами их размещения, относительно которых определяются элементы матрицы расстояний между узлами связи ;

 – множество ребер (сетка линий связи – ЛС), характеризуемых родом связи и вектором пропускных способностей ;

 – множество элементов графа, где , ,  – число элементов (мощность) множеств N, M, D.

Каждому элементу графа ставится в соответствие количественный параметр , который обычно называют обобщённой стоимостью. При этом матрица стоимостей задается массивом  [32, 36–39]. Каждый элемент графа  статистически независимо отказывает с известными вероятностями отказа [28, 37].

Матрицы смежности  и инциденций  неориентированного графа  задаются в следующем виде:

         (2.2)

                      (2.3)

Матрица информационных тяготений ,  определяет интенсивность передаваемого потока r-го класса между i-м и j-м узлами графа .

Вывод

Современное понимание построения сетей и их топология не возможна без теоретико-графовых моделей программ и систем, включая системы переписывания графов и графовые грамматики. Активно используются методы теории графов в искусственном интеллекте. Теория графов является одной из основных описательных моделей построения специфических и не специфических сетей связи. 

Список литературы

1. Алексеев В. Б., Ложкин С. А. Элементы теории графов и схем.М.:МГУ. – 2007. - 40 с.
2. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука. – 2008. - 384 с.
3. Костюкова Н. И. Графы и их применение. Комбинаторные алгоритмы для программистов. М: Интернет-университет информационных технологий, Бином. – 2007. – 312с.
4. Липатов Е. П. Теория графов и ее применение. М: Знание. – 1986. – 367с.
5. Свами М., Тхулалираман К. Графы, сети и алгоритмы. М: Мир. – 2009. – 455с.