1465. Soit G un graphe non orienté avec au moins trois sommets. Un cycle est un chemin fermé ne passant qu’une seule fois par un sommet. On définit, si elle existe, la maille de G comme la plus petite longueur d’un cycle.

a) Soit d la distance maximale entre deux sommets de G. Montrer que la maille, si elle existe, est majorée par 2d + 1.

b) Montrer qu’un graphe est biparti (c’est-à-dire tel que l’ensemble des sommets se partitionne en deux parties non vides S₁ et S₂ telles que toute arête joigne un sommet de S₁ et un sommet de S₂) si et seulement s’il ne contient pas de cycle de longueur impaire. Qu’en déduire sur la maille d’un tel graphe ?

c) Montrer qu’un graphe à n sommets qui contient au plus un cycle, contient au plus n arêtes.

d) Montrer que la maille d’un graphe à n sommets et au moins n + 1 arêtes est majorée par .

e) Soit G un graphe tel que le plus petit degré δ d’un sommet et la maille m soient supérieurs ou égaux à 3. Montrer que, si m est pair, le nombre de sommets est alors minoré par ((δ - 1)^m⁄2 - 1).

1466. Considérons l’alphabet Σ = {a,b} et Σ^ω l’ensemble des mots infinis sur cet alphabet. À tout mot m = m₁ m₂ … Σ^ω et tout automate déterministe fini = (Q,q₀,F,δ), on associe la suite ρ (m) = (q_k )_kN Q^N vérifiant, pour tout k N, q_k+1 = δ(q_k,m_k).

Un langage L ⊂ Σ^ω de mots infinis est

∙ ∃-reconnaissable s’il existe un automate tel que

L = {m Σ^ω ,  ρ(m) contient au moins un état acceptant} ;

∙ ∀-reconnaissable s’il existe un automate tel que

L = {m Σ^ω ,  ρ(m) ne contient que des états acceptants} ;

∙ ω-reconnaissable s’il existe un automate tel que

L = {m Σ^ω ,  ρ(m) contient un nombre infini d’états acceptants} ;

∙ ω -reconnaissable s’il existe un automate tel que

L = {m Σ^ω ,  ρ(m) contient un nombre fini d’états acceptants}.

a) Montrer que le langage des mots (infinis) contenant au moins deux b est ∃-reconnaissable.

b) Montrer que le langage des mots (infinis) contenant une infinité de b est ω-reconnaissable.

c) Montrer que tout langage ∃-reconnaissable est ω-reconnaissable puis que la réciproque est fausse.

d) Montrer que le langage des mots (infinis) ne contenant pas le facteur bb mais contenant au moins une fois le facteur bab est ω-reconnaissable mais pas ∀-reconnaissable.

e) Exhiber un langage ω-reconnaissable qui n’est pas ω-reconnaissable puis un langage ω-reconnaissable qui n’est pas ω-reconnaissable.

1467. a) Construire un automate déterministe complet minimal sur Σ = {a,b} reconnaissant l’ensemble des mots ayant un nombre pair de a et de b.

On admet le théorème suivant

b) Déterminer tous les langages rationnels L sur l’alphabet Σ = {a} tels que ind(L) ≤ 2.

Un langage rationnel L est composé s’il existe des automates complets ₁, …, _k tels que, pour tout i, |_i | < ind (L) et L = ⋂ L(_i). Un langage rationnel non composé est dit premier.

c) Déterminer si les langages suivants sont composés ou premiers :

i) L₁ = {a, b}^* sur l’alphabet Σ = {a,b} ii) L₂ = {a} sur l’alphabet Σ = {a}

iii) L₃ = {a,b} sur l’alphabet Σ = {a,b}

d) Soit k > 0 un entier qui n’est pas la puissance d’un nombre premier. Montrer que le langage (a^k )^* est composé sur l’alphabet Σ = {a}.

e) Déterminer un algorithme qui, à partir d’un automate tel que L = L() et ind(L) = ||, détermine si le langage L est composé ou premier.

f) Montrer le théorème admis.

1468. Soit G = (S,A) un graphe connexe. Un ensemble de sommets X ⊂ S est dominant si tout sommet est soit dans X, soit voisin d’un sommet dans X.

On note γ(G) le cardinal du plus petit ensemble dominant de G.

a) Calculer γ(P_n), où P_n désigne le chemin à n sommets.

b) Montrer que γ(G) ≤|S|, et exhiber un cas d’égalité.

c) Exhiber une infinité de graphes vérifiant γ(G) ≥|S|.

Un graphe est une griffe s’il est de la forme du graphe biparti complet K_1,3.

d) Montrer que si aucun des sous-graphes induits de G n’est une griffe, alors il existe un ensemble dominant minimal X tel que le graphe induit G[X] est sans arête.

e) Trouver un algorithme calculant γ(G) lorsque G est un arbre.

1469. On s’intéresse à différentes propriétés des permutations σ S_n.

a) Soient x₁ , …, x_p des entiers tels que, pour tout k, 0 ≤ x_k ≤ k. La suite finie (x₁,…,x_p) s’appelle l’écriture factorielle de l’entier n = x_kk!. Montrer que cette écriture existe et est unique pour tout entier naturel n.

b) On représente une permutation σ S_n par le mot σ(1)…σ(n). On appelle ordre de σ le nombre de permutations de S_n dont la représentation est strictement inférieure au mot représentant σ pour l’ordre lexicographique. Donner un algorithme calculant l’ordre de σ.

c) Donner un algorithme calculant la permutation suivant σ selon l’ordre lexicographique de leurs représentations.

d) Pour tout σ S_n , notons X_i(σ) la longueur du cycle de σ contenant l’entier i. Montrer en utilisant une représentation appropriée de σ que :

∀k {1, … , n}, |{σ S_n, X₁(σ) = k}| = (n - 1)!.

e) Donner un algorithme donnant avec une probabilité uniforme une permutation σ telle que X₁ (σ) = k.

1470. Un moniteur est un automate fini déterministe A = (Q,q₀,F,δ) avec deux états puits ⊤ et ⊥ tel qu’il existe un chemin depuis chaque état vers l’un des états puits.

Un langage monitorable est un sous-ensemble de l’ensemble L des mots infinis Σ^ω tel qu’il existe un moniteur tel que pour tout mot fini u Σ^* :

– si δ^* (q₀ , u) = ⊤ alors uΣ^ω ⊆ L ; – si δ^*(q₀,u) = ⊥ alors uΣ^ω ∩ L = ∅.

a) Interpréter la notion de langage monitorable.

b) Déterminer si les langages suivants sur l’alphabet Σ = {a,b,c} sont monitorables et si oui, donner un moniteur avec un maximum d’états accessibles possibles

i) L₁ , l’ensemble des mots contenant une infinité de a,

ii) L₂ , l’ensemble des mots contenant au moins un b,

iii) L₃ , l’ensemble des mots contenant au moins un b mais ne contenant pas de c.

c) Soit L ⊆ Σ^ω . Soit u Σ^* tel qu’il existe un mot v Σ^* vérifiant uvΣ^ω ⊆ L. Montrer que L est monitorable. Reprendre la question avec l’hypothèse uvΣ^ω ∪ L = ∅.

Considérons le théorème suivant :

d) Donner une interprétation de ce théorème.

e) Prouver le théorème.

1471. On considère un jeu où deux joueurs, J₁ et J₂, déplacent un jeton sur un graphe orienté G = (S, A) où S est partitionné en deux ensembles S₁ et S₂. Lorsque le jeton est sur un sommet de S_i , J_i doit le déplacer vers un sommet adjacent extérieurement. L’attracteur Attr_i (X) de X ⊂  S est l’ensemble des positions du jeton pour lesquelles J_i dispose d’une stratégie faisant passer à coup sûr le jeton sur un sommet de X. On fixe enfin F ⊂  X.

a) Déterminer Attr₁(F) dans la configuration suivante.

b) Déterminer un algorithme de complexité O(|S| + |A|) permettant de calculer Attr₁(F) lorsque G est acyclique.

c) Montrer que le jeu des allumettes, où les deux joueurs piochent alternativement 1, 2 ou 3 allumettes dans un paquet jusqu’à épuisement (on considère que celui ramassant la dernière gagne), peut-être modélisé comme un jeu de la forme précédente.

d) tendre l’algorithme de la question b) au cas général.

On considère maintenant le jeu infini où J₁ gagne s’il arrive à faire passer le jeton une infinité de fois par un sommet de F .

e) Montrer que s  S est gagnant pour J₁ si et seulement si J₁ possède une stratégie faisant passer le jeton au moins |S| fois par F depuis s.

f) En déduire une algorithme de complexité O(|S||A|) calculant les positions gagnantes pour J₁ .

g) Montrer que les sommets de Attr₂(Attr₁(F)) sont gagnants pour J₂.

h) En déduire un nouvel algorithme de même complexité que le précédent.

1472. Un semi-anneau est un quintuplet (S,+,⊗,0,1) où S est un ensemble, 0,1 S et

- (S, +) est un monoïde commutatif de neutre 0

- (S, ⊗) est un monoïde commutatif de neutre 1

- ⊗ est distributive sur +.

a) Parmi les quintuplets suivants, lesquels sont des semi-anneaux : i) (N,+,⋅,0,1),

ii) (N , min , ⋅, 0, 1), iii) (N,max,⋅,0,1), iv) ((X),∪,∩, ∅,X), si X est un ensemble ?

Soit Q un ensemble de sommets, I, F ⊂ Q (sommets initiaux, finaux). On dit que G = (Q,γ,I,F) est un graphe orienté sur le semi-anneau (S,+,⊗,0,1) lorsque γ associe à chaque couple (p, q) Q × Q un élément de S, appelé coût. On désigne par chemin un chemin dans un graphe au sens usuel. On étend la définition de coût aux chemins. Si c = x₀…x_n est un chemin, alors γ(c) =

Dans la suite de cette question, on considère un graphe orienté sur le semi-anneau (N,+,⋅,0,1), d’ensemble de sommets {1,…,n}.
Pour tout (p, q) Q² et r {0,…,n}, on définit γ par :

γ =

b) Que représente γ ?

c) Soit Σ un alphabet fini. Donner +, ⊗, 0 et 1 pour que ((Σ^*),+,⊗,0,1) soit un semi-anneau.

d) Utiliser la technique de la deuxième question pour définir le langage (A) reconnu par un automate fini non déterministe A.

e) Définir de même l’expression régulière associée à un tel automate.

Soit G = (Q, γ, I,F) un graphe orienté et n N. On définit Π(n) comme l’ensemble de tous les chemins de longueur n d’un sommet de I à un sommet de F . On définit de plus π(n) par π(n) =

f) Donner un algorithme efficace de calcul de π(n).

1473. On s’intéresse à la résolution d’un système d’inéquations linéaires de la forme (S) :

AX ≤ B, d’inconnue X = t(x₁,…,x_n) Rⁿ, où A _m,n(R) et B R^m.

a) i) Montrer que si le système (S) contient deux inéquations (I₁) et (I₂) avec des coefficients en x₁ respectivement > 0 et < 0, on peut trouver une inéquation (I₀) ne mettant pas en jeu la variable x₁ et équisatisfiable à la conjonction (I₁) ∧ (I₂).

ii) En déduire un algorithme de résolution d’un tel système d’inéquations linéaires.

iii) Quelle est sa complexité dans le pire des cas ?

b) On cherche à améliorer l’algorithme précédent. chaque étape de son exécution permettant de supprimer une inconnue x_i, on générait une nouvelle liste d’inéquations. On va maintenant de plus associer à chaque nouvelle inéquation son historique : la partie de {1,…,n} contenant les indices des inéquations du système (S) de départ dont l’inéquation est combinaison linéaire.

i) Expliquer comment on calcule les historiques.

ii) Montrer qu’on peut, à chaque étape de l’algorithme, ne garder que les nouvelles inéquations d’historique minimal (au sens de l’inclusion).

iii) En déduire une amélioration de l’algorithme précédent. Estimer sa complexité.