Homework Answers
Soln :
Since each edge in M are disjoint, to cover all the edges in M we need at least |M| no of vertices ( one end-point of each edge).still If some vertex of the graph is uncovered ( i.e if M is not a perfect matching ) ,then S contains more vertices.
So in general , |S| ≥ |M|.
In particular, max |M| ≤ min |S|
Add Answer to:
M. In particular show that |S Show that if M is a matching and S is some vertex cover max{IM| M is a matching of G} <...
Show that the following problem is NP-Complete (Hint: reduce from 3-SAT or Vertex Cover). Given an undirected graph G wi...
Show that the following problem is NP-Complete (Hint: reduce from 3-SAT or Vertex Cover). Given an undirected graph G with positive integer distances on the edges, and two integers f and d, is there a way to select f vertices on G on which to locate firehouses, so that no vertex of G is at distance more than d from a firehouse?
Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V},...
Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V}, E)\) where \(E\) is the complement set of edges. That is \((\mathrm{v}, \mathrm{w})\) is in \(E\) if and only if \((\mathrm{v}, \mathrm{w}) \notin \mathrm{E}\) Theorem: Given \(\mathrm{G}\), the complement graph of \(\mathrm{G}, \bar{G}\) can be constructed in polynomial time. Proof: To construct \(G\), construct a copy of \(\mathrm{V}\) (linear time) and then construct \(E\) by a) constructing all possible edges of between vertices in...
. Find a max flow in this network from s to t, and show the final...
. Find a max flow in this network from s to t, and show the final flow value along each edge. Also indicate the vertex partition that forms a min cut, and show the edges that cross the min cut. Show max flow Show min cut s (570/47 bonu Desgn an algorithm whose input is a ist of n poes, run in Ofn)t
10) Shortest Paths (10 marks) Some pseudocode for the shortest path problem is given below. When DIJKSTRA (G, w,s) is called, G is a given graph, w contains the weights for edges in G, and s is a sta...
10) Shortest Paths (10 marks) Some pseudocode for the shortest path problem is given below. When DIJKSTRA (G, w,s) is called, G is a given graph, w contains the weights for edges in G, and s is a starting vertex DIJKSTRA (G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) 1: RELAX (u, v, w) 1: if dlv] > dlu (u, v) then 2d[v] <- d[u] +w(u, v) 3 4: end if 4: while Q φ do 5: uExTRACT-MIN Q) for each vertex v...
The Max Cut problem is given a undirected graph G(V, E), finding a set S so...
The Max Cut problem is given a undirected graph G(V, E), finding a set S so that the number of edges that go between S and V − S is maximum. This is an NPC problem. a) Show that there is always a max cut of size at least |E|/2. Hint: Decide where to put vertices according to if they have more neighbors in S or V − S.
Let G, K(m z 2) and G2 W, (n 2 3), where G, and G2 are...
Let G, K(m z 2) and G2 W, (n 2 3), where G, and G2 are graphs. How many edges are in G, U G2 if G, and G2 have p (1 sps min{m,n}) vertices in common one of which is the hub of the wheel and the rest are consecutive vertices along the wheel's circumference?
Let G, K(m z 2) and G2 W, (n 2 3), where G, and G2 are graphs. How many edges are in G, U...
Recall the definition of the degree of a vertex in a graph. a) Suppose a graph has 7 vertices, each of degree 2 or 3. Is the graph necessarily connected ? b) Now the graph has 7 vertices, each degree...
Recall the definition of the degree of a vertex in a graph. a)
Suppose a graph has 7 vertices, each of degree 2 or 3. Is the graph
necessarily connected ?
b) Now the graph has 7 vertices, each degree 3 or 4. Is it
necessarily connected?
My professor gave an example in class. He said triangle and a
square are graph which are not connected yet each vertex has degree
2.
(Paul Zeitz, The Art and Craft of Problem...
Say that we have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears...
Say that we have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears at most once) from s to t that goes via v. Create a flow network by making v a source. Add a new vertex Z as a sink. Join s, t with two directed edges of capacity...
Bonus 1 A walk in a graph G is a sequence of vertices V1, V2, ...,...
Bonus 1 A walk in a graph G is a sequence of vertices V1, V2, ..., Uk such that {Vi, Vi+1} is an edge of G. Informally, a walk is a sequence of vertices where each step is taken along an edge. Note that a walk may visit the same vertex more than once. A closed walk is a walk where the first and last vertex are equal, i.e. v1 = Uk. The length of a walk is the number...
graph G, let Bi(G) max{IS|: SC V(G) and Vu, v E S, d(u, v) 2 i},...
graph G, let Bi(G) max{IS|: SC V(G) and Vu, v E S, d(u, v) 2 i}, 10. (7 points) Given a where d(u, v) is the length of a shortest path between u and v. (a) (0.5 point) What is B1(G)? (b) (1.5 points) Let Pn be the path with n vertices. What is B;(Pn)? (c) (2 points) Show that if G is an n-vertex 3-regular graph, then B2(G) < . Further- more, find a 3-regular graph H such that...
. Find a max flow in this network from s to t, and show the final flow value along each edge. Also indicate the vertex partition that forms a min cut, and show the edges that cross the min cut. Show max flow Show min cut s (570/47 bonu Desgn an algorithm whose input is a ist of n poes, run in Ofn)t
10) Shortest Paths (10 marks) Some pseudocode for the shortest path problem is given below. When DIJKSTRA (G, w,s) is called, G is a given graph, w contains the weights for edges in G, and s is a starting vertex DIJKSTRA (G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) 1: RELAX (u, v, w) 1: if dlv] > dlu (u, v) then 2d[v] <- d[u] +w(u, v) 3 4: end if 4: while Q φ do 5: uExTRACT-MIN Q) for each vertex v...
Let G, K(m z 2) and G2 W, (n 2 3), where G, and G2 are graphs. How many edges are in G, U G2 if G, and G2 have p (1 sps min{m,n}) vertices in common one of which is the hub of the wheel and the rest are consecutive vertices along the wheel's circumference?
Let G, K(m z 2) and G2 W, (n 2 3), where G, and G2 are graphs. How many edges are in G, U...
Recall the definition of the degree of a vertex in a graph. a)
Suppose a graph has 7 vertices, each of degree 2 or 3. Is the graph
necessarily connected ?
b) Now the graph has 7 vertices, each degree 3 or 4. Is it
necessarily connected?
My professor gave an example in class. He said triangle and a
square are graph which are not connected yet each vertex has degree
2.
(Paul Zeitz, The Art and Craft of Problem...
Bonus 1 A walk in a graph G is a sequence of vertices V1, V2, ..., Uk such that {Vi, Vi+1} is an edge of G. Informally, a walk is a sequence of vertices where each step is taken along an edge. Note that a walk may visit the same vertex more than once. A closed walk is a walk where the first and last vertex are equal, i.e. v1 = Uk. The length of a walk is the number...
graph G, let Bi(G) max{IS|: SC V(G) and Vu, v E S, d(u, v) 2 i}, 10. (7 points) Given a where d(u, v) is the length of a shortest path between u and v. (a) (0.5 point) What is B1(G)? (b) (1.5 points) Let Pn be the path with n vertices. What is B;(Pn)? (c) (2 points) Show that if G is an n-vertex 3-regular graph, then B2(G) < . Further- more, find a 3-regular graph H such that...
Most questions answered within 3 hours.
-
Required information
[The following information applies to the questions
displayed below.]
In 2019, Alliant Corporation acquired...
asked 5 minutes ago -
How much must I invest today if I want to withdraw 1/3 of my
original investment...
asked 2 hours ago -
What is meant by a “term premium”?
What can explain such a premium? Is it a...
asked 3 hours ago -
23. Which molecule has only covalent bonds? A. CO2 B. Al2O3 C.
Mg3N2
24. The octet...
asked 4 hours ago -
the
total pressure for a mixture of N2O4 and NO2 is 2.20 atm. If Kp=
7.10...
asked 4 hours ago -
Delaware Corp. prepared a master budget that included $22,385
for direct materials, $28,600 for direct labor,...
asked 4 hours ago -
For pesticide HCB (hexachlorobenzene), its logarithmic partition
coefficient log Kow is 5.6. What would be the...
asked 4 hours ago -
A chemist requires 0.422 mil Na2CO3 for a reaction. How many
grams does this correspond to?
asked 4 hours ago -
If the vapor pressure of carvone is approximately 9.4 torr at 99
°C, approximately how much...
asked 4 hours ago -
A juice bottling company is carrying out a test at 10%
significance that the mean population...
asked 4 hours ago -
What is the reflectivity (in percent) needed to keep water at a
temperature near its freezing...
asked 4 hours ago -
Suppose that the average surface temperature of Earth is 300K.
Assume this is uniform over its...
asked 4 hours ago