Idle thought from yesterday evening [entries|reading|network|archive]
simont

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

Thu 2008-01-31 10:46
Idle thought from yesterday evening
LinkReply
[identity profile] songster.livejournal.comThu 2008-01-31 11:33
Don't see why we need to forbid self-links. The truly interesting question is "What is the longest cyclical graph". It may be that the answer is 1, but hopefully there's something longer out there.
Link Reply to this | Thread
[personal profile] simontThu 2008-01-31 11:48
You can see it that way if you like, but I don't want to see a self-link being used to pad out the length of a nontrivial cycle!
Link Reply to this | Parent | Thread
[identity profile] mooism.livejournal.comThu 2008-01-31 12:04
Can we just say that a band can’t appear more than once in a cycle? Depends whether you see figure-8 cycles as cheating, I suppose.
Link Reply to this | Parent | Thread
[personal profile] simontThu 2008-01-31 12:09
I think it's a question of improbability: the impressiveness of any result is directly related to its unlikelihood of appearing on the assumption that graph edges appear at random with an appropriate probability distribution.

Self-links are known to be common (eponymous albums and/or songs). Hence the base probability model on which to judge impressiveness should reflect that, by considering self-links to appear with a significantly larger probability than non-self links. So including a self-link in a cycle doesn't increase its impressiveness by very much (so I'd be inclined to consider it a cheap trick), and finding a cycle entirely composed of one self-link is definitely too easy to be a challenge. But two nontrivial cycles sharing a vertex would be a more impressive find, so I'd accept the resulting figure-8 as a worthwhile result.
Link Reply to this | Parent
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]