Scribd Logo
Upload

Welcome to Scribd!

  • 107 views

    Euler and Hamilton Paths: Discrete Mathematics and Its Applications

    Uploaded by

    Ibn Sina
    This document discusses Euler paths and circuits as well as Hamilton paths and circuits in graphs. It provides necessary and sufficient conditions for a graph to have an Euler path or circuit. Namely, a connected multigraph has an Euler circuit if each vertex has even degree, and an Euler path if exactly two vertices have odd degree. Hamilton paths and circuits require visiting each vertex exactly once without repeating edges or vertices. Finding Hamilton circuits is computationally difficult compared to Euler circuits.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Euler and Hamilton Paths: Discrete Mathematics and Its Applications

    Uploaded by

    Ibn Sina
    107 views19 pages
    This document discusses Euler paths and circuits as well as Hamilton paths and circuits in graphs. It provides necessary and sufficient conditions for a graph to have an Euler path or circuit. Namely, a connected multigraph has an Euler circuit if each vertex has even degree, and an Euler path if exactly two vertices have odd degree. Hamilton paths and circuits require visiting each vertex exactly once without repeating edges or vertices. Finding Hamilton circuits is computationally difficult compared to Euler circuits.

    Original Title

    Graph Part 4

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses Euler paths and circuits as well as Hamilton paths and circuits in graphs. It provides necessary and sufficient conditions for a graph to have an Euler path or circuit. Namely, a connected multigraph has an Euler circuit if each vertex has even degree, and an Euler path if exactly two vertices have odd degree. Hamilton paths and circuits require visiting each vertex exactly once without repeating edges or vertices. Finding Hamilton circuits is computationally difficult compared to Euler circuits.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    107 views19 pages

    Euler and Hamilton Paths: Discrete Mathematics and Its Applications

    Uploaded by

    Ibn Sina
    This document discusses Euler paths and circuits as well as Hamilton paths and circuits in graphs. It provides necessary and sufficient conditions for a graph to have an Euler path or circuit. Namely, a connected multigraph has an Euler circuit if each vertex has even degree, and an Euler path if exactly two vertices have odd degree. Hamilton paths and circuits require visiting each vertex exactly once without repeating edges or vertices. Finding Hamilton circuits is computationally difficult compared to Euler circuits.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 19

    Discrete Mathematics and Its Applications

    Chapter 8.5
    Euler and Hamilton Paths
    Euler Paths and Circuits
    • The Seven bridges of Königsberg

    C
    c

    D
    A
    a d

    B
    b
    Euler Paths and Circuits
    • An Euler path is a path using every edge
    of the graph G exactly once.
    • An Euler circuit is an Euler path that
    returns to its start.
    C

    Does this graph have an Euler circuit?


    No.
    A D

    B
    Necessary and Sufficient Conditions
    • How about multigraphs?

    • A connected multigraph has a Euler circuit


    iff each of its vertices has an even degree.
    • A connected multigraph has a Euler path
    but not an Euler circuit iff it has exactly
    two vertices of odd degree.
    Example
    • Which of the following graphs has an Euler circuit?

    a b a b a b

    e e

    d c d c c d e

    yes no no
    (a, e, c, d, e, b, a)
    Example
    • Which of the following graphs has an Euler path?

    a b a b a b

    e e

    d c d c c d e

    yes no yes
    (a, e, c, d, e, b, a ) (a, c, d, e, b, d, a, b)
    Euler Circuit in Directed Graphs

    NO (a, g, c, b, g, e, d, f, a) NO
    Euler Path in Directed Graphs

    NO (a, g, c, b, g, e, d, f, a) (c, a, b, c, d, b)
    Condition for directed Graph
    For a directed graph we have:

    A directed graph has an eulerian circuit if and only if it is


    connected and each vertex has the same in-degree as out-
    degree.

    A directed graph has an eulerian path if and only if it is


    connected and each vertex except 2 have the same in-degree
    as out-degree, and one of those 2 vertices has out-degree with
    one greater than in-degree (this is the start vertex), and the
    other vertex has in-degree with one greater than out-degree
    (this is the end vertex).
    Hamilton Paths and Circuits

    • A Hamilton path in a graph G is a path


    which visits every vertex in G exactly once.

    • A Hamilton circuit is a Hamilton path that


    returns to its start.
    Hamilton Circuits

    Is there a circuit in this graph that passes through each


    vertex exactly once?
    Hamilton Circuits

    Yes; this is a circuit that passes through each vertex


    exactly once.
    Finding Hamilton Circuits

    Which of these three figures has a Hamilton circuit?


    Of, if no Hamilton circuit, a Hamilton path?
    Finding Hamilton Circuits

    • G1 has a Hamilton circuit: a, b, c, d, e, a


    • G2 does not have a Hamilton circuit, but does have a
    Hamilton path: a, b, c, d
    • G3 has neither.
    Finding Hamilton Circuits

    • Unlike the Euler circuit problem, finding


    Hamilton circuits is hard.
    • There is no simple set of necessary and
    sufficient conditions, and no simple
    algorithm.
    Properties to look for ...
    • No vertex of degree 1
    • If a node has degree 2, then both edges
    incident to it must be in any Hamilton
    circuit.
    • No smaller circuits contained in any
    Hamilton circuit (the start/endpoint of any
    smaller circuit would have to be visited
    twice).
    A Sufficient Condition
    Let G be a connected simple graph with n
    vertices with n  3.
    G has a Hamilton circuit if the degree of
    each vertex is  n/2.
    Travelling Salesman Problem
    A Hamilton circuit or path may be used to solve
    practical problems that require visiting
    “vertices”, such as:
    road intersections
    pipeline crossings
    communication network nodes
    A classic example is the Travelling Salesman
    Problem – finding a Hamilton circuit in a
    complete graph such that the total weight of its
    edges is minimal.
    Summary
    Property Euler Hamilton
    Repeated visits to a given Yes No
    node allowed?
    Repeated traversals of a No No
    given edge allowed?
    Omitted nodes allowed? No No

    Omitted edges allowed? No Yes

    You might also like