Мультиграф

В математике и, более конкретно, в теории графов , мультиграф — это граф , в котором разрешено иметь несколько ребер (также называемых параллельными ребрами). ^[1]), то есть ребра , имеющие одинаковые конечные узлы . Таким образом, две вершины могут быть соединены более чем одним ребром.

Существует два различных понятия кратных ребер:

Края без собственной идентичности . Идентичность ребра определяется исключительно двумя узлами, которые оно соединяет. В этом случае термин «множественные ребра» означает, что одно и то же ребро может встречаться между этими двумя узлами несколько раз.
Края с собственной идентичностью . Края — это примитивные объекты, такие же, как и узлы. Когда несколько ребер соединяют два узла, это разные ребра.

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

Для некоторых авторов термины псевдограф и мультиграф являются синонимами. По мнению других, псевдограф — это мультиграф, которому разрешено иметь циклы .

Неориентированный мультиграф (ребра без собственной идентичности) [ править ]

Мультиграф G — это упорядоченная пара G := ( V , E ) с

V набор вершин или узлов ,
E — неупорядоченных мультимножество пар вершин, называемых ребрами или линиями .

Неориентированный мультиграф (ребра с собственной идентичностью) [ править ]

Мультиграф G — это упорядоченная тройка G := ( V , E , r ) с

V набор вершин или узлов ,
E набор ребер или линий ,
r : E → {{ x , y } : x , y ∈ V }, назначая каждому ребру неупорядоченную пару узлов конечных точек.

Некоторые авторы допускают наличие в мультиграфах петель , то есть ребра, соединяющего вершину сама с собой. ^[2] в то время как другие называют эти псевдографы , оставляя термин мультиграф для случая отсутствия петель. ^[3]

Направленный мультиграф (ребра без собственной идентичности) [ править ]

Мультиорграф ориентированный — это граф , которому разрешено иметь несколько дуг, т. е. дуг с одними и теми же исходными и целевыми узлами. Мультиорграф G — это упорядоченная пара G := ( V , A ) с

V набор вершин или узлов ,
Мультимножество упорядоченных пар вершин, называемых направленными ребрами , дугами или стрелками .

Смешанный мультиграф G := ( V , E , A ) можно определить так же, как и смешанный граф .

Направленный мультиграф (ребра со своей идентичностью) [ править ]

Мультиорграф или колчан G — это упорядоченная четверка G := ( V , A , s , t ) с

V набор вершин или узлов ,
Набор ребер или линий ,
$s:A\rightarrow V$ , назначая каждому ребру исходный узел,
$t:A\rightarrow V$ , назначая каждому ребру целевой узел.

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

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

Маркировка [ править ]

Мультиграфы и мультидиграфы также поддерживают идею маркировки графов аналогичным образом. Однако единства в терминологии в данном случае нет.

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

Определение 1. Размеченный мультиорграф — это помеченный граф с помеченными дугами.

Формально: помеченный мультиорграф G — это мультиграф с помеченными вершинами и дугами. Формально это восьмерка. $G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})$ где

$V$ представляет собой набор вершин и $A$ представляет собой набор дуг.
$\Sigma _{V}$ и $\Sigma _{A}$ являются конечными алфавитами доступных меток вершин и дуг,
$s\colon A\rightarrow \ V$ и $t\colon A\rightarrow \ V$ две карты, указывающие исходную и целевую вершину дуги,
$\ell _{V}\colon V\rightarrow \Sigma _{V}$ и $\ell _{A}\colon A\rightarrow \Sigma _{A}$ две карты, описывающие маркировку вершин и дуг.

Определение 2 : Помеченный мультиорграф — это помеченный граф с несколькими помеченными дугами, т.е. дугами с одинаковыми конечными вершинами и одной и той же меткой дуги (обратите внимание, что это понятие помеченного графа отличается от понятия, данного в статье « маркировка графа» ).

См. также [ править ]

Примечания [ править ]

^ Например, см. Балакришнан 1997, с. 1 или Чартран и Чжан 2012, с. 26.
^ Например, см. Bollobás 2002, p. 7 или Дистель 2010, с. 28.
^ Например, см. Wilson 2002, p. 6 или Чартран и Чжан, 2012, стр. 26–27.

Ссылки [ править ]

Балакришнан, В.К. (1997). Теория графов . МакГроу-Хилл. ISBN 0-07-005489-4 .
Боллобас, Бела (2002). Современная теория графов . Тексты для аспирантов по математике . Том. 184. Спрингер. ISBN 0-387-98488-7 .
Шартран, Гэри ; Чжан, Пин (2012). Первый курс теории графов . Дувр. ISBN 978-0-486-48368-9 .
Дистель, Рейнхард (2010). Теория графов . Тексты для аспирантов по математике. Том. 173 (4-е изд.). Спрингер. ISBN 978-3-642-14278-9 .
Гросс, Джонатан Л.; Йеллен, Джей (1998). Теория графов и ее приложения . ЦРК Пресс. ISBN 0-8493-3982-0 .
Гросс, Джонатан Л.; Йеллен, Джей, ред. (2003). Справочник по теории графов . КПР. ISBN 1-58488-090-2 .
Харари, Фрэнк (1995). Теория графов . Эддисон Уэсли. ISBN 0-201-41033-8 .
Янсон, Сванте ; Кнут, Дональд Э .; Лузак, Томаш; Питтель, Борис (1993). «Рождение гигантского компонента». Случайные структуры и алгоритмы . 4 (3): 231–358. arXiv : математика/9310236 . Бибкод : 1993math.....10236J . дои : 10.1002/rsa.3240040303 . ISSN 1042-9832 . МР 1220220 . S2CID 206454812 .
Уилсон, Роберт А. (2002). Графы, раскраски и теорема о четырех красках . Оксфордское научное издательство. ISBN 0-19-851062-4 .
Цвиллингер, Дэниел (2002). Стандартные математические таблицы и формулы CRC (31-е изд.). Чепмен и Холл/CRC. ISBN 1-58488-291-3 .

Внешние ссылки [ править ]

В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Мультиграф» . Словарь алгоритмов и структур данных . НИСТ .

[1] Например, см. Балакришнан 1997, с. 1 или Чартран и Чжан 2012, с. 26.

[2] Например, см. Bollobás 2002, p. 7 или Дистель 2010, с. 28.

[3] Например, см. Wilson 2002, p. 6 или Чартран и Чжан, 2012, стр. 26–27.

[1]

[2]

[3]