Parallel Edges in Multigraphs and Digraphs | Graph Theory, Multiple Edges, Multisets

What are parallel edges, also called multiple edges or multi-edges, in graph theory? We'll introduce parallel edges in the context of undirected multi-graphs and in directed graphs in today's video graph theory lesson!


Lesson on directed graphs:    • Intro to Directed Graphs | Digraph Th...  


Typically, parallel edges are defined to be edges joining the same pair of vertices. As you can imagine, our typical way of defining a graph and its edges cannot handle this situation. We typically think of the edge set of a graph as a set of edges, and edges are two-element subsets of the vertex set. Since the edge set is just a normal set, and does not recognize repetition of elements, we need to use a different object! We introduce multisets in this lesson. A graph whose edge set is a multiset is often called a multigraph, and such a graph can have have parallel edges, which again, are edges joining the same pair of vertices.



Directed graphs are a little bit different because we can have two directed edges which have the same end vertices but are distinct because they have opposite directions. We will also discus this situation, and directed multigraphs.



Always remember to be aware of the definitions of the terms being used in any paper or textbook you are reading! Some of these graph theory terms, like multigraphs and pseudographs, are often used to mean slightly different things in different publications.







I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud:   / benwatts-3  
********************************************************************


+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic