Exercice SPE maths_Graphe

[Ashe08]

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.

 

[Barbidoux]

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. 

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. 

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.

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.

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 :

[Barbidoux]

petit oubli...

Le graphe est hamiltonien car il possède un cycle hamiltonien

[Ashe08]

Merci beaucoup !!

Désolé de répondre tardivement