Define Euler path and Hamilton path. Give examples of both Euler and Hamilton path.

Question

Suresh Chand · Accepted Answer

An Eular path is a path using every edge of the graph G exactly once and only once. An Eular Curcuit is an eular path that returns to its staring vertex. An connected multigraph has an eular path but not an eular circuit if and only if it has at most two vertices of odd degree. Example: It is an Eular path. a → c → d → e → b → d → a → b All edges are used to make the path, no edges are repeated. It is not eular circult as it doesn't end with starting vertex. Alsp, d(a) = 3, d(b) = 3,  d(c) = 2,  d(d) = 4,  d(e) = 2 Maximum of two vertices have odd degree so, it can be said eular path. Hamilton Path: Hamilton path is a path which contains each vertex once and only once of graph G, no matter how many edgres. Formally, a simple path in a graph G that passes through every vertex exactly once is called a hamilton path. Note: Length pf Hamilton path is a connected graph of 'n' vertices is (n-1) edge. Examples: 1, 2, 3, 4, 5 or 1, 2, 4, 3 or 1, 4, 3, 2, 5 Here, np vertices is repeated. so, it is hamilton path.

Define Euler path and Hamilton path. Give examples of both Euler and Hamilton path.

Leave your Answer:

Hits Counter

Question

Define Euler path and Hamilton path. Give examples of both Euler and Hamilton path.

Leave your Answer: