Metraipolis › archive › dc_a1cf8bfebfe5

Grafo cop-win — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/Grafo_cop-win
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-31T09:32:15.611Z
SHA-256 of the archived text
f6ced78234d8670a5b62eb90acd15c119a98210394f03c60282d31446e16bcf1
Stable URL of this page
https://metraipolis.com/documento/dc_a1cf8bfebfe5

How to cite

Grafo cop-win — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_cop-win (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_a1cf8bfebfe5 (Metraipolis archive dc_a1cf8bfebfe5, sha256 f6ced78234d8670a5b62eb90acd15c119a98210394f03c60282d31446e16bcf1)
BibTeX
@misc{dca1cf8bfebfe5,
  title = {Grafo cop-win — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Grafo_cop-win},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_a1cf8bfebfe5; sha256 f6ced78234d8670a5b62eb90acd15c119a98210394f03c60282d31446e16bcf1},
  year = {2026}
}

Archived text

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

En teoría de grafos, un grafo cop-win o grafo de victoria del policía es un grafo no dirigido en el que el perseguidor (el policía) siempre puede ganar un juego de persecución-evasión contra un ladrón, en el que los jugadores se turnan y en cada turno pueden moverse a lo largo de una arista del grafo o quedarse quietos, hasta que el policía cae en el vértice del ladrón. Los grafos cop-win finitos también se denominan grafos desmantelables o grafos construibles, porque pueden desmantelarse eliminando repetidamente un vértice dominado (uno cuya vecindad cerrada es un subconjunto de la vecindad de otro vértice) o construirse añadiendo repetidamente un vértice de ese tipo. Los grafos cop-win pueden reconocerse en tiempo polinómico mediante un algoritmo voraz que construye un orden de desmantelamiento. Entre ellos se encuentran los grafos cordales y los grafos que contienen un vértice universal.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Grafo cop-win» — https://es.wikipedia.org/wiki/Grafo_cop-win
Wikidata Q28402476: «type of graph related to pursuit-evasion» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q28402476
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Grafo_cop-win?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 176033216, consultata il 2026-10-31T09:21:45.311Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 25b84f20b3104b22aa531b47833b60e4b14d7cd1cb6af8d5489348077dc659df