Département de Formation Premier Cycle Année 2002 – 2003 Session de Janvier 2003 GU : TCA UE : TCA101 Épreuve d’informatique Date : 14 janvier 2003 Durée : 1h30 Tous documents autorisés. Votre voisin n’est pas un document Vous devez répondre directement sur le sujet Épreuve de M Strandh et M Gavoille

Indiquez votre numéro d’\underline{anonymat} : No :

Question 1. Soient G et H les deux graphes dessinés ci-dessous.

G^{s_{0}}  ^{s_{4}} ^{s_{3}} ^{s_{2}}  ^{s_{1}}  H^{s′_{0}}  ^{s′_{4}} ^{s′_{3}} ^{s′_{2}}  ^{s′_{1}}

Cocher les affirmations qui sont correctes :

□ G a des arêtes multiples □ H est un graphe orienté □ G a 18 arêtes □ H a 9 arcs □ G est connexe □ H est fortement connexe □ G est Eulérien □ G a une chaîne ayant 5 arêtes et 5 sommets différents □ s′_{0}, s′_{3}, s′_{2}, s′_{4}, s′_{1} est un chemin de H

Question 2. Le graphe ci-dessous est-il Eulérien ? Si oui, construire une chaîne passant une seule fois par chacune des arêtes. Si non, justifier votre réponse. Justification :

Si x est un sommet d’un graphe, on notera d(x) le degré de x. Pour tout entier n ⩾ 2, on définit K_{n} le graphe ayant n sommets et tel qu’il existe une arête entre toutes paires de sommets disjoints du graphe.

Question 3. Dessiner ci-dessous le graphe K_{4} de sorte que ses arêtes soient des lignes droites et sans que deux arêtes ne se coupent. Si ce n’est pas possible, indiquer pourquoi. Dessin ou explications :

Question 4. Exprimer en fonction de n, le degré d’un sommet x de K_{n} : d(x) = , le nombre d’arêtes de K_{n} : |E(K_{n})| =

Question 5. Donner une condition nécessaire et suffisante sur n pour que K_{n} soit un graphe Eulérien.

\underline{Condition :}

Question 6. On considère l’algorithme suivant que l’on applique sur un graphe G à n sommets et m arêtes. On suppose qu’\underline{avant} d’appliquer l’algorithme, tous les sommets de G sont \underline{non marqués}. Utiliser le type abstrait centré sommets.

pour i allant de 0 à nb_nodes(G)-1 faire
    s = node(G, i)
    degre = nb_edges(s)
    mark_node(s)
    j = 0
    tant que j<degre et que node_marked(s) faire
        e = edge(s, j)
        voisin = follow_edge(s, e)
        si node_marked(voisin)
            alors unmark_node(s)
        j = j+1

Appliquer cet algorithme sur le graphe suivant en indiquant les sommets qui restent marqués \underline{à la fin} de l’agorithme avec la convention : sommet non marqués = sommet blanc, sommet marqué = sommet noir ou de couleur.

s_{10} s_{4} s_{5} s_{6} s_{11} s_{0} s_{1} s_{2} s_{3} s_{7} s_{8} s_{9}

Exprimer en fonction de n et de m la complexité de l’algorithme.

\underline{Complexité :}

Question 7. On dispose d’un programme P que l’on applique sur trois séries de graphes qui ont tous respectivement n, 2n et 4n sommets. On observe que le temps d’exécution de P est en moyenne 40s pour la première série, 70 s pour la seconde et 130 s pour la troisième série. On s’interroge sur la complexité de P. La complexité est-elle O(n) ou O(n^{2}) ? Justifier votre réponse.

Réponse et justification :

FIN.