Homework 10. Due Tuesday, Dec 5

1.  A graph is strongly connected if:
     For all nodes u
       for all nodes v not equal to u,
         there is a path from u to v.

   1. Let G be any graph of 6 nodes that is NOT strongly connected. (A graph with 6 nodes means that the size of the set of vertices is 6. What is the maximum number of edges possible for G? Briefly explain your answer.

      for the graph to not be strongly connected there must be one group of nodes that cannot reach another group of nodes. The most edges that you can have, is a complete graph (all possible edges between) of 5 nodes, and then all having edges to or from (but not both) the remaining node. This leads to 31 total edges.

   2. Let G be any strongly connected graph with 6 nodes. What is the fewest number of edges possible for G? Briefly explain your answer.

      consider six nodes with edges connecting them in order (as if around a hexagon); this is the smallest strongly connected graph. If there are fewer edges, then some node has no edge leaving it -- so the graph would not be strongly connected.

2. Let G still be any stronly connected graph with 6 nodes. The set of edges E defines a relation on V. let E' be the transitive closure of that relation, and let G' be the graph defined by the set of vertices V and the set of edges E'. How many edges are in G'? Briefly explain your answer.

   A strongly connected graph means every edge can eventaully get to every other edge. If the relation the graph represents is transitive then if you can ever get between nodes, you can get there in one step. Therefore, you can get between every pair of nodes in one step, meaning you have all possible edges. This is 36 edges.

3. The St. Louis rams play in an NFL division with 4 teams, {arizona, seattle, st. louis, san francisco}. define a graph G( V, E), where set the V of vertices is the set of teams listed above, and the set E connects team A to team B if team A beat team B. Here are the edges of this graph for 2006. (The scores are irrelevant, they are just for fun).

        St. Louis 28,     Seattle 30
        San Francisco 27, Arizona 34
        Seattle 21,       Arizona 10 
        St. Louis 24,     Seattle 22
        San Francisco 20, Seattle 14 
        San Francisco 20, St. Louis 13
        St. Louis 16,     Arizona 14
        San Francisco 17, St. Louis 20

   1. Draw the graph shown above. Choose whether your graph is a directed or undirected graph, and explain your choice. (there is a correct answer to this question, this is not an opinion).

      This should be directed; an edge exists from one team to another if this first team beats the other team.

   2. What does the "in-degree" and "out-degree" of a node correspond to?

      wins and losses

   3. Does this graph have a cycle?

      yes, st. louis beat san fran, san fran beat seattle, st. lois beat seattle. (others exist).

   4. Is this graph the representation of a partial order? Why or why not?

      it is not. it is not reflexive and there are also elements that are not symmetric (st. louis, seattle) and (seattle st. louis) are both in the graph.

4. Partial orders.
   1. Define any partial order on a set of 5 elements.

      Let A = {1,2,3,4,5}, and define the relation R as: {(a,b) | a <= b}

   2. Define a partial order on a set of 5 elements such that there are exactly two total orders consistent with that partial order.

      Let A = {1,2,3,4,5}, and define the relation R as: {(a,b) | a <= b} - { (4,5) }. so that the order between 4 and 5 is no longer defined.

   3. Can you define a partial order on a set of 5 elements such there there are exactly 3 total order consistent with that partial order? Is yes, then give an example (of a partial order on 5 elements with exactly 3 consistent total orders), if not, explain why not.

      You can do this, it turns out. define A = {1,2,3,4,s} define R as "the usual" order on 1,2,3,4, then include also (1,s) and (s,4). (so that s has to come between 1 and 4). Then there are 3 consistent total orders:

      1,s,2,3,4
      1,2,s,3,4
      1,2,3,s,4

5. This problem considers Euler Paths/Tours and Hamiltonian Paths/Tours. You are permitted to use Wikipedia to remind yourself of the definitions of these. The below example should have between 5 and 7 nodes.
   1. Draw a graph with an Euler Tour but not a Hamiltonian Cycle.

      

   2. Draw a graph with a Hamiltonian Path but not and Euler Path.

      

   3. Draw a connected graph with neither Hamiltonian Path nor an Euler Path.