Strange Graphs

While trying to come up with one of his stupid Graph Theory problems, Agnishom wrote the following function to generate a random graph:

1
2
3
4
5
6
7
# returns the edgelist of a graph with `n` vertices
def genGraph(n):
    edgeList = []
    for v in xrange(2,n+1):
        u = random.randint(1,v-1)
        edgeList.append((u,v))
    return edgeList

Chris told Agnishom that this algorithm is not really that great and can generate only a particular class of graphs.

Which of the following is the best way to describe these class?

×

Problem Loading...

Note Loading...

Set Loading...