
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
Dernière mise à jour
de ce chapitre:
2017-12-31 17:58:49 | {oUUID 1.784}
Version: 3.2 Révision 8 | Avancement: ~90%
vues
depuis le 2012-01-01: 14'973
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
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
(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:
(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).
Exemple:
Un graphe à 2 faces (la face en gris clair est la face
extérieure
infinie), 4 sommets et 4 arêtes:

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 A - S:
D'abord, la
formule est vraie pour:
(27.2)
car,
dans ce cas, le graphe est un arbre donc il n'a qu'une seule
face (la face extérieure), donc .

Figure: 27.2 - Arbre avec une arête et 2 sommets
Donc:
(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):

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 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)
C.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 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  le
sous-graphe de  .
Si X ' est un sous-ensemble de X, nous
noterons
 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:
(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):
(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 graphes
à 27 sommets - chiffre à comparer avec le fait que nous estimons
à moins de 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 est
un "sous-graphe" ou "sous-graphe
induit" d'un
graphe lorsque
et
.
D9. Un "sous-graphe recouvrant"
d'un graphe est
un sous-graphe ,
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".
Exemple:
Voici quelques graphes complets pour lesquels nous avons bien:
(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 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).

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é .
Dans ce graphe chaque sommet est de degré n-1.
Ainsi, un cas sympathique à traiter est "l'étoile
de David":

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 ):

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"
ou un "chemin":
Un chemin ("path" en anglais) est une liste de
sommets telle qu'il existe dans le graphe une arête entre chaque
paire de sommets successifs: .
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:

Figure: 27.7 - Exemple de chemin simple
Ainsi, nous
définissons aussi un "cycle":
(27.9)
comme
étant un chemin simple finissant à son point de départ tel que .
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
est dit "chemin élémentaire" si chacun des sommets du
parcours est visité une seule fois: .
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 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):
(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:
(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 et :
(27.12)
Pour obtenir une contradiction,
il suffit de supprimer le cycle entre et
.
Alors, nous avons un nouveau chemin:
(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":

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).
Exemple:
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:

Figure: 27.9 - Exemple de représentation d'un planning sous forme de graphe
Nous voyons
dans ce graphe que les tâches sont
critiques.
Un excellent
outil d'utilisation de tels graphes est MS Project dont
le diagramme correspondant à l'exemple
ci-dessus est:

Figure: 27.10 - Même graphe mais vu dans MS Project
D19. Une "composante connexe" d'un graphe G est
un sous-graphe 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).

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

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):

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.

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:

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
sur
G:
-
Considérons le graphe partiel H constitué
des arêtes en dehors du cycle .
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
de
H est
un graphe eulérien, et admet donc un cycle eulérien .
Pour reconstruire un cycle eulérien sur G,
il nous suffit de fusionner le cycle avec
les différents cycles .
Pour cela, nous parcourons le cycle depuis
un sommet arbitraire; lorsque nous rencontrons pour la première
fois un sommet x appartenant
à ,
nous lui substituons le cycle .
Le cycle obtenu est un cycle eulérien pour G,
le cycle
et les cycles formant
une partition des arêtes.
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"
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.
Exemple:
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.

Figure: 27.17 - Exemple de graphe biparti
Remarque: Le graphe biparti complet 
est un graphe de sommets de  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
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
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):
(27.15)
En utilisant la majoration
grossière ,
nous avons:
(27.16)
D'où:
(27.17)
Soit encore:
(27.18)
Ainsi,
quand n tend
vers l'infini, admet
un minorant de l'ordre de .
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 une
matrice carrée M de
dimensions appelée
"matrice d'adjacence" du graphe et dont les éléments valent
0 ou 1. En notant le
terme située au croisement de la ligne i (représentant
le sommet )
et de la colonne j (représentant
le sommet ),
M est
défini par:
si
et seulement si 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
valent
tous 0 et que .
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:

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:
 |
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 sommets
et de matrice d'adjacence:
(27.19)
Pour tout entier naturel k, alors le nombre de chemins
de longueur k d'un sommet à
un
sommet est
donné par:
(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:
(27.21)
désigne bien le nombre de chemins allant de à (où i et j peuvent être égaux).
Supposons le résultat vrai pour l'entier k-1, avec comme:
(27.22)
nous avons alors (par construction de la multiplication matricielle):
(27.23)
Par hypothèse de récurrence, est
le nombre de chemins de longueur k-1 allant de à et est
nous le savons (par construction) le nombre de chemins de longueur
1 allant de à et
en particulier il est égal à 1 si est
une arête du Graphe et 0 sinon!
Donc, le produit:
(27.24)
donne pour une valeur de l donnée le nombre de chemins
de longueur k allant de à dont
la dernière arête est .
La somme:
(27.25)
donne donc toutes les possibilités (chemins) de longueur k allant
de à quel
que soit le point de début de la dernière arête!
C.Q.F.D.
Ainsi, dans notre exemple, la matrice d'adjacence M est
donnée
par:
(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 donnera
toutes les possibilités (chemins) de longueur k allant
de à .
Ainsi, nous avons:
(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 ,
la i-ème colonne de la matrice M, alors:
(27.28)
donnera la i-ème colonne de la matrice M au carré.
Et ainsi de suite:
(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:
(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:

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 est
une des colonnes de la matrice M alors par exemple:
(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:
(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 qui
satisfait (cf. chapitre de Probabilités):

est:
(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 .
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:
(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:

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 ,
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 est
une suite de n flèches
consécutives:
(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:
, et
(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.
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  ( cf.
chapitre de Théorie Des Ensembles). Ainsi, le diagramme
ci-dessus est commutatif si  .
Nous pouvons donc introduire la définition plus formelle:
Définition: Le diagramme ci-dessus est commutatif si .
Remarque: Rappelons que ceci veut dire que pour tout élément  .
Nous pouvons compliquer à souhait les diagrammes en considérant
plus d'ensembles et de flèches (applications) les reliant.
Par exemple:
Figure: 27.22 - Autre exemple de diagramme fléché
Ce diagramme étant commutatif si et seulement si .
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.

- 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
|