Question

1. You will be asked questions about graphs. The graphs are provided formally. To answers the questions, it may help to draw the graphs on a separate sheet. a Consider the graph (V, E), V = {a,b,c,d) and E = {{a,d}, {b,d}, {c, d}}. This graph is directed/undirected This graph is a tree y/n. If yes, the leafs are: This graph is bipartite y/n. If yes, the partitions are: a, d, b, c is/is not a path in this graph. If not, the edge E. b Consider the graph (V, E), V = {a,b,c, d, e, f} and E = {{a,b}, {a,c}, {a,d}, {a, e}, {b,c}, {b, f},{c,d}, {c, e},{d, e}, {e, f}} This graph is planar y/n. If yes, a planar embedding is: This graph is a complete graph y/n. The degree of c is: , and of d is: a,c, b, f is/is not a path in this graph. If not, the edge_ CE. Does this graph have an Euler path? Yes, namely: / No, because: c Consider the graph (V, E), V = {a,b,c,d) and E = {(a,3,b), (a, 1, d), (6, 4, c), (d, 7, c), (C, 2, a)}. This graph is oriented y/n. If not, because the edges and_ are in E. This is a directed acyclic graph y/n. If not, is a circuit in the graph. There is a path of length <8 visiting all vertices y/n. If yes, the path is: d Consider the graph (V, E), V = {a,b,c, d, e, f, g, h, i} and E = {(c, a),(c,b), (d, c), (d, e), (e, f), (e,g),(g, h), (9, i)}. This graph is a tree y/n. If yes, the root is: and the leafs are: This is a directed acyclic graph y/n. If not, is a circuit in the graph. This graph is not strongly connected. We must add at least directed edges to E to make it strongly connected. e Consider the graph (V, E), V = {0, 1, 2} x {0, 1, 2} and E = {{{n, m), a, (k, 2))|(n, m) € V, (k, l) € V, n + m = k+l} {[(n, m), a, (k, l)(n,m) € V,(k,l) EVn-m=k-l}. This graph has _vertices and ____ directed edges. The largest strongly connected component in this graph has_ vertices and ___ directed edges. There is a/is no path from (2, 1) to (0,1). If yes, a path is:

Answer 1

he The edge of the graph has a speche direction. . Hence, it is directed} . one way to make an edge direction less, to put both way direction. (ad) GE but (da) & E, ülmakes the graph dirchiond. Here b) It hem ho cycle but it is not connected , :. It is not a tree. c) It is bipartite. . d) a, a, b, c in not a path. @b} &E, 6C)&E.