Underlying Graphs of Digraphs | Directed Graphs, Graph Theory
Vložit
- čas přidán 15. 02. 2020
- What are underlying graphs of directed graphs in graph theory? This is a sort of undirected graph that "underlies" or "lies under" a directed graph. But how is it actually defined? We'll go over that in today's video graph theory lesson!
A simple way to define the underlying graph of a directed graph is that it is the directed graph, but with all edge directions removed, making it an undirected graph. But there is some potential complication here, what if there are two vertices, u and v, in the directed graph, that are joined by two arcs (u, v) and (v, u)? Then, by the aforementioned casual definition, the underlying graph of this directed graph would have to be a multigraph, with two identical edges joining u and v. These are called parallel edges and you can learn more about them here: • Parallel Edges in Mult...
The more common definition, in my experience, says that if D = (V, A) is a directed graph, then the underlying graph of D is G = (V, E) where uv is an edge of G (as in, uv is an element of E), only if (u, v) is an arc of D or (v, u) is an arc of D. Thus, by this definition, if (u, v), or (v, u), or BOTH (u, v) AND (v, u) are arcs of D, under all of these cases only a single edge is produced in the underlying graph.
If the underlying graph of a directed graph is connected, we say the directed graph is weakly connected. The nice thing about this term is that it doesn't matter what definition of underlying graph we use - both definitions will either produce a connected graph or a disconnected graph, but they will not oppose each other.
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+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
Underlying graphs? More like "Amazing lectures; thanks!"
Thanks for ur Vedio! The definition and examples are simple, but make me understand!
Great!
Thanks for the video ! What should we do when it is a self loop ?
remove the loop