Hellooooooo Jan !
It is 20:20, it is almost dark outside and I am getting home by bike.
Worst of all, I am being assaulted by hungry mosquitoes. I re-read it
the following enough times to be sure that if I miswrote "v" instead
of "x" somewhere, reading it again wouldn't have changed anything.
When v is considered for removal, it is a leaf of the lex-BFS tree.
Its father (and first discoverer) is named x, and we suppose that
there is a vertex y which is not a neighbor of x, otherwise v is
removed without any problem.
Why should there be a x-y path avoiding all of v's neighbors ? Well,
first note that v is the furthest vertex from the source. Not
strictly, of course, but a lex-BFS is a BFS, and as we are testing for
removal the vertices in the reverse of the discovery order, it means
that in the lex-BFS exploration the vertex v is the last one to be
discovered (without considering the vertices that have been deleted
since the beginning of the elimination algorithm). Hence, it is the
one which is the further away from the source, even if other vertices
may be at equal distance from the source.
Now, how can v be adjacent to the other vertices of the graph ? Well,
for instance v can not be connected to any of x's ancestors, as its
distance from the source is strictly greater than the distance between
x and the source. Hence there is a path from x to the source of the
lex-BFS which does not touch any of x's neighbors. By the same reason,
the vertex y can not be closer than v from the source. If it were,
there would be a path from y to the source (from ancestor to ancestor)
which would avoid all of v's neighbors.
Hence, at some point, when the lex-BFS algorithm was processing all
the vertices at distance d(source, y) = d(source, v), it picked y
before v (we are removing the vertices in reverse order). But then, we
know that y and v have different sets of neighbors among the vertices
at distance "d(source, { v or y} ) - 1" from the source. We know that
because by assumption y is not adjacent to x. In this case, because y
was picked before v in the lex-BFS ordering, it means that the lex-BFS
code of y at this moment was strictly greater than the lex-BFS code of
v.
Hence there is a neighbor of y at distance d(source, y) - 1 which is
not a neighbor of v. Hence there is a path from y to the source going
through this vertex which avoids all of v's neighbors, hence
connectedness, hence certificate, hence I can jump on my bike to
escape the mosquitoes.
Nathann
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
