Question

CS 3345: Data Structures and Algorithms -Homework 7 1. These three questions about graphs all have the same subparts. Note that for parts (iii), (iv), and (v), your answer should be in terms of an arbitrary k, not assuming k-4 a) Suppose a directed graph has k nodes, where there are two lspecial" nodes. One has an edge from itself to every non-special node and the other has an edge from every non-special node to itself. There are no other edges at all in the graph. i. Draw the graph (using circles and arrows) assuming k-4 ii. Draw an adjacency list representation of the graph assuming k ii. In terms of k, exactly how many edges are in the graph? iv. Is this graph dense or sparse? v. In terms ofk (if k is relevant), exactly how many correct results for topological sort that does this graph have? b) Suppose a directed graph has k nodes, where each node corresponds to a number (1, 2, ..., k) and there is an edge from node i to node j if and only if i mod 2 6-j mod 2 i. Draw the graph (using circles and arrows) assuming k-4 ii. Draw an adjacency list representation of the graph assuming k-4 ii. In terms ofk exactly how many edges are in the graph assuming k is even? Is this graph dense or sparse? In terms ofk (if k is relevant), exactly how many correct results for topological sort that does this graph have? iv. v. c) Suppose a directed graph has k nodes, where each node corresponds to a number (1, 2, ..., k) and there is an edge from node i to node j if and only ifj-i+1 i. Draw the graph (using circles and arrows) assuming k-4 ii. Draw an adjacency list representation of the graph assuming k ii. In terms of k, exactly how many edges are in the graph? iv. Is this graph dense or sparse? v. In terms ofk (if k is relevant), exactly how many correct results for topological sort that does this graph have?

Answer 1

Answer: Note: I have answered for part A and B only. A) The following directed graph has k nodes as represents D Draw the graph: K-4 ii Draw an adjacency list as representation: Nodes iii) As the given K vertices there will be K-1 edges in the graph. in order to consider all possible edges in the above graph (K-1) edges. Here, K 4 then (4-1)*3 12 edges

iv) From the following graph, it represent as dense graph because it has maximum number of edges. v) In terms of K, the numbers of correct results for an topological sort that the graph has is 8 B) The following directed graph has K nodes, D Draw the graph: i) Draw a graph assuming K-4 ii) Draw an adjacency list as representation:

Nodes iii) As the given K vertices there will be K-1 edges in the graph, in order to consider all possible edges in the above graph (K-1) edges Here, K-4 then (4-1)*4 -12 edges. From the following graph, it represent as dense graph because it has maximum number of edges In terms of K, the numbers of correct results for an topological sort that the graph has iv) v) is8