Graph G with 12 vertices has 5 pair-wise nonadjacent vertices. Minimum vertex co
ID: 3825627 • Letter: G
Question
Graph G with 12 vertices has 5 pair-wise nonadjacent vertices. Minimum vertex cover of G has a. at least 5 vertices Yes No Don't know b. at most 7 vertices Yes No Don't know The Minimum Spanning Tree of a connected weighted graph with 106 edges always a. contains the least weight edge Yes No Don't know b. contains 2 least weight edges Yes No Don't know c. contains 3 least weight edges Yes No Don't know d. has at least 15 edges Yes No Don't know e. has at least 16 edges Yes No Don't know The Single-source Shortest-Path Tree of a edge-positive-weighted graph always a. contains the least weight edge Yes No Don't know b. contains the least weight edge from source Yes No Don't know c. no shorter than MST Yes No Don't know The number of different perfect matchings for 6 points in the plane is no less than 13 Yes No Don't know no more than 15 Yes No Don't know The fastest algorithm for finding a negative cycle in a weighted graph has runtime _____ The fastest algorithm for finding a cycle in graph has runtime _____ A planar graph G has 6 vertices and 8 edges, the # of faces in the dual graph G' is _____Explanation / Answer
1)Given that graph has 12 vertices with 5 pair wise non adjacent vertices.
A vertex cover of a graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover. For this graph we need minimum 7 vertices to vertex cover.
a) Ans: NO.
b) Ans: YES.
2)
a) Ans: YES. It should contains one least weight edge.
b) Ans: No. doesn’t contain more than one least weight edge.
c) Ans: No. doesn’t contain more than one least weight edge.
d) Ans: No.
e) Ans: YES. It needs 16 edges atleast to complete the graph of 106 weighted edges.
5) ANS: Bellman_ford algothm is the fastest algorithm to find negitive cycle in weighted graph.
6) Ans: Floyd-Warshall algorithm. It finds shortest path between all pairs of vertices.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.