Forum de mathématiques - Bibm@th.net

Mia

Invité

Isetl

Bonsoir,

On a un travail de groupe sur isetl et franchement on galère sur cette question...
Est ce que quelqu'un pourrait nous aider à y voir clair ?

Merci à vous d'avance ...

On appelle pseudo-chemin, dans une structure binaire non vide B, toute suite finie non vide d'éléments de B(1) telle que deux éléments consécutifs de cette suite induisent un élément de B(2). C’est-à-dire que Ch est un pseudo-chemin de B si les deux conditions suivantes sont vérifiées :
1. ∃k ∈ N∗,tel que Ch=(xi) i  ∈ [k] et{xi : i∈[k]}⊆ B(1), et
2. soit k=1, soit k=1 et alors ∀i ∈ [k−1], on a (xi,xi+1) ∈ B(2).
On appelle chemin élémentaire dans une structure binaire non vide B tout pseudo-chemin uniquement constitué d’éléments distincts.
Une structure binaire non vide B est sans circuit si tous ses pseudo-chemins sont des chemins élémentaires. On peut montrer qu’une structure binaire non vide est sans circuit si et seulement s’il existe k ∈ N∗ et une suite (Xi)i∈[k], dite suite “linéarisante”, telle que :
1. {Xi : i ∈ [k]} soit une partition de B(1),
2. ∀e ∈ B(2), ∃i,j∈[k] tels que i<N j, e(1)∈Xi et e(2)∈Xj.
On rappelle que la longueur d’une suite correspond au nombre d’ ́el ́ements la composant. Ainsi la suite (αi)i∈[k] est de longueur k. Ecrire les fonctions Isetl suivantes :

1. Linearisantemax(B) : fonction qui prend en entrée une structure binaire non vide et qui retourne une suite. Cette fonction retourne une suite “linéarisante” de longueur maximale si la structure binaire est sans circuit et elle retourne la suite vide sinon.
2. Linearisantemin(B) : fonction qui prend en entrée une structure binaire non vide et qui retourne une suite. Cette fonction retourne une suite “linéarisante” de longueur minimale si la structure binaire est sans circuit et elle retourne la suite vide sinon.
3. Un peu de réflexion :
(a) Montrez qu’une structure binaire non vide B est sans circuit si et seulement si elle possède une suite “linéarisante”.

Mia

Invité

Re : Isetl

On appelle pseudo-chemin, dans une structure binaire non vide B, toute suite finie non vide d’ ́el ́ements de B(1) telle que deux  ́el ́ements cons ́ecutifs de cette suite induisent un  ́el ́ement de B(2). C’est-`a-dire que Ch est un pseudo-chemin de B si les deux conditions suivantes sont v ́erifi ́ees :
1. ∃k∈N∗,telqueCh=(xi)i∈[k] et{xi : i∈[k]}⊆B(1),et
2. soitk=1,soitk=1etalors∀i∈[k−1],ona(xi,xi+1)∈B(2).
On appelle chemin  ́el ́ementaire dans une structure binaire non vide B tout pseudo-chemin uniquement constitu ́e d’ ́el ́ements distincts.
Une structure binaire non vide B est sans circuit si tous ses pseudo-chemins sont des chemins  ́el ́ementaires. On peut montrer qu’une structure binaire non vide est sans circuit si et seulement s’il existe k ∈ N∗ et une suite (Xi)i∈[k], dite suite “lin ́earisante”, telle que :
1. {Xi : i ∈ [k]} soit une partition de B(1),
2. ∀e∈B(2),∃i,j∈[k]telsquei<N j,e(1)∈Xi ete(2)∈Xj.
On rappelle que la longueur d’une suite correspond au nombre d’ ́el ́ements la composant. Ainsi la suite (αi)i∈[k] est de longueur k. E ́crire les fonctions Isetl suivantes :
1
1. Linearisantemax(B) : fonction qui prend en entr ́ee une structure binaire non vide et qui retourne une suite. Cette fonction retourne une suite “lin ́earisante” de longueur maximale si la structure binaire est sans circuit et elle retourne la suite vide sinon.
2. Linearisantemin(B) : fonction qui prend en entr ́ee une structure binaire non vide et qui retourne une suite. Cette fonction retourne une suite “lin ́earisante” de longueur minimale si la structure binaire est sans circuit et elle retourne la suite vide sinon.
3. Un peu de r ́eflexion :
(a) Montrez qu’une structure binaire non vide B est sans circuit si et seulement si elle poss`ede une suite
“lin ́earisante”.

Mia

Invité

Re : Isetl

On rappelle que la longueur d’une suite correspond au nombre d’ ́el ́ements la composant. Ainsi la suite (αi)i∈[k] est de longueur k. E ́crire les fonctions Isetl suivantes :
1
1. Linearisantemax(B) : fonction qui prend en entr ́ee une structure binaire non vide et qui retourne une suite. Cette fonction retourne une suite “lin ́earisante” de longueur maximale si la structure binaire est sans circuit et elle retourne la suite vide sinon.

Mia

Invité

Re : Isetl

Linearisantemin(B) : fonction qui prend en entr ́ee une structure binaire non vide et qui retourne une suite. Cette fonction retourne une suite “lin ́earisante” de longueur minimale si la structure binaire est sans circuit et elle retourne la suite vide sinon.
3. Un peu de r ́eflexion :
(a) Montrez qu’une structure binaire non vide B est sans circuit si et seulement si elle poss`ede une suite
“lin ́earisante”

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Isetl

Bonjour,

Il faut commencer par le début... qu'appelez-vous une structure binaire ? Un type de graphe fini particulier ? Bi-partie?

Alain