Problem Set 2

Problem Set 2

Here is the text of Problem Set 2.

Follow this link to be assigned a graph for the experimental part of the problem set.

Please email Dan if this server gives you an error.

You can find all of the graphs here.

Follow this link to submit a file with the vertices in your tentacles.

This file should just consist of a list of the number of the vertices, separated

by whitespace.  It could look like this:

1 2 10 43 101 ...

or like this

1 

2

10

43 

101

...

The server should then tell you how many vertices it found in your file.

Some students have asked me about the fact that I suggest you remove the vertices in once tentacle before finding another.  This causes some graph packages to renumber the vertices.  In this case, I suggest that you just remove the edges.  Note that the union of the tentacles you find this way will be a union of tentacles in the original graph:

if there are no edges connecting the tentacles you have found, then they are clearly all tentacles in the original graph.  On the other hand, if some of them are connected by edges, then they become one big tentacle (as long as they don't total to more than one-third of the vertices)