=============================================================================
CSC 263                        Tutorial 9                         Winter 2019
=============================================================================

Question 1: Bipartite Graph

An undirected graph G = (V,E) is called "bipartite" when the vertices can be
partitioned into two subsets V = V_1 u V_2 (with V_1 n V_2 = {}) such that
every edge of G has one endpoint in V_1 and the other in V_2 (equivalently,
no edge of G has both endpoints in V_1 or both endpoints in V_2).

 1. Draw two examples of undirected graphs that _are_ bipartite, one with at
    least 7 vertices and 10 edges.

 2. Draw two examples of undirected graphs that are _not_ bipartite, one with
    at least 7 vertices and no "triangle" (three vertices with all the edges
    between them).

 3. Modify the Depth-First Search algorithm so that:
    (a) your algorithm runs on an undirected graph;
    (b) your algorithm returns True if G is bipartite, False otherwise;
    (c) when G is bipartite, your algorithm sets a new field side[v] equal to
        1 or 2 for every vertex v, indicating which side of the bipartition v
        belongs to -- side[v] could have any value when G is not bipartite.
    Argue that your algorithm is correct and analyse its running time.

*4. Prove that an undirected graph is bipartite iff it contains no cycle whose
    length is odd (called simply an "odd cycle").


Question 2: Bug Genders

Dr. Amy Farrah Fowler is a biologist who is currently studying the reproductive
behavior of a rare species of bugs. She assumes that they feature two different
genders and that they only interact with bugs of the opposite gender. In her
experiment, individual bugs and their interactions were easy to identify,
because numbers were printed on their backs.

As the data analyst in Amy's lab, you are given the experiment data which is a
list of bug interactions, i.e., a list of pairs such as [(1, 9), (4, 5), (3,
5), (3, 4), ...]. Your job is to devise an algorithm that decides whether the
experiment supports Amy's assumption of two genders with no same-sex
interaction, or if it contains some bug interactions that falsify it.  In other
words, in we find an evidence proving that Amy's assumption is false, return
"AMY IS WRONG"; otherwise return "AMY MIGHT BE RIGHT".

Devise an algorithm for this and analyze its runtime. Let N be the number of bugs
and K be the number of interactions in the data.