Aller au contenu
Ashe08

Exercice SPE maths_Graphe

Messages recommandés

Bonsoir,

excusez moi d'encore vous déranger mais je ne comprend pas cet exercice.

Pourriez vous m'aider s'il vous plaît.

Voici ce que j'ai déjà fait :

1A je sais pas comment y répondre

B. je pense que c'est 5

C. Je pense que c'est 10

D. Je ne sais pas comment faire

E. IDem

2. Je pense que oui

3. Je pense que c'est hamiltonien mais j'aimerai que l'on m'explique si c'est ça ou non

Merci d'avance pour votre aide.

t.png.4dd764c9127794344dc99935877dcff6.png

 

Modifié par Ashe08

Partager ce message


Lien à poster
Partager sur d’autres sites

1a)—————————

Graphe connexe non complet. Le graphe comprend 10 sommets d’ordre 3 soit 15 arrêtes de longueurs 1, 2, ou 3 unités de graphe (l’unité de graphe étant la longueur du côté du petit pentagone). Un graphe connexe admet une chaîne eulérienne si et seulement si tous ses sommets, sauf deux d’entre eux, sont de degré pair . En conséquence Enora n’a pas pu réaliser cette maquette sans couper le fil. 

1.jpeg.3780200d04546327a930ca01c7262cdb.jpeg

1b)—————————

Pour qu'un graphe dispose d’une chaine eulérienne il faut qu’il dispose de zéro ou deux sommets d’ordre impair. Pour ramener ce graphe à un sous-graphe ayant deux sommets d'ordre impair  (2 sommets d’ordre 3 et 7 sommets d’ordre 2 ce qui fait (2*3+8*2)/2=11 arrêtes)  il est nécessaire de lui ôter 4 arrêtes  qu'il faudra rajouter à la chaine eulérienne pour terminer le graphe. Le nombre minimum de bouts de fils nécessaire pour constituer ce graphe est donc égal à 5.

1c——————————

Pour obtenir la chaine Eulérienne la plus grande on crée un sous-graphe en ôtant au graphe principal 4 arrêtes  les plus courtes possibles. Ainsi on enlève deux chaine de longueur 1u, une de longueur 2u et 1 de longueur 3u. La chaine eulérienne obtenue est de longueur 30-2-2-3=23u. 

2.jpeg.5b8d6b6e9c18dae965228aa154ed020d.jpeg

1d)——————————

le nombre minimum de bouts de fils étant égal à 5, le graphe étant composé de 5 arrêtes de longueur 1u, 2u ou 3u les bouts de fils peuvent tous avoir la même longueur soit 6u.

3.jpeg.779e31ee8bab6f55973d3a2b45a86c53.jpeg

1e)——————————

si les 5 fils utilisés forment une suite arithmétique de premier terme u0 alors la somme des longues des fils s’exprime selon 

u0+(u0+r)+(u0+2r)+(u0+3r)+(u0+4r)=5*u0+10*r=30u ==> u0+2*r=10*u. Si l’on choisit pour la raison de la suite la plus petite arrête soit 1u alors la longueur des fils utilisés vaut respectivement 4,5,6,7 et 8u.

4.jpeg.465074c0f846f747abee97ab9194b7aa.jpeg

2—————————

Pour déterminer s’il est possible de tracer une ligne continue qui traverse toutes les arrêtes du graphe une seule fois on utilise un graphe dont les sommets se trouvent à l’intérieur des surfaces délimitées par le graphe et dont l’ordre est égal au nombre d’arrêtes à traverser. Le graphe obtenu comportant deux sommets impairs il possède une chaine eulérienne qui relie les deux sommets d’ordre impairs et qui qui traverse toutes les arrêtes du graphe une seule fois. Par exemple :

5.jpeg.5d4b3c7d924530a64a3162d53521c955.jpeg

Partager ce message


Lien à poster
Partager sur d’autres sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Invité
Répondre à ce sujet…

×   Collé en tant que texte enrichi.   Coller en tant que texte brut à la place

  Seulement 75 émoticônes maximum sont autorisées.

×   Votre lien a été automatiquement intégré.   Afficher plutôt comme un lien

×   Votre contenu précédent a été rétabli.   Vider l’éditeur

×   Vous ne pouvez pas directement coller des images. Envoyez-les depuis votre ordinateur ou insérez-les depuis une URL.

Chargement

×
×
  • Créer...
Par Création site web