Annuler
connectez vous
probabilités en post-bac
- Un best-of d'exos de probabilités (après le bac)
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Décomposition des matrices en blocs, exponentielle de matrices - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau autre
Algorithme Décomposition d'arbre
Posté par suistrop
Bonjour a vous tous,
Je butte sur une question si quelqu un pouvais m aider:
je dois trouver 1 algorithme qui avec un arbre donné et une partition donné me dise si cette partition décompose l arbre.
Une partition est un ensemble de valeur dont la somme est égal au nombre de sommet de l arbre ex {1,5,7,2,4}
Une partition décompose un arbre si il existe "un moyen de découper l arbre en ici 1,5,7,2,4 sommet" tel que dans chaque ensemble de sommet reunie on puisse aller vers tous les sommets.
Merci de vos réponse si vous avez une idée ou juste une facon de faire qui semble fonctionner hésitez pas.
Posté par MissThé (invité)re : Algorithme Décomposition d'arbre
Bonjour suistrop,
Je ne suis pas sûre de bien comprendre ton problème.
Si j'ai bien suivi: un arbre est un ensemble de sommets (points?) (dans ton exemple, 19 sommets) entre lesquels il existe, ou pas, un chemin (segment ou ligne courbe?). Et la partition {1,5,7,2,4} décompose l'arbre si tu peux répartir tes 19 sommets en 5 paquets de respectivement 1, 5, 7, 2 et 4 sommets tels que si on choisi deux sommets dans un même paquet, il existe toujours un chemin entre ces deux sommets. C'est ça?
Si oui, peut-il aussi exister des chemins entre deux sommets de deux paquets différents? Et sous quelle forme rentres -tu l'arbre au début de l'algorithme? (Pour la partition, ça va, je vois)
J'espère que je vais pouvoir t'aider.
MissThé.
Merci Miss Thé de la reponse
donc les relation entre paquets de sommets on s en moque l arbre il est donné quelconque mon pbl c est que je ne trouve pas l idée pour faire l algo
oui il peux exister une arette entre 2 sommet de paquet différent
J essais de voir comment moi je resoud ce probleme a la main mais je n arrive sur aucune chose reccurente c est au pti bonheur la chance en fct de l arbre de la chaine si je retire une arrette ca change tout je suis un peu perdu.
aidez moi ^^
Posté par MissThé (invité)re : Algorithme Décomposition d'arbre
Bonsoir suistrop,
J'ai essayé de réfléchir à ton problème, mais il s'avère que je ne domine pas suffisament le sujet.
Désolée de ne pas pouvoir t'aider.
MissThé.