THEOREMES DE CARACTERISATION DE CYCLES HAMILTONIENS ET DE CIRCUITS EULERIENS

Eléments de théorie des graphes

Un graphe es t une structure très simple puisqu’il est constitué de points et des lignes continues reliant certains d’entre eux. De manière générale, il permet de représenter la structure, les connexions d’un ensemble complexe en exprimant les relations entre ces éléments ; réseau de communication, réseaux routiers, interaction de diverses espèces animales, circuits électriques. Les points appelés sommets peuvent représenter des individus, des membres, des localités, des opérations, des molécules etc.… et les lignes appelées arcs ou arêtes ou boucles une relation binaire, un lien de parenté, une route, une préférence etc.… Les schémas sont indépendants de l eur signification, ils constituent donc une méthode de pens ée qui permet de m odéliser une g rande variété pour étudier systématiquement leurs propriétés combinatoires le point de vue remonte à Euler qui en 1736 é tudiait la possibilité de parcourir la ville de Königsberg (qui est une partie de notre exposée ) une et une seule fois chacun de ces points qui est le premier résultat formel de la théorie des graphes. Elle s’est pourtant développée depuis la deuxième moitié du 19em e siècle avec Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait etc.… Depuis le début du XXéme siècle, elle constitue une branche à part entière des mathématiques, grâce aux travaux König, Menger, Cayley, puis Berge et d’ErdÖs. E lle présente des liens évidents avec l’algèbre (matrice) la topologie (voisinage), la biologie, la chimie, l’informatique l’électricité et d’autres domaines de la combinatoire. Un graphe orienté représente typiquement un réseau de communication ou encore des relations de domination non réciproque entre personnes etc.… Des outils comme le théorème du flot maximum (Ford et Fulkerson 1962) ou l es algorithmes de transport optimal, ont permis de démontrer simplement une douzaine de résultat théoriques ou pratiques, un autre outil le lemme des chaînes alternées anticipé par Petersen pour démontrer l’existence d’un couplage parfait sur les graphes 3- réguliers, fournit une dém onstration courte et élégante pour d’autres théorèmes d’optimisation. Ce sont e t els outils qui ont motivé la publication d’un nouveau traité sur les graphes (Berge 1958) introduit par Claude Berge sur les hypergraphes ou les arêtes peuvent être de taille arbitraire et non plus seulement de taille deux.Depuis lors, les résultats n’ont cessé de se généraliser et les méthodes de s’améliorer . Les grands problèmes classiques de l a théorie des graphes sont : flots et connectivité (« fiabilité d’un réseau »), couplage (affection) , problème du « postier chinois », problème du « voyageur de c ommerce » ), coloration (le théorème des quatre couleurs ,ensemble absorbant etc.…La résolution de certains de c es problèmes (problème du « postier chinois »,problèmes du « voyageur de commerce ») impliquent très souvent la détermination de cycles Hamiltoniens ou de circuit Euleriens. L’étude de ce mémoire est la recherche d’une meilleure caractérisation de ces objets mathématiques. Dans le chapitre 1 nous rappelons quelques notions de théories des graphes.Dans le chapitre 2 nous allons d’abord citer quelques t héorèmes ou corollaires soient nécessaires ,soient suffisants pour obtenir un gr aphe hamiltonien et enfin exposer quelques propositions nécessaires et suffisantes à la fois. Dans le chapitre 3 on va présenter le célèbre théorème d’Euler (1736) tout en proposant une démarche avec 3 les matrices d’incidence et boucler cette chapitre avec une c omparaison entre un cycle hamiltonien et un cycle eulerien. 2. Graphes non orientés Définition 2.1. Un graphe G = (S, A) est déterminé par la donnée : – d’un ensemble S = {s1, s2 ,…sn } dont les éléments sont appelés sommets ou nœuds . – d’un ensemble A = {a1, a2,…an }⊂ S x S dont les éléments sont des couples de sommets appelés arêtes ou boucles selon la situation . Lorsque a = { x ,y,} ∈ A , on dit que a l’arête de G est d’extrémités x et y, ou que a joint x et y ou que a passa par x et y . Si x = y on dit que a es t une boucle. Un graphe sans boucle est dit graphe simple. Définition 2.2. L’ordre d’un graphe est le nombre de sommets de ce graphe . Définition 2.3. Le degré d’un sommet est le nombre de fois qu’une arête touche à ce sommet. Le degré d’un sommet i est noté par d (i). d (v) = 0 alors le sommet v est isolé . d (v) = 1 alors le sommet v est pendant. Sur une boucle v, d (v) = 2 car en zoomant autour d’elle, on voit une arête qui part et qui revient. Avec le degré des sommets on définit des fonctions de graphes : ∆ (G) = min {d (v) } : degré de sommet le plus bas de G Λ(G) = max. { d (v) } : degré de sommet le plus haut de G Lemme( des poignées de main). Soit G=(S,A) un graphe non orienté : a)La somme de tous les degrés est un nombre pair. C’est le double des arêtes . b)Le nombre de sommets de degré impair est pair Preuve. a) Dans cette somme, chaque arête est comptée deux fois, une au départ et une à l’arrivée (y compris les boucles, vu la convention ci dessus) . b)N le nombre de sommet de degré Soit impair : les degrés valant 2 k1 + 1 ,…………….., 2 kn + 1. Les autres valent k1’……, 2 kn . La somme des degrés vaut : 2( k1 +…………+ kN +k1’ …………..+ km’ ) + N et cette somme est paire d’après a).