Theorie Des Graphes

Question 1

Un graphe est constitué par

Answer 1

• 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é

Question 2

Un graphe est complet si

Answer 2

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

Question 3

Une clique est

Answer 3

Un sous graphe complet
Donc un sous graphe simple pour lequel il existe exactement une arête entre tout paire de sommet

Question 4

Un graphe est dit connexe si

Answer 4

Pour tout couple de sommet il existe une chaîne reliant les deux points du couple

Question 5

Un graphe fortement connexe

Answer 5

(Orienté)
Si il existe un chemin joignant chaque couple de sommet

Question 6

Un graphe est dit simple si

Answer 6

• 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é)

Question 7

Multigraphe

Answer 7

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)

Question 8

Graphe valué

Answer 8

= Pondéré

Est un triplet (e,v,c) avec c une fonction de coût

(Arcs valués, type distance, tps…)

Question 9

Ordre d’un graphe

Answer 9

Nombre de sommet du graphe

Question 10

p-graphe

Answer 10

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

Question 11

Sous graphe de G

Answer 11

Graphe (G’) sont les sommets et les arêtes sont des sommets et des arêtes de G

Question 12

Planarité

Answer 12

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 !!

Question 13

Adjacence

Answer 13

• 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

Question 14

Arc incident

Answer 14

• 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

Question 15

Boucle

Answer 15

Un arc ou une arête de la forme (x,x) est une boucle

Question 16

Chaîne

Answer 16

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

Question 17

Chemin

Answer 17

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

Question 18

Circuit

Answer 18

Graphe orienté

Chemin possédant le même sommet extrémité

Question 19

Cycle

Answer 19

Graphe non orienté

Chaîne possédant le même sommet extrémité

Question 20

Cycle élémentaire

Answer 20

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

Question 21

Cycle Hamiltonien

Answer 21

Cycle élémentaire passant une seule fois par tous les sommets du graphe

Question 22

Degré d’un sommet

Answer 22

• 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

Question 23

Nombre chromatique

Answer 23

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

Question 24

Matrice adjacence

Answer 24

On indique les arêtes ou les arcs existants entre sommets d’origine et de destination

Question 25

Comment colorer un graphe ?

Answer 25

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

Question 26

Graphe eulerien

Answer 26

Graphe admettant un cycle eulerien

Question 27

Graphe semi-eulerien

Answer 27

Graphe admettant une chaîne eulerienne

Question 28

Théorème d’Euler pour un cycle eulerien.

Un multigraphe admet un cycle eulerien ssi

Answer 28

• le graphe est connexe
• Tours les sommets sont de degré pair =/= 0

Question 29

Théorème d’Euler chaîne eulerienne.
Un multigraphe admet une chaîne eulerienne entre deux sommets i et j ssi

Answer 29

• G est connexe
• i et j degré impair
• degre des autres sommets pair

Question 30

Il existe un circuit eulerien dans un graphe orienté

Answer 30

Ssi pour chaque sommet il y a autant d’arcs qui arrivent que d’arcs qui partent