Портовые графы

Портовые графы — одна из разновидностей архиграфов, служащие для моделирования и анализа телекоммуникационных систем.

Задание портового графа

Портовый граф можно задать тройкой [math]\displaystyle{ (V, P, E) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин, [math]\displaystyle{ P }[/math] — множество инцидентных вершинам портов, [math]\displaystyle{ E }[/math] — множество ребер (дуг), связывающих порты. При этом вершина представляет собой телекоммуникационное устройство. Порт — сетевой интерфейс данного устройства. Дуги — линии связи.

Для получения портового графа нам следует задать три класса элементов для разбиения протографа, и правило разбиения такое, что вершины соседствуют только с портами, порты могут соседствовать с дугами и вершинами, дуга связывает только порты. Портограф [math]\displaystyle{ P }[/math] задается множеством элементов [math]\displaystyle{ \{ p_i\} }[/math], [math]\displaystyle{ i=1 }[/math], [math]\displaystyle{ n }[/math] и матрицей соседства (смежности) [math]\displaystyle{ M(n\times n) }[/math], состоящей из 0 и 1, где 1 означает соседство (смежность) элемента [math]\displaystyle{ a }[/math] элементу [math]\displaystyle{ b }[/math].

Формализация

Портовым графом мы назовем граф [math]\displaystyle{ G (P, D, C) }[/math], где [math]\displaystyle{ D }[/math] - множество вершин-устройств (от английского Devices - устройства), [math]\displaystyle{ P }[/math]-множество вершин-портов (от английского Ports - порты), [math]\displaystyle{ C }[/math] - множество ребер, связанных следующим отношением (от английского Connections - соединения).

Никакие две вершины из множества [math]\displaystyle{ D }[/math] не могут быть связан с помощью ребер из [math]\displaystyle{ C }[/math], т.е. [math]\displaystyle{ \forall G(D,P,C) }[/math] [math]\displaystyle{ \forall d_1,d_2\in D }[/math] [math]\displaystyle{ \nexists c=(d_1,d_2)\in C }[/math]

При этом две вершины из множества [math]\displaystyle{ P }[/math] могут быть связаны ребром, т.е. [math]\displaystyle{ \exists G(D,P,C) }[/math] [math]\displaystyle{ \exists p_1,p_2\in P }[/math] [math]\displaystyle{ \exists c=(p_1,p_2)\in C }[/math].

Отношение между вершинами из [math]\displaystyle{ D }[/math] и вершинами из [math]\displaystyle{ P }[/math] необходимо задавать аналогично отношению между вершин и ребер для графа, т.е. с помощью матрицы инцидентности, матрицы смежности и т.п.

Также можно расширить множество [math]\displaystyle{ C }[/math] ребер, связывающих вершины [math]\displaystyle{ d\in D }[/math] множеством [math]\displaystyle{ C_d }[/math] ребер, связывающих [math]\displaystyle{ p\in P }[/math] и [math]\displaystyle{ d\in D }[/math].

В таком случае мы получим второй вариант отображения портового графа, где есть вершины двух типов ([math]\displaystyle{ P }[/math] и [math]\displaystyle{ D }[/math]) и ребра двух типов ([math]\displaystyle{ c=(p_1,p_2)\in C }[/math], [math]\displaystyle{ p_1,p_2\in P }[/math] и [math]\displaystyle{ c_{pd}=(p,d) }[/math], [math]\displaystyle{ c_{pd}\in C_d }[/math], [math]\displaystyle{ p\in P }[/math], [math]\displaystyle{ d\in D }[/math]).

При этом не существует ребер, связывающих вершины из [math]\displaystyle{ D }[/math], т.е. [math]\displaystyle{ \forall d_1, d_2\in D }[/math] [math]\displaystyle{ \nexists c_{dd}=(d_1,d_2)\in C_{p+d} }[/math]

Это обусловлено тем, что устройства подключаются к другим устройствам через порты. Технически могут использоваться интерфейсы для привязки к устройству сетевых адресов, не привязанных к физическим интерфейсам, но при формализации таких схем интерфейсы также должны отображаться в виде вершин-портов [math]\displaystyle{ p\in P }[/math].

Одна вершина из [math]\displaystyle{ D }[/math] может быть связана с несколькими вершинами [math]\displaystyle{ p }[/math], [math]\displaystyle{ \exists G(P,D, C_{p+d}) }[/math] [math]\displaystyle{ \exists d }[/math], [math]\displaystyle{ \exists p_1...p_n }[/math], [math]\displaystyle{ \exists (c_{pi},c_d)\in C_{p+d} }[/math]

[math]\displaystyle{ n=\mid (c_{pi}, c_d) \mid\geq 1 }[/math], [math]\displaystyle{ i=1...n }[/math], но для каждого [math]\displaystyle{ p\in P }[/math] (для случая телекоммуникационных сетей) существует только одна вершина [math]\displaystyle{ d\in D }[/math], связанная с [math]\displaystyle{ p }[/math].

[math]\displaystyle{ \forall p\in P }[/math] [math]\displaystyle{ \exists !d\in D }[/math] [math]\displaystyle{ \exists !c_{dp}=(p,d)\in C_{p+d} }[/math]

Не существует вершин [math]\displaystyle{ p }[/math], не связанных с [math]\displaystyle{ d }[/math], то есть изолированных вершин в множестве [math]\displaystyle{ P }[/math] нет.

[math]\displaystyle{ \forall G(P,D,C_{p+d}) }[/math] [math]\displaystyle{ \nexists p\{(c_p,c_d)\}=0 }[/math]

Но могут существовать вершины [math]\displaystyle{ d }[/math], не связанные не с одним портом. Такая ситуация может быть если устройство не имеет ни одного сетевого интерфейса. Во множестве [math]\displaystyle{ D }[/math] возможны изолированные вершины.

[math]\displaystyle{ \exists G(P,D,C_{p+d}) }[/math] [math]\displaystyle{ \exists d }[/math], [math]\displaystyle{ \forall p }[/math] [math]\displaystyle{ \nexists (c_p, c_d)\in C_{p+d} }[/math]

[math]\displaystyle{ n=|(c_p,c_d)|=0 }[/math]

Также может существовать вершина [math]\displaystyle{ p }[/math], не имеющая ни одно связи с другой вершиной [math]\displaystyle{ p }[/math].

[math]\displaystyle{ \exists G(P,D,C_{p+d}) }[/math] [math]\displaystyle{ \exists p_1 }[/math] [math]\displaystyle{ \nexists p_2 }[/math], [math]\displaystyle{ (c_{p1},c_{p2})\in C }[/math]

Количество связей вершин [math]\displaystyle{ p }[/math] может быть равно нулю или единице, [math]\displaystyle{ |(c_{p1},c_{p2})|=0..1 }[/math] если мы определим, что две вершины могут быть соединены только одним ребром, либо иметь значения 0, 1 или больше, если мы определим, что в схеме допустимы гипер-ребра (для топологий шина и радиосетей).

Изображения портового графа

Возможно два варианта изображения портового графа.

Первый вариант, когда в [math]\displaystyle{ G }[/math] имеется три вида сущностей: вершины-устройства, вершины-порты и ребра, по отношению к графу, имеющему два вида сущностей (вершина и ребро).Такой вариант портового графа изображен на Рисунке 1. Портовый граф. Имеется три вершины из множества [math]\displaystyle{ D }[/math] (устройств), по три вершины из множества [math]\displaystyle{ P }[/math] (портов), инцидентных вершинам из [math]\displaystyle{ D }[/math], имеется четыре ребра из множества [math]\displaystyle{ C }[/math], связывающих вершины-порты. Имеется одна висячая вершина-порт.

Портовый граф может быть изображен в виде мультиграфа, имеющего кратные ребра, тогда под портами будем понимать уникальное соответствие каждой вершины и каждой дуги мультиграфа. Имеется однозначное соответствие между вершиной-портом в портовом графе и инцидентностью между вершиной и дугой в мультиграфе. Таким образом для мультиграфа (см. Рисунок 2) каждый порт [math]\displaystyle{ p }[/math] является парой для инцидентных ребра и вершины. Но отметим, что для портового графа инцидентность должна быть определена не только для пар (вершина-порт, ребро), но и для пар (вершина-устройство, вершина-ребро), что может быть сделано несколькими способами.

Изображенный на Рисунке 1 портовый граф может быть изображен в виде мультиграфа, где вершины [math]\displaystyle{ d_2 }[/math] и [math]\displaystyle{ d_3 }[/math]связывают два кратных ребра [math]\displaystyle{ c_3 }[/math] и [math]\displaystyle{ c_4 }[/math].

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

Фактически при рассмотрении портового графа вершины [math]\displaystyle{ p\in P }[/math] ведут себя по отношению к [math]\displaystyle{ d\in D }[/math] как ребра, а по отношению к [math]\displaystyle{ c\in C }[/math] как вершины. Мы полагаем, что можно найти обобщения графов и большего порядка, если вводить достаточное число сущностей, отличное от 2 (графа) и 3 (портовые графы). Что же касается портового графа, его можно представить и в виде графа, не сводя к мультиграфу, а напротив, воспользовавшись подобием вершин [math]\displaystyle{ p }[/math] по отношению к вершинам [math]\displaystyle{ d }[/math] ребрам графа. Для этого, воспользуемся описанным свойством портового графа, что существует только одна связь [math]\displaystyle{ (p,d) }[/math] для каждого [math]\displaystyle{ p }[/math], и изобразим ее в виде дополнительных ребер, отличных от уже присутствующих в портовом графе.

Расширение множества [math]\displaystyle{ C }[/math] ребрами, показывающими связь [math]\displaystyle{ p }[/math] и [math]\displaystyle{ d }[/math] до множества [math]\displaystyle{ C_{p+d} }[/math] позволяет изобразить портовый граф в виде обычного графа, где имеются вершины и ребра, но вершины и ребра помечены, как имеющие один из двух типов. Для вершин это признак принадлежности множеству [math]\displaystyle{ D }[/math] или [math]\displaystyle{ P }[/math], для ребер - множеству [math]\displaystyle{ C }[/math] или [math]\displaystyle{ C_d }[/math] соответственно.

Портовый граф, изображенный на Рисунке 1 в отображенном виде представлен на Рисунке 3. Такое отображение назовем отображенным портовым графом.

Портовый граф (Рисунок 1, Рисунок 2) отображен на граф с добавлением ребер, соответствующих отношениям вершин [math]\displaystyle{ p }[/math] к вершинам [math]\displaystyle{ d }[/math].

Мы полагаем, что дополнительные ребра из [math]\displaystyle{ C_d }[/math] являются менее значимыми по информативности, нежели дополнительные вершины-порты, вводимые для мультиграфа. Таким образом портовый граф (Рисунок 1) более информативен, чем мультиграф (Рисунок 2), так как содержит больше релевантной информации, и более информативен чем отображенный портовый граф (Рисунок 3), так как содержит меньше избыточной информации.

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

Кроме того, мультиграфы могут быть аналогичным образом отображены в портовые графы и отображенные портовые графы.

Примеры портографов

Конечные портографы:

стек
очередь
карта

Бесконечные портографы:

машина Тьюринга
паркет

Разбор примера портографа телекоммуникационной сети

На рисунке изображен пример портового графа телекоммуникационной сети. При этом вершины помечены характеристиками устройств (указан hostname), порты помечены характеристиками сетевых интерфейсов (имя сетевого интерфейса, ТР-адрес и префикс сети), дуги помечены типом (экранированная/неэкранированная) и категорией витой пары. Отметим, что в рамках модели портового графа могут быть изображены и мультиграфы, используемые для описания телекоммуникационных сетей. При этом мы можем не просто связать два устройства параллельными линиями связи, но и приписать полезную информацию порту (сетевому интерфейсу).

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

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

Раскраска портографа

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

Раскраска протографа осуществляется аналогично раскраске карты [math]\displaystyle{ n }[/math] цветами. Также аналогично для протографа можно определить хроматическое число.

Нераскрашенному графу можно сопоставить протограф с хроматическим числом 2. Граф определен на множестве вершин [math]\displaystyle{ V }[/math] и множестве ребер [math]\displaystyle{ E }[/math], где каждое ребро сопоставлено паре вершин [math]\displaystyle{ (a,b) }[/math]. Сопоставим каждой вершине [math]\displaystyle{ v }[/math] элемент [math]\displaystyle{ p }[/math] протографа, таким образом, что два элемента [math]\displaystyle{ p_i }[/math] не будут смежными. Каждому ребру [math]\displaystyle{ e=(a,b) }[/math] сопоставим элемент [math]\displaystyle{ t }[/math], такой, что [math]\displaystyle{ p_a }[/math] и [math]\displaystyle{ t }[/math] — соседствуют, [math]\displaystyle{ t }[/math] и [math]\displaystyle{ p_b }[/math] — соседствуют. Раскрасим элементы [math]\displaystyle{ p }[/math] в цвет 1. Так как любой [math]\displaystyle{ p }[/math] соединяется только с одним [math]\displaystyle{ t_i }[/math], то [math]\displaystyle{ t_i }[/math] можно покрасить в цвет 2. Так как любой элемент [math]\displaystyle{ t_j }[/math] соседствует только двум элементам [math]\displaystyle{ p_c }[/math] и [math]\displaystyle{ p_d }[/math], которые уже раскрашены в цвет 1, двух цветов достаточно чтобы раскрасить протограф.

Нераскрашенному ориентированному графу можно сопоставить ориентированный портограф с хроматическим числом 2.

Непрямое соседство

Для протографа можно ввести определение непрямого соседства. Когда два элемента 1 класса [math]\displaystyle{ p_a }[/math] и [math]\displaystyle{ p_b }[/math] не соседние, но когда существует элемент 2 класса, при этом существует [math]\displaystyle{ t }[/math], такой что [math]\displaystyle{ p_a }[/math] и [math]\displaystyle{ t }[/math] соседние, [math]\displaystyle{ t }[/math] и [math]\displaystyle{ p_b }[/math] — соседние. Другими словами, непрямые соседи — два элемента одного класса, которые не являются соседними. Но есть элемент второго класса, который является соседним для каждого из тех элементов.

Заключение

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

См. также

Протограф

Список источников

1. Кручинин С.В., Кузнецов А.М., Зотов С.В. Графическое ядро визуализации и анализа инженерных схем//Свидетельство о государственной регистрации программа для ЭВМ № 2011618938 от 27.09.2011. -Федеральная служба по интеллектуальной собственности, патентам и товарным знакам.

2. Кручинин С. В. Математическая модель акторов телекоммуникационной сети в проектировании САПР//Известия Волгоградского государственного технического университета. -2014. -Т. 20. № 6 (133). -С. 123-131.

3. Кузнецов А.М. Реализация математической модели мультиграфа мобильных сетей транспортных средств // Научно-исследовательские публикации. 2016. № 5 (37). С. 50-54.

4. Гордеев Д. С. Визуализация внутреннего представления программ в системе функционального программирования SFP. - Новосибирск, 2004. - 54 с. - (Препр. / РАН. Сиб. Отд-ние. ИСИ; № 110).