Vídeo 25- Grafos eulerianos e hamiltonianos. T. 4 cores

Introduction to Eulerian Paths and Circuits

Overview of the Problem

• The discussion begins with a classic problem involving a rich man and land, illustrated by seven points connected by bridges over a river. The goal is to cross all bridges exactly once and return to the starting point without repetition.

Simplifying the Model

• A simplified model is introduced where bridges are represented as edges and land areas as vertices. This abstraction helps in analyzing the possibility of traversing all edges without repetition.

Understanding Vertex Degree

• The degree (or valency) of a vertex is defined as the number of edges connected to it, which can be either even or odd. For example, specific vertices have degrees ranging from 1 to 4, indicating their connectivity within the graph.

Analyzing Degrees for Traversal

Odd and Even Degree Vertices

• It’s crucial to distinguish between odd and even degree vertices when attempting to find paths:

• Starting at an odd degree vertex allows traversal through all edges before ending at another odd degree vertex.

• In contrast, if all vertices have even degrees, one can start and end at any vertex after traversing each edge once.

Concepts of Eulerian Trails

Definition of Eulerian Trail

• An Eulerian trail is defined as a path that visits every edge exactly once but does not necessarily return to the starting point. This requires careful consideration of vertex degrees during traversal planning.

Definition of Eulerian Circuit

• An Eulerian circuit starts and ends at the same vertex while visiting every edge exactly once; this necessitates that all vertices must have even degrees for such a circuit to exist within a connected graph.

Rules Governing Eulerian Paths and Circuits

Conditions for Existence

• Rule One: An Eulerian trail exists if there are no more than two vertices with an odd degree.

• Rule Two: An Eulerian circuit exists only if all vertices in the graph have an even degree; this ensures that one can enter and exit each vertex without being trapped due to uneven connections.

Practical Implications

Understanding Eulerian Paths and Circuits

Introduction to Graph Degrees

• The concept of graph degrees is introduced, emphasizing that once a vertex is reached in an even degree graph, one cannot return without leaving the path.

• In contrast, odd degree vertices allow for entry and exit; however, there must be exactly two odd degree vertices to form a valid path.

Eulerian Trails vs. Circuits

• An Eulerian trail can traverse all edges without repetition but does not require starting and ending at the same vertex.

• A distinction is made between trails and circuits: an Eulerian circuit requires returning to the starting vertex, necessitating all vertices to have even degrees.

Connectivity Requirement

• For a graph to support an Eulerian circuit, it must be connected; disconnected graphs with all even degree vertices cannot form such circuits.

• An example illustrates that having two odd degree vertices (b and e) prevents the formation of an Eulerian circuit.

Finding an Eulerian Circuit

• A practical example demonstrates how to find an Eulerian circuit by experimenting with paths starting from different vertices.

• The scenario involves five cities represented as vertices with connections (edges), assessing if a route can start and end at city B while traversing each road once.

Degree Analysis of Vertices

• Each city's degree is analyzed: city A has 4 (even), B has 2 (even), C has 4 (even), D has 2 (even), E also has 2 (even). This confirms the possibility of forming an Eulerian circuit.

• A potential route is proposed: starting from B through cities A, C, D, E back to B. Other routes are possible due to connectivity and even degrees.

Chinese Postman Problem

Overview of the Problem

• The Chinese Postman problem involves finding the shortest path for a postman who needs to deliver mail on both sides of streets without retracing steps unnecessarily.

Pathfinding Strategy

• The goal is defined as determining whether it's feasible for the postman to walk through every street once before returning without repetition.

Route Planning Challenges

• Initial analysis shows that some intersections require crossing streets multiple times due to odd-degree connections at certain points.

Optimal Path Solution

• An optimal route is suggested despite needing repetitions due to initial odd-degree constraints at specific vertices like A and D.

Understanding Eulerian and Hamiltonian Graphs

The Chinese Postman Problem

• The discussion begins with the transformation of a graph into an Eulerian graph by repeating edges, which resolves the issue at hand. Notably, vertices B, C, F, and E have even degrees while A and D have odd degrees.

• The central question is whether a postman can deliver mail in a locality by traversing each street exactly once. If not possible, the goal shifts to finding the shortest path that minimizes repeated streets.

Finding Solutions for Eulerian Circuits

• An optimal solution arises when the graph forms an Euler circuit. To tackle problems like the Chinese Postman Problem, one must find ways to create such circuits through minimal repetition of edges.

• "Elizar" refers to repeating certain edges economically until achieving an Euler circuit. For instance, if a graph has vertices with odd degrees (like four), adding specific edges can balance their degrees.

Techniques for Edge Repetition

• To achieve an Eulerian path in graphs with odd degree vertices, one must add edges strategically. This involves duplicating existing edges to ensure all vertices attain even degrees.

• An example illustrates how duplicating edge BE results in all vertices having even degrees, thus forming an Euler circuit.

Strategies for Handling Odd Degree Vertices

• In grid graphs where many vertices have odd degrees, a common technique involves connecting any two adjacent odd-degree vertices until all become even.

• The process continues by linking pairs of odd-degree vertices sequentially until every vertex achieves an even degree.

Understanding Hamiltonian Circuits

• Unlike Euler circuits that focus on traversing every edge once, Hamiltonian circuits aim to visit each vertex exactly once before returning to the starting point.

• An example demonstrates how one might traverse from vertex C through various other points back to C without revisiting any vertex—this constitutes a Hamiltonian circuit.

Key Differences Between Circuit Types

• It’s crucial to note that Hamiltonian circuits do not require passing through every edge; they only necessitate visiting each vertex once.

• The distinction lies in that while both types of circuits return to their starting point, only Hamiltonians are concerned with vertex traversal rather than edge traversal.

Evaluating Graph Properties for Circuits

Hamiltonian Circuits and Graph Theory

Understanding Hamiltonian Circuits

• The discussion begins with the identification of vertices in a graph, noting that vertices with odd degrees (like b and e) pose problems for forming an Eulerian circuit.

• A Hamiltonian circuit is introduced as a path that visits every vertex exactly once before returning to the starting point. An example is provided where the path a-b-d-c-a demonstrates this concept.

• It is clarified that an Eulerian circuit cannot exist due to the presence of vertices with odd degrees; however, creating a Hamiltonian circuit remains straightforward by duplicating edges.

The Four Color Theorem

• Transitioning to graph theory applications, the Four Color Theorem states any map can be colored using only four colors without adjacent regions sharing the same color.

• To illustrate this theorem, countries A, B, C, and D are represented as vertices in a graph. Edges are drawn between vertices representing borders between these countries.

• Connections are established based on neighboring countries: A connects to B and C; B connects to A, C, and D; C connects to B and D; D connects to B and C.

Coloring Process

• The coloring process starts with vertex A being colored red. Vertex B must be green since it borders A.

• Vertex D can also be red because it does not border A but shares borders with B. Conversely, vertex C cannot be red or green due to its connections with both A and B.

• Ultimately, using red, green, and blue allows for successful coloring of the map while adhering to adjacency rules. There exists a broader theorem confirming that any complex map can indeed be colored using just four colors.