A) Graph G with 10 vertices has 4 pair-wise nonadjacent vertices. Minimum vertex

Question

A) Graph G with 10 vertices has 4 pair-wise nonadjacent vertices. Minimum vertex cover of G has b) The Minimum Spanning Tree of a connected weighted graph with 100 edges always c) The Single-source Shortest-Path Tree of a edge-positive-weighted graph always d) The number of different perfect matching for 6 points in the plane is e) The fastest algorithm finding a negative cycle in a weighted graph has runtime ______ f) The fastest algorithm finding a cycle in graph has runtime ______ g) A planar graph G has 5 vertices and 7 edges, the # of faces in the dual graph G' is _____

Explanation / Answer

a)

i)Yes

ii) Dont know

b)

i) Yes

ii) Yes

iii) Dont know

iv) Yes

v) Yes

c)

i) Yes

ii) Yes

iii) Yes

d)

i) No

ii) No

e) O(m+n)

f) O(|E| + |V|)

g) 4 faces

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---