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

Published: 26 January 2021
on channel: Vital Sine
34,798
440

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:
https://www.geeksforgeeks.org/mathema...
http://mathonline.wikidot.com/walks-t...
https://mathworld.wolfram.com/Walk.html

Recommended Books:
******************************* Hypergraph Theory *******************************
"Hypergraph Theory: An Introduction": https://amzn.to/48WKqfy

******************************* Graph Theory *******************************
"Introduction to Graph Theory (Trudeau)": https://amzn.to/48ZWhtj

"Graph Theory (Diestel)": https://amzn.to/4aYCSdW

******************************* Misc. Undergraduate Mathematics *******************************
Discrete Mathematics with Applications (Epp): https://amzn.to/4aWC1dM

A Book of Abstract Algebra (Pinter): https://amzn.to/3S2QmfV

Language, Proof and Logic: https://amzn.to/47EIZkE

Linear Algebra and Its Applications: https://amzn.to/48QsoMt

All the Math You Missed: https://amzn.to/3u5dORP

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


Watch video Guide to Walks, Trails, Paths, Circuits, and Cycles! [Graph Theory Tutorial] online without registration, duration hours minute second in high quality. This video was added by user Vital Sine 26 January 2021, don't forget to share it with your friends and acquaintances, it has been viewed on our site 34,798 once and liked it 440 people.