Graphes équivalents à relation binaire
Fondamental : 1-graphe équivalent à la notion de relation binaire
Un graphe est un couple (X,E) où X est un ensemble et E est un sous-ensemble de X x X.
C'est en fait en mathématiques la définition d'une relation binaire de ExE.
Conséquence
Deux manières de travailler sur les graphes selon que l'on se sent mieux en restant dans les formules et le domaine des mathématiques ou au contraire que l'on préfère raisonner en utilisant les éléments des représentations graphiques de ces relations binaires.
Approche mathématique
Un graphe = Une relation binaire
Il peut donc avoir toutes les propriétés des relations binaires :
Réflexivité, symétrie, antisymétrie, transitivité ...
Et on peut aussi démontrer des propriétés de graphes particuliers en travaillant sur les matrices associées : matrices booléennes ou encore matrices entières en variables 0 et 1 indiquant l'existence ou non d'un arc entre l'indice de ligne et l'indice de colonne.
Approche graphique
Un graphe = Un ensemble de points et des liens entre les points
On s'appuie sur une représentation graphique pour illustrer les propriétés que l'on cherche à démontrer,
ce qui apporte une approche plus intuitive des propriétés.
C'est comme en géométrie, on peut faire les démonstrations sans utiliser le moindre schéma ou dessin, mais cela aide bien d'en faire.
Cliquer sur les flèches pour faire tourner les exemples proposés.
Si vous n'êtes pas familier de ces notions, entraînez vous avec l'exercice ci-dessus (voir le guide d'utilisation intégré).
Pour pouvoir entrer la relation binaire, on a utilisé la matrice en variable 0-1 du graphe ou de la relation binaire, ce qui permet d'utiliser des boutons à bascule, utiliser la liste des couples de la relation binaire aurait été beaucoup plus complexe.
Vous pouvez aussi vous testez avec l'exercice ci-dessus. A nouveau, on a utilisé la matrice en variables 0-1, et non pas la liste des couples de la relation binaire.
En tenant compte du fait que la taille de la matrice doit être la même que le nombre de points du graphe, cela permet d'éliminer de nombreuses possibilités.
