Мультиграф

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

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

Есть два разных понятия множественных ребер:

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

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

Для некоторых авторов термины псевдограф и мультиграф являются синонимами. Для других псевдограф - это мультиграф, который может иметь петли.

• 1 Ненаправленный мультиграф (ребра без собственной идентичности)
• 2 Ненаправленный мультиграф (ребра с собственной идентичностью)
• 3 Направленный мультиграф (ребра без собственной идентичности)
• 4 Направленный мультиграф (ребра с собственной идентичностью)
• 5 Маркировка
• 6 См. Также
• 7 Примечания
• 8 ссылки
• 9 Внешние ссылки

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

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

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

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

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

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

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

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

Мультииграф или колчан G - это упорядоченный набор из четырех G  : = ( V, A, s, t) с

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

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

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

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

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

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

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

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

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

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

• Балакришнан, ВК (1997). Теория графов. Макгроу-Хилл. ISBN   0-07-005489-4.
• Боллобаш, Бела (2002). Современная теория графов. Тексты для выпускников по математике. 184. Springer. ISBN   0-387-98488-7.
• Чартран, Гэри ; Чжан, Пинг (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.
• Янсон, Сванте ; Кнут, Дональд Э. ; Лучак, Томаш; Питтель, Борис (1993). «Рождение гигантского компонента». Случайные структуры и алгоритмы. 4 (3): 231–358. arXiv : math / 9310236. Bibcode : 1993math..... 10236J. DOI : 10.1002 / rsa.3240040303. ISSN   1042-9832. Руководство по ремонту   1220220.
• Уилсон, Роберт А. (2002). Графы, раскраски и теорема о четырех цветах. Oxford Science Publ. ISBN   0-19-851062-4.
• Цвиллинджер, Даниэль (2002). Стандартные математические таблицы и формулы CRC (31-е изд.). Чепмен и Холл / CRC. ISBN   1-58488-291-3.

•  Эта статья включает материалы, являющиеся общественным достоянием  из  документа NIST :  Black, Paul E. "Multigraph". Словарь алгоритмов и структур данных.