190Assignment5
Assignment 5
1. (Mindscape 8 and 9, Chapter 5.3 of text)
- (a)Take a connected graph G and add a vertex in the middle of an existing edge of G, making two edges out of one. What happens to V - E + F? Explain why.
When a vertex is added to an existing edge, the number of edges increases by one, and the number of vertices also increases by one. This preserves the properties of the equation for the part "V - E". The vertices and the edges are the only parts of the graph effected. The V increases by one and the E also increases by one. (V+1) - (E+1) is the same as V-E and so there is no effect on the overall equation.
- (b) Is it possible to add an edge to a graph and reduce the number of regions? Why or why not? Is it possible to add an edge and keep the same number of regions Why or why not?
It is not possible to add an edge to the graph and reduce the number of regions. Either both ends of the new edge are attached to existing vertices or one end of the new edge is attached to an existing vertex and the other end is a new vertex.
- Case one:
If both ends of the new edge are attached to existing vertices, then assuming there is already a connected graph, a new region is added.
- Case two:
If only one end of the new edge is attached to an existing vertex, then there is no change in the number of regions.
As such, neither of the two possible cases allow for the number of regions to be reduced and it can be said that it is not possible to reduce the number of regions by adding an edge.
2. (Mindscape 2, 3 and 30, Chapter 5.4 of text).
- (a). What is the unknot?
The unknot is a loop which can be represented on a 2D plane without any crossings.
- (b). Count the crossings in each knot below.
3,0,5
- (c). Suppose you are given pictures of two knots. If they have a different number of crossings, then must they be different knots? If so, explain; if not, provide different pictures of the same knot with different numbers of crossings.
If two knots have the same number of crossings in a picture it does not necessarily mean that they have the same number of crossings. A simple example of this can be shown with the unknot. The unknot has a total of 0 crossings. This is clear when drawn as a circle "O". If the unknot is twisted by 180 degrees at one end, then the number of visible crossings increases to one. This is still the same knot, however now it resembles an "8" which is depicted with 1 crossing.
3. (Mindcapes 11 and 12, Chapter 5.2 of text)
Use the edge identification diagram of a Mobius band to
- (a) find out how long a band we get when we cut the Mobius band along the centre line.
We get a mobius strip with twice the perimeter. Where the origonal perimeter has a length of unit one. The cut strip has a perimeter of length two.
- (b) find the lengths of the two bands we get when we cut the Mobius band by hugging the right edge.
By cutting a mobius band and hugging the edge, we get one band which has the same length as the origonal band, and one which has twice the length of the original band.
In each case, give the lengths in terms of the length of the original Mobius band.