Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

S1 ENSIIE > Graphe > Flashcards

Graphe Flashcards

1
Q

Graphe non orienté

A

Le sens des aretes n’est pas défini (ie réciporcité de la liaison)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Γ(v)

A

{voisins de v ds G}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Degré

A

d(v) = nb de voisins de v

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Chaîne

A

Suite d’arêtes ininterrompue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Cycle

A

Chaîne qui revient sur le premier sommet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Graphe orienté

A

Sens appliqué aux aretes (ie pas réciprocité de l’arête)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Γ+(v)
Γ-(v)

A

{successeurs de v dans G}
{prédécesseurs de v dans G}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Chemin

A

Chaîne mais pour les graphes orientés

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Circuit

A

Cycle qui respecte l’orientation des aretes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Chemin Hamiltonien

A

Chemin qui ne passe qu’une seule fois par chaque sommet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Graphe hamiltonien

A

Graphe contenant au - un chemin hamiltonien

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Graphe connexe

A

Tte paire de sommet est relié par 1 chaîne

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Sous-graphe

A

1 partie d’1 graphe (ie on a supprimé des sommets avec les aretes qui y sont associées)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Composante connexe

A

Sous-graphe de G connexe maximal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Sous-ensemble maximal

A

L’ajout d’un élément à G lui faire perdre une certaine propriété (ex connexe)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Composante f-connexe

A

Sous-graphe fortement connexe maximal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Graphe réduit

A

Graphe réduit uniquement à ses composantes fortement connexes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Graphe partiel

A

( différent de sous-graphe) graphe dont on a enlevé des arêtes sans toucher aux sommets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

TH : si G est sans circuit ( acyclique )

A

Il existe un unique τ-minimal τ-équivalent à G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Chaîne eulérienne

A

Chaîne qui passe par ttes les arêtes de G 1 seule fois

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

TH d’Euler

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Isthme

A

Arête telle que la retirer déconnecte le graphe

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Ensemble stable

A

Sous-ensemble de G tel que 2 sommets ne sont jamais voisins

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Stabilité maximum

A

L’ensemble des sommets qui ne sont jamais voisins entre eux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Nb de stabilité

A

α(G) = cardinal du + grand ensemble stable de G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

TH : ds un graphe de n sommets et de degré max h

A

La cardinalité de tt ensemble stable maximal est supérieur ou égal à la partie entière supérieure de n/(h+1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Graphe complet

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Clique

A

(Graphes non orientés) c’est un sous-graphe complet de G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Partition des sommets en cliques

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

TH : inégalité entre |S| et |P|

A

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
Q

Ensemble absorbant

A

(Graphes orientés) sous-ensemble A de sommets de G tel que tt sommet n’appartenant pas à A a un successeur dans A

38
Q

Nb d’absorption

A

β(G) = cardinal du + petit ensemble absorbant

39
Q

Ensemble absorbant minimum

A

Il n’existe pas d’absorbant plus petit

40
Q

Noyau

A

(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
Q

Fonction de Grundy

A

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
Q

Cycle

A

Chaîne qui ne contient pas 2 fois le même arc et dont le premier sommet est aussi le dernier

43
Q

Cycle élémentaire

A

Cycle qui ne passe qu’une seule fois par chaque sommet du cycle

44
Q

Notation vectorielle

A

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
Q

Base de cycles (famille de cycles)

A

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
Q

Nb cyclomatique

A

μ(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
Q

Cocycle

A

(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
Q

Base de cocycles

A

Famille de cocycles libre et génératrice

49
Q

Nb de cocyclomatique

A

γ(G) = nb éléments d’une base de cocycles

Si G possède n sommets avec p composantes connexes
γ(G) = n - p

50
Q

Graphe planaire

A

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
Q

Face

A

Région du plan limitée par des aretes dont l’ensemble constitue la frontière + face ∞

52
Q

Graphe planaire topologique

A

Représentation planaire d’un graphe planaire (les contours des cycles élémentaires)

53
Q

TH : graphes planaire topologiques

A

Les contours des faces finies constituent 1 base de cycles

54
Q

TH d’Euler pour les graphes planaires

A

Dans un graphe planaire de n sommets, m arêtes et f faces on a
n - m + f = 2

55
Q

Graphe dual d’un graphe planaire topologique

A

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
Q

Graphe biparti

A

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
Q

Biclique (graphe biparti complet)

A

Graphe biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble

58
Q

Mineur d’un graphe

A

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
Q

TH de Kuratowski

A

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
Q

TH de Robertson-Seymour

A

Un graphe est planaire ssi in ne contient pas comme mineur un K5 ou un K3,3

61
Q

K5
K3,3

A

K5 : graphe complet de 5 sommets
K3,3 : graphe à 6 sommets, 3 d’entre eux se connectant aux trois autres.

62
Q

Coloration

A

Colorier les sommets sans que deux voisins aient la même couleur
Les sommets de la même couleur forment un stable

63
Q

Nb chromatique

A

γ(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
Q

TH des 4 couleurs

A

Si G est planaire => γ(G) < ou = 4
tte carte peut être coloriée d’au + 4 couleurs

65
Q

Ordre

A

Ord(G) = taille d’une clique maximum de G

66
Q

TH sur l’ordre de G

A

G un graphe d’ordre Ord(G) => γ(G) > ou = Ord(G)

67
Q

TH de Brooks

A

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
Q

Reliement contraction

A

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
Q

Coloration des arêtes

A

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
Q

Indice chromatique

A

γ’(G) = nb de couleurs nécessaire pour colorier les arêtes de G

71
Q

Graphe des arêtes (ou Line graph)

A

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
Q

Couplage

A

Sous-ensemble d’arêtes de G tel que 2 arêtes quelconques sont non adjacentes

73
Q

Couplage maximal

A

Couplage tel que ajouter n’importe quelle arête du graphe à ce coulage lui fait perdre sa qualité de couplage

74
Q

Couplage maximum

A

Couplage ayant un nb max d’arêtes non adjacentes

75
Q

Couplage parfait

A

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
Q

Arbre

A

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
Q

Arbre couvrant

A

Graphe partiel connexe et sans cycle

78
Q

TH : graphe partiel admet un arbre

A

1 graphe admet un graphe partiel qui est un arbre ssi il est connexe

79
Q

Arbre couvrant de poids minimum

A

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
Q

Graphe des tâches

A

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
Q

Date de début au plus tôt

A

D’une tâche est la date avant laquelle il est impossible de la commencer à causes des contraintes d’antériorités

82
Q

Date de début au plus tard

A

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
Q

Marge totale

A

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
Q

Marge libre

A

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
Q

Marge certaines

A

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
Q

Tâche critique

A

Tâche pour laquelle aucun retard ne doit être pris sous peine de modifier la durée optimale du projet

87
Q

Chemin critique

A

Chemin allant du début à la fin du projet, constitué intégralement d’une succession de tâches critiques

88
Q

Circuit absorbant

A

Circuit dont la valeur totale est négative

S1 ENSIIE (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions