Due: April 15, 2019 Instructions: Complete the assignment on a separate sheet of paper. Show all ...
Due: April 15, 2019 Instructions: Complete the assignment on a separate sheet of paper. Show all work, write tull sentences, and justify all steps and conclusions unless told otherwise. You may use a computer as an aid, but be sure to include supporting work. 1. Is there a path of length 5 from a to d? If so, given an example. Is this path simple? 2. For each of the items below, write a paragraph addressing each question. (a) Create a graph (directed or undirected) with at least 5 vertices that describes some aspect of your life (travel, social network, etc.) Is there something interesting about your graph that you had not thought of before? (b) The Oracle of Bacon (https://oracleofbacon.org/) is a website that finds the distance between two actors in a large graph. Two actors are connected in the graph if they have appeared in the same movie. Can this graph be a multigraph? What would that mean? If so, try to give an example. (c) Create a complete graph based on 4 locations, K4, that you travel to on a regular basis. For each edge on the graph, add a weight equal to the travel time between the locations represented by the vertices. Find a Hamiltonian cycle where the sum of the edge weights is minimized. What does this Hamiltonian cycle represent?
Due: April 15, 2019 Instructions: Complete the assignment on a separate sheet of paper. Show all work, write tull sentences, and justify all steps and conclusions unless told otherwise. You may use a computer as an aid, but be sure to include supporting work. 1. Is there a path of length 5 from a to d? If so, given an example. Is this path simple? 2. For each of the items below, write a paragraph addressing each question. (a) Create a graph (directed or undirected) with at least 5 vertices that describes some aspect of your life (travel, social network, etc.) Is there something interesting about your graph that you had not thought of before? (b) The Oracle of Bacon (https://oracleofbacon.org/) is a website that finds the distance between two actors in a large graph. Two actors are connected in the graph if they have appeared in the same movie. Can this graph be a multigraph? What would that mean? If so, try to give an example. (c) Create a complete graph based on 4 locations, K4, that you travel to on a regular basis. For each edge on the graph, add a weight equal to the travel time between the locations represented by the vertices. Find a Hamiltonian cycle where the sum of the edge weights is minimized. What does this Hamiltonian cycle represent?