Metraipolis › archive › dc_027c142aa720

Algorithme FKT — Wikipedia (fr)

Source: Wikipedia (fr)
Original: https://fr.wikipedia.org/wiki/Algorithme_FKT
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-17T11:27:23.092Z
SHA-256 of the archived text: c7b9a29c39a9a90bf3d22f534d9a17967d277422940cb4c8ed4dd90cd5e7b350
Stable URL of this page: https://metraipolis.com/documento/dc_027c142aa720

How to cite

Algorithme FKT — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_FKT (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_027c142aa720 (Metraipolis archive dc_027c142aa720, sha256 c7b9a29c39a9a90bf3d22f534d9a17967d277422940cb4c8ed4dd90cd5e7b350)

BibTeX

@misc{dc027c142aa720,
  title = {Algorithme FKT — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_FKT},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_027c142aa720; sha256 c7b9a29c39a9a90bf3d22f534d9a17967d277422940cb4c8ed4dd90cd5e7b350},
  year = {2026}
}

Archived text

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

L'algorithme FKT, nommé ainsi d'après Michael Fisher, Pieter Kasteleyn (en) et Harold N. Temperley, compte le nombre de couplages parfaits dans un graphe planaire, et ceci en temps polynomial. Le même dénombrement est #P-complet pour les graphes généraux. Pour les couplages qui ne sont pas nécessairement parfaits, leur dénombrement reste #P-complet même pour les graphes planaires. L'idée clé de l'algorithme FKT est de convertir le problème en le calcul du pfaffien d'une matrice antisymétrique obtenue à partir d'un plongement planaire du graphe. Le pfaffien de cette matrice est ensuite calculé efficacement à l'aide d'algorithmes standards pour les déterminants .

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 FKT» — https://fr.wikipedia.org/wiki/Algorithme_FKT
Wikidata Q5426031 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5426031
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_FKT?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 231777838, consultata il 2026-10-17T11:07:16.602Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e25c5f8b72953151044ee16c936933e06a7bf43c730bba67d0131a461a6a8170