1. Consider an undirected random graph on the set of four vertices {A, B, C, D}...

Transcribed Image Text:

1. Consider an undirected random graph on the set of four vertices {A, B, C, D} such that each of the 4 2 = 6 potential edges exists with probability 0.2, independently of the presence/absence of any other edges. Simulate 2000 such random graphs and hence estimate the probability that such a random graph is connected (i.e. that any vertex can be reached from any other.) For example, if edges AC, AD and BD were present, but potential edges AB, BC and CD were absent, the graph would still be connected, since any vertex can still be reached from any other. A B C D 1. Consider an undirected random graph on the set of four vertices {A, B, C, D} such that each of the 4 2 = 6 potential edges exists with probability 0.2, independently of the presence/absence of any other edges. Simulate 2000 such random graphs and hence estimate the probability that such a random graph is connected (i.e. that any vertex can be reached from any other.) For example, if edges AC, AD and BD were present, but potential edges AB, BC and CD were absent, the graph would still be connected, since any vertex can still be reached from any other. A B C D