Outward Orientation: Let G = (V,E) be a given connected undirected graph. We say G is...

 

Transcribed Image Text:

Outward Orientation: Let G = (V,E) be a given connected undirected graph. We say G is outward orientable if it is possible to direct the edges of G so that in the resulting directed graph = (V,E) every vertex has positive out-degree. If so, we say G is an outward orientation of G. a) [2%] Show an outward orientation of the graph below by drawing a direction on each edge. b) 14% ] Show that if G is outward orientable, then |VISIEI. c) [14% ] Suppose | VISIEI. Using Depth First Search, design and analyze a linear time algorithm that outputs the adjacency list structure of an outward orientation of G. You may continue your answer on the next page. 6 Outward Orientation: Let G = (V,E) be a given connected undirected graph. We say G is outward orientable if it is possible to direct the edges of G so that in the resulting directed graph = (V,E) every vertex has positive out-degree. If so, we say G is an outward orientation of G. a) [2%] Show an outward orientation of the graph below by drawing a direction on each edge. b) 14% ] Show that if G is outward orientable, then |VISIEI. c) [14% ] Suppose | VISIEI. Using Depth First Search, design and analyze a linear time algorithm that outputs the adjacency list structure of an outward orientation of G. You may continue your answer on the next page. 6