| dbo:abstract
|
- In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can chose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex (one whose closed neighborhood is a subset of another vertex's neighborhood) or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex. (en)
- En théorie des graphes, un graphe cop-win est un graphe non orienté sur lequel le gendarme (cop) peut toujours gagner (win) une partie de contre le voleur, les joueurs jouant à tour de rôle, et pouvant choisir de se déplacer le long d'une arête du graphe ou de rester sur place, jusqu'à ce que le gendarme arrive sur le sommet du voleur. Les graphes cop-win finis sont également appelés graphes démontables ou graphes constructibles, car ils peuvent être démantelés en supprimant à plusieurs reprises un sommet dominé (dont le voisinage fermé est un sous-ensemble du voisinage d'un autre sommet) ou construits en ajoutant à plusieurs reprises un tel sommet. Les graphes cop-win peuvent être reconnus en temps polynomial par un algorithme glouton qui construit un ordre de démantèlement. Ils incluent les graphes cordaux et les graphes qui contiennent un (en). (fr)
- Выигрышный граф полицейского — это неориентированный граф, на котором преследователь (полицейский) может выиграть игру преследования-уклонения, в которой он преследует грабителя и игроки поочерёдно делают передвижения вдоль рёбер графа или стоят на месте пока, полицейский не займёт вершину, на которой находится грабитель. Конечные выигрышные графы полицейского называются также разбираемыми графами или конструируемыми графами, поскольку они могут быть разобраны путём удаления раз за разом доминируемой вершины (вершины, замкнутая окрестность которой является подмножеством окрестности другой вершины) или построены путём повторяющегося добавления такой вершины. Выигрышные графы полицейского могут быть распознаны за полиномиальное время жадным алгоритмом, который создаёт порядок разборки. В этот класс входят хордальные графы и графы, содержащие универсальную вершину. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 22334 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can chose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex (one whose closed neighborhood is a subset of another vertex's neighborhood) or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex. (en)
- En théorie des graphes, un graphe cop-win est un graphe non orienté sur lequel le gendarme (cop) peut toujours gagner (win) une partie de contre le voleur, les joueurs jouant à tour de rôle, et pouvant choisir de se déplacer le long d'une arête du graphe ou de rester sur place, jusqu'à ce que le gendarme arrive sur le sommet du voleur. Les graphes cop-win finis sont également appelés graphes démontables ou graphes constructibles, car ils peuvent être démantelés en supprimant à plusieurs reprises un sommet dominé (dont le voisinage fermé est un sous-ensemble du voisinage d'un autre sommet) ou construits en ajoutant à plusieurs reprises un tel sommet. Les graphes cop-win peuvent être reconnus en temps polynomial par un algorithme glouton qui construit un ordre de démantèlement. Ils incluent (fr)
- Выигрышный граф полицейского — это неориентированный граф, на котором преследователь (полицейский) может выиграть игру преследования-уклонения, в которой он преследует грабителя и игроки поочерёдно делают передвижения вдоль рёбер графа или стоят на месте пока, полицейский не займёт вершину, на которой находится грабитель. Конечные выигрышные графы полицейского называются также разбираемыми графами или конструируемыми графами, поскольку они могут быть разобраны путём удаления раз за разом доминируемой вершины (вершины, замкнутая окрестность которой является подмножеством окрестности другой вершины) или построены путём повторяющегося добавления такой вершины. Выигрышные графы полицейского могут быть распознаны за полиномиальное время жадным алгоритмом, который создаёт порядок разборки. В это (ru)
|
| rdfs:label
|
- Cop-win graph (en)
- Graphe cop-win (fr)
- Выигрышный граф полицейского (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
