7 août 20193 août 2020 Bastien Pasdeloup Can a complete graph be a tree? No, never. Yes, if the order of the graph is an odd number. Yes, if the order of the graph is 1 or 2. Consider a graph G that contains the edges {u, v}, {u, w} and {v, w}. What can you say about the sequence ({u, v}, {v, w}, {w, u})? It is not a cycle, because a cycle is a sequence of vertices, not of edges. It is not a cycle, because {w, u} is not an edge of the graph. It is a cycle. What is the size of a graph with the following adjacency matrix?\[\begin{pmatrix}0 & 1 & 0 & 0 \\1 & 0 & 1 & 0 \\0 & 1 & 0 & 1 \\0 & 0 & 1 & 0\end{pmatrix}\] 3. 4. 6. Let's consider a list with 10 elements. How many elements have to be accessed to reach the 6th element? 6. 1. 10. We use lists to store the neighbors of vertices of a complete graph of order 25. How many elements do such lists contain? 5. 24. 625. Imagine that we want to represent a graph containing many vertices in memory. We know that this graph has very few edges. What data structures are adapted? An array. A list. A dictionary. Consider the following problem: we are given a list of routers and proximities between some of these routers. Each router can be associated with one frequency, with the limit that two routers that are in proximity should not be associated with the same frequency. The aim is to find the minimum number of distinct frequencies that have to be chosen in order to solve the problem. What would be the good way to go about solving this problem? Find a way to formalize the problem, find a solution to solve the formalized problem, then code the solution. Find a solution to solve the problem, code it, then search for possible other solutions in the literature. Code a first solution, write its specification, then find an adequate formalism to express the problem. Time is Up!