Question 8. A connected graph G has 4 vertices and 4 edges of costs 1, 2, 3 and respectively 4. (a) Show that G is not a tree. (b) Show that G has a single minimum spanning tree. (Hint: For example, think how Prim's algorithm constructs the minimum spanning tree). (c) Draw a connected graph G with 4 nodes and 4 edges of costs 1, 2, 3, 4, respectively, so that the minimum spanning tree contains the edge of cost 4. The 4 nodes are below, you need to draw the 4 edges and indicate their cost. a b d

Question 8. A connected graph G has 4 vertices and 4 edges of costs 1, 2, 3 and respectively 4. (a) Show that G is not a tree. (b) Show that G has a single minimum spanning tree. (Hint: For example, think how Prim's algorithm constructs the minimum spanning tree). (c) Draw a connected graph G with 4 nodes and 4 edges of costs 1, 2, 3, 4, respectively, so that the minimum spanning tree contains the edge of cost 4. The 4 nodes are below, you need to draw the 4 edges and indicate their cost. a b d

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Given a graph that is a tree (connected and acyclic). (I) Pick any vertex v.(II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance.(III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are truea. p is the longest path in the graphb. p is the shortest path in the graphc. p can be calculated in time linear in the number of edges/vertices
3) The graph k-coloring problem is stated as follows: Given an undirected graph G= (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in V a color c(v) such that 1
3) The graph k-coloring problem is stated as follows: Given an undirected graph G = (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in Va color c(v) such that 1< c(v)
Given a graph that is a tree (connected and acyclic). (1) Pick any vertex v. (II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance. (III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are true a. p is the longest path in the graph b. p is the shortest path in the graph c. p can be calculated in time linear in the number of edges/vertices a,c a,b a,b,c b.c
5. Fleury's algorithm is an optimisation solution for finding a Euler Circuit of Euler Path in a graph, if they exist. Describe how this algorithm will always find a path or circuit if it exists. Describe how you calculate if the graph is connected at each edge removal. Fleury's Algorithm: The algorithm starts at a vertex of v odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge (a bridge) left at the current vertex. It then moves to the other endpoint of that edge and adds the edge to the path or circuit. At the end of the algorithm there are no edges left ( or all your bridges are burnt). (NOTE: Please elaborate on the answer and explain. Please do not copy-paste the answer from the internet or from Chegg.)
Let V= {cities of Metro Manila} and E = {(x; y) | x and y are adjacent cities in Metro Manila.} (a) Draw the graph G defined by G = (V; E). You may use initials to name a vertex representing a city. (b) Apply the Four-Color Theorem to determine the chromatic number of the vertex coloring for G.
Question 1: In graph theory, a graph X is a "complement" of a graph F if which of the following is true? Select one: a. If X is isomorph to F, then X is a complement of F. b. If X has half of the vertices of F (or if F has half of the vertices of X) then X is a complement of F. c. If X has the same vertex set as F, and as its edges ONLY all possible edges NOT contained in F, then X is a complement of F. d. If X is NOT isomorph to F, then X is a complement of F. Question 2: Which statement is NOT true about Merge Sort Algorithm: Select one: a. Merge Sort time complexity for worst case scenarios is: O(n log n) b. Merge Sort is a quadratic sorting algorithm c. Merge Sort key disadvantage is space overhead as compared to Bubble Sort, Selection Sort and Insertion Sort. d. Merge Sort adopts recursive approach
The minimum vertex cover problem is stated as follows: Given an undirected graph G = (V, E) with N vertices and M edges. Find a minimal size subset of vertices X from V such that every edge (u, v) in E is incident on at least one vertex in X. In other words you want to find a minimal subset of vertices that together touch all the edges. For example, the set of vertices X = {a,c} constitutes a minimum vertex cover for the following graph: a---b---c---g d e Formulate the minimum vertex cover problem as a Genetic Algorithm or another form of evolutionary optimization. You may use binary representation, OR any repre- sentation that you think is more appropriate. you should specify: • A fitness function. Give 3 examples of individuals and their fitness values if you are solving the above example. • A set of mutation and/or crossover and/or repair operators. Intelligent operators that are suitable for this particular domain will earn more credit. • A termination criterion for the…
(1) T F Given a directed graph G and a vertex v in the graph, breath first search (BFS) can be used to detect if v is part of a cycle in the graph. (2) T F Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is decreased by one, then P will still be a shortest path from s to t. (3) T F edge Kruskal's algorithm is always correct even in graphs with negative weights. (4) T F For any flow network, there is only one unique way to assign flow value to the edges so as to achieve the maximum flow for the network. NP problems are those problems that cannot be solved in polynomial (5) T F time.
Given the below graph, show the minimum spanning tree using an adjacency matrix. You may use scratch paper to draw the graph if you wish. 12 A В 2 3 E F 8 G H 10 A В D E F G A В C D E F G H |||
Given the following graph, A C 3 1 E 4 В F 7 D 5 What is the next edge and vertex(s) to be included in the solution if a. we are using Prim's algorithm to find a minimum spanning tree and we have started with vertex E? Edge: Vertex(s): What is the next edge and vertex(s) to be included in the solution if b. we are using Kruskal's algorithm to find a minimum spanning tree Edge: Vertex(s): What is the next edge and vertex(s) to be included in the solution if c. we are using Dijkstra's shortest path algorithm to find shortest paths and we have started with vertex E, with C and F already included in the shortest path tree? Edge: Vertex(s):
16. Use the flow graph of K, to answer the following questions. 6/6 9/11 3/4 6/6 3/3 3/3 2/2 8/8 1/1 b K2 a. Identify each edge and the capacity in graph K, Enter your answer in the space below the question. For example: c(s, a) = 4 b. What is the flow into vertex a and the flow out of a? Flow into a = Flow out of a = c. What is the flow into vertex c and the flow out of c? Flow into c = Flow out of c= d. What is the flow out of source s and the flow into r? Flow into s= Flow out of t=