Solutions 1
Transféré par
ScribdTranslationsSolutions 1
Transféré par
ScribdTranslationsThéorie des graphes - solutions à l'ensemble de problèmes 1
1. Étant donné un graphe G avec un ensemble de sommets V = {v1 , . . . , v n }nous définissons la séquence de degré de G comme étant la liste
d(v1 ), . . . , d(vn ) de degrés dans un ordre décroissant. Pour chacune des listes suivantes, donnez un exemple d'un
graphe avec une telle suite de degrés ou prouver qu'aucun graphe de ce type n'existe :
(a) 3,3,2,2,2,1
(b) 6,6,6,4,4,3,3
(c) 6,6,6,4,4,2,2
Solution :
(a) Il n'existe pas de tel graphe ; car selon le problème 5, le nombre de sommets de degré impair dans un graphe est toujours
même.
(b) Considérez le graphique suivant :
(c) Non, sinon nous avons 3 sommets de degré 6 qui sont adjacents à tous les autres sommets de la
graphe; donc chaque sommet du graphe doit avoir un degré d'au moins 3.
2. Construisez deux graphes ayant la même séquence de degrés mais qui ne sont pas isomorphes.
Solution : Soit G1soit un cycle de 6 sommets, et soit G2soit l'union de deux cycles disjoints sur 3
des sommets chacun. Dans les deux graphes, chaque sommet a un degré de 2, mais les graphes ne sont pas isomorphes, puisque l'un est
connecté et l'autre ne l'est pas.
3. Un graphe est k-régulier si chaque sommet a un degré k. À quoi ressemblent les graphes 1-réguliers ? Et 2-réguliers ?
graphes?
Solution : Un graphe 1-régulier est simplement une union disjointe d'arêtes (qui sera bientôt appelée un appariement).
Un graphe 2-régulier est une union disjointe de cycles.
4. Combien de graphes (étiquetés) existent sur un ensemble donné de n sommets ? Combien d'entre eux contiennent exactement m?
bords?
n
Solution : Comme il y a 2
bords possibles sur les sommets, et un graphe peut ou non avoir chacun d'eux
ces bords, nous obtenons qu'il y en a 2(2 ) graphes possibles sur n sommets. Pour le deuxième problème, parmi
n
le n2 bords possibles, nous voulons choisir des moines. Donc il y a (2n) graphiques possibles sur n sommets et
m
avec des bords.
5. Prouvez que le nombre de sommets de degrés impairs dans un graphe est toujours pair.
Solution : Soit G = (V, E) un graphe arbitraire. Dans le cours, nous avons prouvé que v∈V d(v) = 2|E|.
P
LaissezV1⊆V est l'ensemble des sommets de G qui ont un degré impair et V2=V\V 1soit l'ensemble des sommets de
Gqui ont un degré pair. Nous avons que
X d(v) = X d(v) + X d(v) = 2|E|.
v∈V v∈V 1 v∈V 2
Puisque tous les sommets dans V2ont un degré pair, et 2|E| est pair, nous obtenons que d(v) est pair. Mais
P v∈V1
depuisV1est l'ensemble des sommets de degré impair, nous obtenons que la cardinalité de V1est pair (c'est-à-dire qu'il
sont un nombre pair de sommets de degré impair), ce qui complète la preuve.
6. Soit G un graphe dont le degré minimum δ > 1. Prouvez que G contient un cycle d'une longueur d'au moins δ + 1.
Solution : Tout d'abord, rappelons comment nous avons procédé lors du cours pour trouver un chemin d'une longueur d'au moins δ :
Letv1· · ·vksoit un chemin maximal dans G, c'est-à-dire un chemin qui ne peut pas être étendu. Alors tout voisin de v 1
doit être sur le chemin, sinon nous pourrions l'étendre. Depuis1a au moins δ(G) voisins, l'ensemble
Invalid input2 , . . . , v k }doit contenir au moins δ(G) éléments. Par conséquent, k ≥ δ(G) + 1, donc le chemin a une longueur d'au moins
δ(G).
Maintenant, afin de trouver un cycle de longueur d'au moins δ + 1, nous continuons la preuve ci-dessus. Le voisin de v 1
celui qui est le plus avancé sur le chemin doit êtrejeavec δ(G) + 1. Alors v1· · ·vje v1est un cycle de longueur à
le plus petit δ(G) + 1.
7. Montrez que tout graphe comportant au moins deux sommets contient deux sommets de même degré.
Solution : Supposons que les sommets aient tous des degrés différents et regardons l'ensemble des degrés. Puisque
le degré d'un sommet est au plus n−1, l'ensemble des degrés doit être
{0,1,2, . . . , n−2, n−1}.
Mais ce n'est pas possible, car le sommet avec un degré de n−1 devrait être adjacent à tous les autres.
les sommets, tandis que celui avec un degré 0 n'est adjacent à aucun sommet.
8. Prouvez qu'à une réunion d'au moins 6 personnes, il y a toujours 3 personnes qui se connaissent mutuellement, ou 3
qui ne se connaissent pas mutuellement.
Indice : commencez par prouver l'énoncé suivant. Si G est un graphe avec au moins 6 sommets, alors soit G ou
son complément a un sommet de degré au moins 3.
Le complément d'un graphe G = (V, E), noté GC , est le graphe avec l'ensemble des sommets V et l'ensemble de
bordsEC={uv|uv∈E}.
Solution : Soit G = (V, E) un graphe ayant au moins 6 sommets et v un sommet de G de degré maximal.
∆. Si ∆≥3, alors v est le sommet que nous recherchons. D'autre part, si ∆<3 alors v a un degré
au moins 3 enGC .
Considérons maintenant un bord de G représentant que la personne u connaît la personne v. Sans perte de généralité,
considérez le cas où G a un sommet v de degré 3. Regardez les voisins de v1 , v2 , v3si deux quelconques
sont connectés, nous obtenons un triangle1 v2et ainsi 3 personnes se connaissent. Sinon, nous obtenons le
trianglev1 v2 v3dansGCet donc 3 personnes ne se connaissent pas.
9. Quel est le nombre maximum d'arêtes dans un graphe biparti de n sommets ? (Prouvez votre réponse.)
Solution : Soit G = (A ∪B, E) un graphe bipartite, avec A et B disjoints et |A| + |B| = n. Puisque
toutes les arêtes de G ont un extrémité dans A et l'autre dans B, le nombre d'arêtes |E| de G ne peut pas
dépasser le nombre de paires (a, b)∈A×B, donc |E| ≤ |A| · |B|=|A|(n− |A|). Intuitivement, un tel produit
est maximisé lorsque les deux facteurs sont égaux, donc lorsque |A|=bn/2c. Plus formellement, nous pouvons utiliser le
inégalité 4xy ≤ (x+y) 2obtenir
(|A|+n− |A|)2 n2
|E| ≤ |A|(n− |A|)≤ = .
4 4
Par conséquent, le nombre d'arêtes d'un graphe bipartite avec n arêtes est au maximum n.2 /4.
Notez que2 /4 est exactement le maximum lorsque n est pair, car il est alors atteint par le complet
2
n n
graphe biparti Kn/2,n/2 . Whennis étrange, le maximum est en fait2c · d 2e=n−1, qui est atteint4
parK bn/2c,dn/2e .
