Metraipolis › archive › dc_6cfec4f222d3
Algorithme de Karger — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Algorithme_de_Karger
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-17T11:47:16.851Z
- SHA-256 of the archived text
e31698f3d6485fcfc0bb653712e9657652a304c8e9c8a4deabe39da3def231a7- Stable URL of this page
https://metraipolis.com/documento/dc_6cfec4f222d3
How to cite
Algorithme de Karger — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Karger (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_6cfec4f222d3 (Metraipolis archive dc_6cfec4f222d3, sha256 e31698f3d6485fcfc0bb653712e9657652a304c8e9c8a4deabe39da3def231a7)
BibTeX
@misc{dc6cfec4f222d3,
title = {Algorithme de Karger — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Algorithme_de_Karger},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_6cfec4f222d3; sha256 e31698f3d6485fcfc0bb653712e9657652a304c8e9c8a4deabe39da3def231a7},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Karger. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En algorithmique des graphes, l'algorithme de Karger est un algorithme probabiliste pour le problème de la coupe minimum (MIN-CUT). C'est donc un algorithme d'Atlantic City utilisant une source d'aléas, pour produire une solution correcte avec une bonne probabilité. Le problème en question est le suivant : étant donné un graphe non orienté trouver un ensemble de sommets non trivial minimisant le nombre d'arêtes sortant de cet ensemble. L'outil principal de l'algorithme est la contraction aléatoire d'arêtes, qui fait décroître le nombre de sommets. Il est dû à David Karger et a été publié en 1993. Plusieurs variations ont ensuite été proposées. 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 Karger» — https://fr.wikipedia.org/wiki/Algorithme_de_Karger Wikidata Q4924414: «randomized algorithm for minimum cuts» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4924414 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Karger?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 238781958, consultata il 2026-10-17T11:14:28.959Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 19829df28ef339c81043fa493f53589ac7a1049387b7138e145d1ef80ef21aba