Consider a weighted, directed graph G with n vertices and m edges that have integer weights. A graph walk is a sequence of not-necessarily-distinct vertices vi, v2, --- , Vk such that each pair of consecutive vertices vi, Vi+1 are connected by an edge. This is similar to a path, except a walk can have repeated vertices and edges. The length of a walk in a weighted graph is the sum of the weights of the edges in the walk. Let s, t be given vertices in the graph, and L be a positive integer. We are interested counting the number of walks from s to t of length exactly L. Assume all the edge weights are positive. Describe an algorithm that computes the number of graph walks from sto t of length exactly L in O((n+ m)L) time. Prove the correctness and analyze the running time. (Hint: Dynamic Programming solution)

Consider a weighted, directed graph G with n vertices and m edges that have integer weights. A graph walk is a sequence of not-necessarily-distinct vertices vi, v2, --- , Vk such that each pair of consecutive vertices vi, Vi+1 are connected by an edge. This is similar to a path, except a walk can have repeated vertices and edges. The length of a walk in a weighted graph is the sum of the weights of the edges in the walk. Let s, t be given vertices in the graph, and L be a positive integer. We are interested counting the number of walks from s to t of length exactly L. Assume all the edge weights are positive. Describe an algorithm that computes the number of graph walks from sto t of length exactly L in O((n+ m)L) time. Prove the correctness and analyze the running time. (Hint: Dynamic Programming solution)

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

Discrete mathematics. Let G = (V, E) be a simple graph4 with n = |V| vertices, and let A be its adjacency matrix of dimension n × n. We want to count the L-cycles : such a cycle, denoted by C = u0u1 · · · uL with uL = u0 contains L distinct vertices u0, . . . , uL-1 et L edges E(C) = {uiui+1 | 0 ≤ i ≤ L − 1} ⊆ E. Two cycles are distinct if the edge sets are different : C = C' if and only if E(C) = E(C'). We define the matrices D, T, Q, the powers of A by matrix multiplication : D = A · A = A2, T = A · D = A3, Q = A · T = A4. Consider the values on the diagonals. Prove that for any vertex u ∈ V with degree d(u), d(u) = Du,u.
Computer Science Let V be a fixed set of n vertices. Consider a sequence of m undirected edges e1, e2, ..., em. For 1 ≤ i ≤ m, let Gi denote the graph with vertex set V and edge set Ei = {e1, ..., ei}. Let ci denote the number of connected components of Gi . Design an algorithm to compute ci for all i. Your algorithm should be asymptotically as fast as possible. What is the running time of your algorithm?
consider the undirected graph
The given inputs consist of two nodes (s, t) and a directed graph G = (V, E). In addition, each edge of the graph is either blue or red. The goal is to find a path from point s to point t such that red edges always follow blue edges. There need not be any red or blue borders on the route, but if there are, the red ones should follow the blue ones. Develop an algorithm that does the task in O(n + m) time and analyze its performance.
Consider a graph where vertices represent intersections and edges represent roads. The company Food To Go can place a maximum of one food cart at each intersection. A food cart placed at intersection X has an income equal to the number of roads at intersection X (ie, the degree of vertex X). If two food carts share a road, the income of that road is shared equally among the two. We are interested in calculating the total profit of all food carts placed, ie, the total income minus the cost, where each food cart costs 1 unit and each road provides an income of 1 unit. More formally, the profit for a graph G = (V, E) where the set SC V represents food cart locations, is calculated by the number of edges covered by the vertices in S minus the size of S (ie. |S). A D C E B In this example, placing a food cart on each of the vertices A and C will result in a profit of ISCA P (A D(CD) (CFU VACU-5
........
Given an undirected, weighted graph G(V, E) with n vertices and m edges, design an (O(m + n)) algorithm to compute a graph G1 (V, E1 ) on the same set of vertices, where E1 subset of E and E1 contains the k edges with the smallest edge weights , where k < m.
Algorithms
Consider the following edge-weighted graph G with 9 vertices and 16 edges: 90 Q6.1 Kruskal 40 50 80 130 110 70 S 150 60 30 10 120 140 20 100 List the weights of the MST edges in the order that Kruskal's algorithm adds them the MST. Your answer should be a sequence of 8 integers, with one space between each integer, 14
Note: Solve the following question and please don't repost previous answers and don't give a computer generated answer. Problem: Draw a simple, connected, directed, weighted graph with 9 vertices and 17 edges, each with unique edge weights. Identify one vertex as a “start” vertex and illustrate a running of Dijkstra’s algorithm on this graph.
An undirected graph G = (V,E) is said to be k-colorable if all the vertices of G can be colored using k different colors such that no two adjacent vertices have the same color. Design an algorithm that runs in time O(n + e) to color a graph with two colors or determine that the graph is not 2-colorable.
Be G=(V, E)a connected graph and u, vEV. The distance Come in u and v, denoted by d(u, v), is the length of the shortest path between u'and v, Meanwhile he width from G, denoted as A(G), is the greatest distance between two of its vertices. a) Show that if A(G) 24 then A(G) <2. b) Show that if G has a cut vertex and A(G) = 2, then Ġhas a vertex with no neighbors.