What is a Circuit? | Graph Theory

Описание: Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out my math fashion brand! https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535

What is a circuit in graph theory? That is the subject of today's math lesson! Remember that a trail is a sequence of vertices in a graph such that consecutive vertices are adjacent in that graph, and no edge is traversed more than once, which means if the vertex b follows a in some part of our sequence, then b cannot follow a again in the sequence, nor can a follow b, because that would mean the edge ab was traversed more than once. So, knowing what a trail is, a circuit is just a closed trail of length 3 or greater, and remember the length of a trail is the number of edges traversed during the trail. Thus, the length of a trail is one less than the number of vertices encountered in the trail. Also, we say a trail is closed when its end vertices are the same. So if a trail starts and ends at the same vertex, and has length 3 or greater, then it is a circuit.

Let's look at an example of a circuit. Let G = (V, E) be a graph where V = {a, b, c, d, e, f, g} and E = {ab, ae, bc, bf, de, ga, gf, ec}. Here is an example of a circuit in G,

C = (a, e, c, b, a).

Notice that C is a sequence of vertices in G, where consecutive vertices are adjacent, and no edge is traversed more than once. Thus, C is a trail. Also, C has length 4 and is closed, so it is also a circuit.

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu