Скачать с ютуб What is a Path? | Graph Theory в хорошем качестве

What is a Path? | Graph Theory

What is a path in the context of graph theory? We go over that in today's math lesson! We have discussed walks, trails, and even circuits, now it is about time we get to paths! Recall that a walk is a sequence of vertices in a graph, such that consecutive vertices are adjacent. A path is the same sort of thing but with two additional restrictions. Firstly, no edge can be traversed more than once. Secondly, no vertex can be traversed more than once. And, to make things simpler, you can actually just think of this as one restriction. The one restriction is that you cannot traverse any vertex more than once. This restriction forces you to also not traverse any edge more than once, so it is sufficient all on its own. Thus, a path is a sequence of vertices in a graph, where consecutive vertices in the sequence are adjacent in the graph, and no vertex appears more than once in the sequence. Let's look at an example. Say we have the graph G = (V, E) where V = {a, b, c, d, e, f, g} and E = {ac, af, ag, be, bg, ce, cd, dg, ef}. Then, here is an example of a walk in G: W = (a, c, e, f, a, g, b, a, c). This is a walk, but it is not a path because some vertices and some edges are traversed multiple times. Here is an example of a trail in G: T = (a, c, e, b, g, a, f). This is a trail, since no edge is traversed more than once, but it is not a path because a vertex is traversed more than once. Finally, we see a path: P = (a, f, e, c, d). This is a path because it is a sequence of vertices in G where consecutive vertices are adjacent, and no vertex appears more than once. You can think of paths as being how we move from one place to another. If we want to go from our home to the grocery store, we don't drive halfway to the store, back through our town via some other road, then go to the store, we just go to the store. We don't travel a road or a town multiple times on our way to the store unless we take a wrong turn. So, we are trying to travel in a way analogous to paths. An alternative way of defining paths, which is often used instead, is for them to be a sequence of alternating vertices and edges. In this way of defining a path, the path starts and ends with a vertex, but after a vertex you list the edge traveled, then the vertex you are on, then the edge traveled, and so on up until the final vertex you stop at. So remember our path P = (a, f, e, c, d). If we were to write this path using this alternative definition, we would write P = (a, af, f, fe, e, ec, c, cd, d). This way of defining paths lets the edges traversed be much more explicit, since they are listed out right in the sequence instead of being implied by the vertices traveled. This definition is sometimes preferred, and is very common. 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   Music Channel:    / seanemusic