Graphe Flashcards
(88 cards)
1
Q
Graphe non orienté
A
Le sens des aretes n’est pas défini (ie réciporcité de la liaison)
2
Q
Γ(v)
A
{voisins de v ds G}
3
Q
Degré
A
d(v) = nb de voisins de v
4
Q
Chaîne
A
Suite d’arêtes ininterrompue
5
Q
Cycle
A
Chaîne qui revient sur le premier sommet
6
Q
Graphe orienté
A
Sens appliqué aux aretes (ie pas réciprocité de l’arête)
7
Q
Γ+(v)
Γ-(v)
A
{successeurs de v dans G}
{prédécesseurs de v dans G}
8
Q
d+(v)
d-(v)
A
Demi degré extérieur (ie des arcs partant de v)
Demi degré intérieur (ie des arcs arrivant sur v)
9
Q
Chemin
A
Chaîne mais pour les graphes orientés
10
Q
Circuit
A
Cycle qui respecte l’orientation des aretes
11
Q
Chemin Hamiltonien
A
Chemin qui ne passe qu’une seule fois par chaque sommet
12
Q
Graphe hamiltonien
A
Graphe contenant au - un chemin hamiltonien
13
Q
Graphe connexe
A
Tte paire de sommet est relié par 1 chaîne
14
Q
Sous-graphe
A
1 partie d’1 graphe (ie on a supprimé des sommets avec les aretes qui y sont associées)
15
Q
Composante connexe
A
Sous-graphe de G connexe maximal
16
Q
Sous-ensemble maximal
A
L’ajout d’un élément à G lui faire perdre une certaine propriété (ex connexe)
17
Q
Forte connexité
A
(Uniquement pour les graphes orientés) tt couple de sommet est tel que les deux sommants sont reliés par un chemin dans les deux sens
18
Q
Composante f-connexe
A
Sous-graphe fortement connexe maximal
19
Q
Graphe réduit
A
Graphe réduit uniquement à ses composantes fortement connexes
20
Q
Tri topologique
A
(Dans graphes acycliques orientés) ordre total sur l’ensemble des sommets dans lequel s précède t pour tout arc d’1 sommet s à t
21
Q
Matrice d’adjacente (ou structure booléenne)
A
Lignes = sommet de départ
Colonne = sommet d’arrivée
Si a(ij) = 0 pas d’arc entre le sommet i et j
Si a(ij) = 1 arc de longueur 1 entre le sommet i et j
La matrice d’adjacente à la puissance p donne les arcs de longueurs p entre deux sommets
22
Q
Fermeture transitive
A
τ(G) = (V, τ(E)) Il existe 1 chemin de x à y dans G (ie chemin fictif qui traduit un chemin entre deux sommets)
Dans la fermeture transitive il y a ts les arcs possibles => c’est un graphe complet
23
Q
Graphe partiel
A
( différent de sous-graphe) graphe dont on a enlevé des arêtes sans toucher aux sommets
24
Q
Graphe τ-équivalent
Graphe τ-minimal, τ-équivalent
Graphe τ-minimum, τ-équivalent
A
G’ est la fermeture transitive de G
G’’ est le graphe partiel de G tel qu’on a retiré le maximum d’arêtes sans altérer la fermeture transitive
τ(G) = τ(G’)
τ(G) = τ(G’’)
Graphe τ-minimal, τ-équivalent avec le moins d’arcs possibles
25
TH : si G est sans circuit ( acyclique )
Il existe un unique τ-minimal τ-équivalent à G
26
Chaîne eulérienne
Chaîne qui passe par ttes les arêtes de G 1 seule fois
27
TH d’Euler
1 graphe admet une chaîne eulérienne ssi le nb de sommet de degré impaire est 0 ou 2.
Si c’est 0 : pas de pbl il y a un cycle
Si c’est 2 : il y a un départ et une arrivée
Si > 2 : impossible d’avoir 1 chaîne Eulérienne
28
Isthme
Arête telle que la retirer déconnecte le graphe
29
Ensemble stable
Sous-ensemble de G tel que 2 sommets ne sont jamais voisins
30
Stabilité maximum
L’ensemble des sommets qui ne sont jamais voisins entre eux
31
Nb de stabilité
α(G) = cardinal du + grand ensemble stable de G
32
TH : ds un graphe de n sommets et de degré max h
La cardinalité de tt ensemble stable maximal est supérieur ou égal à la partie entière supérieure de n/(h+1)
33
Graphe complet
Graphe dont ts les sommets sont adjacents 2 à 2 (ie tt couple de sommets est relié par 1 arête)
Si G possède n sommets alors il y n(n-1)/2 arêtes
34
Clique
(Graphes non orientés) c’est un sous-graphe complet de G
35
Partition des sommets en cliques
G = (V,E) un graphe , P = {C1, …, Cn} partition des sommets de G e clique si :
- C1, …, Cn sont des cliques de G
- pour tout i,j appartenant à 1 à n V(Ci) intersection V(Cj) = ens vide
- V(C1) union V(C2) union …. union V(Cn) = V(G)
36
TH : inégalité entre |S| et |P|
S stable de G et P partition en cliques des sommets de G alors
|S| < ou = |P| si égalité alors S est un stable maximum et P une partition minimum
37
Ensemble absorbant
(Graphes orientés) sous-ensemble A de sommets de G tel que tt sommet n’appartenant pas à A a un successeur dans A
38
Nb d’absorption
β(G) = cardinal du + petit ensemble absorbant
39
Ensemble absorbant minimum
Il n’existe pas d’absorbant plus petit
40
Noyau
(Graphes orientés) sous-ensemble de sommets de G qui est à la fois stable et absorbant (il peut ne pas y avoir de noyau dans un graphe comme il peut y en avoir plusieurs)
PS: dans un jeu être sur dans le noyau correspond à une position perdante
41
Fonction de Grundy
But : trouver les noyaux
( Graphes orientés) g si est 1 application de V dans l’ens des entiers naturels telle que g(v) est le + petit entier non attribué aux successeurs de v
Noyau g(v) = 0
42
Cycle
Chaîne qui ne contient pas 2 fois le même arc et dont le premier sommet est aussi le dernier
43
Cycle élémentaire
Cycle qui ne passe qu’une seule fois par chaque sommet du cycle
44
Notation vectorielle
Les arcs d’un graphe sont numérotées de 1 à m, on peut faire correspondre à tt cycle un m-uplet composé de -1,1 et 0.
-1 si arc appartient au cycle + parcourt dans mauvais sens
1 si arc appartient au cycle + parcourt dans le bon sens
0 si arc appartient pas au cycle
Combinaison linéaire possible entre plusieurs cycles
45
Base de cycles (famille de cycles)
Libre (cycles non exprimables comme CL des autres)et génératrice (tt cycle peut s’écrire comme un CL des cycles de la famille)
46
Nb cyclomatique
μ(G) = nb d’élément dans 1 base de cycles
Pour un graphe à n sommets, m arcs et p composantes connexes
μ(G) = m - n + p
47
Cocycle
(A ens des sommets de G) ω(A) l’ENS des arcs incidents à A.
Ceux quittant A seront notés positivement et ceux arrivant sur A seront notés négativement
48
Base de cocycles
Famille de cocycles libre et génératrice
49
Nb de cocyclomatique
γ(G) = nb éléments d’une base de cocycles
Si G possède n sommets avec p composantes connexes
γ(G) = n - p
50
Graphe planaire
Peut se représenter sur un plan (2D) sans qu’aucune arête ou arc ne croise une autre arête ou arc.
K5 pas planaire => Kx non plus si x > 5 car contient Kx-1
K2, K3 et K4 sont planaires
51
Face
Région du plan limitée par des aretes dont l’ensemble constitue la frontière + face ∞
52
Graphe planaire topologique
Représentation planaire d’un graphe planaire (les contours des cycles élémentaires)
53
TH : graphes planaire topologiques
Les contours des faces finies constituent 1 base de cycles
54
TH d’Euler pour les graphes planaires
Dans un graphe planaire de n sommets, m arêtes et f faces on a
n - m + f = 2
55
Graphe dual d’un graphe planaire topologique
G* graphe dual ssi les sommets de G* = faces de G et e* = (f*, g*) est 1 arête de G* ssi les faces f et g de G partagent l’arête e
56
Graphe biparti
Si son ensemble de sommets peut être divisé en 2 sous-ensembles disjoints U et V tel que chaque arête ait 1 extrémité dans U et l’autre dans V => G = (U, V, E) tel que pour tout (u, v) dans E,
{u dans U, v dans V}
57
Biclique (graphe biparti complet)
Graphe biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble
58
Mineur d’un graphe
S’il peut être obtenu en contractant des arêtes d’un sous-graphe
(ie H peut être obtenu en réalisant les opérations sur G:
-suppression d’un sommet isolé (de degré 0)
-suppression d’une arête sans modifier les extrémités
-contraction d’une arête (ie fusion de deux sommets)
59
TH de Kuratowski
Un graphe est planaire ssi il ne contient pas 1 sous-graphe partiel qui soit une expansion d’un K5 ou d’un K3,3
60
TH de Robertson-Seymour
Un graphe est planaire ssi in ne contient pas comme mineur un K5 ou un K3,3
61
K5
K3,3
K5 : graphe complet de 5 sommets
K3,3 : graphe à 6 sommets, 3 d'entre eux se connectant aux trois autres.
62
Coloration
Colorier les sommets sans que deux voisins aient la même couleur
Les sommets de la même couleur forment un stable
63
Nb chromatique
γ(G) = + petit nb de couleur pour un coloration de G
γ(G) = nb nécessaire et suffisant de couleurs pour colorier le graphe
-impossible de colorier G avec - de γ(G) couleurs
-possible de colorier G avec plus de γ(G) couleurs
Tt majorant de γ(G) est le nb de couleurs suffisant pour colorier G
Tt minorant de γ(G) est le nb de couleurs nécessaire pour colorier G
64
TH des 4 couleurs
Si G est planaire => γ(G) < ou = 4
tte carte peut être coloriée d’au + 4 couleurs
65
Ordre
Ord(G) = taille d’une clique maximum de G
66
TH sur l’ordre de G
G un graphe d’ordre Ord(G) => γ(G) > ou = Ord(G)
67
TH de Brooks
G = (V, E) => il est toujours possible de colorier G avec dmax(G) + 1 couleurs
Avec dmax(G) le degré maximum des sommets de G
68
Reliement contraction
But : vérifier une hypothèse de couleur
Permet d’envisager les 2 cas de figure à chaque fois (réalise les deux )
- pour un graphe complet (ou une clique) de n sommets il faut n couleurs
- sinon prendre 2 sommets a et b non reliés -> soit ils ont même couleur => cas 1 => fusion des deux sommets => contraction
-> soit ils ont couleurs différentes => cas 2 => ajout d’un arête => reliement
Le plus petit graphe complet possède le nombre de couleurs nécéssaire pour colorier G
69
Coloration des arêtes
Sans que deux arêtes adjacentes aient la même couleur
2 arêtes adjacentes sont deux arêtes qui partagent un même sommet
70
Indice chromatique
γ’(G) = nb de couleurs nécessaire pour colorier les arêtes de G
71
Graphe des arêtes (ou Line graph)
L(G) = (Y,B) associé à G = (X,A)
- Y = A ( 1 sommet par arête de G)
- [a,b] arête de L si a et b ont 1 extrémité commune dans G
=> les sommets deviennent des arêtes et vice versa
72
Couplage
Sous-ensemble d’arêtes de G tel que 2 arêtes quelconques sont non adjacentes
73
Couplage maximal
Couplage tel que ajouter n’importe quelle arête du graphe à ce coulage lui fait perdre sa qualité de couplage
74
Couplage maximum
Couplage ayant un nb max d’arêtes non adjacentes
75
Couplage parfait
Couplage tel que chaque sommet est 1 sommet du couplage (ie tous les sommets sont touchés par le couplage)
Si nb de sommet est impaire => couplage parfait impossible
Si nb de sommet est pair => pas forcément existence d’un couplage parfait
Couplage maximum n’implique pas forcément couplage parfait
76
Arbre
1) graphe connexe sans cycle
2) graphe sans cycle ayant n-1 arêtes (n = nb de sommets)
3) graphe connexe et n-1 arêtes
4) graphe sans cycle et en ajoutant 1 arête on crée 1 et 1 seul cycle
5) graphe connexe et si on supprime 1 arête, il n’est plus connexe
6) graphe contenant 1 chaîne et 1 seule entre toute paire de sommets
77
Arbre couvrant
Graphe partiel connexe et sans cycle
78
TH : graphe partiel admet un arbre
1 graphe admet un graphe partiel qui est un arbre ssi il est connexe
79
Arbre couvrant de poids minimum
Soit un graphe non orienté connexe dont les arêtes sont pondérées, 1 arbre couvrant de poids minimal (ACM) de ce graphe est un arbre couvrant dont la somme des poids des arêtes est minimale.
80
Graphe des tâches
Chaque tâche = un sommet
On ajoute un sommet pour le début et un sommet pour la fin du graphe
Chaque arc correspond à une tâche d’antériorité (ie tâche d’origine est antérieure à la tâche d’arrivée de l’arc)
Le poids de chaque arc = durée de la tâche située à l’origine de celui-ci
81
Date de début au plus tôt
D’une tâche est la date avant laquelle il est impossible de la commencer à causes des contraintes d’antériorités
82
Date de début au plus tard
D’une tâche est la date après laquelle on ne doit pas la commencer sous peine de retarder l’ensemble du projet
83
Marge totale
Retard que l’on peut prendre sur cette tâche sans modifier la durée optimale du projet
T+tard(i) - T+tot(i)
84
Marge libre
Retard que l’on peut prendre sur cette tâche sans modifier les dates de départ au plus tôt des tâches postérieures
Min[t(i+1)-t(i)-d(i)]
85
Marge certaines
Retard que l’on peut prendre sur cette tâche sans modifier les dates de départ au plus tôt des tâches postérieures, tout en sachant que les tâches précédentes ont commencées à leur date au plus tard.
Min[t(i+1)-max{min[t(i)-d(i+1)]+d(i+1)}-d(i)]
86
Tâche critique
Tâche pour laquelle aucun retard ne doit être pris sous peine de modifier la durée optimale du projet
87
Chemin critique
Chemin allant du début à la fin du projet, constitué intégralement d’une succession de tâches critiques
88
Circuit absorbant
Circuit dont la valeur totale est négative
