Partitionnement d'un graphe — Les-mathematiques.net The most powerful custom community solution in the world

Partitionnement d'un graphe

Bonjour,
Je m'intéresse au problème de partitionnement de graphe en $k$ parties de "tailles" similaires.
En cherchant sur internet, je trouve deux formulations différents dans la littérature :

1. Première formulation :
Soit $G=(V,E)$ un graphe non orienté pondéré positivement sur ses arêtes. Le problème de partitionnement de graphe consiste à trouve une partition $P$ de cardinal $k$ telle que :
  1. Le poids de chaque partie de la partition soit le même - à un facteur de déséquilibre près. (Le poids d'une partie est définie par la somme des arêtes reliant deux sommets appartenant à cette partie).
  2. La somme des poids -ou encore la coupe- inter-parties soit minimal.

2. Deuxième formulation
Soit $G=(V,E)$ un graphe non orienté pondéré positivement sur ses arêtes.
Le problème de partitionnement de graphe consiste à trouve une partition $P$ de cardinal $k$ telle que :
  1. Le nombre de sommets de chaque partie soit le même - à un facteur de déséquilibre près
  2. La somme des poids -ou encore la coupe- inter-parties soit minimal.


    Question 1 : Est-ce que la première formulation englobe en général la deuxième ? Que dire des deux formulations si tous les poids du graphe sont unitaires ? Dans ce dernier cas est-ce que le fait d'imposer un nombre d'arrête de chaque partie soit à peu près le même pour toutes les parties n’entraîne-t-il pas que le nombre des sommets de chaque partie soit à peu près le même ?
    Question 2 : Dans un problème de partitionnement de charge de calcul entre $k$ processeurs. Si les sommets modélisent des tâches élémentaires de calcul, les arêtes modélisent des dépendances de calcul entre ces tâches et les poids l'importance de cette dépendance. Est-ce que l'utilisation de la première formulation est mauvais ici ? Puisque équilibrer les charges de calcul revient à avoir à former $k$ parties ayant à peu près le même nombre de tâches élémentaires, et donc le même nombre de sommets, d'où il est préférable peut être d'utiliser la deuxième formulation. Mais, dans ce cas est ce que les poids des différentes parties (qui ne sont pas nécessairement similaires) n'ont aucun effet ?

    Merci d'avance

Réponses

  • Tu simplifies le problème en prenant des poids tous unitaires, mais ça ne suffit pas. L'autre critère essentiel, c'est : 'Est-ce que le graphe est complet ?'
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!