45:
1356:
568:
can be defined as a multidigraph (with edges having their own identity) equipped with an associative composition law and a distinguished self-loop at each vertex serving as the left and right identity for composition. For this reason, in category theory the term
721:
994:
948:
1360:
94:: The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes.
892:
857:
539:
505:
820:
793:
764:
744:
1011:
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
1393:
624:
1371:
545:
This notion might be used to model the possible flight connections offered by an airline. In this case the multigraph would be a
953:
907:
1165:
1146:
17:
1338:
1319:
1225:
1203:
1184:
1120:
1094:
1305:
100:: Edges are primitive entities just like nodes. When multiple edges connect two nodes, these are different edges.
48:
A multigraph with multiple edges (red) and several loops (blue). Not all authors allow multigraphs to have loops.
1309:
1029:
862:
827:
1112:
65:
77:
1134:
31:
573:
is standardly taken to mean "multidigraph", and the underlying multidigraph of a category is called its
512:
478:
1024:
798:
771:
549:
with pairs of directed parallel edges connecting cities to show that it is possible to fly both
565:
81:
1289:
1261:
407:
205:
8:
295:
124:
1265:
1293:
1251:
1104:
749:
729:
1334:
1315:
1297:
1277:
1221:
1199:
1180:
1161:
1142:
1116:
1090:
462:
444:
249:
231:
162:
1366:
1269:
108:, which is a graph in which an edge can connect any number of nodes, not just two.
1285:
561:
1130:
1012:
586:
546:
315:
69:
1387:
1281:
1235:
1004:
607:
298:, that is, an edge that connects a vertex to itself, while others call these
38:
1242:; Luczak, Tomasz; Pittel, Boris (1993). "The birth of the giant component".
1053:
For example, see
Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.
1273:
1239:
1213:
1034:
589:, in a similar way. However there is no unity in terminology in this case.
140:
57:
1071:
For example, see Wilson 2002, p. 6 or
Chartrand and Zhang 2012, pp. 26-27.
1160:. Graduate Texts in Mathematics. Vol. 173 (4th ed.). Springer.
395:
53:
716:{\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}
105:
1256:
130:
322:
i.e., arcs with the same source and target nodes. A multidigraph
44:
30:
This article is about the mathematical concept. For other uses, see
305:
180:
195:
401:
996:
are two maps describing the labeling of the vertices and arcs.
290:}, assigning to each edge an unordered pair of endpoint nodes.
414:
1062:
For example, see Bollobás 2002, p. 7 or
Diestel 2010, p. 28.
822:
are finite alphabets of the available vertex and arc labels,
302:, reserving the term multigraph for the case with no loops.
84:. Thus two vertices may be connected by more than one edge.
1376:
585:
Multigraphs and multidigraphs also support the notion of
989:{\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}
943:{\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}
617:
Formally: A labeled multidigraph G is a multigraph with
1234:
600:
are similar, and we define only the latter ones here.
37:"Pseudograph" redirects here. Not to be confused with
956:
910:
865:
830:
801:
774:
752:
732:
627:
515:
481:
988:
942:
886:
851:
814:
787:
758:
738:
715:
533:
499:
131:Undirected multigraph (edges without own identity)
1385:
306:Directed multigraph (edges without own identity)
87:There are 2 distinct notions of multiple edges:
359:a multiset of ordered pairs of vertices called
196:Undirected multigraph (edges with own identity)
1311:Graphs, Colourings and the Four-Colour Theorem
1194:Gross, Jonathan L.; Yellen, Jay, eds. (2003).
1129:
27:Graph with multiple edges between two vertices
1331:CRC Standard Mathematical Tables and Formulae
621:vertices and arcs. Formally it is an 8-tuple
402:Directed multigraph (edges with own identity)
1372:Dictionary of Algorithms and Data Structures
1084:
1193:
1174:
1328:
123:is a multigraph that is permitted to have
1364:
1333:(31st ed.). Chapman & Hall/CRC.
1255:
541:, assigning to each edge its target node.
507:, assigning to each edge its source node,
1394:Extensions and generalizations of graphs
1175:Gross, Jonathan L.; Yellen, Jay (1998).
1103:
887:{\displaystyle t\colon A\rightarrow \ V}
852:{\displaystyle s\colon A\rightarrow \ V}
43:
1155:
394:) may be defined in the same way as a
294:Some authors allow multigraphs to have
183:of unordered pairs of vertices, called
14:
1386:
1304:
1212:
24:
977:
931:
803:
776:
651:
638:
25:
1405:
1348:
1177:Graph Theory and Its Applications
104:A multigraph is different from a
1359: This article incorporates
1354:
1244:Random Structures and Algorithms
534:{\displaystyle t:A\rightarrow V}
500:{\displaystyle s:A\rightarrow V}
1139:A First Course in Graph Theory
1065:
1056:
1047:
1030:Glossary of graph theory terms
1003:: A labeled multidigraph is a
973:
927:
875:
840:
710:
634:
606:: A labeled multidigraph is a
525:
491:
119:are synonymous. For others, a
13:
1:
1113:Graduate Texts in Mathematics
1078:
1085:Balakrishnan, V. K. (1997).
894:are two maps indicating the
111:For some authors, the terms
7:
1329:Zwillinger, Daniel (2002).
1115:. Vol. 184. Springer.
1018:
815:{\displaystyle \Sigma _{A}}
788:{\displaystyle \Sigma _{V}}
580:
318:which is permitted to have
68:which is permitted to have
56:, and more specifically in
32:Multigraph (disambiguation)
10:
1410:
1156:Diestel, Reinhard (2010).
92:Edges without own identity
36:
29:
746:is a set of vertices and
1196:Handbook of Graph Theory
1040:
1025:Multidimensional network
1314:. Oxford Science Publ.
98:Edges with own identity
1361:public domain material
1274:10.1002/rsa.3240040303
990:
944:
888:
853:
816:
789:
760:
740:
717:
535:
501:
49:
991:
945:
889:
854:
817:
790:
761:
741:
718:
598:labeled multidigraphs
536:
502:
47:
954:
908:
863:
828:
799:
772:
750:
730:
625:
513:
479:
1266:1993math.....10236J
1109:Modern Graph Theory
594:labeled multigraphs
592:The definitions of
326:is an ordered pair
80:that have the same
18:Directed multigraph
1220:. Addison Wesley.
986:
940:
884:
849:
812:
785:
756:
736:
713:
575:underlying digraph
531:
497:
406:A multidigraph or
50:
1306:Wilson, Robert A.
1167:978-3-642-14278-9
1148:978-0-486-48368-9
902:vertex of an arc,
880:
845:
766:is a set of arcs.
759:{\displaystyle A}
739:{\displaystyle V}
557:these locations.
16:(Redirected from
1401:
1380:
1358:
1357:
1344:
1325:
1301:
1259:
1240:Knuth, Donald E.
1231:
1209:
1190:
1171:
1152:
1126:
1100:
1072:
1069:
1063:
1060:
1054:
1051:
995:
993:
992:
987:
985:
984:
966:
965:
949:
947:
946:
941:
939:
938:
920:
919:
893:
891:
890:
885:
878:
858:
856:
855:
850:
843:
821:
819:
818:
813:
811:
810:
794:
792:
791:
786:
784:
783:
765:
763:
762:
757:
745:
743:
742:
737:
722:
720:
719:
714:
709:
708:
696:
695:
659:
658:
646:
645:
540:
538:
537:
532:
506:
504:
503:
498:
377:mixed multigraph
21:
1409:
1408:
1404:
1403:
1402:
1400:
1399:
1398:
1384:
1383:
1365:Paul E. Black.
1355:
1351:
1341:
1322:
1228:
1206:
1187:
1168:
1149:
1131:Chartrand, Gary
1123:
1097:
1089:. McGraw-Hill.
1081:
1076:
1075:
1070:
1066:
1061:
1057:
1052:
1048:
1043:
1021:
980:
976:
961:
957:
955:
952:
951:
934:
930:
915:
911:
909:
906:
905:
864:
861:
860:
829:
826:
825:
806:
802:
800:
797:
796:
779:
775:
773:
770:
769:
751:
748:
747:
731:
728:
727:
704:
700:
691:
687:
654:
650:
641:
637:
626:
623:
622:
583:
562:category theory
514:
511:
510:
480:
477:
476:
404:
308:
198:
133:
42:
35:
28:
23:
22:
15:
12:
11:
5:
1407:
1397:
1396:
1382:
1381:
1350:
1349:External links
1347:
1346:
1345:
1339:
1326:
1320:
1302:
1250:(3): 231–358.
1236:Janson, Svante
1232:
1226:
1210:
1204:
1191:
1185:
1172:
1166:
1153:
1147:
1127:
1121:
1105:Bollobás, Béla
1101:
1095:
1080:
1077:
1074:
1073:
1064:
1055:
1045:
1044:
1042:
1039:
1038:
1037:
1032:
1027:
1020:
1017:
1013:graph labeling
1007:with multiple
998:
997:
983:
979:
975:
972:
969:
964:
960:
937:
933:
929:
926:
923:
918:
914:
903:
883:
877:
874:
871:
868:
848:
842:
839:
836:
833:
823:
809:
805:
782:
778:
767:
755:
735:
712:
707:
703:
699:
694:
690:
686:
683:
680:
677:
674:
671:
668:
665:
662:
657:
653:
649:
644:
640:
636:
633:
630:
587:graph labeling
582:
579:
547:directed graph
543:
542:
530:
527:
524:
521:
518:
508:
496:
493:
490:
487:
484:
474:
456:
413:is an ordered
403:
400:
373:
372:
361:directed edges
354:
320:multiple arcs,
316:directed graph
307:
304:
292:
291:
261:
243:
204:is an ordered
197:
194:
193:
192:
174:
132:
129:
102:
101:
95:
74:parallel edges
70:multiple edges
26:
9:
6:
4:
3:
2:
1406:
1395:
1392:
1391:
1389:
1378:
1374:
1373:
1368:
1362:
1353:
1352:
1342:
1340:1-58488-291-3
1336:
1332:
1327:
1323:
1321:0-19-851062-4
1317:
1313:
1312:
1307:
1303:
1299:
1295:
1291:
1287:
1283:
1279:
1275:
1271:
1267:
1263:
1258:
1253:
1249:
1245:
1241:
1237:
1233:
1229:
1227:0-201-41033-8
1223:
1219:
1215:
1214:Harary, Frank
1211:
1207:
1205:1-58488-090-2
1201:
1197:
1192:
1188:
1186:0-8493-3982-0
1182:
1179:. CRC Press.
1178:
1173:
1169:
1163:
1159:
1154:
1150:
1144:
1140:
1136:
1132:
1128:
1124:
1122:0-387-98488-7
1118:
1114:
1110:
1106:
1102:
1098:
1096:0-07-005489-4
1092:
1088:
1083:
1082:
1068:
1059:
1050:
1046:
1036:
1033:
1031:
1028:
1026:
1023:
1022:
1016:
1014:
1010:
1006:
1005:labeled graph
1002:
981:
970:
967:
962:
958:
935:
924:
921:
916:
912:
904:
901:
897:
881:
872:
869:
866:
846:
837:
834:
831:
824:
807:
780:
768:
753:
733:
726:
725:
724:
705:
701:
697:
692:
688:
684:
681:
678:
675:
672:
669:
666:
663:
660:
655:
647:
642:
631:
628:
620:
615:
613:
609:
608:labeled graph
605:
601:
599:
595:
590:
588:
578:
576:
572:
567:
563:
558:
556:
552:
548:
528:
522:
519:
516:
509:
494:
488:
485:
482:
475:
472:
468:
464:
460:
457:
454:
450:
446:
442:
439:
438:
437:
435:
431:
427:
423:
419:
416:
412:
409:
399:
397:
393:
389:
385:
381:
378:
370:
366:
362:
358:
355:
352:
348:
344:
341:
340:
339:
337:
333:
329:
325:
321:
317:
313:
303:
301:
297:
289:
285:
281:
277:
273:
269:
265:
262:
259:
255:
251:
247:
244:
241:
237:
233:
229:
226:
225:
224:
222:
218:
214:
210:
207:
203:
200:A multigraph
190:
186:
182:
178:
175:
172:
168:
164:
160:
157:
156:
155:
153:
149:
145:
142:
138:
135:A multigraph
128:
126:
122:
118:
114:
109:
107:
99:
96:
93:
90:
89:
88:
85:
83:
79:
75:
72:(also called
71:
67:
63:
59:
55:
46:
40:
39:Pseudepigraph
33:
19:
1370:
1367:"Multigraph"
1330:
1310:
1257:math/9310236
1247:
1243:
1218:Graph Theory
1217:
1195:
1176:
1158:Graph Theory
1157:
1138:
1108:
1087:Graph Theory
1086:
1067:
1058:
1049:
1035:Graph theory
1008:
1001:Definition 2
1000:
999:
899:
895:
618:
616:
611:
604:Definition 1
603:
602:
597:
593:
591:
584:
574:
570:
559:
554:
550:
544:
470:
466:
458:
452:
448:
440:
433:
429:
425:
421:
417:
410:
405:
391:
387:
383:
379:
376:
374:
368:
364:
360:
356:
350:
346:
342:
335:
331:
327:
323:
319:
312:multidigraph
311:
309:
300:pseudographs
299:
293:
287:
283:
279:
275:
271:
267:
263:
257:
253:
245:
239:
235:
227:
220:
216:
212:
208:
201:
199:
188:
184:
176:
170:
166:
158:
151:
147:
143:
141:ordered pair
136:
134:
120:
116:
112:
110:
103:
97:
91:
86:
76:), that is,
73:
61:
58:graph theory
51:
1135:Zhang, Ping
396:mixed graph
121:pseudograph
113:pseudograph
54:mathematics
1079:References
420: := (
382: := (
330: := (
211: := (
146: := (
117:multigraph
106:hypergraph
62:multigraph
1298:206454812
1282:1042-9832
1141:. Dover.
978:Σ
974:→
968::
959:ℓ
932:Σ
928:→
922::
913:ℓ
876:→
870::
841:→
835::
804:Σ
777:Σ
702:ℓ
689:ℓ
652:Σ
639:Σ
526:→
492:→
345:a set of
278:} :
82:end nodes
1388:Category
1308:(2002).
1216:(1995).
1137:(2012).
1107:(2002).
1019:See also
581:Labeling
566:category
564:a small
449:vertices
347:vertices
266: :
236:vertices
181:multiset
167:vertices
1290:1220220
1262:Bibcode
1198:. CRC.
1009:labeled
619:labeled
612:labeled
436:) with
415:4-tuple
338:) with
223:) with
154:) with
1337:
1318:
1296:
1288:
1280:
1224:
1202:
1183:
1164:
1145:
1119:
1093:
900:target
896:source
879:
844:
723:where
614:arcs.
408:quiver
369:arrows
206:triple
139:is an
1363:from
1294:S2CID
1252:arXiv
1041:Notes
610:with
571:graph
471:lines
467:edges
453:nodes
351:nodes
314:is a
296:loops
258:lines
254:edges
240:nodes
189:lines
185:edges
171:nodes
125:loops
78:edges
66:graph
64:is a
1377:NIST
1335:ISBN
1316:ISBN
1278:ISSN
1222:ISBN
1200:ISBN
1181:ISBN
1162:ISBN
1143:ISBN
1117:ISBN
1091:ISBN
950:and
898:and
859:and
795:and
596:and
555:from
553:and
365:arcs
270:→ {{
115:and
60:, a
1270:doi
1015:).
560:In
469:or
465:of
463:set
451:or
447:of
445:set
367:or
349:or
256:or
252:of
250:set
238:or
234:of
232:set
187:or
169:or
165:of
163:set
52:In
1390::
1375:.
1369:.
1292:.
1286:MR
1284:.
1276:.
1268:.
1260:.
1246:.
1238:;
1133:;
1111:.
577:.
551:to
461:a
443:a
432:,
428:,
424:,
398:.
390:,
386:,
375:A
363:,
334:,
310:A
286:∈
282:,
248:a
230:a
219:,
215:,
179:a
161:a
150:,
127:.
1379:.
1343:.
1324:.
1300:.
1272::
1264::
1254::
1248:4
1230:.
1208:.
1189:.
1170:.
1151:.
1125:.
1099:.
982:A
971:A
963:A
936:V
925:V
917:V
882:V
873:A
867:t
847:V
838:A
832:s
808:A
781:V
754:A
734:V
711:)
706:A
698:,
693:V
685:,
682:t
679:,
676:s
673:,
670:A
667:,
664:V
661:,
656:A
648:,
643:V
635:(
632:=
629:G
529:V
523:A
520::
517:t
495:V
489:A
486::
483:s
473:,
459:A
455:,
441:V
434:t
430:s
426:A
422:V
418:G
411:G
392:A
388:E
384:V
380:G
371:.
357:A
353:,
343:V
336:A
332:V
328:G
324:G
288:V
284:y
280:x
276:y
274:,
272:x
268:E
264:r
260:,
246:E
242:,
228:V
221:r
217:E
213:V
209:G
202:G
191:.
177:E
173:,
159:V
152:E
148:V
144:G
137:G
41:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
