Juego de policías y ladrones en grafos

Pozuelo Rollón, Blanca María (2018). Juego de policías y ladrones en grafos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Juego de policías y ladrones en grafos
Author/s:
  • Pozuelo Rollón, Blanca María
Contributor/s:
  • Hernández Peñalver, Gregorio
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2018
Subjects:
Freetext Keywords: Grafo; Policías y ladrones; "cop number"; Graph; Cops and robber
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

Policías y ladrones es un juego que se juega sobre un grafo. En este juego los jugadores se desplazan de vértice en vértice a través de la aristas del grafo. El objetivo de los policías es capturar al ladrón, mientras que el ladrón tiene que huir de los policías. Este juego se introdujo durante los años 80 y ha sido ampliamente estudiado desde entonces. Una de las características más estudiadas de este juego es el "cop number", es decir, el número mínimo de policías necesarios para capturar al ladrón, ya que uno sólo no siempre puede capturar al ladrón, y colocando uno en cada vértice sería muy sencillo. En los primeros capítulos de este documento se presenta un estudio de este juego, en el que se mostrarán tanto algunas cotas del "cop number" como algunas estrategias que deben seguir los jugadores para ganar.---ABSTRACT---Cops and robbers is a game played on a graph. In this game players move from vertex to vertex across the edges of the graph. The objective of the cops is to capture the robber, while the robber try to avoid the cops. This game was introduced during the 80s and has been widely studied since then. One of the most studied features of this game is the "cop number", which is the minimum number of cops needed to capture the robber, since only one cop can not capture the robber, and placing one in each vertex would be very simple. In the first chapters of this document, a study of this game is presented, in which some bounds of the "cop number" are shown, as well as some strategies that the players must follow to win.

More information

Item ID: 52279
DC Identifier: http://oa.upm.es/52279/
OAI Identifier: oai:oa.upm.es:52279
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 17 Sep 2018 08:55
Last Modified: 17 Sep 2018 08:55
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM