Reference no: EM133700410
Assignment - In what follows, a (non-directed) graph has at most one edge between every two vertices (no multi-edge) while an (undirected) multigraph may have several edges between two vertices (multi- edge). A loop is an edge between one vertex and itself (both extremities are identical). A simple graph is a graph without loop. For the following questions, you can use for instance to draw graphs or multigraphs.
Question 1: We would like to compare different AI engines / programs trained to recognise dogs from photographies. The program is fed with a bunch of photographies and is supposed to select those representing a dog. Two popular criteria for the accuracy of such computer programs are precision and recall. The former is defined as the proportion of dogs among all images selected by the system while the latter is the proportion of images selected among those representing a dog. Ideally both should be close to 100% , but this is obviously not the case and it is often a "tug of war" game between both criteria. In our experiment, we have 8 different aprograms with the following results:
|
Program
|
Precision(%)
|
Recall(%)
|
|
A1
|
70
|
80
|
|
A2
|
80
|
75
|
|
A3
|
95
|
80
|
|
A4
|
65
|
85
|
|
A5
|
70
|
55
|
|
A6
|
60
|
60
|
|
A7
|
50
|
50
|
|
A8
|
85
|
90
|
Table 1: Precision and Recall scores
(a) [(K,M,P,E)=(2,1,2,1)] We consider the relation ≤a on N × N defined by:
(a, b) ≤a (a′, b′) <=> (a ≤ a′) ∧ (b ≤ b′) Show that it defines a partial order on N × N.
(b) [(K,M,P,E)=(2,2,1,1)] we use ≤a to compare the different programs based on the corresponding ordered pair (Precision, Recall). Draw the related Hasse diagram. Do we have a minimum element (i.e., worse algorithm)? Minimal elements? Do we have a maximum element (i.e., a nest algorithm)? Maximal elements? Briefly justify.
Question 2: Consider the following degree sequence: {7, 7, 5, 5, 5, 3, 2, 2}.
[(K,M,P,E)=(0.5,1,3,1)] Is it possible to sketch a simple graph that has this degree sequence? If yes, sketch the graph. If not, give a convincing argument why it is not possible.
We recommend to first establish the number of vertices and edges of such a graph, if it exists.
[(K,M,P,E)=(0.5,1.5,1,0.5)] Is it possible to sketch a multigraph without loop and with 1 connected component that has this degree sequence? If yes, sketch the multigraph. If not, give a convincing argument why it is not possible.
[(K,M,P,E)=(0.5,1.5,1,0.5)] Is it possible to sketch a multigraph without loop and with 2 connected components that has this degree sequence? If yes, sketch the multi- graph. If not, give a convincing argument why it is not possible.
[(K,M,P,E)=(0.5,1.5,1,0.5)] Is it possible to sketch a multigraph without loop and with 3 connected components that has this degree sequence? If yes, sketch the multi- graph. If not, give a convincing argument why it is not possible.
[(K,M,P,E)=(0.5,1.5,2,1)] Is it possible to sketch a multigraph without loop and with 4 connected components that has this degree sequence? If yes, sketch the multigraph. If not, give a convincing argument why it is not possible.
Question 3: We consider the graph G10 on vertices {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} with an edge between two vertices if the sum of their labels is a prime. For instance (0, 3), (1, 4), (10, 1) are edges.
[(K,M,P,E)=(1.5,2,1,0.5)] Draw the graphs G10; is it connected?
[(K,M,P,E)=(1.5,1,1,1)] Is G10 Eulerian? Briefly justify. We do not request an Eulerian walk.
[(K,M,P,E)=(1,1,1,0)] The graph G11 is obtained from G10 by adding one vertex labelled 11 and the edges as defined before (sum of labels is a prime). Draw G11.
[(K,M,P,E)=(1.5,1,1,1)] Is G11 Eulerian? Briefly justify. We do not request an Eulerian walk.