В математике , а точнее в теории графов , мультиграф - это граф, которому разрешено иметь несколько ребер (также называемых параллельными ребрами [1] ), то есть ребер с одинаковыми конечными узлами . Таким образом, две вершины могут быть соединены более чем одним ребром.
Есть два разных понятия множественных ребер:
- Кромки без собственной идентичности : идентичность кромки определяется исключительно двумя узлами, которые она соединяет. В этом случае термин «несколько ребер» означает, что одно и то же ребро может встречаться несколько раз между этими двумя узлами.
- Края с собственной идентичностью : Края - это примитивные объекты, как и узлы. Когда несколько ребер соединяют два узла, это разные ребра.
Мультиграф отличается от гиперграфа , который представляет собой граф, в котором ребро может соединять любое количество узлов, а не только два.
Для некоторых авторов термины псевдограф и мультиграф являются синонимами. Для других псевдограф - это мультиграф, которому разрешено иметь петли .
Ненаправленный мультиграф (ребра без собственной идентичности) [ править ]
Мультиграф G - это упорядоченная пара G : = ( V , E ) с
- В наборе из вершин или узлов ,
- E мультимножеством неупорядоченных пар вершин, которые называются ребрами или линиями .
Ненаправленный мультиграф (ребра с собственной идентичностью) [ править ]
Мультиграф G - это упорядоченная тройка G : = ( V , E , r ) с
- В наборе из вершин или узлов ,
- Е набор из краев или линий ,
- r : E → {{ x , y }: x , y ∈ V }, присваивая каждому ребру неупорядоченную пару узлов конечных точек.
Некоторые авторы позволяют мультиграфам иметь петли , то есть ребро, которое соединяет вершину с самим собой [2], в то время как другие называют эти псевдографы , оставляя термин мультиграф для случая без петель. [3]
Направленный мультиграф (ребра без собственной идентичности) [ править ]
Multidigraph представляет собой ориентированный граф , который разрешено иметь несколько дуг, то есть, дуг с одинаковыми исходными и целевыми узлами. Мультииграф G - это упорядоченная пара G : = ( V , A ) с
- V набор вершин или узлов ,
- Мультимножеством упорядоченных пар вершин называемых ориентированных ребер , дуг или стрелки .
Смешанный мультиграф G : = ( V , Е , ) может быть определен таким же образом , как смешанный граф .
Направленный мультиграф (ребра с собственной идентичностью) [ править ]
Мультииграф или колчан G - это упорядоченный набор из четырех G : = ( V , A , s , t ) с
- В наборе из вершин или узлов ,
- Набор из краев или линий ,
- , назначая каждому ребру его исходный узел,
- , назначая каждому ребру его целевой узел.
Это понятие можно использовать для моделирования возможных стыковок рейсов, предлагаемых авиакомпанией. В этом случае мультиграф будет ориентированным графом с парами направленных параллельных ребер, соединяющих города, чтобы показать, что можно летать как в эти места, так и из них.
В теории категорий небольшую категорию можно определить как мультидиграф (с ребрами, имеющими собственную идентичность), снабженный законом ассоциативной композиции и выделенной петлей в каждой вершине, служащей левой и правой идентичностью для композиции. По этой причине в теории категорий термин граф обычно означает «мультидиграф», а лежащий в основе мультидиграф категории называется ее базовым орграфом .
Маркировка [ править ]
Мультиграфы и мультидиграфы также поддерживают идею разметки графов аналогичным образом. Однако терминологического единства в данном случае нет.
Определения меченых мультиграфов и меченые multidigraphs похожи, и мы определяем только последний из них здесь.
Определение 1. Помеченный мультииграф - это помеченный граф с помеченными дугами.
Формально: помеченный мультиграф G - это мультиграф с помеченными вершинами и дугами. Формально это восьмерка, где
- V - множество вершин, а A - множество дуг.
- и являются конечными алфавитами доступных меток вершин и дуг,
- и две карты, указывающие исходную и целевую вершины дуги,
- и две карты, описывающие разметку вершин и дуг.
Определение 2 : Помеченный мультиграф - это помеченный граф с несколькими помеченными дугами, т. Е. Дуги с одинаковыми конечными вершинами и одинаковой меткой дуги (обратите внимание, что это понятие помеченного графа отличается от понятия, заданного разметкой графа статьи ).
См. Также [ править ]
- Многомерная сеть
- Глоссарий терминов теории графов
- Теория графов
Заметки [ править ]
- ^ Например, см. Балакришнан 1997, стр. 1 или Chartrand and Zhang 2012, стр. 26.
- ^ Например, см. Bollobás 2002, p. 7 или Diestel 2010, стр. 28.
- ^ Например, см. Wilson 2002, p. 6 или Chartrand and Zhang 2012, стр. 26-27.
Ссылки [ править ]
- Балакришнан, ВК (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" . Словарь алгоритмов и структур данных .
Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. "Multigraph" . Словарь алгоритмов и структур данных .