I noticed that you can write the problem using rewriting rules (for this graph for example):

And so on where every letter can be replaced by a vertex connecting to it and itself, left recursively.

So a Hamilton circuit for this graph could be generated following the rules like so:b -> aB

aB

a -> dA

dAB

d -> gD

gDAB

g -> fG

fGDAB

f -> eF

eFGDAB

e -> cE

cEFGDAB

c -> bC

bCEFGDAB

Writing graph problems as Context Free Grammars and in this case left recursive ones gives immediately many useful theorems. See: http://en.wikipedia.org/wiki/Context-free_grammar

For example many problems about Context Free Grammars are undecidable in the general case.

## No comments:

## Post a Comment