Un graphe est un ensemble de points appelés sommets reliés ou pas par des lignes appelées arêtes.
Un graphe est dit orienté si les arêtes sont orientées. Elles ne peuvent être parcourues que dans un sens symbolisé par une flèche (→―).
(les arêtes ont une origine et une extrémité)
On parle de graphe non-orienté quand les arêtes peuvent alors être parcourues dans les deux sens.
Le nombre total de sommets définit l'ordre du graphe.
Deux sommets reliés entre eux sont dits adjacents.
Dans le cas de graphe orienté on parle d'arcs.
Un sommet relié à lui-même définit une boucle.
Un sommet qui n'est relié à aucun autre sommet est dit isolé.
Une arête reliant deux sommets est dite incidente à ces sommets.
Le degré d'un sommet est le nombre d'arêtes incidentes à ce sommet. Une boucle compte pour deux.
Dans le cas de graphe orienté on parle de degré entrant ou sortant.
La somme des degrés de tous les sommets d'un graphe non-orienté est égal au double du nombre total d'arêtes. Elle est donc paire !
Ainsi, il y a un nombre pair de sommets de degré impair.
Une chaine est une suite d'arêtes consécutives.
La chaine est dite fermée lorsque les deux extrémités sont les mêmes.
La longueur d'une chaine est le nombre d'arêtes qu'elle contient.
Dans le cas de graphe orienté on parle de chemin, chemin fermé, longueur de chemin.
Un cycle est une chaine fermée formé d'arêtes distinctes.
Dans le cas de graphe orienté on parle de circuit.
Un graphe est dit simple s'il ne comporte pas de boucle et si au plus une arête relie une paire de sommets.
Un graphe est dit complet si tous les sommets sont deux à deux adjacents.
Un graphe est dit connexe si deux sommets quelconques peuvent être reliés par une chaine.
Un sous graphe est un graphe composé de certains de ses sommets d'un autre graphe avec toutes les arêtes qui les relient.
Une chaine est dite eulérienne si elle contient chaque arête une et une seule fois.
Un cycle eulérien est une chaine eulérienne fermée, c'est-à-dire un cycle qui passe une et une seul fois par chaque arête.
Un graphe non-orienté connexe admet une chaine eulérienne si est seulement si le nombre de sommets de degré impair est 0 ou 2.
- Si il y a deux sommets de degré impair, ce sont les extrémités de la chaine eulérienne.
- Si il y a plus de deux sommets de degré impair, il n'existe pas de chaine eulérienne.
- Un graphe connexe admet un cycle eulérien si est seulement si tous les sommets sont de degré pair.
Un graphe est dit pondéré si les arêtes sont affectées de coefficients positifs appelés poids. Le poids d'un chemin est la somme des poids des arcs qui le composent. Un plus court chemin entre deux sommets est un chemin de poids minimal Algorithme de Dijkstra est un algorithme donnant une plus courte chaîne entre deux sommets.