Q2. As new links are created and old ones are removed among an existing set of Web pages, thepages move between different parts of the bow-tie structure. (05)(a) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe largest strongly connected component.(b) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe set IN.(c) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe set OUT.
strongly connection component : It is the subgraph of the given graph where each node can be reachable from every other vertex in the selected subgraph
In set : set of all nodes which have an incoming edge incident upon the node
out group: set of all nodes which have an outgoing edge from the node
first question : you can never increase the size of the strongly connected component with deleting an edge you must always add an edge
the largest strongly connected component in the given graph is the 9,14,15 and we can increase the size by adding another edge 9->13
second question: when we add the edge 11->6 we will increase the inset because there is no in edge on node 6 so it is not present in the in set now once we add the 11->6 edge it will be added to inset and the size will be increased
third question :
when we add the edge 2->7 we will increase the out group because there is no out edge from node 2 so it is not present in the out group now once we add the 2->7 edge it will be added to out group and the size will be increased
No comments:
Post a Comment