Définitions et propriétés liées aux relations binaires
Définition : Réflexivité
Un graphe (X,E) est réflexif si la relation binaire Γ associée l'est ;
c'est-à-dire si ( ∀ x ∈ X ) ( x Γ x )
ou encore s'il existe une boucle en chacun de ses points.
Définition : Symétrie
Un graphe (X,E) est symétrique si la relation binaire Γ associée l'est ;
c'est-à-dire si ( ∀ (x,y) ∈ XxX ) ( x Γ y ⇒ y Γ x ).
Pour les graphes symétriques, comme tout arc existe dans les deux sens, on ne représente plus le sens des arcs sur les représentations graphiques, on les appelle également des graphes non orientés.
Si le graphe est valué, il est non orienté seulement si les valeurs sur les arcs sont exactement les mêmes dans les deux sens.
Définition : Anti-symétrie
Un graphe (X,E) est antisymétrique si la relation binaire associée Γ l'est ;
c'est-à-dire si ( ∀ (x,y) ∈ XxX ) ( x Γ y ⇒ non y Γ x ).
Définition : Transitivité
Un graphe (X,E) est transitif si la relation binaire associée Γ l'est ;
c'est-à-dire si (∀ (x,y,z) ∈ ExExE) ( x Γ y et y Γ z ⇒ x Γ z ).
Définition : Union de graphes
Le graphe (X, E∪E'), union des graphes (X, E) et (X, E'), est obtenu en retenant tous les arcs des deux graphes :
(∀ (x,y) ∈ XxX ) ( x Γ y ou x Γ' y ⇒ x Γ∪Γ' y ) et ( non x Γ y et non x Γ' y ⇒ non x Γ∪ Γ'y ).
Utiliser les boutons précédent ou suivant ainsi que plus petit ou plus grand pour faire défiler des exemples d'union de graphes illustrées sur les représentations graphiques.
Utiliser les boutons précédent ou suivant ainsi que plus petit ou plus grand pour faire défiler des exemples d'union de graphes illustrées sur les matrices en variables 0-1.
Cliquer sur Anim pour démarrer l'animation, qui vous permet d'utiliser des boutons à bascules sur les représentations matricielles de manière à construire des graphes ainsi que leur union et de vérifier si l'union construite est correcte.
Cliquer sur Anim pour testez vos connaissances.
Choisissez un graphe à gauche et en haut, puis chercher à droite le graphe qui correspond à l'union des deux graphes que vous avez choisis.
Même test sur des matrices plus grosses.
Définition : Intersection de graphes
Le graphe (X, E∩E'), intersection des graphes (X, E) et (X, E'), est obtenu en ne conservant que les arcs communs aux deux graphes :
( ∀ (x,y) ∈ XxX ) ( x Γ y et x Γ' y ⇒ x Γ∩Γ' y ) et ( non x Γ y ou non x Γ' y ⇒ non x Γ∩Γ'y ).
Utiliser les boutons précédent ou suivant ainsi que plus petit ou plus grand pour faire défiler des exemples d'intersection de graphes illustrées sur les représentations graphiques.
Utiliser les boutons précédent ou suivant ainsi que plus petit ou plus grand pour faire défiler des exemples d'intersection de graphes illustrées sur les matrices en variables 0-1.
Cliquer sur Anim pour démarrer l'animation, qui vous permet d'utiliser des boutons à bascules sur les représentations matricielles de manière à construire des graphes ainsi que leur intersection et de vérifier si l'union construite est correcte.
Cliquer sur Anim pour testez vos connaissances.
Choisissez un graphe à gauche et en haut, puis chercher à droite le graphe qui correspond à l'intersection des deux graphes que vous avez choisis.
Même test sur des matrices plus grosses.
Définition : Produit de graphes
Le graphe produit (X, E.E') est défini par
( ∀ (x,y) ∈ XxX ) ( x Γ.Γ' y ⇔ ∃ z ∈ X : x Γ z et z Γ' y )
Utiliser les boutons précédent ou suivant ainsi que plus petit ou plus grand pour faire défiler des exemples de produits de graphes illustrées sur les représentations graphiques.
Utiliser les boutons précédent ou suivant ainsi que plus petit ou plus grand pour faire défiler des exemples de produits de graphes illustrées sur les matrices en variables 0-1.
Cliquer sur Anim pour démarrer l'animation, qui vous permet d'utiliser des boutons à bascules sur les représentations matricielles de manière à construire des graphes ainsi que leur produit et de vérifier si la solution construite est correcte.
Cliquer sur Anim pour testez vos connaissances.
Choisissez un graphe à gauche et en haut, puis chercher à droite le graphe qui correspond au produit des deux graphes que vous avez choisis.
Même test sur des matrices plus grosses.
Elévation d'un graphe à la puissance k
Pour élever un graphe G=(X,E) à la puissance k, on effectue k-1 produits de graphes : le graphe G par lui même, puis le résultat obtenu par le graphe G etc.
On le note Gk.
Par définition, G à la puissance 0 est égal au graphe identité composé de toutes les boucles et uniquement des boucles.
Cliquer sur Anime. Utiliser les flèches P et S pour sélectionner un graphe. Utiliser la flèche + pour augmenter la puissance du graphe. Pour voir l'évolution, on représente toujours la puissance k-1 en bas à gauche et la puissance k en bas à droite. Selon les graphes, on peut observer des phénomènes différents, on peut tendre vers un graphe limite qui ne change plus (parfois ce graphe est vide d'arcs) ou on peut obtenir un phénomène périodique.
Définition : Autre définition de la fermeture transitive
Le graphe FT(G)=Go∪G1∪G2∪...∪Gn est appelé fermeture transitive du graphe G et est aussi noté (X,E*).
Cliquer sur précédent ou suivant pour faire défiler des exemples de graphes et de leur fermeture transitive.
Algorithme de construction de la fermeture transitive utilisant la représentation matricielle
On utilise la distributivité de l'union par rapport au produit :
FT(G)=((...((Go∪G).G∪G).G∪G)...).G∪G).
On commence par un graphe ne contenant que les boucles.
A chaque itération, on multiplie le graphe courant par le graphe G et on effectue l'union du graphe obtenu avec le graphe G.
FTo = Go = I = {boucles} ;
pour k de 1 à n faire
FTk=FTk-1.G∪G ;
finpour
En fait, on arrête les itérations dès l'instant où FTk est identique à FTk-1.
Cliquer sur Anim pour démarrer l'animation, puis sur P ou S pour choisir un graphe.
L'écran présente toujours deux états de FT en cours de construction, au démarrage FTo qui contient les boucles et FT1 qui contient G.
La couleur rouge est utilisé sur le graphe de droite pour y mettre en évidence les arcs qui ont été ajoutés par rapport au graphe de gauche.
Définition : Autre définition de la fermeture transitive stricte
Le graphe FTS(G)=G1∪G2∪...∪Gn est appelé fermeture transitive stricte du graphe G et est noté (X,E+).
Remarque :
Contrairement à la fermeture transitive (au sens large), les boucles ne sont pas systématiquement ajoutées à la fermeture transitive stricte.
La fermeture transitive stricte du graphe G contient une boucle en x, s'il y avait déjà une boucle en x dans le graphe G ou s'il existe, dans le graphe G, un circuit qui passe par x (c'est-à-dire une suite d'arcs qui se suivent dont le premier a pour origine x et le dernier pour extrémité x).
Cliquer sur précédent ou suivant pour faire défiler des exemples de graphes et de leur fermeture transitive.
Algorithme de construction de la fermeture transitive stricte utilisant la représentation matricielle
On utilise la distributivité de l'union par rapport au produit :
FT(G)=((...((G∪G).G∪G).G∪G)...).G∪G).
On commence par le graphe G.
A chaque itération, on multiplie le graphe courant par le graphe G et on effectue l'union du graphe obtenu avec le graphe G.
FTo = G ;
pour k de 2 à n faire
FTk=FTk-1.G∪G ;
finpour
En fait, on arrête les itérations dès l'instant où FTk est identique à FTk-1.
Cliquer sur Anim pour démarrer l'animation, puis sur P ou S pour choisir un graphe.
L'écran présente toujours deux états de FT en cours de construction, au démarrage FTo qui contient les boucles et FT1 qui contient G.
La couleur rouge est utilisé sur le graphe de droite pour y mettre en évidence les arcs qui ont été ajoutés par rapport au graphe de gauche.
Remarque :
La fermeture transitive FT(G) est le plus petit graphe réflexif et transitif contenant G.
La fermeture transitive stricte FTS(G) est le plus petit graphe transitif contenant G.
Définition : Graphe inverse
G-1 = (X,E-1) est le graphe inverse du graphe G si et seulement si (x,y) ∈ E ⇔(y,x) ∈ E -1
Pour passer du graphe G à son graphe inverse G-1, il suffit de retourner le sens de tous les arcs.
Remarque :
G∪G-1 est le plus petit graphe symétrique contenant G.
