Download pdf - Graphes_Td3

Transcript
  • Universit Paris 13 Sup Galile INFO2Institut Galile Anne 2011-2012

    Algorithmique de GraphesTD3 : Quelques preuves dans les graphes

    Exercice 1Pour un graphe G = (V,E), montrer que :

    1.vV

    dv = 2|E|, o dv est le degr du sommet v.

    2. Le nombre de sommets de degr impair est pair.

    3. Si m = |E| et n = |V | et G est simple, m n(n1)2 .

    Exercice 2Existe-t-il

    1. un graphe dont la suite des degrs esta) 1, 3, 3, 4, 5, 6, 6, 6, 6, 6, 6, 7 ?b) 2, 3, 4, 5 ? Si (di)1in est une suite dentiers non dcroissante, dmontrer que

    lon peut lui associer un graphe si et seulement si la somme des di est paire.

    2. un graphe simple dont la suite des degrs est 1, 1, 3, 3, 3, 3, 5, 6, 8, 9 ?

    Exercice 3Soit G = (V,A) le graphe orient dfini par :V = {a, b, c, d, e}A = {(a, b), (a, c), (b, d), (c, b), (c, d), (d, a), (d, e), (e, c)}

    1. On note d+(x) le degr sortant de x, cest--dire le nombre darcs (x, y), x 6= y.On note de faon analogue d(x) le degr entrant.Calculer d+(x) et d(x) pour chaque sommet x V .

    2. Trouver dans G un cycle de longueur 4, un circuit de longueur 3.

    3. On appelle chemin (resp. circuit) eulrien un chemin (resp. circuit) qui passe une fois etune seule sur chaque arc du graphe.On a les proprits suivantes :Proprit 1 : Un graphe orient connexe admet un chemin eulrien de a b ssid+(a) d(a) = d(b) d+(b) = 1et x, x 6= a, x 6= b, d+(x) = d(x).Proprit 2 : Un graphe orient connexe admet un circuit eulrien ssix, d+(x) = d(x).G admet-il un chemin eulrien ? Un circuit eulrien ? Si oui, en trouver un.

    Exercice 4Peut-il exister un groupe de 15 personnes au sein duquel chacun a exactement 3 amis ?

    Exercice 5Les artes dun graphe complet n 6 sommets ont t colores en rouge et en vert au hasard.Montrer que le graphe contient au moins un triangle unicolore.

    1

  • Exercice 6Le professeur Mongraf et sa femme ont organis une soire avec quatre autres couples. Cer-taines personnes, issues de couples diffrents, se sont serres la main. A la fin de la soire,Mongraf demande chacun combien de mains il a serr. Il reoit neuf rponses diffrentes.Combien sa femme a-t-elle serr de mains ?

    Exercice 7G = (V,E) est un graphe simple non orient. Soit (G) =

    PvV

    d(v)

    2|V | .

    1. Quelle interprtation peut-on donner (G) ?

    2. On suppose quil existe v1 de V tel que d(v1) (G). Posons{V1 = V \{v1}E1 = E\{[v1, v]; v V }

    Considrons le graphe G1 = (V1, E1). Quelle relation a-t-on entre (G) et (G1) ?

    3. En dduire un algorithme qui permet dextraire un sous-graphe H dun graphe nonorient simple G, vrifiant : min{dH(v); v H} > (H) (G).

    Exercice 8Le conseil gnral dun dpartement comprend 7 commissions. On sait que :- tout conseiller gnral fait partie de 2 commissions exactement,- 2 commissions quelconques ont exactement un conseiller gnral en commun.Combien y a-t-il de conseillers gnraux ? (Justifier clairement la rponse en utilisant ungraphe.)

    2

  • Universit Paris 13 Sup Galile INFO2Institut Galile Anne 2011-2012

    Algorithmique de GraphesTD3 : Quelques preuves dans les graphes

  • Universit Paris 13 Sup Galile INFO2Institut Galile Anne 2011-2012

    Algorithmique de GraphesTD3 : Quelques preuves dans les graphes