notion de base Flashcards
comment savoir si 2 graphes sont les mêmes ?
Deux graphes sont isomorphes si chaque point des deux graphes à le même voisinage en les renumérotant
Citer le corrolaire sur le nombre de sommets et le degré
Le nombre de sommets de degrée impair est pair
Citer le théorème de la relation entre la somme des degré d’un graphe et le nombre d’arêtes
Soit G = (V, E) un graphe. Alors,
Somme(v∈V , d(v) = 2|E|).
Quel est le nombre maximum d’arêtes dans un graphe d’ordre n
Nnmax = ( n (n-1) ) / 2
Pour chacune des suites indiquées ci-dessous, décider si elle représente la liste des
degrés des sommets d’un graphe simple.
(a) 7, 6, 5, 4, 3, 2, 1,
(a) Non. En effet, cette suite contient 7 valeurs, un tel graphe aurait donc 7 sommets
et, d’après la Remarque 1, le degré de chaque sommet serait inférieur ou égal à 6, or cette suite
contient 7.
Pour chacune des suites indiquées ci-dessous, décider si elle représente la liste des
degrés des sommets d’un graphe simple.
(b) 6, 6, 5, 4, 3, 3, 1
(b) Non. En effet, cette suite contient 7 valeurs, un tel graphe aurait alors 7 sommets dont
deux de degré 6. Chacun de ces deux sommets serait donc relié à tous les sommets (sauf luimême), ainsi tous les sommets seraient de degré supérieur ou égal à 2; or cette suite contient la
valeur 1, on aboutit à une contradiction.
Pour chacune des suites indiquées ci-dessous, décider si elle représente la liste des degrés des sommets d’un graphe simple.
(c) 3, 3, 2, 1, 1,
oui
Pour chacune des suites indiquées ci-dessous, décider si elle représente la liste des
degrés des sommets d’un graphe simple.
(d) 3, 3, 2, 2
oui
(e) 5, 4, 3, 1, 1, 1, 1,
(e) Non. Supposons par l’absurde que G est un graphe simple tel que les degrés de G soient
5, 4, 3, 1, 1, 1, 1. Par l’Exercice 4, le nombre d’arêtes de G est égal à la somme des degrés des
sommets divisée par 2, donc 8. En supprimant les quatre sommets de degré 1 on supprime au
plus quatre arêtes. Il reste donc trois sommets et au moins quatre arêtes, ce qui est impossible
dans un graphe simple.
(g) 1, 2, 2, 3, 4, 4, 5, 6, 6,
(g) Non, car il y a trois nombres impairs dans cette suite or, par l’Exercice 5, dans un graphe
le nombre de sommets de degré impair est pair.
Montrer qu’un graphe simple ayant au moins deux sommets contient deux sommets
de même degré \ dans un groupe d’au moins deux individus, il y en a toujours deux qui ont le même nombre d’amis (en supposant que l’amitié est une relation symétrique).
Soit G un graphe simple avec n ≥ 2 sommets. Par la Remarque 1, il y a n valeurs
possibles pour le degré d’un sommet de G : 0, 1, . . . , n − 1. Si tous les sommets sont de degrés
différents, alors pour chaque 0 ≤ i ≤ n − 1 on a un sommet vi de degré i. Ceci est impossible.
En effet, considérons les sommets v0 et vn−1. Puisque 0 6= n − 1, ces sommets sont distincts. De
plus : d’une part v0vn−1 ne peut pas être une arête car v0 n’est relié à aucun sommet, et d’autre
part v0vn−1 doit être une arête car vn−1 est relié à tous les sommets.
4 Montrer que la somme des degrés des sommets d’un graphe G = (V, E) est égale à
deux fois le nombre d’arêtes
n Calculer la somme des degrés des sommets d’un graphe G revient à compter les arêtes
incidentes à chaque sommet et puis à ajouter ces nombres. Chaque arête uv est comptée exactement deux fois dans la somme : une fois dans d(u) et une autre fois dans d(v).
Soit G un graphe simple à n sommets tel que chaque sommet est de degré supérieur
ou égal à ⌊n/2⌋. Montrer que G est connexe
n Supposons par l’absurde que G possède plus qu’une composante connexe. Dans ce cas,
puisque G contient n sommets, au moins une composante connexe de G contient un nombre de
sommets inférieur ou égal à ⌊n/2⌋. Soit G′ une telle composante connexe de G et n′ le nombre de sommets de G′
. Par les Remarques 11 et 1, pour chaque sommet v de G′ on a dG(v) = dG′(v) ≤ n′ − 1 ≤ ⌊n/2⌋ − 1,
ce qui contredit l’hypothèse dG(v) ≥ ⌊n/2⌋
