Discrete Math II - 10.5.2 Hamilton Paths and Circuits

Summary

In this video, Kimberly Brehm delves into the concepts of Hamilton paths and circuits within graph theory. Hamilton's focus was on visiting every vertex once, contrasting with Euler's emphasis on edges. The video outlines the conditions necessary for identifying Hamilton paths and circuits and discusses various examples to illustrate these principles. A key takeaway is that while there's no definitive method to determine the existence of a Hamilton path or circuit, certain theorems like Dirac's can provide guidance. However, these theorems often only confirm the existence rather than the absence of such paths or circuits, leaving much to exploration and experimentation.

Highlights

• Hamilton focused on vertices, visiting each once. Euler focused on graph edges. 📌
• Hamilton circuits start and end at the same vertex, paths don't. 🚦
• No surefire way to find Hamilton paths or circuits; it's all about practice. 🚧
• Dirac's theorem offers hints but isn’t comprehensive. 🤔
• Trial and error is often the best approach to discover Hamilton paths and circuits. 🎲

Key Takeaways

• Hamilton paths and circuits focus on visiting each vertex once, unlike Euler paths which focus on edges. 🎯
• Hamilton circuits require starting and ending at the same vertex, while paths do not. 🎢
• There's no definitive algorithm for finding Hamilton paths or circuits, leaving much to trial and error. 🔍
• Dirac's theorem provides some guidance but is not foolproof in detecting Hamilton circuits. 📘
• Practicing with different graphs is crucial to understand Hamilton paths and circuits. 📊

Overview

In the world of graph theory, Hamilton paths and circuits present a fascinating puzzle for budding mathematicians. Unlike Euler, who was captivated by traversing each edge of a graph, Hamilton's legacy is rooted in the idea of visiting each vertex precisely once. This video explores the enigmatic realm of Hamiltonian graphs, offering insights into the nuanced conditions that might lead us to uncover these elusive paths and circuits.

Hamiltonian circuits require a journey that both begins and concludes at the same vertex, a round trip of sorts through a graph’s vertices. If this journey doesn’t loop back to the origin, it’s merely a path. However, identifying these requires more than just a keen eye—they demand patience and a willingness to experiment, as there’s no all-encompassing algorithm to detect their presence. The video emphasizes that finding such paths and circuits can often come down to practice and pattern recognition.

While Dirac's theorem can sometimes shine a light on the existence of a Hamiltonian circuit, it is far from a guarantee. Offering mathematical enthusiasts a reason to pause and ponder, Dirac’s theorem provides circumstances under which a circuit definitely exists, but unfortunately, it falls short of telling us when one doesn't. In the absence of universal rules, one must dissect each graph with an exploratory spirit, keeping in mind that the journey of understanding is as significant as the destination.

Chapters

• 00:00 - 03:00: Introduction to Hamilton Paths and Circuits The chapter introduces the concept of Hamilton paths and circuits, focusing on visiting every vertex once, unlike Euler’s focus on edges. It seeks to establish the necessary conditions for identifying Hamilton paths or circuits, starting with distinguishing between the two.
• 03:00 - 06:00: Characteristics of Hamilton Paths and Circuit The chapter discusses the characteristics of Hamilton paths and circuits, explaining that in a Hamilton circuit, you visit each vertex once and return to the starting vertex, while in a Hamilton path, you visit each vertex once but do not return to the starting vertex. The chapter uses the example of the wheel graph W5 to find both a Hamilton path and a Hamilton cycle.
• 06:00 - 09:00: Theorems and Examples The chapter discusses the concept of visiting vertices in a graph. It emphasizes the importance of visiting each vertex exactly once and returning to the starting point. An example is provided where a path travels through vertices in the following order: A -> E -> F -> D -> C -> B -> A.
• 09:00 - 13:00: Problem-Solving with Hamilton Paths and Circuits The chapter titled 'Problem-Solving with Hamilton Paths and Circuits' explores the concept of Hamilton paths and cycles in graph theory. It explains the difference between a Hamilton cycle and a Hamilton path through examples. For instance, a cycle might be presented as d, c, b, a, marking a return to the starting point, while a path could be a, e, f, d, c, b, showing that it doesn't necessarily conclude at the origin. The chapter also touches upon the lack of algorithms that can definitively determine the existence of such paths or circuits, highlighting the inherent challenge in finding them in mathematical problems.

Discrete Math II - 10.5.2 Hamilton Paths and Circuits Transcription

• 00:00 - 00:30 in this video we're going to take a look at hamilton paths and circuits hamilton was more concerned about being able to visit every vertex once and only once as opposed to euler who was more concerned about the edges of a graph just as we did with euler paths and circuits we want to find necessary conditions for finding either a hamilton path or a hamilton circuit so first of all what's the difference between the two obviously if we're dealing with a hamilton circuit we're going to start at
• 00:30 - 01:00 one vertex we're going to travel to visit each other vertex only once and then travel back to our beginning vertex so even though we say that it uses each vertex once and only once if we're talking about a circuit we will begin and end at the same vertex for a path we don't begin and end at the same vertex but we still visit every vertex so for instance see if we can find a hamilton path and a hamilton cycle for w5 so the wheel graph
• 01:00 - 01:30 if each exists so if i start say at a i want to visit every vertex once and only once and end up back at a so let's say i traveled to e then to f then to d then to c then to b then to a so i went to a e f
• 01:30 - 02:00 d c b a that is a hamilton cycle so what's a hamilton path a e f d c b so i just don't finish and go back to a now it would be great if there was some algorithm that told us exactly whether or not there was a hamilton path or circuit or how to find it but unfortunately that does not exist for hamilton paths or circuits so all we can do is
• 02:00 - 02:30 take a look at what we know is true and then basically just give it a shot so here's what we know about hamilton paths and circuits so if g contains a hamilton circuit then g also contains a hamilton path by simply taking away that last edge which we just talked about on our last example but of course the converse is not necessarily true now again there's no form for us to know when there is a
• 02:30 - 03:00 hamilton circuit but we do have a few hints that will help us so if g has a hamilton circuit then each vertex has degree of at least two so right away if we look at a graph and we have a vertex of degree one it's not going to have a circuit now it could have a path but it's not going to have a circuit because again we would have to end up beginning and ending back at the same vertex the next one if
• 03:00 - 03:30 a is some vertex in our graph and the degree of a is 2 then the two edges that are incident with the vertex must appear in the hamilton circuit so again if i've got this is an example from your textbook that had one that looked like this and said hey do you have a hamilton circuit for this graph well this has a degree two and a degree two and degree two in degree two which means i have to
• 03:30 - 04:00 use these two edges these two edges these two edges these two edges which means guess what's going to happen at this vertex we're going to go through it more than just once so that one is not going to have a hamilton circuit the third one if a is some vertex in our graph and the degree of a is greater than 2 then as we start to build our hamilton cycle once
• 04:00 - 04:30 we pass through the vertex we have to get rid of any unused edges so again looking back at this particular example if i start here or even if i start here and i go through once i go through here then i would have to get rid of this and this edge so we have to get rid of edges that are connected to that vertex and again that's why we can't have a
• 04:30 - 05:00 hamilton cycle because i can't end up back over where i started your textbook does have two theorems derox theorem and or theorem that do give you some guidance as to when a hamiltonian circuit would exist for instance derox's theorem says that if you have a simple graph with n vertices where n is greater than or equal to 3 three if every vertex is at least n divided by two
• 05:00 - 05:30 then there is a hamilton circuit so for instance there are six vertices here and what dirac's theorem says is if each the degree of each vertex is at least six divided by two which is three then you're going to have a hamilton circuit however what it doesn't say is what if you have say something of degree two like a or b or e or f it doesn't give you any
• 05:30 - 06:00 guidance there so again for instance here n is five so five divided by 2 is 2.5 well this one has a degree of 2. so does that mean there's no hamilton circuit no it doesn't so those theorems aren't super helpful except that they would tell you for certain when there is one but it won't tell you when there is not one so we're just going to wing it and practice on our own and determine if
• 06:00 - 06:30 each graph has a hamilton path or circuit so again when we're doing this we're trying to get to each vertex we don't care about edges we only want to be worried about the vertices so let's say i started here at a well to go from a let's say i go down to b and then over to c and remember i'm trying to find a circuit where i end up back over at a so i can get over to d
• 06:30 - 07:00 but here's the problem this is called a cut edge because essentially once i've traversed over that i can't use that again so i'm for sure not going to be able to find a circuit because whether i go to e next and f or f than e there's no way for me to get to either of those back to a so while there is a path for this example which gets to each vertex but not back to the beginning so it is not a circuit
• 07:00 - 07:30 for our second one again um dirac wasn't very helpful in determining whether or not there is going to be a hamilton circuit but let's give it a shot on our own so if i start at a i can travel to b i can travel to c i can travel to d i can travel to e and i can travel back to a so this one does in fact have a circuit but again there's no theorem that's going to tell us for sure whether there
• 07:30 - 08:00 is or is not a circuit or path for each of these examples coming up next we're going to take a look at some shortest path problems