Coupe minimale

Bonjour à tous,
j'aimerais trouver un algorithme permettant de déterminer la coupe minimale d'un graphe non orienté. J'ai farfouillé un peu partout sur le web et j'ai trouvé plusieurs solutions :
-l'algorithme de Karger, qui est probabiliste.
-une adaptation de Ford-Fulkerson : on oriente le graphe, en choisissant par exemple de sélectionner les arêtes $(i,j)$ avec $i<j$, on choisit deux sommets de façon aléatoire et on trouve la coupe minimale associé à ce couple "source/puit". Ici encore, bien que l'algorithme Ford-Fulkerson soit déterministe, on se retrouve avec un algorithme probabiliste,
-l'algorithme 'naïf", on choisit deux sommets au hasard, on cherche un chemin reliant ces deux sommets. En itérant ce procédé, on regarde les chemins qui apparaissent le plus souvent et on regarde les composantes connexe du graphe privé du chemin modal, des deux chemins modaux....
-l'algorithme "field vector", qui consiste à scinder le graphe en deux partitions déduites des coordonnées d'un vecteur propre de la matrice laplacienne associée au graphe. Cet algorithme, s'il est déterministe, donne une coupe "minimale" en un sens un peu différent du sens naïf et ne fournit donc pas toujours la fameuse coupe minimale.
Bref, tout ce que je n'ai trouvé que des algorithme probabilistes. Ma question est donc existe-t-il un algorithme déterministe, qui fonctionne en un temps raisonnable, permettant de déterminer cette fameuse coupe minimale ?
Bonne soirée
F.
PS. Par coupe minimale, j'entends une partition $S_1,S_2$ des sommets de mon graphe tel que le nombre d'arêtes reliant un sommet de $S_1$ à un sommet de $S_2$ soit minimal.

Réponses

  • @fredaulycee2 Essaies $S_1$ avec un seul sommet!
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
Connectez-vous ou Inscrivez-vous pour répondre.