Déterminer l'ordre d'un graphe orienté.
Répondre à la discussion
Affichage des résultats 1 à 13 sur 13

Déterminer l'ordre d'un graphe orienté.



  1. #1
    invitedb6c0e9c

    Déterminer l'ordre d'un graphe orienté.


    ------

    Tout d'abord, bonjour à tous.

    Je me trouve confronté à un problème que moi et mon binome n'arrivont pas à résoudre.
    Nous y avons quand même passé quelques heures ...

    Si quelqu'un a une piste de réflexion, je suis fortement preneur.
    Même un petit indice est le bienvenue.

    le problème est le suivent :
    Nom : Capture.PNG
Affichages : 91
Taille : 20,4 Ko

    Merci d'avance à vous !
    Bonne soirée.

    -----

  2. #2
    Médiat

    Re : Déterminer l'ordre d'un graphe orienté.

    Bonsoir,

    Qu'est-ce que vous ne comprenez pas ? C'est de l'arithmétique de base
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    invitedb6c0e9c

    Re : Déterminer l'ordre d'un graphe orienté.

    Je ne comprends pas qu'elle méthode ou quel calcul faire.
    Le problème n'est pas tant de trouver le nombre l'ordre mais de le justifier.

    L'ordre est évidemment de 5 (3 sommets de degré 3 et 2 de degré 5).
    Mais il nous est demandé de le justifier en montrant le raisonnement qui nous a mené à ce résultat.

    Et je ne vois pas quel raisonnement adopter..

  4. #4
    Médiat

    Re : Déterminer l'ordre d'un graphe orienté.

    Qu'est-ce qui vous y a mené?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  5. A voir en vidéo sur Futura
  6. #5
    invitedb6c0e9c

    Re : Déterminer l'ordre d'un graphe orienté.

    Déduction / tâtonnement mais ce n'est pas ce qui est attendu.

  7. #6
    invite9dc7b526

    Re : Déterminer l'ordre d'un graphe orienté.

    Tu peux partir du fait que chaque arête sort d'un sommet ou d'un autre, donc la somme des degrés sortants est égale au nombre d'arêtes, soit 19.

  8. #7
    Médiat

    Re : Déterminer l'ordre d'un graphe orienté.

    Citation Envoyé par FocSon Voir le message
    Déduction / tâtonnement mais ce n'est pas ce qui est attendu.
    Déduction est exactement ce qui est attendu, mais minushabens a vendu la mèche (la moitié)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  9. #8
    invitedb6c0e9c

    Re : Déterminer l'ordre d'un graphe orienté.

    D'accord merci de confirmer une partie de ma démarche !

    J'avais fais des recherches en partant d'une double équation dans le style:
    5x + 3y = 19

    Je vais chercher où continuer !

  10. #9
    Médiat

    Re : Déterminer l'ordre d'un graphe orienté.

    A partir d'ici c'est facile, quelles sont les valeurs de x possibles ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #10
    invitedb6c0e9c

    Re : Déterminer l'ordre d'un graphe orienté.

    x peut prendre
    1 avec un reste de 16 (non divisible par 5)
    2 avec un reste de 13 (non divisible par 5)
    3 avec un reste de 10 (divisible par 5)
    4 avec un reste de 7 (non divisible par 5)
    5 avec un reste de 4 (non divisible par 5)
    6 avec un reste de 1 (non divisible par 5)

    La seule reponse possible est donc x=3 et y=2 pour x représentant les sommets de degré sortant 3 et y représentant les sommets de degré sortants 5 ...

    C'étais donc si simple ...

  12. #11
    invitedb6c0e9c

    Re : Déterminer l'ordre d'un graphe orienté.

    merci beaucoup !

  13. #12
    Médiat

    Re : Déterminer l'ordre d'un graphe orienté.

    Vous avez fait y et non x (moins de valeurs), et iln'y a aucune raison de ne pas étudier x = 0
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #13
    invitedb6c0e9c

    Re : Déterminer l'ordre d'un graphe orienté.

    Sur le compte-rendu j'ai pensé à préciser le cas où y prends la valeur 0.
    J'ai justifié le choix de l'autre valeur de cette facon :

    Le nombre de sommets de degré sortant 5 peut être soit :
    - 0 il reste 19 sommets (non divisible par 3)
    - 1 il reste 14 sommets (non divisible par 3)
    - 2 il reste 9 sommets (divisible par 3)
    - 3 il reste 4 sommets (non divisible par 3)

    Or, on nous dit que tout les sommets sont de degrés sortant 5 ou 3.

    Pour respecter ces données, il faut qu'une fois les arrètes concernant les sommets de degrés sortant 5 enlevés,
    il nous reste un nombre d'arrêtes divisible par 3.

    La seule solution possible est donc : 2 sommets de degrés sortants 5 et 3 sommets de degrés sortant 3.

    Un tel graphe est donc d'ordre 5.

Discussions similaires

  1. Trouver tous les chemins possibles entre deux sommets dans un graphe orienté
    Par invitef94e1e60 dans le forum Programmation et langages, Algorithmique
    Réponses: 4
    Dernier message: 21/02/2017, 09h48
  2. Existe-t-il une méthode suffisante pour determiner si un graphe est Hamiltonien?
    Par invite188b808b dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 22/06/2016, 13h23
  3. comment determiner l'equation d'une courbe d'après son graphe
    Par invite859f478b dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 17/10/2015, 20h42
  4. pourquoi un appartement orienté au nord est plus sombre qu'un autre orienté au sud?
    Par invite865c3b9b dans le forum Habitat bioclimatique, isolation et chauffage
    Réponses: 3
    Dernier message: 06/05/2011, 12h49
  5. recherche tous les chemins dans un graphe orienté
    Par invitea5e67aa9 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 11/02/2011, 13h05