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 "special" 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 4 iii. In terms of k, exactly how many edges are in the graph? iv. Is this graph dense or sparse? v. In terms of k (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 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 iii. In terms of k, exactly how many edges are in the graph assuming k is even Is this graph dense or sparse? In terms of k (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 4 iii. In terms of k, exactly how many edges are in the graph? iv. Is this graph dense or v. In terms of k (if k is relevant), exactly how many correct results for sparsc? topological sort that does this graph have