Télécharger le fichier original (Mémoire de fin d’études)
Dénombrement de CH passant par k arêtes adjacents ou pas
Nous supposons dans cette section que l es arêtes ne peuv ent former que des chaînes. Soit Hkm l’ensemble de ces k arêtes et m le nombre de chaînes composant
m Hkm . Supposons que chaque chaîne est de longueur ki ; Alors k=i∑=1ki .
Nous distinguons plusieurs cas et sous- cas ; nous allons étudier ici le cas particulier où toutes les chaînes sont de longueur impaire c’est à dire que pour tout entier i tel que 1 ≤ i ≤ m ; ki = 2pi +1.
m m m 2 pi+m=k ce qui donne :
Donc k peut s’écrire : k= ∑ ki ∑ (2 p1+1)= ∑ i=1 i=1 i=1 k-m = ∑ (2pi ) est un entier pair. Dans ces conditions ; nous remplaçons chaque chaîne i par une arête (ui vi) ; où u i et vi sont les extrémités de cette chaîne nous obtenons un graphe réduit biparti complet tel que :
| Sn,1 | = | Sn,2 | = n – k−m = 2n−k+m = n’
Ainsi Hkm est réduit à Hm = { u1v1 ; u2 v2 ; – – – umvm } de cardinal m. Nous sommes dans les conditions d’application du t héorème 6 pour le graphe complet Kn’n’ et Hm on obtient la formule suivante : M(Hkm) = ( 2n−k+m )! ² (2n−k−1)! ; 2n ≥ k+m ≥ 0.
(2n−k−m)! Remarquons que cette formule est une généralisation du théorème 6 et de l a formule a) c ar en posant m = 1 on a k = 2p+1 et M(H2p+1) = (n-p-1 )! ² on retrouve la formule a) De même en posant m = k alors les arêtes de Hk sont non adjacentes on a M(Hk) = (n-k)! ² (2nn−k−k1)! n ≥ k. On retrouve le théorème 6. (2 −2 )!
Dénombrement de CH empruntant k arêtes et évitant m arêtes
Nombre de CH évitant une arête
Posons M( ij ) est le nombre de C.H évitant l’arête (ij). Avec i ∈ Sn,1 et j ∈ Sn,2;
Proposition 8 Le nombre M( ij ) de cycles hamiltoniens de K n,n évitant une arête (ij) est :
M( ij ) = 12 (n-1)! ²(n-2).
Preuve. On a : M( ij ) + M( ij ) = M (Kn;n )
Par soustraction, M( ij ) = M(Kn,n ) – M(ij) d’ après les résultats précédents on
obtient :
M( ij ) = 12 ( n-1 )! ²( n-2 )
Nombre de CH empruntant k arêtes et évitant une autre
Il existe plusieurs cas et sous-cas à ét udier suivant la parité de k et suivant la position des k arêtes par rapport à (ij) ; la méthode est la même dans tous les cas ; il suffit d’écrire la relation suivante : M(Hk-1 ; ij ) + M(Hk-1 ; ij ) = M(Hk ).
Exemple 1.5 Soit à déterminer le nombre de CH empruntant k arêtes adjacentes formant une chaîne élémentaire et évitant une autre adjacente à cette chaîne par un de c es extrémités. Nous distinguons deux sous-cas suivant la parité de l’entier naturel k.
a) Si k = 2p+1 ; on a :
H k ∪ {ij} est une chaîne de longueur paire égale à 2p+2
Et d’autre part : M (H2p+1 ; ij ) + M (H2p+1 ; ij ) = M(H2p+1 ). M (H2p+1 ; ij ) = M(H2p+1) – M(H2p+2)
D’après les résultats précédents nous avons :
M(H 2p+2) = ( n-p-2 )!( n-p-1 )! si k = 2p+2
M(H 2p+1) = (n-p-1)! ² si k = 2p+1
D’où M(H2p+1 ; ij ) = (n-p-2)! ²(n-p-1 )( n-p-2 ).
a) Si k = 2p On a en appliquant la même méthode ; M(H2p; ij ) = M (H2p) – M (H2p+1 ) = (n-p-1 )(n-p-1)!²
Nombre de CH empruntant k arêtes et évitant m arêtes
Nous s upposerons dans cette section que l es arêtes de H k ∪Hm sont toutes non adjacentes et posons M( H m ; Hk) le nombre de CH empruntant Hk et évitant Hm
Proposition 9 Le nombre de CH empruntant k arêtes et évitant m, formant un
ensemble de (k+m) arêtes de Kn,n noté M( m ;Hk ) est égal à :
H m i
M( m ;H k) = ∑ (-1 ) m- i Cm (n-k-m+i)!² (2n−2k−m+i)! (θ)
H
(2n−2k−2m+2i)!
i=0
Preuve. D’après la proposition 5 on a :
m i
M( m ;H k)= ∑ (-1 ) m- i Cm M( Hk+m-i )
H
i=0
D’autre part on a : M( H k+m-i ) = (n-k-m+i)!² (2n−2k−m+i)!
(2n−2k−2m+2i)!
D’où le résultat énoncé.
5.4 Nombre de CH évitant m arêtes non adjacentes
En posant Hm l’ensemble de ces m arêtes et M( H m ) le nombre de C.H évitant Hm ; ce nombre est donné par la proposition suivante :
Proposition 10 M( H m ) = ∑ (-1 ) m- i Cm (n-m+i)!² (2n−m+i)!
m i
i=0 (2n−2m+2i)!
Preuve. En posant k = 0 dans la formule (θ) On a immédiatement le résultat. En particulier pour m = 1 on M( ) = ( n-1 )! ²( n-2 ) ij Pour m = n ; on obtient le nombre de CH évitant un couplage parfait de Kn,n ; Il est n i égal à : M( n ) = ∑ (-1 ) n- i Cn ( i )! ² (n+i)! .
H
i=0 (2i)!
Nous avons étudié les C H évitant des arêtes qui ne forment que des chaînes dans nos études précédentes de ce chapitre. En ce qui concerne les arêtes formant des fourches ou des chaînes de longueur inférieure à n nous pouvons appliquer la méthode algébrique déj à ét udiée au c hapitre 2.Dans la section suivante nous allons étudier le dénombrement des CH disjoints au sens des arêtes. Dénombrement des CH disjoints de Kn,n On cherche très souvent à recouvrir l’ensemble des arêtes du graphe par un nombre minimal de c haînes di sjointes ; d’ où l’intérêt de dénom brer les C H di sjoints. Notons Md(Kn,n) le nombre de ces CH. Il est donné par le théorème suivant :
Théorème 7 Soit Kn,n le graphe complet et Md(Kn,n ) le nombre maximum de CH disjoints qu’on peut former avec les arêtes de Kn,n est :
Md(Kn,n ) = [ n ] Preuve. Nous allons démontrer le théorème par éliminations successives de CH
de Kn,n . Posons :
– Kn,n = Gn
– Ci : le cycle hamiltonien éliminé à l’étape i de la récurrence i
– Gn-2i =Gn \{ ck } le graphe réduit obtenu en éliminant tous les CH des étapes 1à k =1 i.
Table des matières
Introduction
chapitre1: Eléments de théorie des graphes
1 Concepts de graphe
1.1 Définitions
2 Représentation de graphe
2.1 Représentation graphique
2.2 Représentation matricielle Erreur ! Signet non défini.
3 Manipulation de graphes
4 Couplage parfait
5 Connexité de graphe
6 Graphe complet Kn
7 Graphe biparticomplet Kn,n
8 Cycles hamiltoniens
Chapitre 2: Dénombrement des cycles hamiltoniens de Kn
1 Nombre total de cycles hamiltoniens de Kn
2 Dénombrement de CH empruntant k arêtes ; (k≥1)
2.1 Nombre de CH empruntant une arête
2.2 Nombre de C.H empruntant k arêtes non adjacentes
2.3 Nombre de CH empruntant k arêtes adjacentes
2.4 Nombre de CH empruntant k arêtes adjacentes ou pas
3 Dénombrement de CH empruntant k arêtes et évitant arêtes
3.1 Nombre de cycles hamiltoniens évitant une arête ( ij )
3.2 Nombre de CH empruntant k arêtes et évitant ( ij )
4 Amélioration
4.1 Nombre de CH empruntant un ensemble Ak et évitant Ah
4.2 Nombre de CH évitant Hm arêtes
5 Méthode algébrique
5.1 Présentation de la méthode
5.2 Exemple d’application
6 Dénombrement des CH disjoints de Kn
Chapitre 3: Dénombrement de cycles hamiltoniens de Kn, n
1 Nombre total de cycle hamiltoniens de Kn, n
2 Nombre de CH de Kn, n empruntant k arêtes nonadjacentes
2.1 Nombre de CH passant par une arête (ij)
2.2 Nombre de C.H de Kn, n passant par n arêtes non adjacentes
2.3 Nombre de C.H de Kn, n passant par k arêtes non adjacentes
3 Dénombrement des CH de Kn, n passant par k arêtes adjacentes
4 Dénombrement de CH passant par k arêtes adjacents ou pas
5 Dénombrement de CH empruntant k arêtes et évitant m arêtes
5.1 Nombre de CH évitant une arête
5.2 Nombre de CH empruntant k arêtes et évitant une autre
5.3 Nombre de CH empruntant k arêtes et évitant m arêtes
5.4 Nombre de CH évitant m arêtes non adjacentes
6 Dénombrement des CH disjoints de Kn, n
Conclusion
Annexe
Analyse combinatoire
Bibliographie
Résuméّ
