What is a Walk? | Graph Theory
ฝัง
- เผยแพร่เมื่อ 29 ก.ย. 2018
- What is a walk in the context of graph theory? That is the subject of today's math lesson! A walk in a graph G can be thought of as a way of moving through G, where you start at any vertex in the graph, and then move to other vertices through the edges in the graph. In a walk, you are allowed to traverse the same vertices and edges multiple times.
So, a walk can be described as a sequence of vertices. Let's say we have the graph G and G = ( V, E ) where V = { a, b, c, d, e, f } and E = { ab, ac, de, ef, cd }. Then we could describe a walk in G like this: W = ( c, a, b, a, c, d ). So a walk is a sequence of vertices in a graph, where consecutive vertices are adjacent in that graph. Notice in the walk W, all consecutive vertices are joined by an edge, and we traversed some of the same vertices and edges multiple times.
If a walk starts and ends on the same vertex, it is called a "closed walk", otherwise it is called an "open walk". The vertices and edges encountered during the walk are said to "lie on" the walk. So going back to the walk W = ( c, a, b, a, c, d ), the vertex c lies on W, as does the edge ca. Also, we can call W a c-d walk in G, because it starts at vertex c, ends at d, and is a walk in G.
An alternative way of defining walks, which is often used instead, is for them to be a sequence of alternating vertices and edges. In this way of defining a walk, the walk 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 walk W = ( c, a, b, a, c, d ). If we were to write this walk using this alternative definition, we would write W = ( c, ca, a, ab, b, ba, a, ac, c, cd, d ). This way of defining walks 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
So far I've really been enjoying my *walk* through this graph theory playlist 👍
Graph theory is the most theoretical thing I've ever studied. I'm glad pure mathematics is devoid of theory and definitions.
I'm not sure what you mean by "devoid of theory and definitions" as I find this theoretical math packed with both. But I agree it is a highly unique subject! The proofs of graph theory were often quite different from other proofs I had seen when I started studying.
Thanks so much for all the time you put into these videos, they are most certainly helpful.
thanks for all the videos that are posted on the graph theory, they helped me a lot for my final exam.
Happy to help!
How'd the class go overall, and do you think you'll ever encounter graph theory again in the future?
I'm really appreciated this full content, u explained this VERY WELL, thank you!
Glad to help! Thanks for watching and check out my graph theory playlist for more! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thank you, this makes the topic so much clearer
My pleasure, thanks for watching! Check out my Graph Theory playlist if you're looking for more: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Many lessons still to come!
A super fun ( not really) recommendation: How to create a equation of a parabola using only a focus and a directrix, this would be helpful for me :) Gracías
It sounds super fun to me! With any luck, I can record it tomorrow and it will be out Wednesday. Fingers crossed and thank you for the recommendation!
Here it is!
th-cam.com/video/HdQA84eqnlM/w-d-xo.html
Hehe.
"trivial it may be, it is a walk!" Nice one
my discrete mathematics final is tomorrow, glad I found this series today 🤣
How'd your final go?
Hey Sean, I hope you know you are my discrete math professor.
Glad to help! 😊
Mans accurately describes the wock.
Well explained!
Thank you! Check out my Graph Theory playlist if you're looking for more! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Many more lessons to come!
What is the name of the program that u used in this video?
Hey Sean, Thank you for the videos ~ you are helping me a lot. I have a question / questions:
1) Would you consider a trivial walk: open or close? I feel it should be close
2) Should Paths have a minimum length of 1? I feel yes, else if we allow paths to have length 0 then we would end up repeating vertices, which would go against the definition of path
Please and Thank You!
1) A trivial walk would be closed. By definition, a closed walk has the same starting point as the end point. This is true since the first point will also be the last in a trivial walk.
2) Having the path be length 0 wouldn't necesarilly repeat vertices. It's still just 1 vertex, the starting/ending vertex. However, in a non-simple graph where perhaps there is a loop, an edge that connects a vertex to itself, then a path of (v1, v1) would be invalid since you do repeat a vertex. Either way, a path of length 0 is valid.
if a vertex got a loop, we could say that: W = (V1, V1, V1) thus having a length of 3 riight?
'Walk is a sequence of vertices in a graph where consecutive vertices are adjacent.' - why does it qualify as a walk if V4 and V5 are not connected? Should the word consecutive be used then? Thank you!
Sir in second graph how walk is trivial ? Because first we are going from u yo v and then v to w
He mentioned w = (v) which means that he did not travel from u to v or v to w. That is why it was trivial as that walk has a length of 0.
great video +1, sub
goat
Haha, thank you! If you haven't already checked it out, you may find my graph theory playlist useful: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
thank you !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!