Мультиграф - Multigraph

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

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

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

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

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

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

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

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

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

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

Мультиграф грамм заказанный тройной грамм := (V, E, р) с

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

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

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

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

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

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

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

Мультидиграф или колчан грамм заказанный 4-кратный грамм := (V, А, s, т) с

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

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

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

Маркировка

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

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

Определение 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, с. 1 или Chartrand and Zhang 2012, стр. 26.
^ Например, см. Bollobás 2002, p. 7 или Diestel 2010, стр. 28.
^ Например, см. Wilson 2002, p. 6 или Chartrand and Zhang 2012, стр. 26-27.

внешняя ссылка

Эта статья включает материалы общественного достояния отNIST документ:Блэк, Пол Э. «Мультиграф». Словарь алгоритмов и структур данных.

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

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

[3] Например, см. Wilson 2002, p. 6 или Chartrand and Zhang 2012, стр. 26-27.

[1]

[2]

[3]