L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

Ce problème s'intéresse à la structure cyclique de certains graphes. La première partie porte sur le calcul d'un arbre couvrant et des cycles fondamentaux d'un graphe non orienté. La seconde partie étudie plusieurs algorithmes de calcul d'une base minimale de l'espace des cycles d'un graphe non orienté et pondéré. La seconde partie pourra être largement abordée même si la première n'a pas été complètement résolue.

Préliminaires

Pseudo-programmes, structures de données et algorithmes. Pour les questions demandant d'écrire un pseudo-programme, on utilisera un langage ou pseudo-langage au choix, avec les structures de données (tableaux uni- et multi-dimensionnels, listes, files, piles, etc.) et de contrôle (si, tant que, pour, etc.) usuelles. Les indices d'un tableau tab de taille

vont de 1 à

, et ses éléments seront notés

. Les déclarations de variables ne sont pas imposées. Les questions demandant de donner un algorithme n'imposent pas un pseudo-programme mais une description concise et précise, en français, de l'algorithme. Dans les deux cas, la qualité de la rédaction ainsi que les justifications (correction, coût) seront des éléments d'appréciation.

Estimations de coût. Le coût d'un algorithme ou d'un pseudo-programme est le nombre d'opérations élémentaires qu'il effectue dans le cas le pire : lecture ou écriture dans une variable ou une case de tableau, opération arithmétique (notamment : comparaison, addition, soustraction, multiplication) sur des entiers ou sur des éléments d'un corps, test, ajout ou suppression en tête de liste, empilement ou dépilement dans une pile, etc. On ne cherchera pas à calculer les coûts demandés exactement. Ils seront seulement estimés en ordre de grandeur, avec des expressions du type

, etc., où

sont par exemple des paramètres en entrée de l'algorithme ou du pseudo-programme.

Autres conventions. On note

l'ensemble des entiers naturels. Si

est un nombre réel alors

désigne le plus grand entier inférieur ou égal à

. Pour

, l'entier naturel égal à

sera noté

. Pour un corps K , on note

l'ensemble des matrices à

lignes et

colonnes, dont les éléments sont dans K . Ces matrices pourront être représentées par des tableaux bidimensionnels.

Définitions et notations

Les graphes considérés dans ce problème sont finis et non orientés. Pour

, un graphe (fini, non orienté) à

sommets et

arêtes est un couple (

) où

, l'ensemble des sommets du graphe, est identifié à

, et où

, l'ensemble de ses arêtes, est un sous-ensemble de

de cardinal

. Une arête

sera notée indistinctement (

) ou (

); on dira que

est un voisin de

dans le graphe et que

est un voisin de

dans le graphe.

On appelle chaîne de longueur

reliant

dans le graphe (

) toute suite

de sommets du graphe tels que

pour

. Un graphe est connexe si pour chaque paire

de sommets il existe au moins une chaîne reliant

dans ce graphe. On dira qu'une chaîne est élémentaire si de plus

sont distincts deux à deux.

Une chaîne

dans le graphe forme un cycle élémentaire du graphe si

sont distincts deux à deux. Soient

deux chaînes de même longueur et formant chacune un cycle élémentaire du graphe; s'il existe

tel que, pour

alors on dira que ces deux chaînes forment le même cycle élémentaire.

Soit

un graphe connexe. On appelle arbre couvrant de

tout graphe (

) connexe, sans cycle élémentaire, et tel que

. Étant donnés un arbre couvrant

et une arête

(si elle existe), le
cycle fondamental de

par rapport à

, noté

, est le cycle élémentaire de

obtenu en "fermant" avec l'arête

la chaîne élémentaire reliant

dans

. L'ensemble des cycles fondamentaux de

par rapport à

est

Dans toute la suite,

désigne un graphe connexe à

sommets et

arêtes. On supposera de plus que

est donné par sa structure d'adjacence, c'est-à-dire par un tableau Adj de

listes d'entiers tel que, pour

est la liste (dans un ordre arbitraire) des voisins de

dans

. Les pseudo-programmes et les algorithmes demandés pourront exploiter toutes ces hypothèses sur

Partie 1. Arbres couvrants et cycles fondamentaux

Question 1.1.

(a) Montrer que le nombre de cycles élémentaires de est fini.
(b) Montrer que admet au moins un arbre couvrant.
Montrer que tout arbre couvrant de a exactement arêtes.
Écrire un pseudo-programme SansCycleElem qui, étant donné , détermine si ne contient aucun cycle élémentaire. Pourquoi est-il correct et quel est son coût ?

Question 1.2.

Donner la structure d'adjacence d'un arbre couvrant de pour et .
Écrire un pseudo-programme ArbreCouvrant qui, étant donné , calcule la structure d'adjacence d'un arbre couvrant de . Pourquoi est-il correct et quel est son coût ?

Question 1.3.

Vérifier l'existence et l'unicité de la chaîne élémentaire utilisée à la fin de la partie Définitions et notations pour définir le cycle fondamental .
Étant donné un arbre couvrant de , on note la somme des longueurs des éléments de .
(a) Majorer en fonction de .
(b) On suppose ici que . En calculant la valeur de pour deux arbres couvrants de , montrer que l'ordre de grandeur de dépend de .
(a) Écrire un pseudo-programme Phi qui, étant donné , calcule un ensemble de cycles fondamentaux de (c'est-à-dire pour un arbre couvrant quelconque de ). Pourquoi est-il correct ?
(b) Exprimer, en le justifiant, le coût de Phi en fonction de et de la somme des longueurs des cycles fondamentaux calculés.

Partie 2. Bases minimales de l'espace des cycles

Dans cette partie, on suppose que

possède au moins un cycle élémentaire et qu'il est de plus pondéré. Un graphe est pondéré si à chaque arête

est associé un réel positif ou nul, noté

et appelé poids de l'arête

. Dans un graphe pondéré, le poids

d'une chaîne

est nul si

, et égal à

. De plus, pour deux sommets

d'un graphe pondéré, on définit

de la façon suivante : s'il n'existe pas de chaîne reliant

dans le graphe alors

; sinon,

î à

On note K le corps fini à deux éléments, 0 et 1 . On suppose connu

un arbre couvrant de

, et on numérote les arêtes de

de sorte que

avec

. On appelle support tout sous-ensemble non vide de

. Soit

l'ensemble de tous les sous-ensembles de

; en particulier,

contient

et l'ensemble vide, noté

. On appelle vecteur d'incidence d'un élément

l'unique vecteur

tel que, pour

sinon. On identifiera

au K -espace vectoriel

en identifiant chaque élément de

à son vecteur d'incidence. Pour

, on notera

leur produit scalaire dans la base canonique

: si

avec

pour

, alors

est un cycle élémentaire de

, on le considère dans cette partie représenté par ses arêtes et on écrira

. On appelle cycle de

un cycle élémentaire de

ou une union de cycles élémentaires de

disjoints deux à deux. L'espace des cycles de

, noté

, est le K -sous-espace vectoriel de

engendré par l'ensemble des cycles de

. Le poids d'un cycle

est

, la somme des poids des arêtes qui composent ce cycle; le poids d'une base

est

, la somme des poids des cycles qui composent cette base. Une base minimale de l'espace des cycles de

est une base de

de poids minimal parmi toutes les bases de

Question 2.1.

Soient et .
(a) Soit . Quel sous-ensemble de chacune des trois expressions , représente-t-elle?
(b) Caractériser en termes d'arêtes communes le fait que .
Soit un support. Montrer qu'il existe tel que .
Montrer que est une base de .

On appelle BaseMinimale1 l'algorithme décrit ci-dessous en encadré :

pour i de 1 à N faire
    Si \leftarrow un support tel que }\langle\mp@subsup{C}{k}{},\mp@subsup{S}{i}{}\rangle=0,1\leqk\leqi-
    Ci \leftarrow un cycle de G de poids minimal tel que }\langle\mp@subsup{C}{i}{},\mp@subsup{S}{i}{}\rangle=
fin pour

Dans toute la suite et à l'exception de la question 2.5,

sont spécifiés comme à l'itération

de BaseMinimale1.

Question 2.2.

Dans cette question, on suppose que

ont pu être trouvés par BaseMinimale1 et on étudie certaines propriétés des

Pour , montrer que est linéairement indépendant de .
Montrer que est une base minimale de .

Question 2.3.

On s'intéresse dans cette question au coût du calcul de

indépendamment de

. (On ignorera donc le coût du calcul de

dans toute cette question.)

(a) Soit fixé. Écrire un pseudo-programme Support qui, étant donnés les vecteurs d'incidence des cycles de , calcule le vecteur d'incidence d'un support tel que pour .
(b) Donner en le justifiant le coût de Support. Quel coût total (en fonction de m) obtient-on alors pour avec cette méthode?
(a) Montrer comment calculer en introduisant pour des ensembles de supports qui vérifient les deux conditions suivantes :

pour sont linéairement indépendants;
pour et .
(b) Réécrire l'algorithme BaseMinimale1 de façon à ce que l'itération calcule , et, si . Quel nouveau coût total (en fonction de ) obtient-on pour ?

Question 2.4.

Soit

fixé. Dans cette question, on associe à

et à

le graphe signé

défini de la façon suivante. Le graphe

sommets distincts, obtenus en dupliquant les

sommets de

: pour

, on notera

les deux sommets de

correspondants; de plus, pour toute arête

si alors possède les deux arêtes et , chacune de poids ;
si alors possède les deux arêtes et , chacune de poids .

Soit où et . On suppose de plus que pour tout . Dessiner les sommets et les arêtes de et pour .
Pour donné, soit une chaîne reliant à dans .
(a) Montrer qu'à correspond un cycle de , qu'on notera , tel que et .
(b) On suppose que est représenté de façon partielle par un tableau chaine d'entiers tel que, pour , chaine si , et . Écrire un pseudo-programme qui calcule le vecteur d'incidence de à partir de chaine. Quel est son coût ?
(c) Montrer que si alors et .
On suppose disposer d'un algorithme PlusCourteChaine de coût qui, à partir de , de et d'un sommet de , calcule le couple (distance, chaine) où distance et où chaine est la représentation partielle (définie à la question 2.4.2.(b)) d'une chaîne reliant à dans et telle que .
(a) Écrire un pseudo-programme calculant le vecteur d'incidence de à partir de et . Quel est son coût ?
(b) Conclure en exprimant le coût de l'algorithme BaseMinimale1 en fonction de et .

Question 2.5.

Dans cette question,

désigne un nombre réel tel que

, et on suppose disposer d'un algorithme MulMat de coût

pour multiplier deux matrices de

(a) Soient et avec . Donner un algorithme qui calcule le produit et exprimer son coût en fonction de et .
(b) Soit triangulaire et inversible. Soit . Donner un algorithme qui calcule la matrice telle que , et exprimer son coût en fonction de et .
Soient et dans tels que . Soient des cycles de , soient des supports, et soit la matrice dont la colonne est égale au vecteur d'incidence de si et à celui de si . Pour , on suppose que les trois propriétés suivantes sont vérifiées :

pour ;
;
pour .

On suppose de plus que

sont tels que la matrice

a la structure suivante : pour

, l'élément situé sur la ligne

et la colonne

est nul si

et égal à 1 si

.
(a) Montrer, en introduisant un système linéaire de la forme

avec

deux matrices de

dont on explicitera les éléments, que l'on peut transformer

en un autre ensemble de supports, noté

et tel que

pour

.
(b) Proposer un algorithme MiseAJour qui calcule les vecteurs d'incidence de

à partir de ceux de

. Exprimer son coût en fonction de

.
3. On suppose que

avec

et on fait la même hypothèse qu'à la question 2.4.3.
(a) Proposer un algorithme BaseMinimale2 qui calcule les vecteurs d'incidence d'une base minimale

à l'aide de MiseAJour.
(b) Montrer que le coût de BaseMinimale2 est

. Pourquoi cet algorithme est-il correct ?