Explore BrainMass
Share

Explore BrainMass

    Automata and Computability

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    An undirected graph is bipartite if its nodes may divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn't contain a cycle that has an odd number of nodes.

    See attached file for full problem description.

    © BrainMass Inc. brainmass.com October 9, 2019, 7:17 pm ad1c9bdddf
    https://brainmass.com/computer-science/files/automata-computability-113567

    Attachments

    Solution Preview

    Please see attached file.

    Problem 39

    An undirected graph is bipartite if its nodes may divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn't contain a cycle that has an odd number of nodes.
    Let

    BIPARTITE = {G | G is bipartite graph}.

    Show that BIPARTITE  NL.

    Solution.

    First we show that if a graph is bipartite, it must not contain a cycle with
    an odd number of nodes. Suppose it did contain such a cyle. Label the
    nodes n1; n2; ::::n2k; n2k+1. Clearly, if n1 is in some set A, then n2 must
    be in set B, so n3 must be in set A, etc. By induction, we see ...

    Solution Summary

    The expert examines automata and computability.

    $2.19