Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

a
p
Visibility Graphs J
Cop-Win Graph Properties
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
iammosespaulr
10 posts
#1 • 2 Y
This topic is linked to Problem 7.
Y by Adventure10, Mango247
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices $n>3$ and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex $n>3$ are pilferer win graphs so for the cop to win the graph must be a cyclic graph with $n\leq{3}$ or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches $k/2$ turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only $k/2$ turns the distance that the pilferer is allowed to travel must be $\leq{k/2}$ for a non-cyclic graph i.e terminating branched graphs.
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#2 • 2 Y
Y by Adventure10, Mango247
iammosespaulr wrote:
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
That would be great, looking forward to see the simulation.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#3 • 2 Y
Y by Adventure10, Mango247
iammosespaulr wrote:
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices $n>3$ and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex $n>3$ are pilferer win graphs so for the cop to win the graph must be a cyclic graph with $n\leq{3}$ or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches $k/2$ turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only $k/2$ turns the distance that the pilferer is allowed to travel must be $\leq{k/2}$ for a non-cyclic graph i.e terminating branched graphs.
I think there are good ideas here, but I do not understand the proof right now. I am confused around here:
Quote:
let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches $k/2$ turns
Could you clarify the statement of the result and format the proof to make it easier to read?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
iammosespaulr
10 posts
#4 • 2 Y
Y by Adventure10, Mango247
yeah sure .
I wanted to imply the fact that adding a dominant vertex wasn't going to the change the outcome provided that the cop and the pilferer had put in their best efforts i.e try considering a cyclic graph where the number of vertices > 3. This is clearly a cop win graph ,but adding a branch to one of the vertices on the graph leads to a possibility that the pilferer may enter the branch and get caught, but he chooses not to .This clearly does not change the outcome .So we could conclude that the addition of the dominant vertex does not affect the end result so hence removing a dominant vertex must also not affect the end result.

BTW the simulation is working. i had built it on the GraphTea
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
iammosespaulr
10 posts
#5 • 1 Y
Y by Adventure10
Algorithm's kinda faulty working on it will let you know soon..
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#6 • 2 Y
Y by Adventure10, Mango247
iammosespaulr wrote:
yeah sure .
I wanted to imply the fact that adding a dominant vertex wasn't going to the change the outcome provided that the cop and the pilferer had put in their best efforts i.e try considering a cyclic graph where the number of vertices > 3. This is clearly a cop win graph ,but adding a branch to one of the vertices on the graph leads to a possibility that the pilferer may enter the branch and get caught, but he chooses not to .This clearly does not change the outcome .So we could conclude that the addition of the dominant vertex does not affect the end result so hence removing a dominant vertex must also not affect the end result.

BTW the simulation is working. i had built it on the GraphTea
Thanks for clarifying about the proof (and I think you mean "robber win" where you wrote "cop win"?).

I agree that adding a vertex with a single edge to a cycle of length at least $4$ will not change the result. However, how are we concluding that removing a dominant vertex will not change the result in general?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
iammosespaulr
10 posts
#7 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
iammosespaulr wrote:
yeah sure .
I wanted to imply the fact that adding a dominant vertex wasn't going to the change the outcome provided that the cop and the pilferer had put in their best efforts i.e try considering a cyclic graph where the number of vertices > 3. This is clearly a cop win graph ,but adding a branch to one of the vertices on the graph leads to a possibility that the pilferer may enter the branch and get caught, but he chooses not to .This clearly does not change the outcome .So we could conclude that the addition of the dominant vertex does not affect the end result so hence removing a dominant vertex must also not affect the end result.

BTW the simulation is working. i had built it on the GraphTea
Quote:
Thanks for clarifying about the proof (and I think you mean "robber win" where you wrote "cop win"?).

I agree that adding a vertex with a single edge to a cycle of length at least $4$ will not change the result. However, how are we concluding that removing a dominant vertex will not change the result in general?
yeah you're right i meant robber win and i was trying to use the idea of implying that since
JGeneson wrote:
"the addition of the vertex with a single edge to a cycle of length at least $4$ will not change the result"
the removal of a vertex (which is actually adding the negative of that vertex) will also not change the result.
This post has been edited 2 times. Last edited by iammosespaulr, Nov 24, 2017, 4:23 AM
Reason: Aesthetic Reasons
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#8 • 2 Y
Y by Adventure10, Mango247
iammosespaulr wrote:
JGeneson wrote:
Thanks for clarifying about the proof (and I think you mean "robber win" where you wrote "cop win"?).

I agree that adding a vertex with a single edge to a cycle of length at least $4$ will not change the result. However, how are we concluding that removing a dominant vertex will not change the result in general?
yeah you're right i meant robber win and i was trying to use the idea of implying that since
JGeneson wrote:
"the addition of the vertex with a single edge to a cycle of length at least $4$ will not change the result"
the removal of a vertex (which is actually adding the negative of that vertex) will also not change the result.
I'm confused about how removing a vertex would not change the result. If this was true, then wouldn't every graph have the same result as a graph with just two vertices and an edge between them?
This post has been edited 1 time. Last edited by JGeneson, Nov 27, 2017, 4:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
iammosespaulr
10 posts
#9 • 2 Y
Y by Adventure10, Mango247
no not every graph can be simplified take a heptagon for example ,you would not be able to remove any vertices because it has no dominant vertices
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#10 • 1 Y
Y by Adventure10
iammosespaulr wrote:
no not every graph can be simplified take a heptagon for example ,you would not be able to remove any vertices because it has no dominant vertices
Thanks for clarifying about this, so the claim is that removing any dominant vertex does not change the result of the game.
Suppose we start with a graph $G$ on $5$ vertices. Four of the vertices form a cycle, and the last vertex $v$ has edges with all of the other vertices, so $v$ is a dominant vertex in $G$.
Let $G'$ be the graph obtained by deleting the vertex $v$, so $G'$ is just a cycle on $4$ vertices.
Does the game have different results on $G$ and $G'$?
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Cop-Win Graph Properties
iammosespaulr   9
N Dec 2, 2017 by JGeneson
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices $n>3$ and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex $n>3$ are pilferer win graphs so for the cop to win the graph must be a cyclic graph with $n\leq{3}$ or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches $k/2$ turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only $k/2$ turns the distance that the pilferer is allowed to travel must be $\leq{k/2}$ for a non-cyclic graph i.e terminating branched graphs.
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
9 replies
iammosespaulr
Nov 14, 2017
JGeneson
Dec 2, 2017
J
No more topics!
H
J
H
Cop-Win Graph Properties
iammosespaulr   9
N Dec 2, 2017 by JGeneson
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices $n>3$ and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex $n>3$ are pilferer win graphs so for the cop to win the graph must be a cyclic graph with $n\leq{3}$ or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches $k/2$ turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only $k/2$ turns the distance that the pilferer is allowed to travel must be $\leq{k/2}$ for a non-cyclic graph i.e terminating branched graphs.
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
9 replies
iammosespaulr
Nov 14, 2017
JGeneson
Dec 2, 2017
J