Graphe Flashcards
Graphe non orienté
Le sens des aretes n’est pas défini (ie réciporcité de la liaison)
Γ(v)
{voisins de v ds G}
Degré
d(v) = nb de voisins de v
Chaîne
Suite d’arêtes ininterrompue
Cycle
Chaîne qui revient sur le premier sommet
Graphe orienté
Sens appliqué aux aretes (ie pas réciprocité de l’arête)
Γ+(v)
Γ-(v)
{successeurs de v dans G}
{prédécesseurs de v dans G}
d+(v)
d-(v)
Demi degré extérieur (ie des arcs partant de v)
Demi degré intérieur (ie des arcs arrivant sur v)
Chemin
Chaîne mais pour les graphes orientés
Circuit
Cycle qui respecte l’orientation des aretes
Chemin Hamiltonien
Chemin qui ne passe qu’une seule fois par chaque sommet
Graphe hamiltonien
Graphe contenant au - un chemin hamiltonien
Graphe connexe
Tte paire de sommet est relié par 1 chaîne
Sous-graphe
1 partie d’1 graphe (ie on a supprimé des sommets avec les aretes qui y sont associées)
Composante connexe
Sous-graphe de G connexe maximal
Sous-ensemble maximal
L’ajout d’un élément à G lui faire perdre une certaine propriété (ex connexe)
Forte connexité
(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
Composante f-connexe
Sous-graphe fortement connexe maximal
Graphe réduit
Graphe réduit uniquement à ses composantes fortement connexes
Tri topologique
(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
Matrice d’adjacente (ou structure booléenne)
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
Fermeture transitive
τ(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
Graphe partiel
( différent de sous-graphe) graphe dont on a enlevé des arêtes sans toucher aux sommets
Graphe τ-équivalent
Graphe τ-minimal, τ-équivalent
Graphe τ-minimum, τ-équivalent
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
TH : si G est sans circuit ( acyclique )
Il existe un unique τ-minimal τ-équivalent à G
Chaîne eulérienne
Chaîne qui passe par ttes les arêtes de G 1 seule fois
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
Isthme
Arête telle que la retirer déconnecte le graphe
Ensemble stable
Sous-ensemble de G tel que 2 sommets ne sont jamais voisins
Stabilité maximum
L’ensemble des sommets qui ne sont jamais voisins entre eux
Nb de stabilité
α(G) = cardinal du + grand ensemble stable de G
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)
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
Clique
(Graphes non orientés) c’est un sous-graphe complet de G
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)
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
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
Nb d’absorption
β(G) = cardinal du + petit ensemble absorbant
Ensemble absorbant minimum
Il n’existe pas d’absorbant plus petit
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
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
Cycle
Chaîne qui ne contient pas 2 fois le même arc et dont le premier sommet est aussi le dernier
Cycle élémentaire
Cycle qui ne passe qu’une seule fois par chaque sommet du cycle
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
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)
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
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
Base de cocycles
Famille de cocycles libre et génératrice
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
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
Face
Région du plan limitée par des aretes dont l’ensemble constitue la frontière + face ∞
Graphe planaire topologique
Représentation planaire d’un graphe planaire (les contours des cycles élémentaires)
TH : graphes planaire topologiques
Les contours des faces finies constituent 1 base de cycles
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
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
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}
Biclique (graphe biparti complet)
Graphe biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble
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)
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
TH de Robertson-Seymour
Un graphe est planaire ssi in ne contient pas comme mineur un K5 ou un K3,3
K5
K3,3
K5 : graphe complet de 5 sommets
K3,3 : graphe à 6 sommets, 3 d’entre eux se connectant aux trois autres.
Coloration
Colorier les sommets sans que deux voisins aient la même couleur
Les sommets de la même couleur forment un stable
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
TH des 4 couleurs
Si G est planaire => γ(G) < ou = 4
tte carte peut être coloriée d’au + 4 couleurs
Ordre
Ord(G) = taille d’une clique maximum de G
TH sur l’ordre de G
G un graphe d’ordre Ord(G) => γ(G) > ou = Ord(G)
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
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
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
Indice chromatique
γ’(G) = nb de couleurs nécessaire pour colorier les arêtes de G
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
Couplage
Sous-ensemble d’arêtes de G tel que 2 arêtes quelconques sont non adjacentes
Couplage maximal
Couplage tel que ajouter n’importe quelle arête du graphe à ce coulage lui fait perdre sa qualité de couplage
Couplage maximum
Couplage ayant un nb max d’arêtes non adjacentes
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
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
Arbre couvrant
Graphe partiel connexe et sans cycle
TH : graphe partiel admet un arbre
1 graphe admet un graphe partiel qui est un arbre ssi il est connexe
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.
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
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
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
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)
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)]
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)]
Tâche critique
Tâche pour laquelle aucun retard ne doit être pris sous peine de modifier la durée optimale du projet
Chemin critique
Chemin allant du début à la fin du projet, constitué intégralement d’une succession de tâches critiques
Circuit absorbant
Circuit dont la valeur totale est négative
