Some cities in country are connected with oneway road. It is known that every closed cyclic route, that don`t break traffic laws, consists of even roads. Prove that king of city can place military bases in some cities such that there are not roads between these cities, but for every city without base we can go from city with base by no more than $1$ road.
HIDE: PS I think it should be one more condition, like there is cycle that connect all citiesProblem
Source: St Petersburg Olympiad 2014, Grade 10, P7
Tags: combinatorics, graph theory
27.03.2018 09:17
(1) Reduction claim: Suppose we have chosen some bases B that satisfy no roads between bases. If every city that can reach a base in one move can also be reached from another base in one move. Let S be the set of cities that can reach a base in one move and be reached from a base in one move. Then upon constructing a configuration for G-S, we will obtain a legal configuration for G. Proof: Just combine the chosen bases. It is clear that (A) there are no roads between bases (B) Every base can be reached from a city (2) There exist a city A such that no city B satisfy the following: A is reachable from B but B is not reachable from A. This naturally follows from reachability is transitive. (3) Consider the city A. Let T be the set of cities that can reach A and can be reached from A (including A). Then it is possible to place some bases on T such that the reduction claim (1) is satisifed. Proof: For each city in T, consider its distance from A. By the even condition, this distance has a well defined parity. Take A and all even distanced cities in T. This will satisfy the reduction claim. Thus we can always reduce to a smaller case. The proof is complete.
27.03.2018 14:46
arvindf232 wrote: (1) Reduction claim: Suppose we have chosen some bases B that satisfy no roads between bases. If every city that can reach a base in one move can also be reached from another base in one move. Let S be the set of cities that can reach a base in one move and be reached from a base in one move. Then upon constructing a configuration for G-S, we will obtain a legal configuration for G. Proof: Just combine the chosen bases. It is clear that (A) there are no roads between bases (B) Every base can be reached from a city Could you elaborate on "just combining them".As i understand the choice of bases in G(V)\S is completely independent of that in $S$ so why is (A) obvious?
29.03.2018 18:33
RagvaloD wrote: Some cities in country are connected with oneway road. It is known that every closed cyclic route, that don`t break traffic laws, consists of even roads. Prove that king of city can place military bases in some cities such that there are not roads between these cities, but for every city without base we can go from city with base by no more than $1$ road. The claim is true when the di-graph $G$ is strongly connected. (for any two vertices $a,b$ there is a path from $a$ to $b$) Proof: First, notice that the vertices of $G$ can be colored with two colors, say white and black, such that any two vertices of the same color are not connected. Indeed, fix some vertex $a$ and color it with white. For any other vertex $x$, there is a path from $a$ to $x$. We color the vertices of that path starting from $a$ alternatively white-black-white-... till arriving at $x$. It's can be seen easily that such coloring is correct, using the fact all cycles in $G$ are with even length and $G$ is strongly connected. Finally, we dispose the bases in the white colored vertices, and check that it satisfies all conditions. $\blacksquare$ Now, we can proceed using induction on the number of vertices of $G$. Taking some graph $G$, we decompose it into strongly connected components $G_1,G_2,\dots,G_m$. The arcs between any two components $G_i$ and $G_j$ are in only one directions, say from $G_i$ to $G_j$. If we contract all vertices in $G_i\,,\,i=1,2,\dots,m$ into single point (we denote it again with $G_i$) we make an acyclic directed graph. We can reorder its vertices $G_i\,,\,i=1,\dots,m$ in such an order, we denote it in the same way, $G_1,G_2,\dots,G_m$ such that if $G_i$ is connected with $G_j$ (in that direction) then $i<j$. After that, we apply the above claim for $G_1$ and choose the set of its bases(vertices) $G'_1$. We delete all vertices in $G_2,\dots,G_m$ that $G'_1$ is connected with. Then proceed with the remaining vertices in $G_2$. It may happen $G_2$ is no more strongly connected, but yet we can apply the induction hypothesis to it, choose bases, say $G'_2$ then delete all vertices connecting $G'_2$ to $G_3,\dots,G_m$ , and so on.
31.03.2018 12:57
"just combining them" means the set of bases consists of exactly the chosen bases in the reduction claim B (For inside S) and the new configuration in G-S. (A) is obvious since we have excluded all the neighbours of B from G-S when defining S. More precisely: <Connected means immediately adjacent> Since in the definition, every cities reachable from B, or can reach a base in B, are included in S. So no bases in G-S could possibly be connected to B, the bases in S. Two bases within B cannot connect to each other by the imposed requirements on B. Two bases in G-S could not be connected since it is a legal configuration for G-S.
24.06.2019 13:37
This problem is a well-known one such set of cities are called a Kernel for the graph.It is appeared in for example Introduction to graph theory(West).(p.58).