Prev: When your math is wrong
Next: expanding the history chapter of this book Chapt 2 #156; ATOM TOTALITY
From: Mike Terry on 13 Jun 2010 10:08
"William Elliot" <marsh(a)rdrop.remove.com> wrote in message
news:20100613031744.T30925(a)agora.rdrop.com...
> On Sun, 13 Jun 2010, stdazi(a)gmail.com wrote:
>
> > On Jun 13, 8:13 am, William Elliot <ma...(a)rdrop.remove.com> wrote:
> >> On Sat, 12 Jun 2010, Yann David wrote:
> >>> I'd like to know whether there is any known simple instance of planar
> >>> triangulation (finite planar graph which is maximal in the sense that
> >>> no edge can be added to it) in which there is no semi-Hamiltonian path
> >>> of which both endpoints are on the external face.
> >>
> >>> (A semi-Hamiltonian path is an elementary path that traverses each
> >>> vertex of the graph exactly once.)
> >>
> >>> One could, more specifically, ask for a triangulation in which no
semi-
> >>> Hamiltonian path has both endpoints on the same face (be it the outer
> >>> one or otherwise) or even without any semi-Hamiltonian path at all (a
> >>> non semi-Hamiltonian triangulation).
> >>
> >> o
> >> |
> >> o--o--o
> >>
> >> in monospace font, has no Hamiltonian paths.
> >>
> >>> Any solutions, pointers, suggestions... are most welcome!
> >
> > how is that a triangulation?
> >
> It's a finite planar graph as OP described above.

It's not maximal as the OP described above.

o
|\
| \
o--o--o

Look - I managed to add another edge!

> Why is the beginning of your sentence not capitalized?

Why didn't you read what the OP asked? :)

Mike.


From: spudnik on 14 Jun 2010 21:40
if a "semi-hamiltonian" path ended
on the same face as it began,
is it hamiltonian?

thus&so:
1/9 is, in base-9, 1/10; or 0.10000... so,
what is the canonical digit for base-one?

thus&so:
time obviously doesn't bend, except in a subjective sense
of living & dying, sleeping & waking ... it's too bad
about Schroedinger's joke-cat, though ...
Schroedinger's cat is dead; long-live Schroedinger's cat!

the curvature of space was dyscovered with "synchronized sundials"
by Aristarchus; it was measured in Alsace-Lorraine by Gauss,
with his theodolite & trigonation ... for money, ne'er again!

Dear Editor;
It is apparent from the City ordinance, proposed to ban high-density
polyethylene (HDPE) bags -- excepting take-out at restaurants -- that
it will be a state-wide eco-tax. The "green fee" is slated to be 25
cents for any paper bag from the retailer, grocer or farmer at the
market. This is unfortunate for two reasons, although, as I stated a
year ago in Council, when it first came-up, the super-light-weight &
super-inexpenseve bags (much less than the Staff Report was willing to
concede) are so good at what they do, before they inevitably break-up
& decompose (but , according to the apocrypha & studies of Heal the
Bay etc., HDPEbagsR4ever) that coastal cities may be justified in a
ban,
to prevent stormdrain blockages.

Firstly, just like with "hemp for haemarrhoids," it is not a panacea
or much of an economic stop-gap, if only because "only criminals &
baby-smotherers will have HDPE bags." Really, there are plenty of
natural plastics; "plastic" is really an adjective, as in the plastic
arts! Note also that even plant-derived plastic bags will be banned,
although they are acknowledged to biodegrade.

Secondly, a very small Carbon Tax would be much more realistic than
simply allowing Waxman's CO2 cap & trade nostrum, of letting the
abitrageurs & daytraders raise the price of our energy as much as they
can in the "free market" -- with no provision whatever for government
revenue (contrary to the slogan of "cap & tax" used by Tea Partiers,
"Republicans," and the WSUrinal).

As with the much-greater amount of materiel & energy that is required
for the paper bags, we might do better to ban *low* density
polypropolene bags at department & boutique stores, which are many
times heavier than the HDPE bags. It is surprising that a fifth of
the HDPE bags are recycled, considerng that a) they're only good for
garbage, if they get dirty, and b) they are quite often re-used by
folks; recycling them is an unsanitary joke, though composting might
be educational fun.

The retailers would get ten of the 25 cents, which seems to be a quite
an incentive for the overhead. However, has anyone seen any analysis
on the energy requirements for the "reusable" replacement, and their
importation?

--Sincerely, Brian H.

--Stop BP's/Waxman's arbitragueur-daytripper's delight, cap&trade
(Captain Tax in the feeble minds of Tea Partiers,
"'republicans' R us," and the WSUrinal (and
the latter just l o v e Waxman's '91 cap&trade bill !-))
http://wlym.com

From: Yann David on 15 Jun 2010 07:59
On Jun 14, 9:40 pm, spudnik <Space...(a)hotmail.com> wrote:
> if a "semi-hamiltonian" path ended
> on the same face as it began,
> is it hamiltonian?

Hum, I guess you're right. Since every face is a triangle, a semi-
Hamiltonian path with both endpoints on the same face is Hamiltonian.
How could I miss that?

Anyway, the problem is still open as far as I'm concerned - but maybe
it should be more clearly divided in 2:
1) find a non Hamiltonian triangulation;
2) find a non semi-Hamiltonian triangulation.
From: Yann David on 15 Jun 2010 20:10
On Jun 15, 7:59 am, Yann David <yann_da...(a)hotmail.com> wrote:
> On Jun 14, 9:40 pm, spudnik <Space...(a)hotmail.com> wrote:
>
> > if a "semi-hamiltonian" path ended
> > on the same face as it began,
> > is it hamiltonian?
>
> Hum, I guess you're right. Since every face is a triangle, a semi-
> Hamiltonian path with both endpoints on the same face is Hamiltonian.
> How could I miss that?
>
> Anyway, the problem is still open as far as I'm concerned - but maybe
> it should be more clearly divided in 2:
> 1) find a non Hamiltonian triangulation;
> 2) find a non semi-Hamiltonian triangulation.

In fact, a semi-Hamiltonian path with both endpoints on the external
face is actually "stronger" than a "simple" Hamiltonian circuit since
a Hamiltonian circuit can trivially be derived from such a path, but
the reverse is not true - it's only possible when the circuit
traverses one of the edges of the external face. Finding a
counterexample should be easier then. :)
From: William Elliot on 16 Jun 2010 02:56
On Tue, 15 Jun 2010, Yann David wrote:

> Anyway, the problem is still open as far as I'm concerned - but maybe
> it should be more clearly divided in 2:
> 1) find a non Hamiltonian triangulation;
> 2) find a non semi-Hamiltonian triangulation.
>
What's a trianglation?

Are these definitions the same definitions you're using?
A graph is Hamiltonian when there's a circuit that visits
each vertex only once.
A graph is semi-Hamiltonian when there's a path that visits
each vertex only once.

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: When your math is wrong
Next: expanding the history chapter of this book Chapt 2 #156; ATOM TOTALITY