Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

(graph theory) Amount of connectivity yielding solutions?

  1. Jun 11, 2013 #1
    I have what I presume to be a basic knowledge of the terminology involved in graph theory which I will attempt to utilize in order to describe the problem in my mind.

    Suppose an amount of nodes corresponding to a square number is arranged accordingly, forming n rows and n columns. Each node is to be assigned a value of either 1 or 0. An edge or connection is placed between two nodes if they are “orthogonally” adjacent in the arrangement, and if they both have a value of 1.
    Given any (n x n) arrangement of the above description, how many of the 2^(n*n) possible combinations of 0s and 1s will result in connectivity between two specific opposing corner nodes?

    An example of a connectivity yielding combination, or solution, for a 5 x 5 arrangement would be:

    - - - - - - x
    1 1 1 0 1
    1 0 1 0 1
    1 0 1 1 1
    1 0 0 0 0
    1 0 0 0 0

    For all intents and purposes we will assert that a solution depends on the connectivity specifically between the lower-right and upper-left corner nodes, and no other two nodes. X is here to indicate the location of these two nodes; they are NOT nodes themselves.

    Another distinct solution would be:

    1 1 1 1 1
    1 0 1 0 1
    1 0 1 1 1
    1 0 0 0 0
    1 0 0 1 1

    Keep in mind that despite being traversable by the same path as in the example above, in addition to numerous others, we are only considering connectivity, meaning that it has one, *or more*, traversable paths between the two specified nodes.

    Finding an answer for very small arrangements, is quite simple.
    Here are all the solutions for 2 x 2:

    1 1
    1 0

    0 1
    1 1

    1 1
    1 1

    So 3 out of the 16 possible combinations are solutions that result in specified connectivity.

    The answer for any arrangement could very well be determined using some computer program to iterate through all the possible combinations, finding which ones yield connectivity, but I would like to determine a mathematical/logical approach. So how would you go about this problem?
    Last edited: Jun 11, 2013
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted