Metraipolis › archive › dc_7183ca251376

Pfaffian orientation — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Pfaffian_orientation
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T11:25:31.023Z
SHA-256 of the archived text
85f53b5b245e78f0b69aca6739e0faf301de5d6f95799ee7f6cd73a153b7d6e8
Stable URL of this page
https://metraipolis.com/documento/dc_7183ca251376

How to cite

Pfaffian orientation — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Pfaffian_orientation (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7183ca251376 (Metraipolis archive dc_7183ca251376, sha256 85f53b5b245e78f0b69aca6739e0faf301de5d6f95799ee7f6cd73a153b7d6e8)
BibTeX
@misc{dc7183ca251376,
  title = {Pfaffian orientation — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Pfaffian_orientation},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7183ca251376; sha256 85f53b5b245e78f0b69aca6739e0faf301de5d6f95799ee7f6cd73a153b7d6e8},
  year = {2026}
}

Archived text

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

In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a Pfaffian orientation, the orientation can be used to count the perfect matchings of the graph. This is the main idea behind the FKT algorithm for counting perfect matchings in planar graphs, which always have Pfaffian orientations. More generally, every graph that does not have the utility graph K 3 , 3 {\displaystyle K_{3,3}} as a graph minor has a Pfaffian orientation, but K 3 , 3 {\displaystyle K_{3,3}} does not, nor do infinitely many other minimal non-Pfaffian graphs.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»).
Fonte: Wikipedia in inglese, voce «Pfaffian orientation» — https://en.wikipedia.org/wiki/Pfaffian_orientation
Wikidata Q49000601 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q49000601
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Pfaffian_orientation?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 1364456348, consultata il 2026-10-07T11:16:08.679Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 94cff55e409b7eab6e1dbbf8bff5ee4f02455979263bcdf72849626e729fac25