Мультиграф - Multigraph
В математике , и более конкретно в теории графов , мультиграф - это граф, которому разрешено иметь несколько ребер (также называемых параллельными ребрами ), то есть ребра, которые имеют одинаковые конечные узлы . Таким образом, две вершины могут быть соединены более чем одним ребром.
Есть два разных понятия множественных ребер:
- Кромки без собственной идентичности : Идентичность кромки определяется исключительно двумя узлами, которые она соединяет. В этом случае термин «несколько ребер» означает, что одно и то же ребро может встречаться несколько раз между этими двумя узлами.
- Края с собственной идентичностью : Края - это примитивные объекты, как и узлы. Когда несколько ребер соединяют два узла, это разные ребра.
Мультиграф отличается от гиперграфа , который представляет собой граф, в котором ребро может соединять любое количество узлов, а не только два.
Для некоторых авторов термины псевдограф и мультиграф являются синонимами. Для других псевдограф - это мультиграф, который может иметь петли .
Ненаправленный мультиграф (ребра без собственной идентичности)
Мультиграф 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 ) с
- В наборе из вершин или узлов ,
- Набор из краев или линий ,
- , назначая каждому ребру его исходный узел,
- , назначая каждому ребру его целевой узел.
Это понятие можно использовать для моделирования возможных стыковок рейсов, предлагаемых авиакомпанией. В этом случае мультиграф будет ориентированным графом с парами направленных параллельных ребер, соединяющих города, чтобы показать, что можно летать как в эти места, так и из них.
В теории категорий небольшая категория может быть определена как мультидиграф (с ребрами, имеющими собственную идентичность), снабженный законом ассоциативной композиции и выделенной петлей в каждой вершине, служащей левой и правой идентичностью для композиции. По этой причине в теории категорий термин граф обычно означает «мультидиграф», а лежащий в основе мультиграф категории называется базовым орграфом .
Маркировка
Мультиграфы и мультидиграфы также поддерживают идею разметки графов аналогичным образом. Однако в данном случае терминологического единства нет.
Определения меченых мультиграфов и меченые multidigraphs похожи, и мы определяем только последний из них здесь.
Определение 1. Помеченный мультиграф - это помеченный граф с помеченными дугами.
Формально: помеченный мультиграф G - это мультиграф с помеченными вершинами и дугами. Формально это восьмерка, где
- V - множество вершин, а 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" . Словарь алгоритмов и структур данных .