21.4.06

 

help

i am looking for the number of digraphs on 6 vertices, where every vertex can be reached from every other by following the edges in the right direction, and the graph is minimal with this property; ie., if you remove any single edge, you can no longer reach every vertex from every other vertex. i don't know whether this property (the first property, not the minimal property) has a name (connected digraph?). if you can get one such graph from another one by swapping round vertices, i consider them to be the same, or in other words, i'm counting unlabelled, not labelled graphs.

the dumbest kind of brute force (checking every digraph on 6 vertices) would give about 1 billion graphs to check for connectedness, minimality, and whether they are variations on each other. analysing and counting 1 billion graphs quickly is quite feasible. it's storing them and then comparing them to each other which almost immediately becomes practically impossible. in fact, storing a billion graphs is only slightly out my reach, but comparing them to each other is prohibitive. so it's necessary to come up with simplifications. the first of these are very quick and often rewarding - the low-hanging fruit. for example trying only a full set of unlabelled graphs, however many there are on 6 vertices, for the set of arrows in each direction. or ordering the graphs so that each one comes before all the ones which have the same edges plus some more, so that we find the minimal connected one first, and then don't need to bother with the rest. after that optimizations become a little more tricky. we start to have to use graph theory or symmetries in clever ways. (not withstanding the fact that the set of symmetries of 6 unlabelled points has no particular characteristics whatsoever - it's just the set of permutation of six items.) the universal tradeoff between computer time and programmer time comes into play, and every cpu clock tick has to be measured off against the more limited, and potentially more valuable, heartbeats and ticks of the human brain..

right now though, i do not have the time. someone do this for me please.

edit: a digraph where you can reach every vertex from every other is called strongly connected.


Comments:
Could we be talking about a tournament on six vertices? Your problem doesn't explicitly enumerate the need to visit each node only once, but graph people seem to be crazy about that shit.

Anyway, I know a little bit about edge coloring from wireless routing research, but that's about it for me and graph theory. Good luck.
 
not quite.

each vertex is connected to each other by a directed path in each direction, which may contain more than one edge, where as it seems in a tournament each vertex is connected to each other by a single edge, but which only goes in one direction.

i'm glad to find out that edge colouring is actually used for practical things.
 
Are you stuck in a job that is leading you on the path to no where?
We can help you obtain a College Degree with classes, books, and exams
Get a Genuine College Degree in 2 Weeks!
Well now you can get them!

Call this number now 24 hours a day 7 days a week (413) 208-3069

Get these Degrees NOW!!!

BA, BSc, MA, MSc, MBA, PHD,

Within 2 weeks!
No Study Required!
100% Verifiable

Call this number now 24 hours a day 7 days a week (413) 208-3069

These are real, genuine, They are verifiable and student records and
transcripts are also available. This little known secret has been
kept quiet for years. The opportunity exists due to a legal loophole
allowing some established colleges to award degrees at their discretion.


With all of the attention that this news has been generating, I wouldn't
be surprised to see this loophole closed very soon

Get yours now, you will thank me later
Call this number now (413) 208-3069
We accept calls 24 hours a day 7 days a week.
 
What's happened to Po's blog? She should sort it out.
 
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?