Look up the definition of a biconnected undirected graph on Wikipedia. Give a one sentence definition based on induced sub-graphs. Start your definition with “An undirected graph G = (V, E) is biconnected, if . . . ” (b) For a directed graph G = (V, E), its underlying undirected graph is obtained by replacing every directed edge (u, v) with an undirected one {u, v}. (If (u, v) and (v, u) are both in E, then the underlying undirected graph still contains only one edge {u, v}.) Give a strongly connected directed graph such that its underlying undirected graph is not biconnected.
Look up the definition of a biconnected undirected graph on Wikipedia. Give a one sentence definition based on induced sub-graphs. Start your definition with “An undirected graph G = (V, E) is biconne...
Problem 5. (12 marks) Connectivity in undirected graphs vs. directed graphs. a. (8 marks) Prove that in any connected undirected graph G- (V, E) with VI > 2, there are at least two vertices u, u є V whose removal (along with all the edges that touch them) leaves G still connected. Propose an efficient algorithm to find two such vertices. (Hint: The algorithm should be based on the proof or the proof should be based on the algorithm.) b....
An orientation of an undirected graph G = (V, E) is an assignment of a direction to each edge e ∈ E. An acyclic orientation is the assignment of a direction to every edge such that the resulting directed graph contains no cycles. Either prove that there exist undirected graphs with no acyclic orientation, or provide an efficient O(V +E) algorithm for producing an acyclic orientation for an undirected graph G and explain why it produces a valid acyclic orientation.
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of G, that is...
2. Let G = (V, E) be an undirected connected graph with n vertices and with an edge-weight function w : E → Z. An edge (u, v) ∈ E is sparkling if it is contained in some minimum spanning tree (MST) of G. The computational problem is to return the set of all sparkling edges in E. Describe an efficient algorithm for this computational problem. You do not need to use pseudocode. What is the asymptotic time complexity of...
Problem 4 Let G = (V. E) be an undirected, connected graph with weight function w : E → R. Furthermore, suppose that E 2 |V and that all edge weights are distinct. Prove that the MST of G is unique (that is, that there is only one minimum spanning tree of G).
Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so...
6. Prove that the following graphs are connected: (a) The 3 vertex cycle: (b) The following 4 vertex graph: (c) K 7. An edge e of a connected graph G is called a cut edge if the graph G obtained by deleting that edge (V(G) V(G) and E(G) E(G) \<ej) is not connected. Prove that if G1 and G2 are connected simple graphs which are isomorphic and if G1 has a cut edge, then G2 also has a cut edge....
Let G= (V, E) be a connected undirected graph and let v be a vertex in G. Let T be the depth-first search tree of G starting from v, and let U be the breadth-first search tree of G starting from v. Prove that the height of T is at least as great as the height of U
MST For an undirected graph G = (V, E) with weights w(e) > 0 for each edge e ∈ E, you are given a MST T. Unfortunately one of the edges e* = (u, z) which is in the MST T is deleted from the graph G (no other edges change). Give an algorithm to build a MST for the new graph. Your algorithm should start from T. Note: G is connected, and G − e* is also connected. Explain...
IN JAVA Given is a weighted undirected graph G = (V, E) with positive weights and a subset of its edges F E. ⊆ E. An F-containing spanning tree of G is a spanning tree that contains all edges from F (there might be other edges as well). Give an algorithm that finds the cost of the minimum-cost F-containing spanning tree of G and runs in time O(m log n) or O(n2). Input: The first line of the text file...