Définitions diverses sur les graphes orientés
Définition : Sous-graphes
(X',E') est un sous-graphe de (X,E) si
1) X' ⊆ X ,
2) E' est la restriction de E à X'.
Pour passer d'un graphe à un de ses sous-graphes, on enlève des points et donc en conséquence les arcs qui ne sont plus définis parce que les points ont disparus. Le graphe lui-même fait partie de l'ensemble de ses sous-graphes.
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Définition : Graphes partiels
(X,E') est un graphe partiel de (X,E)
si E ⊆ E‘,
c'est-à-dire (∀ (x,y) ∈ XxX ) ( x Γ' y ⇒ x Γ y ).
Pour passer d'un graphe à un de ses graphes partiels, on enlève simplement des arcs. Le graphe lui-même fait partie de l'ensemble de ses graphes partiels.
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Définition : Sous-graphes partiels
(X',E') est un sous-graphe partiel de (X,E)
si X' ⊆ X, E' ⊆ E et x Γ' y ⇒ x ∈ X' et y ∈ X'.
Pour passer d'un graphe à un de ses sous-graphes partiels, on enlève des points, les arcs qui sont adjacents à ces points (c'est-à-dire qui ont comme extrémités un de ses points), mais également des arcs supplémentaires qu'on aurait gardé dans le sous-graphe. Le graphe lui-même fait partie de l'ensemble de ses sous-graphes partiels.
Cliquez sur précédent et suivant pour avoir de nombreux exemples petits ou grands en utilisant le bouton du bas.
Définition : Isomorphisme de graphes ou de sous-graphes
Une application Φ de (X,E) dans (X',E') est un isomorphisme si et seulement si :
1) Φ est une application bijective de X sur X' ,
2) (∀ (x,y) ∈ XxX)
( x Γ y si et seulement si Φ(x) Γ' Φ(y) ).
On dit alors que les graphes (X,E) et (X',E') sont isomorphes.
Deux graphes sont isomorphes si on peut renommer les points d'un des deux graphes de telle sorte qu'après modification des identifiants des points, les deux graphes deviennent identiques.
Le problème le plus intéressant est en général de tester si un graphe G1 est isomorphe à un sous-graphe d'un autre graphe G2.
Définition : Graphe complet au sens des arêtes
Un graphe (X,E) est complet au sens des arêtes
si ( ∀ (x,y) ∈ XxX ) ( x Γ y ou y Γ x ).
Cliquez sur les flèches pour voir quelques exemples.
Définition : Graphes complets au sens des arcs (ou cliques)
Un graphe (X,E) est complet au sens des arcs s'il est symétrique et complet au sens des arêtes.
Remarque :
Tous les graphes de n points complets au sens des arcs sont isomorphes et on les désigne par Kn.
On les appelle également des cliques.
Pour certains problèmes, on s'intéresse aux sous-graphes d'un graphe qui sont des cliques. C'est en particulier le cas pour les problèmes de coloration où on doit donner une couleur différente à tout couple de points qui sont reliés par une arête.
Cliquez sur les flèches pour voir quelques exemples.
