traverses each edge of exactly once according to its direction such tour is connected and the in-degree equals the out-degree of each always exists if vertex in with vertices and edges is cycle that describe an ( )-time algorithm for finding an euler tour of such digraph - an independent set of an undirected graph ( ,eis subset of such that no two vertices in are adjacent that isif and are in ithen ( ,vis not in maximal independent set is an independent set such thatif we were to add any additional vertex to mthen it would not be independent any more every graph has maximal independent set (can you see thisthis question is not part of the exercisebut it is worth thinking about give an efficient algorithm that computes maximal independent set for graph what is this method' running timec- let be an undirected graph with vertices and edges describe an ( )-time algorithm for traversing each edge of exactly once in each direction - justify proposition - give an example of an -vertex simple graph that causes dijkstra' algorithm to run in ( log ntime when its implemented with heap - with negative-weight edgesgive an example of weighted directed graph but no negative-weight cyclesuch that dijkstra' algorithm incorrectly computes the shortest-path distances from some start vertex - consider the following greedy strategy for finding shortest path from vertex start to vertex goal in given connected graph initialize path to start