graph theory Flashcards
Qu’est-ce qu’un graphe simple ?
Graphe n’ayant ni boucle, ni plusieurs arcs allant d’un sommet à un autre (de direction similaire)
Citez des sommets adjacents et des arcs adjacents de ce graphe :
b et c sont des sommets adjacents
4 et 3 sont des arcs adjacents
Qu’est-ce que d pour l’arc 3 ?
Qu’est-ce que b pour l’arc 3 ?
b est l’extrémité initiale de 3
d est l’extrémité finale de 3
Quel est l’ordre de ce graphe ?
C’est un graphe d’ordre 5 (5 sommets)
Quels sont les prédecesseurs de d ?
a et b sont les prédécesseurs de d
Quels sont les successeurs de b ?
c et d sont les successeurs de b
De combien est le demi-degré intérieur de d ?
Le demi-degré intérieur de d est égale à 2
De combien est le demi-degré extérieur de b ?
Le demi-degré extérieur de b est de 2
Quel est le degré de d ?
Le degré de d est égal à 3
Quel élément de définir ce graphe comme “graphe simple”
Les arcs 5 et 6
ou
les arcs 5 et 4
Soit un ensemble S = {A,B, C,D} dont les éléments sont les sommets du graphe et un ensemble A = {(A,B), (B,A), (B,D), (C, C), (C,D)} dont les éléments sont les arcs de ce graphe.
Réalisez la représentation sagittale de graphe
Soit S = {A,B, C,D} ensemble des sommets du graphes
et A = {(A,B), (B,A), (B,D), (C, C), (C,D)} ensemble des arcs du graphe
La représentation saggitale de ce graphe est alors :
Qu’est-ce qu’un graphe complet ?
Graphe possédant n sommets tous reliés deux à deux par une arête
Qu’est-ce qu’un clique, pour un graphe quelconque G ?
Un sous-ensemble de sommets induisant un sous-graphe complet de G
Dessinez les graphes complets d’ordre 2, 3, 4 et 5
(Un graphe complet d’ordre n est noté : Kn)
Quel est la particularité de ce graphe ? pourquoi ?
il est biparti
Comment est définit un graphe biparti ?
Un graphe est dit biparti si pour l’ensemble de ses sommets en deux sous-ensembles U et V tel que chaque arête ait une extrémité dans U et une dans V.
Un graphe biparti permet notamment de représenter une relation binaire.
Comment est définit un graphe biparti complet ?
Un graphe est dit biparti complet (ou encore est appelé une biclique) s’il est biparti et contient le nombre maximal d’arêtes.
En d’autres termes, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de U est relié à chaque sommet de V.
Si U est de cardinal m et V est de cardinal n le graphe biparti complet est noté
Qu’est ce qu’un parcours Eulérien ?
C’est un parcours passant par toutes les arêtes une et une seule fois
Qu’est ce qu’un parcours Hamiltonien ?
C’est un parcours passant une et une seule fois par chaque un des sommets du graphe.
Qu’est-ce que le nombre chromatique d’un graphe ?
Qu’est qu’un graphe complet ?
Un graphe dont tous ses sommets sont adjacents deux à deux
