Metraipolis › archive › dc_f8adcc6384eb

Produit zig-zag de graphes — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Produit_zig-zag_de_graphes
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T16:54:40.223Z
SHA-256 of the archived text
bc518ac63eb99bbf13cd54250c9c6fedd3c0312a2c64a8727f51a38e67e79bd0
Stable URL of this page
https://metraipolis.com/documento/dc_f8adcc6384eb

How to cite

Produit zig-zag de graphes — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Produit_zig-zag_de_graphes (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f8adcc6384eb (Metraipolis archive dc_f8adcc6384eb, sha256 bc518ac63eb99bbf13cd54250c9c6fedd3c0312a2c64a8727f51a38e67e79bd0)
BibTeX
@misc{dcf8adcc6384eb,
  title = {Produit zig-zag de graphes — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Produit_zig-zag_de_graphes},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f8adcc6384eb; sha256 bc518ac63eb99bbf13cd54250c9c6fedd3c0312a2c64a8727f51a38e67e79bd0},
  year = {2026}
}

Archived text

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

En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes G {\displaystyle G} et H {\displaystyle H} , noté G ∘ H {\displaystyle G\circ H} , prend en arguments un grand graphe G {\displaystyle G} et un petit graphe H {\displaystyle H} et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si H {\displaystyle H} est un bon graphe expanseur, alors le taux d'expansion du graphe résultat G ∘ H {\displaystyle G\circ H} est seulement un peu moins bon que le taux d'expansion de G {\displaystyle G} . De manière informelle, le produit zig-zag G ∘ H {\displaystyle G\circ H} remplace chaque sommet de G {\displaystyle G} par une copie de H {\displaystyle H} (un « nuage », cloud en anglais) et relie les sommets en trois étapes : une première (le zig) à l'intérieur du nuage, suivi d'une deuxième entre deux nuages, et enfin une troisième (le zag) à l'intérieur du nuage d'arrivée. Le produit zig-zag a été introduit par Omer Reingold, Salil Vadhan et Avi Wigderson en 2002 et a été utilisé pour la construction explicite d'expanseurs et d'extracteurs de degré constant. Les auteurs ont obtenu le prix Gödel pour ce travail. Ultérieurement le produit zig-zag a été employé en théorie de complexité pour prouver que les classes de complexité SL (espace logarithmique symétrique) et L (espace logarithmique) coïncident.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»).
Fonte: Wikipedia in francese, voce «Produit zig-zag de graphes» — https://fr.wikipedia.org/wiki/Produit_zig-zag_de_graphes
Wikidata Q8071744 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q8071744
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Produit_zig-zag_de_graphes?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 221189799, consultata il 2026-10-07T16:23:38.449Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 78ff2542a51dc62c6438479a30be55f184fefb9502a0d16fbfd28e7ee36609ae