Мультиграф

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

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

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

Маркировка

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

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

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

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

$V$ is a set of vertices and $A$ is a set of arcs.
$\Sigma _{V}$ and $\Sigma _{A}$ are finite alphabets of the available vertex and arc labels,
$s\colon A\rightarrow \ V$ and $t\colon A\rightarrow \ V$ are two maps indicating the source and target vertex of an arc,
$\ell _{V}\colon V\rightarrow \Sigma _{V}$ and $\ell _{A}\colon A\rightarrow \Sigma _{A}$ are two maps describing the labeling of the vertices and arcs.

Definition 2: A labeled multidigraph is a labeled graph with multiple labeled arcs, i.e. arcs with the same end vertices and the same arc label (note that this notion of a labeled graph is different from the notion given by the article graph labeling).

Notes

^ For example, see Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.
^ For example, see Bollobás 2002, p. 7 or Diestel 2010, p. 28.
^ For example, see Wilson 2002, p. 6 or Chartrand and Zhang 2012, pp. 26-27.

References

Balakrishnan, V. K. (1997). Graph Theory. McGraw-Hill. ISBN 0-07-005489-4.
Bollobás, Béla (2002). Modern Graph Theory. Graduate Texts in Mathematics. Vol. 184. Springer. ISBN 0-387-98488-7.
Chartrand, Gary; Zhang, Ping (2012). A First Course in Graph Theory. Dover. ISBN 978-0-486-48368-9.
Diestel, Reinhard (2010). Graph Theory. Graduate Texts in Mathematics. Vol. 173 (4th ed.). Springer. ISBN 978-3-642-14278-9.
Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN 0-8493-3982-0.
Gross, Jonathan L.; Yellen, Jay, eds. (2003). Handbook of Graph Theory. CRC. ISBN 1-58488-090-2.
Harary, Frank (1995). Graph Theory. Addison Wesley. ISBN 0-201-41033-8.
Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris (1993). "The birth of the giant component". Random Structures and Algorithms. 4 (3): 231–358. arXiv:math/9310236. Bibcode:1993math.....10236J. doi:10.1002/rsa.3240040303. ISSN 1042-9832. MR 1220220. S2CID 206454812.
Wilson, Robert A. (2002). Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. ISBN 0-19-851062-4.
Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC. ISBN 1-58488-291-3.

External links

This article incorporates public domain material from Paul E. Black. "Multigraph". Dictionary of Algorithms and Data Structures. NIST.