Connectivity of a graph with fixed number of vertices and edges - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T18:53:44Z http://mathoverflow.net/feeds/question/86722 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86722/connectivity-of-a-graph-with-fixed-number-of-vertices-and-edges Connectivity of a graph with fixed number of vertices and edges Mnarc 2012-01-26T14:29:38Z 2012-10-25T13:59:33Z <p>Hi,</p> <p>first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge.</p> <p>So this is the setup: -the graph is fully connected</p> <p>-the graph is directed</p> <p>-number of states are given</p> <p>-number of edges are given</p> <p>-the graph displays a markovchain, so all outgoing edges of a node have to be 1, summed up</p> <p>-there is one input node and one output node, no more absorbing states</p> <p>before the algorithm starts i want to estimate the probability of the most probable path.</p> <p>I was thinking about: what is the most probable graph structure, what would be the average connectivity and how would the probability distribution be.</p> <p>like I said before I'm new to this, so this might be stupid or to easy or impossible :P</p> http://mathoverflow.net/questions/86722/connectivity-of-a-graph-with-fixed-number-of-vertices-and-edges/110661#110661 Answer by Rosh for Connectivity of a graph with fixed number of vertices and edges Rosh 2012-10-25T13:59:33Z 2012-10-25T13:59:33Z <p>My just published book , " A New Algorithm for Studying Routes in a Connected Graph', Kindle Edition, by Amazon. Com may be helpful in your problem. My new algorithm does not employ search, recursion or AI. It is based on combinatorial Analysis/Block Design. My algorithm produces all routes of length (PL) between the starting node, s and all other nodes. The number of such routes is simply Avg(Nc)^PL where Avg(Nc) is average degree of nodal connectivity. My software package (EcoNets) also selects routes (simple or cyclic) between any two nodes s and t. It can also select any routes with any set of route-attributes such as distance, link costs or reliabilities. A sample network (10n, 20s) took about 1 minute of my laptop and about 1 Gigabytes of RAM for all routes with PL &lt;=10. If you go to Amazon.com website, you can peruse the sample pages of my book and study the algorithm. Wish you luck. </p>