Reference no: EM131710915
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.
|
How do title vii and its amendments protect employees
: How do Title VII and its amendments protect employees? Do you believe that laws are necessary to govern the ethical treatment of employees?
|
|
Organizations can leverage to add value to operations
: List and explain the five kinds of assets or capital that organizations can leverage to add value to operations.
|
|
What is the globalization
: What is globalization? What impact could the outsourcing of highly skilled programming jobs, traditionally held by employees in American companies.
|
|
Discuss case of the mercedes-benz automobiles
: Some critics and skeptics suggest that the digital divide is not really an ethical issue, because there have always been divisions or "divides" between group.
|
|
What would be the simplest way to draw a digraph
: 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 were some of the strategies institutions and practices
: What were some of the strategies, institutions, and practices that empires innovated or adopted to help them maintain and consolidate their power.
|
|
Development of the given software applications
: For example, should engineers working in the United States and other developed countries design applications to ensure that people living in remote areas.
|
|
What are some way that environmental and geographical factor
: What are some ways that natural, environmental, and geographical factors helped shape the society, religious worldview, politics, and the settlement.
|
|
Drawbacks of group decision making is most evident
: she participated in a team discussion in her office to decide their monthly goal. which of the following drawbacks of group decision making is most evident?
|