A graph is something that looks like this. It has vertices, and edges. Each edge connects two vertices. It is used to model various things where there are "connections". For example, it could be cities and roads between them, or it could be the graph of friendship between people: each vertex is a person and two people are connected by an edge if they are friends. There is no interaction between edges that intersect in the middle. Part I: Question 18 1. How many vertices are there in the above graph? How many edges? (0.3pt) 2. What is the order of this graph? (0.3pt) 3. Can you list the vertices of the graph? Can you list the connections? (this is like giving the 'friend list' for each person) ( 0.4pt) 4. In the above graph, how many vertices of degree 1,2,3,4,5 are there? ( 1pt) 5. Make a graph with 5 vertices where each vertex has degree 2. Can you make a graph with 5 vertices where each vertex has degree 3 instead of degree 2 . Is this possible? Why? (1 pt) A clique is a group of vertices that are all connected to each other (e.g. a group of people who are all friends with each other). A k-clique in a graph is a clique with k people in it. 6. How many 2-cliques are there in the above graph? How many 3-cliques? How many 4cliques? (1 pt) 7. List 4 paths that go from vertex 1 to vertex 6?(0.5pt) 8. What is the length of the shortest path from vertex 1 to vertex 6 ? How many edges does it have? (0.5pt) A graph with n vertices where every two vertices are connected to each other is called a fully connected graph. Also called a Kn (everyone's friends, in fact best friends) 9. Can you draw aK5,aK6 ? Think about how many edges do you need to draw for each. 10. In Kn, how many edges are there? Part III: Question 11 - 13 (3 pts) 11. You are visiting the Guggenheim Museum in New York City. Consider representing the museum as a graph where the works of art are the vertices and paths between adjacent works of art are the edges. We want to see each work of art exactly once. Would this path be represented by an Euler circuit or a Hamiltonian circuit? 12. Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex L. a. List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends. b. What is the total weight along the Hamiltonian circuit? Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex N. a. List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends. b. What is the total weight along the Hamiltonian circuit? A graph is something that looks like this. It has vertices, and edges. Each edge connects two vertices. It is used to model various things where there are "connections". For example, it could be cities and roads between them, or it could be the graph of friendship between people: each vertex is a person and two people are connected by an edge if they are friends. There is no interaction between edges that intersect in the middle. Part I: Question 18 1. How many vertices are there in the above graph? How many edges? (0.3pt) 2. What is the order of this graph? (0.3pt) 3. Can you list the vertices of the graph? Can you list the connections? (this is like giving the 'friend list' for each person) ( 0.4pt) 4. In the above graph, how many vertices of degree 1,2,3,4,5 are there? ( 1pt) 5. Make a graph with 5 vertices where each vertex has degree 2. Can you make a graph with 5 vertices where each vertex has degree 3 instead of degree 2 . Is this possible? Why? (1 pt) A clique is a group of vertices that are all connected to each other (e.g. a group of people who are all friends with each other). A k-clique in a graph is a clique with k people in it. 6. How many 2-cliques are there in the above graph? How many 3-cliques? How many 4cliques? (1 pt) 7. List 4 paths that go from vertex 1 to vertex 6?(0.5pt) 8. What is the length of the shortest path from vertex 1 to vertex 6 ? How many edges does it have? (0.5pt) A graph with n vertices where every two vertices are connected to each other is called a fully connected graph. Also called a Kn (everyone's friends, in fact best friends) 9. Can you draw aK5,aK6 ? Think about how many edges do you need to draw for each. 10. In Kn, how many edges are there? Part III: Question 11 - 13 (3 pts) 11. You are visiting the Guggenheim Museum in New York City. Consider representing the museum as a graph where the works of art are the vertices and paths between adjacent works of art are the edges. We want to see each work of art exactly once. Would this path be represented by an Euler circuit or a Hamiltonian circuit? 12. Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex L. a. List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends. b. What is the total weight along the Hamiltonian circuit? Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex N. a. List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends. b. What is the total weight along the Hamiltonian circuit
