Q1. We know that the walk and positive walk relations on a directed graph define relations, and the positive walk relation on a DAG defines a strict partial order. Answer each of the following and explain your answer.
a. What sort of digraph has a walk relation that describes a total (linear) order?
b. Given R is an equivalence relation, what would be the simplest way to draw a digraph that represents R with the walk relation? What would the digraph look like? What would each equivalence class look like?
c. Why does a partial order have to be a DAG?
Q2. Let R be the relation on ordered pairs of positive integers defined below. For each definition determine what properties of relations it has and whether or not it is an equivalence relation.
a. (a, b)R(c, d) ↔ ac = bd
b. (a, b)R(c, d) ↔ ad = bc
Q3. Consider the routing
|
Input
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
|
Output
|
12
|
10
|
15
|
6
|
3
|
7
|
4
|
9
|
13
|
8
|
11
|
14
|
1
|
2
|
5
|
16
|
Showing your work give how to route each packet through a Benes network with 16 inputs to achieve congestion 1.
Q4. Hall's marriage theorem uses an algorithm of men proposing to women, then women rejecting men.
a. Show that it is possible for every woman to be matched with her last choice by giving an example with four men and four women where this happens.
b. Suppose both men and women are given the option of saying that there are unacceptable pairings. i.e. there are potential partners that are worse than being alone. Describe how you would modify the algorithm to handle this situation, and give an example of using your modified algorithm.
Q5. This problem will outline how to prove that any graph with no odd length circuits is 2-colorable.
a. Find a spanning tree of the following graph (LaTeX Hint: Just remove edges until your spanning tree is left)
b. Two color your spanning tree (fill the nodes).
c. Put your deleted edges back in with the coloring from part b to show that this is also a two-coloring of the original graph.
d. Explain why a two-coloring of a spanning tree will be a two-coloring of the original graph, given the original graph has no cycles of odd length.