Théorie des graphes

Question 1

C’est quoi un graphe (non orienté) ? Comment cela est noté ?

Answer 1

Ce sont deux ensemble :
- Un semble de sommets, noté V (Vertices)
- Un ensemble d’arrêtes, noté E (Edges)

Question 2

Donner un exemple de boucle

Answer 2

Arrête uu

Question 3

C’est quoi un multigraphe ?

Answer 3

Graphe ou la présence de plusieurs arêtes est autorisée entre chaque paire de sommets.

Question 4

C’est quoi un voisin de u ?

Answer 4

v est voisins de u si l’arrête uv existe.

Question 5

C’est quoi le voisinage de u ? Comment cela est noté ?

Answer 5

C’est l’ensemble des voisins de u dans G :
N_g = {u : uv dans E}

Question 6

C’est quoi le degré d’un sommet u ? Comment cela est noté ?

Answer 6

C’est le nombre de voisin / Cardinal du voisinage d’un sommet
Noté d_G(u)

Question 7

C’est quoi une feuille / sommet pendant ?

Answer 7

C’est un sommet de degré 1 = exactement un voisin

Question 8

Comment sont noté le degré maximal et minimal d’un graphe ?

Answer 8

Max = DELTAMAJUSCULE_G
Min = deltaminuscule_g

Question 9

C’est quoi un graphe de type cycle ? Comment cela est noté ?

Answer 9

Graphe dont chaque sommet et lié à un suivant afin de faire un cycle.
Noté C_n

Question 10

C’est quoi un graphe complet ? Comment cela est noté ?

Answer 10

Graphe dont chaque sommet est lié à tous les autres.
Noté K_n

Question 11

C’est quoi une grille ? Comment cela est noté ?

Answer 11

Graphe dont chaque sommet est lié à 4 voisins sauf les extrémités qui sont lié soit à 3 soit à deux pour les coins

GR_{pxq}

Question 12

C’est quoi un tor ? Comment cela est noté ?

Answer 12

Grille où les “extremités” sont liées entre elle, donc chaque sommet à exactement 4 voisins

TR_{pxq}

Question 13

Exprimer la somme des degré des sommets d’un graphe en fonction du nombre d’arrête

Answer 13

https://imgbox.com/1YTLeJiC

Question 14

Donner un encadrement du nombre d’arrête en fonction du nombre de sommet

Answer 14

https://imgbox.com/WKX0cPzR

Question 15

C’est quoi un graphe partiel ?

Answer 15

Un graphe partiel de G est obtenu en gardant tous les sommets de G et en retirant certaines de ses arrêtes

Question 16

C’est quoi un sous-graphe de G induit par S dans V ? Comment est il noté ?

Answer 16

C’est un graphe obtenu en ne gardant que les sommets de S et les arrêtes de G entre les sommets de S.

G[S]

Question 17

C’est quoi un chemin ? C’est quoi les extrémités du chemin ?

Answer 17

Un chemin entre deux sommet u et v de G est une suite d’arêtes telle que deux arrête successives partagent un sommet comment.

Les extrémités sont les premières et dernière arête du chemin.

On peut aussi noter un chemin sur les sommets.

Question 18

C’est quoi la longueur d’un chemin ?

Answer 18

C’est le nombre d’arête d’un chemin.

S’il n’y en a aucune, la longueur vaut 0.

= NbsommetChemin -1

Question 19

C’est quoi un graphe partiel de G ?

Answer 19

Il est obtenu en gardant tous les sommets de G et en retirant certaines arêtes

Question 20

C’est quoi un sous-graphe de G induit par S inclus dans V ? Comment est t-il noté ?

Answer 20

Il est obtenu en ne gardant que les sommets de S et les arrête de G entre les sommets de S.
Il est noté G[S]

Question 21

C’est quoi un chemin entre deux sommet u et v ? C’est quoi les extrémité de ce chemin ?

Answer 21

C’est une suite d’arêtes où deux arrête successive partagent un sommet commun.

Les extrémités du chemin sont les sommet à la base et à la fin du chemin (ici u et v)

On peut aussi noter un chemin comme une suite de sommet.

Question 22

C’est quoi la longueur d’un chemin ?

Answer 22

C’est son nombre d’arête. Un chemin composé de 0 arête (entre u et u) est de longueur 0

Question 23

C’est quoi un chemin simple ?

Answer 23

Un chemin est dit simple si les arête de cette suite sont unique.

Question 24

C’est quoi un chemin élémentaire ?

Answer 24

Un chemin est dit élémentaire si les sommet de cette suite sont unique.

Question 25

Qu’implique le fait d’être élementaire pour un chemin ?

Answer 25

Il est aussi simple

Question 26

Qu’implique le fait d’être simple pour un chemin ?

Answer 26

Rien.

Question 27

C’est quoi un cycle ?

Answer 27

C’est un chemin de longueur au moins 3 où les deux extrémités sont lié par une arrête.

Question 28

C’est quoi un graphe connexe ?

Answer 28

Un graphe est connexe si pour tout sommet u,v il existe un chemin de u à v

Question 29

C’est quoi une composante connexe ?

Answer 29

C’est un sous-ensemble S maximal de V tel que le sous-graphe induit par S est connexe.

A noter que si G est déjà connexe il ne contient qu’une seule composante connexe composée de tous ses sommets

Question 30

C’est quoi une clique ?

Answer 30

Sous-ensemble de sommet de G induisant un graphe complet dans G.

Question 31

C’est quoi un sommet isolé ?

Answer 31

Sommet de degré 0

Question 32

C’est quoi un graphe vide ?

Answer 32

Graphe dont tous les sommets sont de degré 0 (E vide)

Question 33

C’est quoi un stable (ou indépendant) ?

Answer 33

Sous ensemble de sommets de G induisant un graphe vide

Question 34

Quelle relation y a t’il entre les clique et les stables dans un graphe G ?

Answer 34

Clique dans G barre = stable dans G et inversement

Avec G barre, le complémentaire de G

Question 35

C’est quoi un arbre ?

Answer 35

C’est un graphe connexe sans cycle

Question 36

Soit T = (V, E) un arbre à n sommets donner l’ensemble des propositions équivalente

Answer 36

• T est connexe et a n-1 arête
• T est sans cycle et a n -1 arête
• T est sans cycle et quelle que soit l’arête que l’on ajoute à T cela créer un cycle = Sans cycle maximal
• T est connexe et quelle que soit l’arête que l’on supprime on obtient un graphe non connexe = Connexe minimal
• Pour toute paire de sommet u,v T contient exactement un chemin entre u et v

Question 37

Donner une façon alternative de prouver qu’un graphe est connexe

Answer 37

S’il contient un arbre couvrant qui contient tout ses sommet (Réciproque vraie)

“Si on peut lui enlever des arrête pour enlever les cycles en trop”

Question 38

C’est quoi un arbre couvrant ?

Answer 38

Graphe partiel qui est un arbre

Question 39

Soit T un arbre à n sommets. Donner un encadrement de son nombre de feuilles en fonction de n

Answer 39

2 <= nbFeuille <= n - 1