Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :
La théorie des graphes concerne cette seconde acception.
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:
Quand on parle de graphes non orientés, il est admis ne pas en préciser le type.
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 :
Cette théorie est fortement liée à l'algorithmique et à la complexité.
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 :
Un arbre couvrant minimal est un arbre couvrant d'un graphe pondéré dont la somme des poids des arêtes est minimal.
Arête dont les extrémités sont confondues. Notion utile en théorie des automates.
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.
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.
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.
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.
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..
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 .
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 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.
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.
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 dont on peut relier tous les sommets par un chemin unique. 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 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.
Graphe sans boucle, et très simple de personnalité.
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.
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.
Un stable est un sous-graphe sans arêtes...
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.).
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.
(voir coloration de graphe)
