Evènement pour le groupe GT Graphes et Applications


Date 2011-10-21  14:00-14:30
TitrePartition arbitraire et préaffectation de sommets 
RésuméSoit G = (V, E) un graphe d'ordre n. Une partition tau = (tau_1, ..., tau_k) de n, avec tau_1 >= ... >= tau_k, est dite réalisable dans G s'il est possible de partitionner V en k parts V_1, ..., V_k de sorte que quelque soit i de [1,k], le sous-graphe G[V_i] soit connexe et d'ordre tau_i. G est dit arbitrairement partitionnable si toute partition de n y est ainsi réalisable. Plusieurs versions de la partition arbitraire, augmentées de contraintes supplémentaires, ont fait l'objet de diverses études, articulées principalement autour de la famille des arbres. Après un bref rappel des résultats principaux la concernant, nous nous concentrerons sur le cas des graphes biconnexes. Pour cela, nous introduirons une version forte de la partition arbitraire, dite "avec une préaffectation", caractérisant le fait qu'il soit toujours possible de trouver, étant donnés un sommet arbitraire v de G et un entier quelconque i appartenant à [1,k], une réalisation V_1, ..., V_k de tau dans G vérifiant v inclus dans V_i. Une fois la biconnexité des graphes arbitrairement partitionnables de cette manière mise en évidence, nous montrerons qu'il en existe une infinité et étudierons plus spécifiquement certaines classes de graphes, notamment celle des ballons. 
LieuSalle 178 
OrateurJulien Bensmail 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index