Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Entraide (supérieur)
- » Isetl
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- bridgslam
- 10-11-2021 16:45:16
Bonjour,
Il faut commencer par le début... qu'appelez-vous une structure binaire ? Un type de graphe fini particulier ? Bi-partie?
Alain
- Mia
- 01-11-2021 19:19:34
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
- 01-11-2021 19:17:54
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
- 01-11-2021 19:14:44
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
- 01-11-2021 19:11:54
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”.