Hello, everyone, my name is William. Today we're going to talk about oil arian paths and circuits. From a computer science perspective, we're going to start with discussing what Euler paths and circuits are, how to determine their existence, how to find them. And lastly, we're going to look at some code to wrap things up. Let's begin with what an oil arian path is. an Euler path, also called an oil arian Trail is a path of edges in a graph that visits every edge exactly once.

Suppose we have the undirected graph below, and we want to find an Euler path first after every graph has an Euler in path this one does, but even still, we need to be careful about which node we start our path at Suppose we begin the path at the middle rate node and decide to follow the path left Down, up up again and finally left this completes the oil arian path. However, suppose we start at the top node, what happens if we decide to find a path from this node. If we take the edge going down, you'll notice that we are now stuck. We cannot go anywhere else from this node since there are no edges left to follow. More importantly, the issue is that we have unvisited edges that we still have not used or traversed. So we'll see how to resolve or rather avoid this issue altogether later so that we always find an oil arian path when we know one exists.

Moving on let's talk about oil arian circuits, also called oil arian cycles and oil arian circuit isn't oil and gas. which starts and ends on the same vertex. So similar to Euler and paths, not every graph has an oil arian circuit, but the following graph does. If you know your graph has an oil arian circuit, then you can begin the circuit at any note. I'm going to begin the circuit on the orange note and also ended on the orange note. And that's the full circuit if your graph does not contain or Larian circuit, you may not be able to return to the start node or you will not be able to visit all the edges of the graph.

For example, let's start another circuit starting from the same node on this slightly modified graph. So by randomly selecting edges to traverse, we weren't able to make it back to the starting node. Furthermore, we also have unvisited edges, so that's double bad. Luckily for us, we don't have to guess whether or not a graph contains an Euler path or in or their union circuit, we can inspect the graph we're dealing with by counting the in and out degrees of each node to determine whether or not the graph meets one of the conditions. In this table. There are four flavors of or Larian paths and circuits that we care about.

And those are whether the graph is directed or undirected and whether or not we want to find an Euler in path or an or Larian circuit. All of these variants talk about no degrees, so I won't have a quick look at that before coming back to this table. The degree of a node means different things depending on whether the graph we're dealing with is directed Or undirected in an undirected graph, the node degree is simply how many edges are attached to a particular node. The blue node in this picture has three edges attached to it. So it's degrees three. In a directed graph, there are two forms of no degrees there are in degrees and out degrees because the edges are directed.

The End degree is the number of incoming edges to a node and the out degree of a node is the number of outgoing edges from that node. So in the example on the right, the in degree of the notice to while the out degree is one pretty simple. Coming back to the table, you should be able to understand the constraints required for each variant of the oil arian path and oil arian circuit problem. However, let's go over them one by one. Anyways, the simplest case is when we have an undirected graph and we want to find an Euler in circuit. The requirement for this is that every node in the graph has an E degree the oil area and path the problem on an undirected graph is very similar except that in addition that every vertex has an even degree, you can also have exactly two vertices which have an odd degree.

Those two vertices, if they exist would be the start and end nodes of the oil arian path is a directed graph, you can have an Euler circuit if every vertex has an equal in and out degree, this is the counterpart to the undirected graph version. The last variant is finding Euler path on a directed graph for there to exist an over there and path on a directed graph. at most one vertex has an out degree minus an N degree which is equal to one and at most one vertex as an end degree minus out degree equal to one and all other vertices have equal internet degrees. So it's now Quiz time, and I'm going to make sure you've been paying attention I'm going to present to you various graphs and you need to determine whether the following graph has an Euler path in order Larian circuit or both.

So we'll start with undirected graphs and then later move on to directed graphs. Please feel free to pause the video to think things over. So this graph has no or Larian path or circuit you can tell because there are too many nodes with an odd degree. How about this graph? Again, feel free to pause the video. This graph has an Euler path and the green nodes represent the valid Start and End notes for the oil area and path.

What about this graph? This graph has both in oil arian path and an oil arian circuit as a side question, True or false? If a graph has an oil arian circuit, it also has an oil arian path, like give you a moment to think about it. The answer is true. Any circuit is in a way Larian path. Here's another one.

Are there any paths or circuits in this graph? This one is a bit of a trick question, but there are no or they're in paths or circuits here. And the additional requirement I have not yet mentioned is that when finding paths and circuits is that all vertices with nonzero degree need to belong to a single connected component. And here we have two connected components. So we cannot have an Euler path or circuit. Now let's have a look at an example with a directed graph.

Does the following graph have any or they're in paths or circuits? I'll give you A moment to think about it. Yes, this graph has both an Euler path and an Euler in circuit because all in and out degrees are equal. What about this graph? This graph has no oil arian paths or circuits. The red nodes either have too many incoming or outgoing edges for an oil arian path or circuit to exist.

What about this graph? I'll give you a bit more time because there are a lot of edges. This graph only has an Euler path, but no Euler circuit. It also has a unique start and end node for the path. Note that the singleton node has no incoming or outgoing edges so it doesn't impact whether or We have an oil arian path. Okay, that's it for this video on the existence of oil arian paths and circuits for directed and undirected graphs.

I hope that made sense. Please give this video a thumbs up if you learn something and also stick around for the next video where things get even more interesting and we have a look at an algorithm to actually find these