Théorie des graphes Article, Signification, Explication
Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :
- le graphe d'une fonction (à distinguer de sa représentation graphique)
- un objet représentant une série de relations binaires, orientées ou non, entre des éléments d'un ensemble.
On nomme graphe un couple (S,A), S étant un ensemble et A une partie de S×S (produit cartésien d'ensembles).
Les éléments de S sont appelés les sommets, le nombre de sommets se nomme l'ordre du graphe.
On distingue deux types de graphes:
Graphiquement, une relation entre deux sommets d'un graphe orienté peut se représenter à l'aide d'une flèche entre ceux-ci. Dans le cas d'un graphe non orienté, c'est un trait qui symbolise cette relation.
La théorie des graphes étudie les propriétés de ces objets.
Parmi les problèmes classiques figurent :
Dans un graphe orienté, un chemin entre deux sommets a et b est une suite finie de n sommets (si) tels que a = s1, b = sn et pour tout i dans [1, n-1] il existe une arête entre si et si+1. Un chemin est dit élémentaire si un sommet y est présent au plus une fois.
Dans le cas d'un graphe non-orienté, on parle de chaîne.
Si un sommet est à la fois premier et dernier d'un chemin ou d'une chaîne, alors ce chemin ou cette chaîne est appelé un cycle. Dans le cas d'un graphe orienté, on utilise le terme de circuit.
Dans un graphe orienté, on distingue pour un sommet le degré entrant et le degré sortant. Le premier correspond au nombre d'arcs dont l'extrémité finale est . Le second est le nombre d'arcs dont l'extrémité initiale est . Le degré d'un sommet dans un graphe orienté est la somme du degré entrant et sortant de .
Une valuation d'un graphe est une fonction qui, à chaque arête, associe un poids (nombre réel).
Exemples : Une valuation possible d'un réseau routier est la longueur de la route. Une autre, le montant du péage à acquitter entre deux points, ou celle de toute autre ressource pour aller d'une ville à l'autre (consommation de carburant, coût, temps, etc.).
Un graphe complet est un graphe dont tous les sommets sont reliés deux à deux. Le graphe complet à n sommets est noté: .
voir l'article Graphe complet.
Un graphe orienté est dit fortement connexe, si pour tout couple de sommets (u,v) du graphe il existe un chemin de u à v et de v à u. Les travaux de Pitts et McCullough suggèrent que le cerveau des mammifères est fortement connexe.
Graphe qui contient un cycle hamiltonien. Le graphe est nommé hypohamiltonien s'il suffit d'en retirer un sommet quelconque pour qu'il devienne hamiltonien. Utile dans le problème du voyageur de commerce.
Un graphe est un graphe de permutation si il existe une permutation dont le graphe est son graphe d'inversion.
Un graphe est planaire s'il existe au moins une façon de le dessiner dans le plan sans que deux arêtes se croisent. Cette propriété est importante pour les circuits imprimés monocouche.
C'est un article concernant le Théorie des graphes. La page contient la signification du Théorie des graphes , Description et explication au sujet de Théorie des graphes Définition formelle
Quand on parle de graphes non orientés, il est admis ne pas en préciser le type.Exemples
Champ d'utilisation
Cette théorie est fortement liée à l'algorithmique et à la complexité.Détails
Définitions
Arbre couvrant minimal
Un arbre couvrant minimal est un arbre couvrant d'un graphe pondéré dont la somme des poids des arêtes est minimal.Boucle
Arête dont les extrémités sont confondues. Notion utile en théorie des automates.Chemins et chaînes
Chaîne eulérienne
Une chaîne eulérienne est une chaîne composée de toutes les arêtes d'un graphe prises chacune une et une seule fois.
Un graphe connexe possède une chaîne eulérienne ssi tous ses sommets sont de degré pair à l'exception d'au plus 2 d'entre eux. Chaîne hamiltonienne
Une chaîne hamiltonienne est une chaîne composée de tous les sommets d'un graphe pris chacun une et une seule fois.Cycles et circuits
Cycle eulérien
Un cycle eulérien est une chaîne eulérienne dont les extrémités sont confondues.
Un graphe connexe possède un cycle eulérien ssi tous ses sommets sont de degré pair.Cycle hamiltonien
Un cycle hamiltonien est une chaîne hamiltonienne dont les extrémités sont confondues.Degré
Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes issues de ce sommet. La somme des degrés de chaque sommet est égale au double du nombre total d'arêtes..Partition
Une partition des sommets d'un graphe est ensemble disjoint de sommets telle que leur union est l'ensemble des sommets.Sous graphe
Soit G=(S,A) un graphe, un sous-graphe induit ou sous-graphe de G, est un graphe G'=(S',A'), où:
Si , G' est sous-graphe couvrant.
Si , G' est un sous-graphe partiel.Sous-graphe complet ou clique
On nomme clique un sous-graphe complet. Une p-clique est une clique de p sommets. Cette notion est utile pour constituer des groupes en classification automatique.Sous-graphe stable ou ensemble stable
Un stable est un sous-graphe sans arêtes...Valuation d'un graphe
Classes de graphes
Arbre
On nomme arbre un graphe connexe acyclique (sa forme évoque en effet la ramification des branches d'un arbre). On distingue deux types de sommets dans un arbre :
Graphe biparti
Un graphe est biparti si il y a une partition des sommets du graphe en deux sous ensembles A et B telle que toutes les arêtes du graphe ont un sommet dans A et un sommet dans B.Graphe complet
Graphe connexe
Un graphe non orienté est connexe, si et seulement si pour toute paire de sommets [a,b] il existe une chaîne entre les sommets a et b.
Si on parle de connexité pour un graphe orienté, c'est que l'on considère non pas ce graphe, mais le graphe non-orienté correspondant.Graphe k-connexe
Un graphe non orienté est k-connexe s'il reste connexe après suppression d'un ensemble quelconque de k-1 arêtes et s'il existe un ensemble de k arêtes qui déconnecte le graphe. Autrement dit, un graphe est k-connexe si et seulement s’il existe au moins k chaînes indépendantes (arcs-disjointes) entre chaque couple de sommets. Cette notion est utilisée en électronique, en calcul de la fiabilité, et dans l'étude de jeux de stratégie comme le cut and connect.Graphe fortement connexe
Graphe hamiltonien
Graphe d'intervalles
Si I est un ensemble d'intervalles sur les réels et qu'on peut associer à chaque sommet un intervalle et que pour chaque sommets u et v il y a une arête entre u et v si et seulement si l'intersection entre leurs intervalles associés n'est pas nulle, alors le graphe défini par ces sommets et ces arêtes est un graphe d'intervalles.Graphe de permutation
Soit P une permutation de la séquence 1,...,n. Le graphe d'inversion associé à P est le graphe dont les sommets sont les entiers 1,...,n et dont pour tout sommets u et v il y a une arête entre u et v si et seulement si u et v sont inversés dans P.Graphe planaire
Graphe simple
Graphe sans boucle, et très simple de personnalité.Graphe split
Un graphe est split si il existe une partition des sommets du graphe en deux sous ensembles S et C telle que S est un ensemble stable et C est une clique.Algorithmes importants de la théorie des graphes
Algorithmes de plus court chemin
Algorithme d'arbres couvrant minimaux
Algorithme pour les flots maximums
Algorithmes de parcours de graphe
procedure BFS(arbre a):
{
locale: File f, Noeud x,z;
CreerFile(f);
Enfiler(f, Racine(a));
debut
TANT-QUE NON FileVide(f) FAIRE
x=Défiler(f);
TANT-QUE ExisteFils(x) FAIRE
z=FilsSuivant(x);
Enfiler(f, z);
FIN-TANT-QUE
FIN-TANT-QUE
fin
}NB : Cela suppose la connaissance du concept de file (FIFO : first in, first out).
(aussi appelé si je ne me trompe pas, algorithme de Trémaux)procedure DFS (arbre a):
{
Noeud u = Racine(a);
Marquer(u);
debut
POUR tout successeur w de u FAIRE
SI NonMarqué(w)
ALORS DFS(SousArbre(w));
FIN-SI
FIN-POUR
fin
}Marquer(Noeud u) : marque un noeud, de manière à ne pas le considérer plusieurs fois.
SousArbre(noeud u) : retourne le sous-arbre de racine u.Algorithmes de coloration
(voir coloration de graphe)Algorithmes divers
Voir aussi
Liens externes