Metraipolis › archive › dc_dbbf07a0e720

Algorithme de Stoer-Wagner — Wikipedia (fr)

Source: Wikipedia (fr)
Original: https://fr.wikipedia.org/wiki/Algorithme_de_Stoer-Wagner
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-17T11:48:05.144Z
SHA-256 of the archived text: de76db81eb1bc0e4a57dc17b209321305a715419a175295361426da753fd3616
Stable URL of this page: https://metraipolis.com/documento/dc_dbbf07a0e720

How to cite

Algorithme de Stoer-Wagner — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Stoer-Wagner (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_dbbf07a0e720 (Metraipolis archive dc_dbbf07a0e720, sha256 de76db81eb1bc0e4a57dc17b209321305a715419a175295361426da753fd3616)

BibTeX

@misc{dcdbbf07a0e720,
  title = {Algorithme de Stoer-Wagner — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_de_Stoer-Wagner},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_dbbf07a0e720; sha256 de76db81eb1bc0e4a57dc17b209321305a715419a175295361426da753fd3616},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Stoer-Wagner. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En théorie des graphes, l'algorithme de Stoer-Wagner est un algorithme récursif déterministe pour trouver la coupe minimale dans des graphes non orientés pondérés, avec des poids positifs. Autrement dit, il s'agit de séparer le graphe en deux morceaux non vides, de telle sorte que la somme des poids attribués aux arêtes reliant un sommet d'un des morceaux à un sommet de l'autre soit la plus petite possible. L'algorithme a été proposé en 1994 par Mechthild Stoer et Frank Wagner lors d'un symposium européen à Utrecht. L'idée essentielle est de réduire progressivement la taille du graphe à considérer, en fusionnant des sommets par paire, jusqu'à ce que le graphe ne contienne que deux ensembles de sommets combinés. À chaque étape, l'algorithme choisit deux sommets s {\displaystyle s} et t {\displaystyle t} , calcule la coupe minimale qui les sépare, puis (récursivement) la coupe minimale du graphe obtenu en les fusionnant, et renvoie le minimum des deux.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Algorithme de Stoer-Wagner» — https://fr.wikipedia.org/wiki/Algorithme_de_Stoer-Wagner
Wikidata Q23808439: «Recursive algorithm in graph theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q23808439
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Stoer-Wagner?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 216594659, consultata il 2026-10-17T11:17:54.891Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e1da0526052f2b8f29a2f7658ee8544793163fb92cae2dff5deab9cce0087ccf