Arches and galleries
Yann David
The following simple procedure generates graphs that seem to be
Hamiltonian, but I don't manage to prove or disprove it. Will you be
any luckier (or just plain smarter:)?
The procedure basically accumulates finitely many "arches" on a
straight line (the "base").
There's no constraint on the first arch; each subsequent arch must
have exactly one "foot" (extremal point of contact with the base)
strictly between the feet of some preceding arch.
Example:
(1st arch)
+----1---+
| |
| |
----a--------b---------
(2nd arch)
+----1---+
| |
| |
----a---c----b-----d--
| |
| |
+-----2----+
(3rd arch)
+----1---+
| |
| |
----a---c--e-b-----d--f
| | | |
| | | |
+--|--2----+ |
| |
+-----3----+
I hope you get the idea. No other ingredients seem necessary to make
it work: the feet may overlap, and I don't demand that the drawing be
planar (even though some interesting things, or just a simpler proof,
could be found for planar arch systems).
The graph under consideration is formed naturally: the feet of the
arches are the nodes; the arches and the segments of the base that
separate successive arch feet form the edges. Let's call such a graph
a "gallery".
For instance, the above drawing yields the following graph:
G = ( V = {a, b, c, d, e, f}, E = { (a, b), (c, d), (e, f), (a, c),
(c, e), (e, b), (b, d), (d, f) } )
One Hamiltonian cycle is a-b-e-f-d-c-a. (A Hamiltonian cycle is a path
that traverses each node exactly once before returning to its starting
point.)
Is that a known problem? Is any solution available? Is it difficult to
recognize that a graph is a gallery?
Any comments or suggestions are welcome!
Cheers,
Yann David
Jasen Betts
> Hello.
>
> The following simple procedure generates graphs that seem to be
> Hamiltonian, but I don't manage to prove or disprove it. Will you be
> any luckier (or just plain smarter:)?
>
> The procedure basically accumulates finitely many "arches" on a
> straight line (the "base").
> There's no constraint on the first arch; each subsequent arch must
> have exactly one "foot" (extremal point of contact with the base)
> strictly between the feet of some preceding arch.
>
> Example:
>
>
> (1st arch)
>
> +----1---+
> | |
> | |
> ----a--------b---------
>
>
> (2nd arch)
>
> +----1---+
> | |
> | |
> ----a---c----b-----d--
> | |
> | |
> +-----2----+
>
>
> (3rd arch)
>
> +----1---+
> | |
> | |
> ----a---c--e-b-----d--f
> | | | |
> | | | |
> +--|--2----+ |
> | |
> +-----3----+
>
drawing them like this may help
---a-c-e-.
| | | |
| | | |
1 2 3 |
| | | |
| | | |
.-b-d-f-|--
| |
`-------'
the obvious path is to visit the nodes in a clockwise direction across the top down the rightmost arch back across
the bottom and up the first arch.
Yann David
> drawing them like this may help
>
> ---a-c-e-.
> | | | |
> | | | |
> 1 2 3 |
> | | | |
> | | | |
> .-b-d-f-|--
> | |
> `-------'
>
> the obvious path is to visit the nodes in a clockwise direction across the top down the rightmost arch back across
> the bottom and up the first arch.
This is an ingenious way to represent the example that illustrates the
problem, but can it be generalized to all galleries? I don't see how
right now, but maybe you're onto something.
Mike Williams
my normal account. Apologies if my previous attempt does get through
eventually, but here it is again:
If the feet of the arches are allowed to be coincident, then I have a
counterexample:
+-----------+
| +---+ |
| | | |
---a---b---c---d---e---f
| / \ |
+-----+ +---------+
BE is the first arch, and the three subsequent arches, CA, CF and CD
all
connect at the point C. That's not a Hamiltonian graph.
Yann David
Yes, this is a good counterexample.
So let us consider the following, slightly modified constraint: each
new arch n (after the first) must have one foot strictly between the
feet of some preceding arch p, and the other strictly outside the span
of p. In fact, the relationship between n and p becomes symmetrical,
as each one partially overlaps the other:
+----n---+
| |
| |
----+---+----+-----+--
| |
| |
+-----p----+
I think that preserves the proposition, while excluding your
counterexample, in which c-d doesn't partially overlap any other arch.
With the modified constraint, you gallery becomes
+-----------+
| +-----+ |
| | | |
---a---b-g-c---d---e---f
| / \ |
+-----+ +---------+
(HC: a-c-f-e-d-g-b-a)
or
+-----------+
| |
| |
---a---b---c---d---e-g-f
| / \ | | |
+-----+ \ +-----+ |
+--------+
(HC: a-c-f-g-d-e-b-a)
so it stops being a counterexample.
Mike Williams
> On Dec 11, 11:23 am, Mike Williams <nos...@econym.demon.co.uk> wrote:
>
>
>
> > For some reason I don't seem to be able to reply to this thread from
> > my normal account. Apologies if my previous attempt does get through
> > eventually, but here it is again:
>
> > If the feet of the arches are allowed to be coincident, then I have a
> > counterexample:
>
> > +-----------+
> > | +---+ |
> > | | | |
> > ---a---b---c---d---e---f
> > | / \ |
> > +-----+ +---------+
>
> > BE is the first arch, and the three subsequent arches, CA, CF and CD
> > all
> > connect at the point C. That's not a Hamiltonian graph.
>
> Yes, this is a good counterexample.
>
> So let us consider the following, slightly modified constraint: each
> new arch n (after the first) must have one foot strictly between the
> feet of some preceding arch p, and the other strictly outside the span
> of p. In fact, the relationship between n and p becomes symmetrical,
> as each one partially overlaps the other:
Adding that constraint breaks that particular counterexample, but it's
easy to generate another counterexample that obeys that constraint.
+-------+
| |
+---------- ----------+
| | \ / | |
---a---b---c---d---e---f---g
| / \ |
+------ ------+
Once again, I'm using coincident points for the feet.
In this one, CE is the first arch. Each of DA, DB, DF and DG have one
leg strictly inside CE and the other leg strictly outside CE.
Mike Williams
galleries, and have just come up against this example:
+-----------2-----------+
| +-------3-------+ |
| | | |
---a---b---c---d---e---f---g---h---i---j
| | | | | |
+-----1-----+ | +-----4-----+ |
+---------5---------+
It's planar, obeys your new constraint, has no coincident feet, but
it's not Hamiltonian.
Yann David
> On Dec 12, 4:22 pm, Yann David <yann_da...@hotmail.com> wrote:
>
>
>
> > On Dec 11, 11:23 am, Mike Williams <nos...@econym.demon.co.uk> wrote:
>
> > > For some reason I don't seem to be able to reply to this thread from
> > > my normal account. Apologies if my previous attempt does get through
> > > eventually, but here it is again:
>
> > > counterexample:
>
> > > +-----------+
> > > | +---+ |
> > > | | | |
> > > ---a---b---c---d---e---f
> > > | / \ |
> > > +-----+ +---------+
>
> > > all
> > > connect at the point C. That's not a Hamiltonian graph.
>
> > Yes, this is a good counterexample.
>
> > So let us consider the following, slightly modified constraint: each
> > new arch n (after the first) must have one foot strictly between the
> > feet of some preceding arch p, and the other strictly outside the span
> > of p. In fact, the relationship between n and p becomes symmetrical,
> > as each one partially overlaps the other:
>
> Adding that constraint breaks that particular counterexample, but it's
> easy to generate another counterexample that obeys that constraint.
>
> +-------+
> | |
> +---------- ----------+
> | | \ / | |
> ---a---b---c---d---e---f---g
> | / \ |
> +------ ------+
>
> Once again, I'm using coincident points for the feet.
>
> In this one, CE is the first arch. Each of DA, DB, DF and DG have one
> leg strictly inside CE and the other leg strictly outside CE.
Well, this time I'm not convinced by your counterexample: isn't the
following an HC?
a-d-g-f-e-c-b-a
My overall perspective on the problem is that I have a (vague)
intuition there is something to be found here - there is some
elementary procedure that just piles up random arches, following a few
simple rules, and systematically yields HCs, in some non-trivial
manner.
I might be plain wrong.
I might also miss the right mix of constraints: maybe we shouldn't let
the feet of distinct arches coincide after all, or we should restrict
this to planar arches... It's not obvious yet though.
Yann David
What about:
a-b-h-i-j-e-f-g-c-d-a
?
Yann David
+-------------------+
| |
| +-------------------+
| | _______ | |
| | ____/____ \ | |
| |/ / \ \| |
a---b---c---d---e---f---g---h
| |
+---------------+
This gallery is not Hamiltonian. Any elementary cycle avoids at least
one node.
One could still ask for the highest rate of avoided nodes that can in
general be obtained with the best elementary cycle - in other words,
how bad the best cycle can get, or how hard to traverse a gallery can
be. By augmenting the above construct, one can see that this rate can
be made arbitrarily close to 1/6, but maybe higher rates can be
obtained. Anyway, finding the highest rate is probably not for the
faint of heart.
As far as I am concerned, the problem is still open for planar
galleries (i.e., are they Hamiltonian?) - even with coincident feet.
Cheers,
Yann David
Yann David
+-----------------------+ +---------------------------+
| +---------------+ | | +---------------+ |
| | | | | | | |
a---b---c---d---e---f---g---h---i---j---k---l---m---n---o---p
| | | | | | | |
| | +---------------+ | | +-----------+
| +---------------------------+ |
+-----------------------------------+
This gallery was found by a computer program that builds random planar
galleries and then looks for a Hamiltonian circuit.
It didn't find any with no feet overlaps and less than 8 arches, but
when feet overlaps are allowed, 5 arches suffice:
+-------------------+
| +-----------+ |
| | | |
a---b---c---d---e---f---g---h---i
| | | | | |
| | +-----------+ | |
| +-------------------+ |
+---------------------------+
Cheers,
Yann David