##### Assignment Instructions

CS515 Homework 8.

CS515, Fall 2020
Homework 8
Due: November 11, 2020
1. (16 pts.) Let e1 and e2 be two lowest-weight edges in a connected and weighted graph G. Show that
e1 and e2 belong to some MST in G.
2. (16 pts.) Consider this statement: If e1, e2 and e3 are three lowest-weighted edges in a connected
and weighted graph G, then e1, e2 and e3 belong to some MST in G. Is this statement true? Either
prove it or show a counterexample.
3. (16 pts.) Show that every MST in a connected, weighted graph G is returned by Kruskal’s algorithm
for some sorted order of the edges of G.
4. (16 pts.) Let G be a connected, weighted graph G and let e be an edge in G. Is it possible for e to
be a part of every MST in G? If so, describe a general condition that guarantees it.
5. (20 pts.) Let G be a connected, weighted graph G and let e be a highest-weight edge in G. Is it
possible for e to be a part of some MST in G? If you think the answer is no, explain why. If you
think the answer is yes, formulate a possibly general conditions under which e is included in some
MST.
6. (16 pts.) Suppose all edge weights in a graph are integers in the range 1 to V . How fast can you
make Kruskal’s algorithm run? Explain.
7. (Bonus: 30 pts.) A directed graph G = (V; E) is semi-connected if for all pairs of vertices u; v 2 V ,
u is reachable from v or v is reachable from u. Describe a O(jV j + jEj) algorithm to determine
whether or not G is semi-connected. A precise narrative is acceptable. Explain why your algorithm
is correct and justify the running time.

CS515 Homework 8

Price (USD)
\$

#### This assignment has been solved!

Place your order for a custom solution to this or a similar paper.

### Why Choose Us For Your Assignment?

##### Privacy

We value all our customers' privacy. For that reason, all information stays private and confidential and will never be shared with third parties.

##### Punctuality

With our service you will never miss a deadline. We use strict follow-ups with our writers to ensure that all papers are submitted on time.

##### Authenticity

We have no tolerance for plagiarism. All papers go through thorough checking to ensure that no assignments contain plagiarism.

##### Money Back

You feel unsatisfied with your results? No worries. We offer refunds to our customers if any paper is not written according to the instructions.

### Clients Love Us

Client #121678
This is by far the best I have ever scored in a custom essay. I am surprised the writer handled this assignment so well despite the short notice. I will definitely use your service next time.
Client #21702
When I was recommended to you by my friends, I wasn't sure you could deliver excellent results for Masters research papers until I submitted my first order. I am all yours now.
Client #20730