loadingPage en cours de chargement
    ACCUEIL | TÉLÉCHARGER | QCM | DON | ANNONCES | CHAT | FORUM | LIVRE D'OR | PARTENAIRES | CONTACT | BLOG
 
  Rechercher
  separation
  Introduction
  Arithmétique
  Algèbre
  Analyse
  Géométrie
  Mécanique
  Électrodynamique
  Atomistique
  Cosmologie
  Chimie
  Informatique Théorique
  Maths. Sociales
  Ingénierie
  separation
  Biographies
  Références
  Liens
  separation
  Humour
  Serveur d'exercices
  separation
  Parrains
21 connectés
News News :: Erreur Erreur :: Statistiques Visiteurs :: ClearType ClearType :: Imprimer Imprimer :: Bookmark and Share

Géométrie

TRIGONOMÉTRIE | GÉOMÉTRIE EUCLIDIENNE | GÉOMÉTRIES NON-EUCLIDIENNES
GÉOMÉTRIE PROJECTIVE | GÉOMÉTRIE ANALYTIQUE | GÉOMETRIE DIFFÉRENTIELLE
FORMES GÉOMÉTRIQUES | THÉORIE DES GRAPHES

27. THÉORIE DES GRAPHES

Dernière mise à jour de ce chapitre: 2017-08-06 17:23:29 | {oUUID 1.784}
Version: 3.2 Révision 8 | Avancement: ~90%
viewsvues depuis le 2012-01-01: 10'722

Table des matières LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

L'histoire de la théorie des graphes (ou des "complexes cellulaires") débute peut-être avec les travaux d'Euler au 18ème siècle et trouve son origine dans l'étude de certains problèmes, tels que celui des ponts de Königsberg (les habitants de Königsberg se demandaient s'il était possible, en partant d'un quartier quelconque de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à leur point de départ), la marche du cavalier sur l'échiquier ou le problème du coloriage de cartes et du plus court trajet entre deux points.

La théorie des graphes s'est alors développée dans diverses disciplines telles que la chimie (isomères), la biologie, les sciences sociales (réseaux de transports), gestion de projets (C.P.M.), informatique (topologie des réseaux, complexité algorithmique, protocoles de transferts), la physique quantique, etc. Depuis le début du 20ème siècle, elle constitue une branche à part entière des mathématiques, grâce aux travaux de König, Menger, Cayley puis de Berge et d'Erdös. Cette branche des mathématiques a connu un grand regain d'intérêt suite à l'émergence des réseaux sociaux Internet dont les connexions entre "amis" et "suiveurs" constituent des graphes dont l'analyse topologique et statistique peut nous apprendre de nombreuses choses.

De manière générale, un graphe permet de représenter la structure, les connexions d'un ensemble complexe en exprimant les relations entre ses éléments: réseau de communication, réseaux routiers, interaction de diverses espèces animales, circuits électriques, ...

Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété de problèmes en les ramenant à l'étude de sommets et d'arcs.

Les derniers travaux en théorie des graphes sont souvent effectués par des informaticiens, du fait de l'importance que revêt l'aspect algorithmique dans leur domaine (voir le début du chapitre de Méthodes Numériques pour un petit exemple).

Effectivement, il s'agit essentiellement de modéliser des problèmes. Nous exprimons le problème en termes de graphes de sorte qu'il relève d'un problème de la théorie des graphes que nous savons le plus souvent résoudre car rentrant dans une catégorie de problèmes connus.

Les solutions de problèmes de graphes peuvent être faciles et efficaces (le temps nécessaire pour les traiter informatiquement étant raisonnable car ils dépendent polynomialement du nombre de sommets du graphe) ou difficiles (le temps de traitement étant alors exponentiel) auquel cas nous utilisons une heuristique, c'est-à-dire un processus de recherche d'une solution (pas forcément la meilleure).

Si la théorie des graphes connaît un assez grand engouement ces 30 dernières, peut-être est-ce dû au fait qu'elle ne nécessite pas dans ses concepts élémentaires de bagage mathématique considérable. Effectivement, il suffit d'avoir parcouru les chapitres de Probabilités, de Théorie Des Ensembles et d'Algèbre Linéaire ainsi que de Topologie présentés sur le site pour déjà se sentir à l'aise avec les différentes définitions.

Nous allons introduire le vocabulaire de base de la théorie des graphes. Les termes employés sont ceux du langage commun de la géométrie euclidienne (et malheureusement ils sont aussi en grand nombre...).

Définitions:

D1. Un "graphe" (ou "polygraphe") G est un couple equation constitué d'un ensemble X non vide et fini (les sommets), et d'un ensemble E (les arêtes) de paires d'éléments de X reliés par un segment de droite ou autrement dit (...) d'une partie du produit cartésien equation (cf. chapitre de Théorie Des Ensembles).

Remarque: Un graphe est souvent noté en français G=(S,A) où le S est la première lettre du mot "Sommet" et A la première lettre du mot "Arêtes".

L'ensemble des sommets est noté G(X) et l'ensemble des arêtes G(E).

Un graphe est dit "graphe planaire" quand nous pouvons le représenter dans un plan sans qu'il y ait intersection d'arêtes.

Maintenant, montrons que si F est le nombre de faces d'un graphe planaire (compte aussi pour une face la face extérieure infinie), A son nombre d'arêtes et S son nombre de sommets, nous avons alors:

equation   (27.1)

qui est la relation connue sous le nom de "formule d'Euler" ou "théorème de Descartes-Euler" (démonstration après l'exemple) et qui nous sera utile plusieurs fois sur ce site (dans le présent chapitre et lors de notre étude des polyèdres dans le chapitre sur les Formes Géométriques).

exempleExemple:

Un graphe à 2 faces (la face en gris clair est la face extérieure infinie), 4 sommets et 4 arêtes:

equation
Figure: 27.1 - Graphe à 2 faces, 4 sommets et 4 arêtes

Démonstration:

Nous démontrons cette formule en effectuant une récurrence (cf. chapitre de Théorie De La Démonstration) sur la différence S:

D'abord, la formule est vraie pour:

equation    (27.2)

car, dans ce cas, le graphe est un arbre donc il n'a qu'une seule face (la face extérieure), donc equation.

equation
Figure: 27.2 - Arbre avec une arête et 2 sommets

Donc:

equation   (27.3)

Puis, prenons un graphe connexe (voir définition plus loin) contenant au moins un cycle G (la figure ci-dessous est un exemple de graphe avec 3 cycles):

equation
Figure: 27.3 - Graphe avec au moins un cycle

Si nous retirons une arête e à ce cycle, nous devrions pouvoir alors par récurrence appliquer au graphe equation la même formule si elle est juste. Effectivement, le graphe amputé de l'arête aura F faces, S sommets et A arêtes et donc la formule:

F - A + S = 2   (27.4)

si nous lui remettons l'arête alors nous écrirons:

(F + 1) - (A + 1) + S = F - A + S =2   (27.5)

equationC.Q.F.D.

D2. Les éléments de X sont donc les "sommets" du graphe G, ceux de E sont les "arêtes" du graphe G (effectivement, une arête est composée de deux sommets reliés par un segment de droite, d'où l'allusion aux paires d'éléments dans la définition précédente).

Remarque: Dans un "multigraphe", les deux sommets d'une arête peuvent être identiques (boucle) et deux arêtes distinctes peuvent avoir leurs deux extrémités communes. Un multigraphe ne satisfait plus alors la définition D1.

D3. Soit equation une arête de G, nous disons que les sommets x, y qui sont les "extrémités" de l'arête de G, sont "adjacents" ou "voisins" dans le graphe G, et que l'arête e est "incidente" aux sommets x, y.

D4. Si deux arêtes e et e' ont une extrémité en commun, nous dirons qu'elles sont "incidentes", autrement, qu'elles sont indépendantes.

Remarque: Si e est une arête de G, nous noterons equation le sous-graphe de equation. Si X ' est un sous-ensemble de X, nous noterons equation le graphe G privé des sommets de X '.

D5. Ce que nous nommons "ordre" du graphe est le nombre de ses sommets.

Soit G un graphe d'ordre n, l'ensemble E doit être par définition choisi comme sous-ensemble de l'ensemble des paires d'éléments de l'ensemble X, donc d'un ensemble de cardinal:

equation   (27.6)

Il s'agit d'un résultat relativement trivial puisque chacun des sommets est lié à tous les autres sommets sauf lui-même (d'où le numérateur) et on divise par deux simplement pour ne pas compter les sommets voisins deux fois (et ils le sont tous lorsque nous les parcourons tous).

En conséquence, il existe (voir le chapitre de Probabilités: arrangements de n éléments non distinguables par couples de deux):

equation   (27.7)

choix possibles pour E et donc autant de graphes admettant X pour ensemble de sommets. Certains de ces graphes, sont par le fait que nous considérons leurs sommets comme non distinguables  "automorphes" (voir la définition de ce terme un peu plus loin dans ce chapitre). 

Le résultat obtenu signifie qu'il existe environ 2 millions de graphes à 7 sommets, et quelques equation graphes à 27 sommets - chiffre à comparer avec le fait que nous estimons à moins de equation le nombre d'atomes dans l'Univers (...).

D6. Le "voisinage" d'un sommet est l'ensemble de ses voisins.

D7. Nous appelons "degré" d'un sommet s et notons D(s), le nombre de ses voisins, qui est également le nombre d'arêtes qui lui sont incidentes (un sommet de degré zéro étant appelé un "sommet isolé").

Remarque: Un sommet de degré 1 est appelé "sommet pendant".

Propriétés (sans démonstration): 

P1. La somme des degrés des sommets est égale au double du nombre d'arêtes.

P2. Dans un graphe, le nombre de sommets de degré impair est toujours pair.

Remarque: Un "graphe régulier" est un graphe dont tous les sommets ont même degré k. Nous disons alors que le graphe est "k-régulier".

D8. Nous dirons qu'un graphe equationest un "sous-graphe" ou "sous-graphe induit" d'un graphe equation lorsque equation et equation.

D9. Un "sous-graphe recouvrant" d'un graphe equation est un sous-graphe equation, c'est-à-dire un sous-graphe dont sont sommets tous les sommets de G et dont les arêtes sont dans E'.

D10. Pour un graphe d'ordre n, il existe deux cas extrêmes pour l'ensemble de ses arêtes: soit le graphe n'a aucune arête, soit toutes les arêtes possibles pouvant relier les sommets deux à deux sont présentes. Dans ce dernier cas le graphe est dit appelé un "graphe complet".

exempleExemple:

Voici quelques graphes complets pour lesquels nous avons bien:

equation   (27.8)

arêtes. Nous remarquons que les quatre premiers graphes sont planaires (effectivement remarquez comment il est possible, par projection d'un sommet dans le plan, de transformer le quatrième K4 en equation de manière à ce qu'il n'y ait plus d'intersections). Le cinquième graphe K5 est non-planaire (nous ne pouvons trouver des déplacements évitant les croisements).

equation
Figure: 27.4 - Exemples de graphes complets

Un graphe complet est donc un graphe où chaque sommet est relié à tous les autres. Le graphe complet d'ordre n est noté equation. Dans ce graphe chaque sommet est de degré n-1.

Ainsi, un cas sympathique à traiter est "l'étoile de David":

equation
Figure: 27.5 - Étoile de David

qui n'est évidemment un graphe complet par définition que si l'on joint tous les sommets entre eux (ainsi nous perdons la géométrie de l'étoile mais obtenons un graphe equation):

equation
Figure: 27.6 - Étoile de David sous forme de graphe complet

Remarque: Ce résultat est intéressant dans le domaine de la gestion de la communication des projets d'entreprise et de la sécurité informatique (cf. chapitre de Cryptographie). Si par exemple vous gérez un projet avec 10 intervenants (correspondant à n), il y a donc n(n-1)/2 canaux de communication (e-mail ou téléphone) possibles, soit 45 (et dans le domaine de la sécurité il y aurait 45 clés de cryptage à système symétrique à générer). D'où l'importance en gestion de projet de définir des règles de communication claires (sous forme d'un graphe) si l'on ne veut pas être noyé par les e-mails ou les téléphones inutilement (et dans le domaine de la sécurité à mettre en place des systèmes asymétriques). Nous retrouverons aussi ce résultat dans le modèle de la goutte liquide du noyau nucléaire dans le chapitre de Physique Nucléaire.

D11. Un "graphe stable" est sous-graphe sans arête et une "clique" un sous-graphe complet.

D12. Dans un graphe, il est naturel de vouloir se déplacer de sommet en sommet en suivant les arêtes. Une telle marche passant par n sommets est appelée une "chaîne" equation ou un "chemin":

Un chemin ("path" en anglais) est une liste equation de sommets telle qu'il existe dans le graphe une arête entre chaque paire de sommets successifs: equation. La longueur du chemin correspond au nombre d'arêtes parcourues: k-1.

Un chemin est dit "chemin simple" si chaque arête du chemin est empruntée une seule fois. Voici par exemple un chemin simple avec 5 sommets:

equation
Figure: 27.7 - Exemple de chemin simple

Ainsi, nous définissons aussi un "cycle":

equation   (27.9)

comme étant un chemin simple finissant à son point de départ tel queequation. Ainsi, s'il existe deux chaînes distinctes reliant deux sommets x et y d'un graphe G, alors ce graphe admet un cycle.

D13. Un "cycle simple" est un cycle dont toutes les arêtes sont différentes.

D14. Un "graphe orienté" est un graphe dont les arêtes ont une direction et un sens et sont dès lors appelées des "arcs" (donc à l'opposé du graphe non orienté).

Remarques:

R1. Les termes de "chemin" et de "circuit" s'emploient en propre pour les graphes orientés. Pour les graphes non orientés que nous manipulons principalement ici, nous parlons de "chaîne" et de "cycle". Cependant, la définition formelle est exactement la même dans les deux cas, seule change la structure (graphe orienté ou non) sur laquelle ils sont définis.

R2. Un graphe non orienté n'est qu'un graphe orienté symétrique. Effectivement, si un arc relie le sommet a au sommet b et un autre arc relie le sommet b au sommet a, nous ne traçons alors qu'un trait entre a et b que nous appelons... une arête.

D15. Un chemin equation est dit "chemin élémentaire" si chacun des sommets du parcours est visité une seule fois: equation. Un chemin élémentaire est donc un chemin simple et sans cycle.

Propriétés: Dans un graphe G d'ordre n:

P1. Tout chemin élémentaire est de longueur au plus n-1. Effectivement, un chemin élémentaire visitant au plus 1 fois chaque sommet du graphe, sa longueur (nombre d'arêtes) ne peut effectivement excéder n-1.

P2. Le nombre de chemins élémentaires dans le graphe est fini. Effectivement, le nombre de chemins de longueur  equation est au plus la combinatoire du choix d'une suite de k+1 sommets distinguables parmi n. Il y en a donc (cf. chapitre de Probabilités):

equation   (27.10)

Les chemins élémentaires sont la restriction naturelle que nous recherchons à la notion de chemin. La question qui se pose est de savoir si nous perdons quelque chose en ne considérant que les chemins élémentaires dans un graphe: peut-on toujours remplacer un chemin du graphe par un chemin élémentaire?

Le "lemme de König" répond affirmativement à cette question: de tout chemin, nous pouvons extraire un sous-chemin élémentaire.

L1. S'il existe un chemin entre 2 sommets x et y, alors il existe un chemin élémentaire entre x et y.

Démonstration:

L'idée de la preuve est de choisir un chemin particulier entre x et y et de montrer qu'il est élémentaire. Quel chemin choisir? Si un chemin comporte un circuit, ce circuit est un détour sur la route menant de x et y. Un bon candidat à être un chemin élémentaire semble donc être un plus court chemin.

Parmi tous les chemins reliant x à y, choisissons ainsi un chemin:

equation   (27.11)

comportant le moins d'arêtes. Supposons par l'absurde que p n'est pas élémentaire. Il existe alors dans ce chemin un sommet z apparaissant au moins 2 fois le long du chemin p.

Soient i, j les 2 premiers indices tels que equation et equation:

equation   (27.12)

Pour obtenir une contradiction, il suffit de supprimer le cycle entre equation et equation. Alors, nous avons un nouveau chemin:

equation   (27.13)

est un chemin, reliant x à y. Sa longueur est strictement inférieure à celle de p, ce qui contredit notre choix initial comme étant un plus court chemin.

D16. Un graphe est dit "graphe connexe" si et seulement si, il existe au moins un chemin entre chaque paire de sommets (le chemin n'étant donc implicitement pas nécessairement direct - pouvant passer par un ou plusieurs sommets intermédiaires). S'il existe un chemin entre chaque paire de sommets, nous disons que nous avons un "graphe fortement connexe".

Remarques: Que se passe-t-il si le graphe G n'est pas connexe? Il apparaît alors comme un ensemble de graphes connexes mis les uns à côté des autres. Chacun de ces graphes est un sous-graphe particulier de G, appelé "composante connexe". Il est souvent utile de se placer sur les composantes connexes d'un graphe pour se ramener au cas d'un graphe connexe.

D17. Un "arbre" ou "arbre couvrant" est un graphe connexe (non orienté), sans cycle simple (acyclique) et sans boucles. Dans un arbre le nombre d'arêtes est égal au nombre de sommets - 1. Une arbre couvrant avec les poids minimaux d'un graphe value est appelé "arbre couvrant minimal":

equation
Figure: 27.8 - Exemple d'un arbre couvrant (source: Wikipédia)

Si vous imaginez que chaque point est une ville, est qu'une Nation n'a pas assez d'argent pour la maintenant de toutes les routes actuellement existante entre plusieurs villes, alors l'arbre couvrant minimal représente les routes à préserver qui minimisent les coûts tout en connectant toutes les villes entre elles.

D18. Un "arbre valué" ou "graphe valué" est un arbre (respectivement un graphe) où les arêtes ont des valeurs (pondérations) positives. La somme de toutes les valeurs qui sont sur les arêtes parcourues d'un arbre est appelé alors le "coût d'un arbre valué" (respectivement "coût d'un graphe valué").

Remarque: Les arbres valués sont utilisés dans de très nombreux domaines. Citons les réseaux informatiques dans lesquels on cherche à optimiser le nombre d'interconnexions entre machines pour éviter les redondances d'envois de paquets de données ou la gestion de projets (voir l'exemple ci-dessous).

exempleExemple:

Un excellent exemple pratique de graphe connexe valué et orienté (abrégé sous le terme de "digraphe") est celui utilisé en gestion de projets pour le calcul du chemin critique. Il s'agit d'un graphe qui représente les dépendances entre n tâches intermédiaires nécessaires pour réaliser un projet, communément appelé "diagramme de Gantt" ou en encore "graphe d'ordonnancement". La durée (poids) de chaque tâche est la valeur des arcs incidents extérieurement au noeud correspondant. Les arcs représentent les contraintes d'enchaînement des tâches. Nous ajoutons toujours un noeud (dans le monde de la gestion de projets on parle plutôt de jalon...) initial et un noeud final. Le premier est relié par un arc de valeur nulle à tous les noeuds sans prédécesseurs, et tous les noeuds sans successeurs sont reliés au noeud final. Le graphe obtenu doit évidemment être acyclique.

Un "chemin critique" est un chemin de longueur maximale entre les deux jalons. Il peut éventuellement y en avoir plusieurs, de même longueur. Toute tâche située sur un chemin critique ne peut être retardée sans répercussion sur la durée totale du projet. En d'autres termes, sa "marge totale" est nulle (nous disons alors aussi que sa date de fin/début au plus tôt est strictement égale à sa date de fin/début au plus tard). Par ailleurs, nous définissons aussi en gestion de projets, la "marge libre" qui indique la durée sur laquelle une tâche peut glisser sans bouger la tâche successeur. La marge libre se calcule comme la différence entre la date de début au plus tôt d'une tâche sommée de sa durée et la date de début au plus tard de la tâche successeur.

Prenons pour l'exemple un projet qui se compose des tâches suivantes:

Tâches
Tâches antérieures
Durée
A
E
3
B
K,C
4
C
-
3
D
E,J
2
E
-
2
F
G,L
3
G
-
4
H
A,M,R
2
J
E
2
K
C
2
L
G
5
M
C
4
N
G
3
R
J
2
Tableau: 27.1  - Ordonnancement de tâches

Le graphe orienté valué connexe correspondant à ce tableau une fois la définition du chemin critique appliqué est le suivant en utilisant les dates de début:

equation
Figure: 27.9 - Exemple de représentation d'un planning sous forme de graphe

Nous voyons dans ce graphe que les tâches equation sont critiques.

Un excellent outil d'utilisation de tels graphes est MS Project dont le diagramme correspondant à l'exemple ci-dessus est:

equation
Figure: 27.10 - Même graphe mais vu dans MS Project

D19.  Une "composante connexe" d'un graphe G est un sous-graphe equation connexe maximal.

Remarque: Un graphe ne possédant qu'une seule composante connexe est simplement un graphe connexe. Un sommet isolé (de degré 0) constitue toujours une composante connexe à lui seul. La relation sur les sommets "il existe un chemin entre ..." est une relation d'équivalence (réflexive, symétrique et transitive). Les composantes connexes d'un graphe correspondent aux classes d'équivalences de cette relation.

Propriété (triviale): Un graphe G d'ordre n connexe comporte au moins n-1 arêtes.

D20. Un "cycle" est un chemin simple rebouclant sur lui-même. Un graphe dans lequel il n'existe aucun cycle possible est dit "acyclique".

Les graphes acycliques non-connexes composés d'arbres constituent une classe intéressante de graphes, avec des propriétés remarquables et un nom: les "forêts" (terme très souvent utilisé par les informaticiens réseaux).

equation
Figure: 27.11 - Exemple d'un graphe connexe contenant un cycle

equation
Figure: 27.12 - Exemple d'un arbre (graphe connexe ne contenant pas de cycle)

Ci-dessous un exemple de forêt (composée d'arbres, chaque arbre étant connexe mais l'ensemble formant un graphe acyclique et non-connexe):

equation
Figure: 27.13 - Exemple d'une forêt (3 composantes connexes)

Nous voyons ainsi qu'une forêt est un graphe dont les composantes sont des arbres. Les sommets de degré 1 sont appelés "feuilles" d'un arbre.

Propriétés:

P1. (triviale) Si dans un graphe G tout sommet est de degré supérieur ou égal à 2, alors G possède au moins un cycle.

Remarque: Cette propriété simple implique qu'un graphe sans cycle possède au moins un sommet de degré 0 ou 1. À l'inverse, nous pouvons lier cette fois l'absence de cycle dans un graphe avec le nombre d'arêtes.

P2. (triviale) Un graphe acyclique G à n sommets possède au plus n-1 arêtes.

D21. Un "cycle eulérien" est un cycle passant une et une seule fois par chaque arête du graphe et revenant au point de départ (nous verrons plus loin les propriétés que doit posséder un tel graphe pour qu'un tel cycle y existe)

D22. Un graphe est dit "graphe eulérien" s'il admet un cycle eulérien.

D23. Un "cycle hamiltonien" est un cycle simple passant par tous les sommets du graphe une et une seule fois. Pour avoir un cycle hamiltonien, le graphe doit être connexe et il ne doit pas y avoir de sommet pendant.

D24. Un "graphe hamiltonien" est un graphe qui possède un cycle hamiltonien.

Il convient d'ouvrir maintenant une parenthèse (pour les paillettes...) sur le problème le plus connu en théorie des graphes: les ponts de Königsberg.

Euler (voir page des biographies), aimait à faire une promenade dans sa bonne ville de Königsberg. Il affectionnait selon la légende tout particulièrement de parcourir les 7 ponts qui enjambent la rivière. L'âge venant (les connaissances mathématiques aussi...), il se demanda si sans sacrifier à sa promenade, il pouvait en raccourcir la longueur en ne traversant chaque pont qu'une seule fois. Ce problème est sans doute l'un des plus anciens en théorie des graphes: celui de l'existence d'une chaîne passant une et une seule fois par chaque arête.

equation
Figure: 27.14 - Carte de la ville de Königsberg

La rivière sépare la ville de Königsberg en quatre parties, a, b, c, d. Chaque pont relie deux de ces parties. Nous pouvons alors représenter notre problème par un graphe avec quatre sommets, où chaque arête représente l'un des sept ponts de Königsberg. Sur cet exemple le graphe n'est pas un graphe simple:

equation        equation
Figure: 27.15 - Représentation des sept ponts de Königsberg

La question est donc ici de savoir si le graphe est eulérien ou non? Si pour notre problème le graphe obtenu est eulérien, il faut pouvoir exhiber un cycle eulérien, ce qui ne semble pas facile. Mais s'il ne l'est pas? Euler a donné une caractérisation très forte des graphes eulériens donnée par l'énoncé suivant:

Théorème d'Euler: Un graphe est eulérien si et seulement s'il est connexe et tous ses sommets sont de degré pair (il y a donc un nombre pair d'arêtes qui arrivent sur chaque sommet dont la moitié d'entre elles servant à arriver sur le sommet, l'autre à en repartir) sauf au plus deux (ces deux exceptions étant les sommets de départ et d'arrivée).

De façon plus précise pour un graphe connexe:

- le graphe n'a pas de sommets impairs, alors il est eulérien (et la chaîne est donc cyclique)

- le graphe ne peut avoir un seul sommet impair de par la propriété (déjà énoncée plus haut) que dans un graphe, le nombre de sommets de degré impair est toujours pair.

- si le graphe a deux sommets impairs, ces sommets sont alors les extrémités de la chaîne eulérienne

Corollaire: un graphe ayant plus de deux sommets impairs ne possède pas de chaîne eulérienne.

Avec cette caractérisation (comme nous allons le démontrer de suite après), les sommets a, b, c, d étant de degré impair, on sait immédiatement qu'il est impossible de parcourir tous les ponts de Königsberg seulement une fois au cours d'une promenade.

Démonstration:

1. Supposons qu'un graphe G soit eulérien. Il existe alors une chaîne c parcourant une et une seule fois chaque arête (jusque-là c'est facile). Bien évidemment, dans le cas d'une chaîne, les sommets se situant aux extrémités de la chaîne sont de degré impair et sont au nombre de deux.

2. Considérons maintenant un sommet x et supposons cette fois-ci non pas un graphe eulérien mais un cycle eulérien. Lors du parcours du cycle, à chaque fois que nous passons par le sommet x, nous nous retrouvons au point de départ et pour effectuer un nouveau tour chacune des 2 arêtes s'offre à nous (le chemin pouvant être parcouru dans les deux sens puisque le graphe est non orienté). Le sommet x est donc de degré pair et peut être défini n'importe où dans le cycle, d'où le fait que l'ensemble des sommets sont de degré pair.

3. Réciproquement considérons un graphe G connexe dont tous les sommets sont de degré pair. Nous allons montrer par induction sur le nombre d'arêtes que G est alors eulérien:

- Si G se réduit à un unique sommet isolé, il est évidemment eulérien.  Sinon tous les sommets de G sont de degré supérieur ou égal à 2. Ceci implique qu'il existe un cycle equation sur G:

- Considérons le graphe partiel H constitué des arêtes en dehors du cycle equation. Les sommets de H sont également de degré pair, le cycle contenant un nombre pair d'arêtes incidentes pour chaque sommet. Par induction chaque composante connexe equation de H est un graphe eulérien, et admet donc un cycle eulérien equation. Pour reconstruire un cycle eulérien sur G, il nous suffit de fusionner le cycle equation avec les différents cycles equation. Pour cela, nous parcourons le cycle equation depuis un sommet arbitraire; lorsque nous rencontrons pour la première fois un sommet x appartenant à equation, nous lui substituons le cycle equation. Le cycle obtenu est un cycle eulérien pour G, le cycle equation et les cycles equation formant une partition des arêtes.

equation
Figure: 27.16 - Graphe Eulérien?

Remarque: Ce principe de décomposer un graphe en graphes connexes et de les sommer permet de construire un algorithme récursif permettant de déterminer si un graphe est eulérien ou non.

D25. Deux graphes G et G ' sont "graphes complémentaires" lorsqu'ils vérifient les conditions suivantes:

1. Ils ont le même ensemble de sommets

2. Deux sommets x, y sont voisins dans G ne sont pas voisins dans G '

D26. Un "graphe biparti" equation est un graphe tel que nous puissions partitionner l'ensemble de ses sommets en deux classes respectivement de cardinal p et q de sorte que toute arête ait une extrémité dans chacune des deux classes.

exempleExemple:

Voici donc une représentation d'un graphe biparti K3,3 classique. Il représente le problème fameux de l'approvisionnement de trois maisons au départ de trois usines (eau, électricité, gaz) sans droit d'alignement des services. Nous voyons immédiatement que ce graphe est non-planaire.

equation
Figure: 27.17 - Exemple de graphe biparti

Remarque: Le graphe biparti complet equation est un graphe de sommets de equation sommets configuré de telle sorte que chaque sommet d'une classe soit adjacent à tous les sommets de l'autre et seulement à ceux-ci.

D27. Deux graphes sont isomorphes s'il existe une bijection f de X dans X ' telle que, pour tous sommets x et y de G:

x adjacent à y dans equation equation equation adjacent à f(y) dans G '

Nous disons aussi que f est un "isomorphisme de G sur G ' ".

S'il existe une bijection f de X dans lui-même telle que:

x adjacent à y dans equation equation equation adjacent à f(y) dans G

nous disons alors que f est un automorphisme dans G (par permutation des sommets il existe beaucoup d'exemples possibles...).

Remarque: Attention!! Parfois nous parlons de graphes équivalents à "un isomorphisme près". Cela signifie plus clairement, qu'à l'exception d'une et unique violation parmi l'ensemble des arêtes, les graphes sont isomorphes.

Comme l'isomorphisme dans le cas des graphes va d'un ensemble à un autre de même cardinal n, le nombre de bijections possibles différentes est (voir le chapitre de Probabilité sur les arrangements):

n!   (27.14)

Cela signifie qu'il existe au maximum n! graphes qui peuvent se regrouper dans une même classe d'équivalence. En conséquence, il existe au minimum (minorant) le rapport du nombre total de n sommets sur le cardinal majoré de la plus grande classe d'équivalence possible (mais pas nécessairement existante):

equation   (27.15)

En utilisant la majoration grossière equation, nous avons:

equation   (27.16)

D'où:

equation   (27.17)

Soit encore:

equation   (27.18)

Ainsi, quand n tend vers l'infini, equation admet un minorant de l'ordre de equation.

MATRICE D'ADJACENCE

Au plan formel, un graphe est aussi un ensemble sur lequel nous avons défini une relation binaire, antiréflexive (aucun élément n'est en relation avec lui-même) et symétrique (si x est en relation avec y, alors y est en relation avec x). La structure de graphe peut alors sembler particulièrement pauvre.

Mais nous pouvons aussi associer à un graphe G de sommets equation une matrice carrée M de dimensions equation appelée "matrice d'adjacence" du graphe et dont les éléments valent 0 ou 1. En notant equation le terme située au croisement de la ligne i (représentant le sommet equation) et de la colonne j (représentant le sommet equation), M est défini par:

equation si et seulement si equation sont adjacents

De par cette définition et celle du graphe lui-même, il vient que dans une matrice d'adjacence d'un graphe formel que les éléments diagonaux pour lesquels equation valent tous 0 et que equation.

Rappelons qu'une telle matrice est dite "symétrique" (cf. chapitre d'Algèbre linéaire).

Remarque: Nous savons aussi que les graphes sont représentés par des matrices dans le cadre de l'étude des chaînes de Markov dans le domaine des probabilités (cf. chapitre de Probabilités).

Voyons un exemple à la fois abstrait mais facilement applicable à de nombreux domaines de l'industrie, de la sociologie et de la biologie. Considérons le graphe orienté suivant et observons qu'il n'est pas antiréflexif ni symétrique:

equation
Figure: 27.18 - Exemple de chaîne de Markov (graphe antiréflexif ni symétrique)

Nous pouvons représenter ce diagramme sous forme d'un tableau dans lequel nous noterons "1" quand une transition est possible de l'état mentionné en haut de la colonne de la case vers l'état mentionné au début de la ligne et "0" sinon:

equation

E1

E4

E2

E3

E5

E7

E6

E1

0

0

0

0

0

0

0

E4

0

0

1

0

0

0

0

E2

1

1

1

1

0

0

0

E3

0

0

1

0

0

0

0

E5

0

0

0

1

0

0

0

E7

0

1

1

1

0

0

0

E6

0

1

1

1

0

0

0

Tableau: 27.2  - Matrice d'adjacence

Il est indispensable de comprendre parfaitement la signification des valeurs se trouvant dans ce tableau! Mais à ce niveau du site cela ne devrait pas poser de difficulté majeure.

Maintenant évaluons le nombre de manières permettant d'aller:

1. De E2 vers E2 en deux étapes

2. De E3 vers E4 en deux étapes

3. De E2 vers E7 en deux étapes.

Il est facile dans le cas particulier ci-dessus de dénombrer ces possibilités. Mais dans le cas d'un graphe plus complexe cela devient difficile, voire impossible pour un être humain dans un temps raisonnable.

Nous devons faire appel alors au théorème suivant:

Soit un graphe orienté avec equation sommets et de matrice d'adjacence:

equation   (27.19)

Pour tout entier naturel k, alors le nombre de chemins de longueur k d'un sommet equation à un sommet equation est donné par:

equation   (27.20)

où l'exposant de M dénote la puissance de k de la matrice d'adjacence.

Démonstration:

Effectuons une récurrence sur k:

equation   (27.21)

désigne bien le nombre de chemins allant de equation à equation (où i et j peuvent être égaux). Supposons le résultat vrai pour l'entier k-1, avec equation comme:

equation   (27.22)

nous avons alors (par construction de la multiplication matricielle):

equation   (27.23)

Par hypothèse de récurrence, equation est le nombre de chemins de longueur k-1 allant de equation à equation et equation est nous le savons (par construction) le nombre de chemins de longueur 1 allant de equation à equation et en particulier il est égal à 1 si equation est une arête du Graphe et 0 sinon!

Donc, le produit:

equation   (27.24)

donne pour une valeur de l donnée le nombre de chemins de longueur k allant de equation à equation dont la dernière arête est equation.

La somme:

equation   (27.25)

donne donc toutes les possibilités (chemins) de longueur k allant de equation à equation quel que soit le point de début de la dernière arête!

equationC.Q.F.D.

Ainsi, dans notre exemple, la matrice d'adjacence M est donnée par:

equation   (27.26)

et n'est ni symétrique, ni antiréflexive comme nous en avions déjà fait mention.

Donc si nous la portons à la puissance k, chaque composant equationdonnera toutes les possibilités (chemins) de longueur k allant de equation à equation. Ainsi, nous avons:

equation   (27.27)

en utilisant par exemple la fonction PRODUITMAT( ).

Nous avons alors la réponse à nos trois questions en lisant la matrice ci-dessus:

1. De E2 vers E2 en deux étapes nous avons donc 3 possibilités.

2. De E3 vers E4 en deux étapes nous avons donc 1 possibilité.

3. De E2 vers E7 en deux étapes nous avons donc 3 possibilités.

Il est possible de gagner un peu de temps dans ce genre de calculs. Si nous notons equation, la i-ème colonne de la matrice M, alors:

equation   (27.28)

donnera la i-ème colonne de la matrice M au carré. Et ainsi de suite:

equation   (27.29)

Donc nous obtenons systématiquement le nombre de chemins de longueur k d'un point de départ donné correspondant à la colonne i.

Cet exemple a une autre approche très intéressante dans certains domaines étudiant le comportement d'individus dans diverses situations (achats, tourismes, accidents, etc.).

Si au lieu de noter dans la matrice M le nombre de chemins possibles d'un sommet à l'autre, nous notons la probabilité (la partie) du nombre total d'individus qui partent de ce même sommet pour en arriver à un autre alors nous avons par exemple (valeurs imposées par l'expérience!) la matrice:

equation   (27.30)

qui est déjà la matrice stochastique transposée du graphe visible ci-dessous (conformément à la théorie des chaînes de Markov, nous avons vu qu'il fallait prendre la transposée de la matrice stochastique pour calculer les probabilités d'états).

En considérant que ces probabilités ne changent pas au cours du temps, nous avons alors une chaîne de Markov homogène (sans cycles). Nous voyons alors que:

1. La somme des probabilités de transitions au départ de chaque sommet (état) doit toujours logiquement être égale à 1 (ce que nous avions déjà mentionné dans le chapitre de Probabilités)

2. Tout le monde part de la première étape E1

3. Certains stagnent (s'arrêtent) à une certaine étape

4. Ceux qui arrivent à une étape de fin E5, E6 ou E7 y restent et ne reviennent pas sur leurs pas (états absorbants).

Le graphe équivalent devient alors:

equation
Figure: 27.19 - Graphe équivalent à la matrice

En appelant N (au lieu de M pour ne pas confondre) la matrice construite à partir du graphe ci-dessus nous voyons que si equation est une des colonnes de la matrice M alors par exemple:

equation   (27.31)

donne la somme des probabilités de transition que ce qui part de E1 arrive en 2 étapes en respectivement E1(0), E2(0.662), E3(0.218)... (la distribution du vecteur initial peut être quelconque tant que la somme des valeurs de la colonne est égale à 1)!

Si nous multiplions ensuite encore une fois:

equation   (27.32)

donne la somme des probabilités de transition que ce qui part de E1 arrive en 3 étapes en respectivement E1(0), E2(0.691), ... et ainsi de suite. Nous pouvons ainsi savoir qu'elle est la probabilité qu'un individu arrivant à E2 puisse arriver à un des sommets terminaux (E5, E6 ou E7) en un nombre d'étapes donné.

Remarque: Se rappeler que la somme des probabilités des colonnes T obtenues est toujours égale à 1 pour la transposée de la matrice stochastique.

En continuant encore longtemps ainsi... nous trouvons que la mesure d'équilibre equation qui satisfait (cf. chapitre de Probabilités):

equation

est:

equation   (27.33)

quelle que soit la distribution du vecteur de départ. Propriété que l'on appelle "ergodique" dans le domaine des chaînes de Markov.

Ce qui signifie 45% de probabilité de se trouver en E5, 32% de probabilité de se trouver en E7 et 23% de probabilité de se trouver en E6. Une autre manière de voir les choses est de dire que si une cohorte de 100 individus part de l'étape E1 avec les probabilités constantes dans le temps entre les transitions d'étapes, à l'équilibre nous aurons 45 personnes en E5, 32 personnes en E7 et 23 personnes en E6.

CATÉGORIES

L'introduction des catégories à travers la "théorie des catégories" par Eilenberg et MacLane en 1942 avait pour but de transformer de difficiles problèmes de Topologie en problèmes plus abordables d'algèbre. Plus tard, la théorie des catégories s'est beaucoup développée, à la fois pour elle-même et pour ses applications dans les domaines les plus variés des mathématiques (par exemple en géométrie différentielle). Même si une partie de son développement autonome a parfois été critiquée, les catégories sont maintenant reconnues comme un langage puissant pour développer une sémantique universelle des structures mathématiques. On les utilise aussi en logique et plus récemment en physique, et une collaboration fructueuse semble se développer entre catégoriciens et informaticiens.

Définitions:

D1. Intuitivement une "catégorie" est juste un graphe orienté sur lequel nous nous sommes donné une loi pour composer des flèches consécutives, vérifiant certains axiomes.

D2. Un "graphe orienté" est formé d'un ensemble d'objets, appelés sommets du graphe, avec des liens entre eux, représentés par des flèches d'un sommet A vers un sommet B, ce que nous notons equation . Nous disons que A est la "source" de la flèche, et B son "but". Il peut y avoir plusieurs flèches de même source et de même but (nous les disons "parallèles") et il peut y avoir des flèches "fermées", dont la source et le but sont confondus.

D3. Deux flèches f, g sont dites "flèches consécutives" si le but de la première est en même temps la source de la seconde:

equation   (27.34)

nous disons alors qu'elles forment un chemin de longueur 2 de A vers C.

Une catégorie est donc un graphe dans lequel nous définissons une composition de flèches, associant à tout chemin (f , g) de longueur 2 de A vers C une flèche du graphe de A vers A, dite "composée" du chemin, et notée fg:

equation
Figure: 27.20 - Exemple de graphe de catégorie

Cette composition vérifie les axiomes suivants:

A1. Associativité : Si fgh est un chemin de longueur 3, les deux composés f(gh) et (fg)h que nous en déduisons sont associatifs. Il s'ensuit qu'à tout chemin de longueur n est aussi associé un seul composé de sommets (invariance de l'itinéraire).

A2. Identités: À tout sommet A est associée une flèche fermée de A vers A, dite "identité" de A et notée equation, dont le composé avec une flèche de source ou de but A est égal à cette autre flèche.

Plus généralement, un chemin (de longueur n) de A vers equation est une suite equation de n flèches consécutives:

equation   (27.35)

Remarques:

R1. Les sommets du graphe sont aussi appelés "objets" de la catégorie et ses flèches des "morphismes" (ou simplement "liens") dans le cadre de la théorie des catégories 

R2. Une flèche f est un isomorphisme (cf. chapitre de Théorie Des Ensembles) s'il existe une flèche g  (appelée "inverse") telle que les composés fg et gf soient des identités (cet inverse est alors unique).

Ainsi, une catégorie est formée par des objets (les sommets du graphe) et des liens entre eux (les flèches ou morphismes), mais l'idée essentielle est de privilégier les liens sur les objets. En fait, le succès des catégories dans les domaines les plus variés est dû à la richesse des informations sur les objets qui peuvent être déduites de la seule considération des liens et des opérations sur ceux-ci, quelle que soit la nature et l'anatomie de ces objets.

Dans les quelques lignes qui suivent, nous expliquerons comment lire les graphes orientés que nous pouvons rencontrer parfois dans les livres de math. Ceci sera un bon exemple de la théorie des catégories, car nous avons déjà rencontrés de tels graphes sans les décrire dans les chapitres sur les Nombres et la Cryptographie par exemple.

Pour simplifier nous allons expliquer ces diagrammes lorsque les objets de base sont les ensembles (ce qui est le cas le plus courant sur l'ensemble du site de toute manière).

Considérons trois ensembles A, B, et C et trois applications:

equation, equation et equation   (27.36)

Nous pouvons considérer les applications f, g et h comme des flèches qui relient les objets (ensembles) A, B, et C pour former un triangle.

equation
Figure: 27.21 - Exemple de diagramme commutatif

Définition (simpliste): Nous disons  que le diagramme fléché ci-dessus est "un diagramme commutatif" si tous les chemins que nous empruntons pour aller d'un objet (ensemble) à un autre représentent la même application.

Remarque: Il existe deux façons d'aller de A à C . Nous pouvons y aller directement par g ou bien suivre d'abord f puis h. Ce dernier chemin est représenté par l'application composée equation (cf. chapitre de Théorie Des Ensembles). Ainsi, le diagramme ci-dessus est commutatif si equation.

Nous pouvons donc introduire la définition plus formelle:

Définition: Le diagramme ci-dessus est commutatif si equation.

Remarque: Rappelons que ceci veut dire que pour tout élément equation.

Nous pouvons compliquer à souhait les diagrammes en considérant plus d'ensembles et de flèches (applications) les reliant. Par exemple:

equation
Figure: 27.22 - Autre exemple de diagramme fléché

Ce diagramme étant commutatif si et seulement si equation.

Remarques:

R1. Généralement dans la littérature mathématique de tels diagrammes sont sous-entendus comme étant commutatifs.

R2. Comme déjà mentionné, les objets de ces diagrammes peuvent plus généralement être des groupes d'anneaux des espaces topologiques, etc. Dans ces cas, les flèches ne sont plus des applications quelconques mais respectivement des homomorphismes de groupes, des homomorphismes d'anneaux, des applications continues, etc.

En Savoir Plus

- Théorie des graphes, O. Cogis + C. Robert, Éditions Vuibert, ISBN 2711753212

- Social Media Mining, R. Zafarani + M. Ali Abbasi, H. Liu, Éditions Cambridge University Press, ASIN B00IO0E5L8


Haut de page

FORMES GEOMETRIQUESPRINCIPES DE LA MECANIQUE


Like10   Dislike2
68.28% sur 100%
Notée par 29 visiteur(s)
12345
Commentaires: [0] 
 
 


W3C - HTMLW3C - CSS Firefox
Ce travail est dans le domaine public
2002-2017 Sciences.ch

Haut de page