Theorie Des Graphes Flashcards
Un graphe est constitué par
- un ensemble de sommets
- une famille d’éléments du produit cartésien
Si les liens entre sommets sont orientés alors ce sont des arcs et c’est un graphe orienté
Si les liens ne sont pas orientés alors ce sont des arêtes et le graphe est non orienté
Un graphe est complet si
Chaque sommet du graphe est relié directement à tous les autres sommets
Propriétés :
- dans un graphe non orienté complet d’ordre n, tous les sommets sont de degré n-1
- le nombre d’arêtes pour Kn est égal à n(n-1)/2
Une clique est
Un sous graphe complet
Donc un sous graphe simple pour lequel il existe exactement une arête entre tout paire de sommet
Un graphe est dit connexe si
Pour tout couple de sommet il existe une chaîne reliant les deux points du couple
Un graphe fortement connexe
(Orienté)
Si il existe un chemin joignant chaque couple de sommet
Un graphe est dit simple si
- il n’existe pas de boucle
- il n’existe pas plus d’une arête entre 2 sommets (ou d’un arc de même orientation pour un graphe orienté)
Multigraphe
Graphe non orienté tel qu’il peut exister une boucle et/ou plus d’une arête entre un couple de sommet (on parle alors d’arêtes multiples)
Graphe valué
= Pondéré
Est un triplet (e,v,c) avec c une fonction de coût
(Arcs valués, type distance, tps…)
Ordre d’un graphe
Nombre de sommet du graphe
p-graphe
Pour un graphe orienté
Si le nombre d’arcs qui va d’un sommet x a un sommet y est inférieur ou égal a p alors le graphe est un p-graphe
Sous graphe de G
Graphe (G’) sont les sommets et les arêtes sont des sommets et des arêtes de G
Planarité
Un graphe G est dit planaire ssi il admet une représentation planaire où les points sont les sommets et les courbes sont les arêtes ou arcs
Les arcs ne doivent pas se croiser !!
Adjacence
- deux sommet sont adjacents s’il existe une arête/arc les reliant
- deux arêtes/arcs sont adjacentes si tu lles ont un sommet en commun
Arc incident
- un arc incident au sommet x vers l’extérieur = arc dont le sommet x est l’extrémité initiale (= arc sortant)
Inversement pour un arc entrant
Boucle
Un arc ou une arête de la forme (x,x) est une boucle
Chaîne
Dans un graphe G non orienté une chaîne est une séquence d’arête de G telle que chaque arête de la séquence ait une extrémité en commun avec l’arête précédente et l’autre extrémité avec l’arête suivante
Chemin
Dans un graphe G orienté, un chemin est une séquence d’arc telle que l’extrémité finale d’un arc coïncide avec l’extrémité initiale de l’arc suivant
Circuit
Graphe orienté
Chemin possédant le même sommet extrémité
Cycle
Graphe non orienté
Chaîne possédant le même sommet extrémité
Cycle élémentaire
Cycle ne passant pas deux fois par le même sommet à la exception du sommet initial qui est nécessairement le même que le sommet final
Cycle Hamiltonien
Cycle élémentaire passant une seule fois par tous les sommets du graphe
Degré d’un sommet
- nombrE d’arêtes incidentes à ce sommet, une boucle compte pour deux arêtes
- démi degré : extérieur = nbre arcs sortant (d+)
- demi degré : intérieur = nbre arcs entrants (d-)
Propriétés :
- la somme des degre de tous les sommets d’un graphe est égale au double d’un nombre total d’arêtes
- un graphe simple à un nombre pair de sommet de degré impair
Nombre chromatique
Nombre minimal de couleurs nécessaires pour colorier tous les sommets du graphe G sans que deux sommets adjacents soient de la même couleur
Propriétés :
- nbre chromatique est inférieur ou égal à k+1 avec k nombre de sommets
- nbre chromatique d’un graphe complet Kn est n
- le nbre chromatique du graphe sera supérieur ou égal à l’ordre de sa pluz grande clique
- nbre chroma d’un cycle élémentaire est 2 si son nombre de sommet est pair, sinon 3
Matrice adjacence
On indique les arêtes ou les arcs existants entre sommets d’origine et de destination
Comment colorer un graphe ?
Algo de Welsh-Powell
Classe sommet par plus haut degré et attribution des couleurs par ordre décroissant
Deux sommets reliés ne peuvent pas avoir la même couleur
Graphe eulerien
Graphe admettant un cycle eulerien
Graphe semi-eulerien
Graphe admettant une chaîne eulerienne
Théorème d’Euler pour un cycle eulerien.
Un multigraphe admet un cycle eulerien ssi
- le graphe est connexe
- Tours les sommets sont de degré pair =/= 0
Théorème d’Euler chaîne eulerienne.
Un multigraphe admet une chaîne eulerienne entre deux sommets i et j ssi
- G est connexe
- i et j degré impair
- degre des autres sommets pair
Il existe un circuit eulerien dans un graphe orienté
Ssi pour chaque sommet il y a autant d’arcs qui arrivent que d’arcs qui partent
