Geek or not

Accueil du site > MOCA > Définitions sur les graphes

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 10 mars 2006.
3861 personnes ont affiché cette page et sa popularité est de 100.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Définitions sur les graphes

Graphes orientés

Définition d’un graphe orienté

Un graphe orienté est défini par le doublet où :

X est l’ensemble des sommets du graphe
U est l’ensemble des arcs du graphe


Graphe orienté

$X = \left\lbrace1, 2, 3, 4, 5\right\rbrace$
$U = \left\lbrace u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, u_{7}, u_{8}, u_{9}\right\rbrace$

Définition d’un chemin

Un chemin est défini par une liste de sommets (1,2,...,k) tel qu’il existe un arc de chaque sommet vers le suivant.

Voir la figure Graphe orienté

$P_{1} = \left\lbrace 1, 2, 3, 4\right\rbrace$
$P_{1} = \left\lbrace u_{1}, u_{3}, u_{4}\right\rbrace$

Définition de la longueur d’un chemin

La longueur d’un chemin est définie par le nombre d’arcs composant le chemin.

Voir la figure Graphe orienté

$L(P_{1}) = 3$

Définition d’un circuit

Un circuit est un chemin d’un sommet vers lui-même.

Voir la figure Graphe orienté

$P_{2} = \left\lbrace1, 2, 3, 4, 5, 1\right\rbrace$
$P_{2} = \left\lbrace u_{1}, u_{3}, u_{6}, u_{5}\right\rbrace$

Définition d’une boucle

Une boucle est un circuit de longueur 1

Voir la figure Graphe orienté

$P_{3} = \left\lbrace5, 5\right\rbrace$
$P_{3} = \left\lbrace u_{8}\right\rbrace$

Définition d’un chemin élémentaire

Un chemin élémentaire est un chemin tel qu’en le parcourant, on ne rencontre pas deux fois le même sommet.

Voir la figure Graphe orienté

$P_{4} = \left\lbrace1, 2, 3\right\rbrace$ est un chemin élémentaire
$P_{5} = \left\lbrace \underline{2}, 1, \underline{2}, 3, 4\right\rbrace$ n’est pas un chemin élémentaire

Définition d’un chemin simple

Un chemin simple est un chemin ne passant pas plus d’une fois par le même arc.

Voir la figure Graphe orienté

$P_{6} = \left\lbrace2, 1, 2, 3, 4\right\rbrace$
$P_{6} = \left\lbrace u_{2}, u_{1}, u_{3}, u_{4}\right\rbrace$ est un chemin simple
$P_{7} = \left\lbrace1, 2, 1, 2, 3\right\rbrace$
$P_{7} = \left\lbrace \underline{u_{1}}, u_{2}, \underline{u_{1}}, u_{3}\right\rbrace$ n’est pas un chemin simple

Définition d’un graphe complet

Un graphe est dit comple si chaque sommet possède un [1] arc vers tout autre sommet y compris lui-même.


Graphe complet

$N$ sommets $\Rightarrow N^2$ arcs

pages : 1 2 3 4 5 6 7 8 >>

[1] et un seul

Poster un message