Guide to Walks, Trails, Paths, Circuits, and Cycles! [Graph Theory Tutorial]

This video explains walks, trails, paths, circuits, and cycles in graph theory.

In graph theory, a walk is defined as a sequence of alternating vertices and edges, like Vertex 1, Edge 1, Vertex 2, Edge 2, etc. Walks are how we traverse a network. In a walk, you are allowed to repeat edges and vertices as many times as you'd like. A trail, on the other hand, is a walk in which you do not repeat edges. And a path is a walk in which you do not repeat edges and you do not repeat vertices (note that the set of paths in a graph is a subset of trails in that graph).

I think it's important to know that some authors do define these terms slightly differently; some refer to what we just called a 'trail' as a 'path' as well, while referring to what we called a 'path' as a 'simple path' instead.

Here are some links for more information:

Recommended Books:
******************************** Hypergraph Theory ********************************

******************************** Graph Theory ********************************

******************************** Misc. Undergraduate Mathematics ********************************

These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.

0:00 - Graph Walks
0:53 - Graph walks as lists
1:35 - Trails
2:50 - Circuits
3:30 - Paths
4:50 - Closed paths = Cycle
5:30 - Summary
6:44 - Real-world Example
7:35 - Traveling Salesman Problem

[VitalSine]

Thank you for watching! Let me know if you have any feedback or questions.

[khaledfada]

on minute 4:39 there is a typo when it says (D, G, E) is a cycle, you should add D after the E.
Thank you.

[VitalSine]

0:00 - Graph Walks
0:53 - Graph walks as lists
1:35 - Trails
2:50 - Circuits
3:30 - Paths
4:50 - Closed paths = Cycle
5:30 - Summary

6:44 - Real-world Example
7:35 - Traveling Salesman Problem

[supraender]

Great video! It was clear and concise. One thing I noted, at 4:25, you highlighted (D, E, G, D) but wrote (D, G, E) on the screen. Thanks for all your hard work!!

[timelygoose]

Thank you sir, such a great concise explanation

[blackoptime]

7:35 little error path abd has weight 5 = 3.5, should be 5+3.5

[iamwatchingthisvid.]

is it possible to skip vertex in a trail? for example G>E>F>D???? anyone please? answer..

[MrChicken_]

how would this be useful for real life other than passing tests? or is it just pointless