Graphe complet, chaînes, longueur d'une chaîne et distance - Exercice 1

20 min
35
Un graphe est complet lorsque tous ses sommets sont adjacents deux à deux. On note KnK_{n} le graphe complet d'ordre nn .
Question 1

Représenter K4K_{4} et K5K_{5} , puis donner le degré de chaque sommet et le nombre d'arêtes de chacun de ces deux graphes.

Correction
  • Dans un graphe, nous avons la relation suivante : nombre d’areˆtes=la somme des degreˊs des sommets2\text{nombre d'arêtes}=\dfrac{\text{la somme des degrés des sommets}}{2} .
    • Le graphe K4\red{\text{Le graphe }K_{4}} :

    Chaque sommet est relié aux 33 autres : tous les sommets sont de degré 33 .
    nombre d’areˆtes=4×32\text{nombre d'arêtes}=\dfrac{4\times 3}{2}
    Ainsi :
    nombre d’areˆtes de K4=6\text{nombre d'arêtes de }K_{4}=6

    Le graphe K5\red{\text{Le graphe }K_{5}} :

    Chaque sommet est relié aux 44 autres : tous les sommets sont de degré 44 .
    nombre d’areˆtes=5×42\text{nombre d'arêtes}=\dfrac{5\times 4}{2}
    Ainsi :
    nombre d’areˆtes de K5=10\text{nombre d'arêtes de }K_{5}=10

    Question 2

    Démontrer que, pour tout entier n≥2n\ge 2 , le graphe complet KnK_{n} possède n(n−1)2\dfrac{n\left(n-1\right)}{2} arêtes.

    Correction
  • Dans un graphe, nous avons la relation suivante : nombre d’areˆtes=la somme des degreˊs des sommets2\text{nombre d'arêtes}=\dfrac{\text{la somme des degrés des sommets}}{2} .
    • Dans KnK_{n} , chaque sommet est relié aux n−1n-1 autres sommets : il est de degré n−1n-1 .
    Les nn sommets ont donc pour somme des degrés n(n−1)n\left(n-1\right) .
    Finalement :
    nombre d’areˆtes de Kn=n(n−1)2\text{nombre d'arêtes de }K_{n}=\dfrac{n\left(n-1\right)}{2}

    Question 3

    Lors d'un tournoi de handball, 88 équipes se rencontrent chacune une et une seule fois. Combien de matchs sont joués ?

    Correction
    On modélise le tournoi par un graphe : les sommets sont les équipes et chaque match est une arête. Comme deux équipes quelconques se rencontrent, c'est le graphe complet K8K_{8} .
    D'après la question 22 : 8×72=28\dfrac{8\times 7}{2}=28
    Ainsi :
    2828 matchs sont joués

    Question 4

    Un autre tournoi du même type comporte 4545 matchs. Combien d'équipes y participent ?

    Correction
    Notons nn le nombre d'équipes. D'après la question 22 , n(n−1)2=45\dfrac{n\left(n-1\right)}{2}=45 équivaut successivement à :
    n(n−1)=90n\left(n-1\right)=90
    n2−n−90=0n^{2}-n-90=0
    Δ=(−1)2−4×1×(−90)=361\Delta =\left(-1\right)^{2}-4\times 1\times \left(-90\right)=361 d'où Δ>0\Delta >0
    n1=−b−Δ2an_{1}=\dfrac{-b-\sqrt{\Delta } }{2a} ainsi n1=1−192×1n_{1}=\dfrac{1-19}{2\times 1} d'où n1=−9n_{1}=-9
    n2=−b+Δ2an_{2}=\dfrac{-b+\sqrt{\Delta } }{2a} ainsi n2=1+192×1n_{2}=\dfrac{1+19}{2\times 1} d'où n2=10n_{2}=10
    Comme nn est un entier naturel, n=10n=10 . Vérification : 10×92=45\dfrac{10\times 9}{2}=45 .
    Finalement :
    1010 équipes participent au tournoi

    Signaler une erreur

    Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

    Connecte-toi ou crée un compte pour signaler une erreur.