Teori Graph - Graph Euler dan Graph Hamilton

Summary

This video delves into graph theory, focusing on the concepts of Eulerian and Hamiltonian graphs. It explains key definitions, such as Eulerian paths, circuits, and the characteristics of Eulerian graphs. The video also discusses the conditions under which a graph is Eulerian, including having an even degree for each vertex. Additionally, the Hamiltonian cycle is introduced, emphasizing how it differs from Eulerian cycles, as it involves visiting all vertices rather than edges. The presentation provides practical examples and includes an explanation of the Eulerian algorithm used for finding circuits in graphs.

Takeaways

• 😀 Eulerian Path is a path that visits every edge in a graph exactly once.
• 😀 Eulerian Circuit is a closed loop where every edge is visited exactly once and the path returns to the starting point.
• 😀 A graph has an Eulerian path if it has exactly zero or two vertices with an odd degree.
• 😀 A graph has an Eulerian circuit if all of its vertices have an even degree.
• 😀 Hamiltonian Path visits each vertex exactly once without repeating any vertex.
• 😀 Hamiltonian Circuit is a Hamiltonian path that forms a closed loop, visiting every vertex exactly once and returning to the starting point.
• 😀 A graph with an Eulerian circuit can be traversed starting from any point, while a Hamiltonian circuit requires visiting every vertex exactly once.
• 😀 The Eulerian circuit and path are defined based on edges, while the Hamiltonian path and circuit focus on vertices.
• 😀 The Fury algorithm is used to find Eulerian circuits, starting from a vertex and selecting edges until all are visited.
• 😀 A Hamiltonian circuit cannot be easily determined using simple conditions, as it depends on the vertices and the connectivity of the graph.

Q & A

What is the definition of an Eulerian path?

An Eulerian path is a path in a graph that traverses every edge exactly once. If the path forms a cycle (i.e., it returns to the starting point), it is an Eulerian circuit.

What criteria must be met for a graph to have an Eulerian circuit?

For a graph to have an Eulerian circuit, every vertex in the graph must have an even degree, and the graph must be connected, meaning there must be a path between every pair of vertices.

Can you explain the difference between an Eulerian path and an Eulerian circuit?

The difference is that an Eulerian path visits every edge exactly once without necessarily returning to the starting point, while an Eulerian circuit is an Eulerian path that returns to the starting point, forming a cycle.

What does it mean for a graph to be an Eulerian graph?

A graph is an Eulerian graph if it contains an Eulerian circuit, meaning that there is a closed loop where every edge is visited exactly once.

How can you determine if a graph is not Eulerian?

A graph is not Eulerian if it has any vertex with an odd degree or if it is disconnected (i.e., some vertices are not connected to others by edges).

What is the key difference between Eulerian and Hamiltonian graphs?

The key difference is that in Eulerian graphs, every edge is visited exactly once, whereas in Hamiltonian graphs, every vertex is visited exactly once. Eulerian paths/circuits focus on edges, while Hamiltonian paths/circuits focus on vertices.

What is a Hamiltonian circuit?

A Hamiltonian circuit is a closed loop in a graph where every vertex is visited exactly once before returning to the starting point.

How can you tell if a graph has a Hamiltonian path?

A graph has a Hamiltonian path if it is possible to visit every vertex exactly once, without necessarily returning to the starting vertex. A Hamiltonian circuit requires returning to the start point to form a cycle.

What is the Fury algorithm and how does it work?

The Fury algorithm is a step-by-step method for finding an Eulerian circuit. It involves selecting a starting point, choosing edges that connect to the current vertex, and continuing this process until no more edges are available. If all edges are traversed, the algorithm confirms the existence of an Eulerian circuit.

What does the degree of a vertex mean in graph theory?

The degree of a vertex refers to the number of edges connected to it. In Eulerian graphs, for a circuit to exist, all vertices must have an even degree.