Мультиграф

Граф с несколькими ребрами между двумя вершинами

Мультиграф с несколькими ребрами (красный) и несколькими петлями (синий). Не все авторы допускают наличие петель в мультиграфах.

В математике , а точнее в теории графов , мультиграф — это граф , которому разрешено иметь несколько ребер (также называемых параллельными ребрами ^[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 набор вершин или узлов ,​​
• A — набор рёбер или линий ,​
• ${\displaystyle s:A\rightarrow V}$, назначая каждому ребру его исходный узел,
• ${\displaystyle t:A\rightarrow V}$, назначая каждому ребру его целевой узел.

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

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

Маркировка

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

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

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

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

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

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

Смотрите также

• Многомерная сеть
• Глоссарий терминов теории графов
• Теория графов

Примечания

1. Например, см. Балакришнан 1997, с. 1 или Чартран и Чжан 2012, с. 26.
2. Например, см. Bollobás 2002, стр. 7 или Diestel 2010, стр. 28.
3. Например, см. Wilson 2002, стр. 6 или Chartrand and Zhang 2012, стр. 26-27.

Ссылки

• Балакришнан, ВК (1997). Теория графов . McGraw-Hill. ISBN 0-07-005489-4.
• Bollobás, Béla (2002). Современная теория графов . Graduate Texts in Mathematics . Vol. 184. Springer. ISBN 0-387-98488-7.
• Chartrand, Gary ; Zhang, Ping (2012). Первый курс теории графов . Дувр. ISBN 978-0-486-48368-9.
• Дистель, Рейнхард (2010). Теория графов . Тексты для аспирантов по математике. Т. 173 (4-е изд.). Springer. ISBN 978-3-642-14278-9.
• Гросс, Джонатан Л.; Йеллен, Джей (1998). Теория графов и ее приложения . CRC Press. ISBN 0-8493-3982-0.
• Гросс, Джонатан Л.; Йеллен, Джей, ред. (2003). Справочник по теории графов . CRC. ISBN 1-58488-090-2.
• Харари, Фрэнк (1995). Теория графов . Эддисон Уэсли. ISBN 0-201-41033-8.
• Janson, Svante ; Knuth, Donald E. ; Luczak, Tomasz; Pittel, Boris (1993). «Рождение гигантского компонента». Случайные структуры и алгоритмы . 4 (3): 231–358. arXiv : math/9310236 . Bibcode :1993math.....10236J. doi :10.1002/rsa.3240040303. ISSN  1042-9832. MR  1220220. S2CID  206454812.
• Уилсон, Роберт А. (2002). Графы, раскраски и теорема о четырех цветах. Oxford Science Publ. ISBN 0-19-851062-4.
• Цвиллингер, Дэниел (2002). CRC Стандартные математические таблицы и формулы (31-е изд.). Chapman & Hall/CRC. ISBN 1-58488-291-3.

Внешние ссылки

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