MO412 Exercises - Graph Algorithms by Daniel Hosomi

   Question 4 - Consider the the Barabási-Albert model and its context, choose the wrong alternative: a) This graph model generate graphs with vertex degree distributions correspondent to the power law.  b) The average shortest path distance in the Barabási-Albert model graph increases approximately logarithmically with the graph size. c) In a Barabási-Albert model graph, when a new vertex is added to the network the probability of connection with other vertices is proportional to the other vertices degree. d) Barabási-Albert graphs have the same properties of Scale-Free graphs. e) None of the above Original idea by: Daniel Hosomi

  Question 3 - Consider the the Scale-Free property and its context, choose the wrong alternative: a) The WWW is an example of a Scale-Free graph. b) Random Networks usually have a scale of node degree (an average degree among all nodes that is similar to the degree of every node on the network). c) Scale-Free graphs node usually have different degrees and the ones with the higher degrees are called HUB's.  d) None real network is a Scale-Free graph. e) None of the above Original idea by: Daniel Hosomi

    Question 2 - Consider the BFS algorithm, choose the wrong alternative: a) The algorithm can be implemented using a data structure similar to a Queue. b) The BFS is a base algorithm to others like Tarjan's Algorithm (to find bridges and articulation points). c) The BFS follows the FIFO order (the first node visited in the BFS is the first to be fully processed). d) The BFS algorithm finds the shortest path between its origin vertex and every other node in the graph (considering that the graph is not pondered). e) None of the above Original idea by: Daniel Hosomi

  Question 1 - Consider the DFS algorithm, choose the wrong alternative: a) The algorithm can be implemented using a data structure similar to a Stack. b) The DFS is a base algorithm to others like Tarjan's Algorithm (to find bridges and articulation points). c) The DFS follows the LIFO order (the last node visited in the DFS is the first to be fully processed). d) The DFS algorithm finds the shortest path between its origin vertex and every other node in the graph (considering that the graph is not pondered). e) None of the above Original idea by: Daniel Hosomi