Блог пользователя AndreiBalanici

Автор AndreiBalanici, история, 3 года назад, По-английски

Hi,everyone! Does anyone know how to compute number of paths of length 2 in a complet bipartit graph Kn,m? I search on Google and I have found only this one proof:(http://math.colorado.edu/~kstange/graph-theory-worksheet-solns.pdf),last page,exercise 6!I am not sure about the paths which have only one edge!For example,let be vertex A in the first subset and the vertices B,C in the second one!The above proof takes in counting the paths A-B-A,B-A-B,A-C-A,C-A-C.......This is right?

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

First of all, we know or can find out both subset. Then, we choose a subset and for each of it's vertices we know the number of connected vertices of the other subset.So,we can find out our answer using combinatorics. And,as for a single eage, I think that depends on whether the eages are bidirectional or not, I'm not sure,sorry.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The number of paths depends on what you consider as a "path". If we consider that paths can have non-distinct vertices (so paths like $$$A-B-A$$$ are also valid), then the formula can be found as follows: say you start the path in the first partition: this means that the path next goes into the second partition, then into the first partition again. You have $$$n*m*n$$$ such paths (you have $$$n$$$ ways to choose the first vertex in the path, $$$m$$$ ways to choose the second vertex and $$$n$$$ ways to choose the third vertex). Similarly, we count the paths that begin in the second partition and we get $$$m*n*m$$$. In conclusion, the total number is (the number of paths that start in the first partition) + (the number of paths that start in the second partition) = $$$n*m*n + m*n*m$$$.

If we consider that paths must have distinct vertices, we can actually use a similar reasoning. If we start our path in the first partition, then we have $$$n*m*(n-1)$$$ paths (there are $$$n$$$ ways to choose the first vertex, $$$m$$$ ways to choose the second, but the third vertex cannot be identical to the first one, so we have only $$$n-1$$$ choices we can make). For paths that start in the second partition, we get $$$m*n*(m-1)$$$. The final answer is $$$n*m*(n-1) + m*n*(m-1)$$$.