Question: 4) For an Undirected Graph G-(V, E), we defined a Connected Component of G as a connected subgraph Gi-(Vi, Ei) of G that is maximal

4) For an Undirected Graph G-(V, E), we defined a Connected Component of G as a connected subgraph Gi-(Vi, Ei) of G that is maximal Terminology reminder: G is a subgraph of G means that Vi is a subset of V and Ei is a subset of E. "Maximal" means that there's no Gz-(V2, E2) that is also a connected subgraph of G such that G is a subgraph of G2, but G2 has additional vertices or edges (or both) Intuitively, Gi is a Connected Component of G ifyou can't add more vertices and/or edges from G into Gi and get a graph that is still connected. Another way to think about Connected Components is that two vertices u and v are in the same Connected Component if there is a path from u to v (i.e., if v is reachable from u). This definition makes sense for an Undirected Graph because paths in Undirected Graphs have the following properties i. There's a path from any vertex to itself. ii. If there's a path from u to v, then there's a path from v to u. iii. If there's a path from u to v, and there's path from v to w, then there's a path from u to w Paths are reflexive; "v" is a path from vertex v to itself. Paths are symmetridc Paths are transitive Defining Connected Components in a Directed Graph doesn't make sense because directed paths don't have some of the properties listed above. Answer the following questions for directed paths in a Directed Graph G-(V, E). Besides answering YES or NO, be sure to justify each answer clearly. No points for a correct answer if justification isn't provided. a) Are directed paths reflexive1? b) Are directed paths symmetric? c) Are directed paths transitive
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
