0
$\begingroup$

I got a problem related to graph theory -

Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, d) if |a-c|<=1 and |b-d|<=1 The number of edges in this graph is

Answer is given as 506 but I am calculating it as 600, please see attachment.

I am unable to get why it is coming as 506 instead of 600.

Thanksenter image description here

$\endgroup$
  • 2
    $\begingroup$ How did you get to the conclusion that it's 600? $\endgroup$ – orezvani Apr 8 '14 at 6:44
  • 4
    $\begingroup$ You have 11 "boxes" in each row and column, you did the computation with 12. $\endgroup$ – A.Schulz Apr 8 '14 at 7:16
6
$\begingroup$

For a grid in the range of $[n_1,n_2]$, according to the problem statment, the number of edges is:

$$\#edges=\frac{8 \times (n_2-n_1+1)^2- 4\times 5-4\times3\times(n_2-n_1-1)}{2}$$

explanation: suppose every node has a degree of 8, then sum of the degrees is $8\times(n_2-n_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\times5$) and for every other border node we considered 3 more edges (the term $4\times3\times(n_2-n_1-1)$).

The solution for your problem is:

$$\frac{8(12-1+1)^2-4(5)-4\times3\times(12-1-1)}{2}=\frac{8(144)-20-12(10)}{2}=\frac{1012}{2}=506$$

$\endgroup$
  • $\begingroup$ how did u get this formula? $\endgroup$ – codeomnitrix Apr 8 '14 at 7:50
  • $\begingroup$ I've explained in the answer. First consider the simplest case where every node has a degree of 8, then remove those edges that are not in the graph (5 for each corner node, 3 for other border nodes) Which part of it is not clear? $\endgroup$ – orezvani Apr 8 '14 at 7:52
  • $\begingroup$ Yeah got it, it is more of less similar to the graphical counting method I was using. I got it now that I was using 13 rows instead of 12. Thanks Emab $\endgroup$ – codeomnitrix Apr 8 '14 at 7:59
2
$\begingroup$

Method 1

This is one kind of problem you can write a program to solve instantly. We are counting the number pairs satisfying the conditions you state. First generate the vertices (I'm using Python).

vertices = []
for x in range(1, 13):
  for y in range(1, 13):
    vertices.append([i, j])

Next count the pairs satisfying the conditions.

count = 0
for p in pts:
  for q in pts:
    if p != q:
      a, b = p
      c, d = q
      if abs(a - c) <= 1 and abs(b - d) <= 1:
        count = count + 1

Every edge has been counted twice, hence the answer is count / 2.

Method 2

There are four types of edges: vertical, horizontal, diagonal (slope 1 and -1). Observe that the number of vertical edges is equal to the number of horizontal edges and the number of slope -1 diagonal edges is equal to the number of slope 1 diagonal edges. So the total number of edges is 2 * #vertical + 2 * #diagonal.

The number of vertical edges is $11\times 12=132$. The number of diagonal edges is $2\times(1+2+\dots+10)+11=121$. $132\times 2 + 121 * 2 = 506$. This can be generalized to a square grid of any size: if the $1\le i,j\le n$, then the number of edges is $$2(n(n-1) + (n-1)(n-2) + (n-1)) = 2(n-1)(2n-1)$$.

Plug $12$ in the formula and you get $506$.

$\endgroup$
1
$\begingroup$

This is simple math no need to generalize any folrmula.

condition type1 :a=c

condition type2: a-c=1 or c-a=1.

total combinations satisfying condition1 : 12

total combinations satisfying condition2 : 11 (I am taking only one case either a-c=1 or c-a=1 .Think about it why?)

so satisfying combinations for 'a' and 'c' = 11+12 =23

IN Similar way satisfying combinations for 'b' and 'd' = 23

[ a     b]
      *
[ c     d]

So total solutions = 23*23 = 529

Now there are some cases where loop exists like :

[1,2]        [5,5]
[1,2]   OR   [5,5]

There will be 23 such cases .Why ?? :)

So remove such cases : 529-23 = 506

visit : http://yougeeks.blogspot.in/2015/01/consider-undirected-graph-g-where-self.html#more

$\endgroup$
0
$\begingroup$

Total number of vertices $= 12*12 = 144.$

The graph formed by the description contains $4$ (corner) vertices of degree $3$ and $40$ (external) vertices of degree $5$ and $100$ (remaining) vertices of degree $8.$

According to (handshake theorem's)

$2|E|=$ sum of the degrees

$ 2|E| = 4*3+40*5+100*8= 1012$

$|E| = 1012/2 = 506$ edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.