The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+46 votes
5.6k views
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
asked in Graph Theory by Veteran (112k points)
retagged by | 5.6k views
+8

So,

2e = 100*8 + 40*5 + 4*3 => e = 506 (ans)

Take a smaller graph of 4 vertices and evaluate then scale it to 12 vertices.

0
@Tuhin make this answer
0
Solve for smaller problem and the generalize it :) .

5 Answers

+110 votes
Best answer
If you think of a $12\times 12$ grid (like a chess board of size $12\times 12$), then each each point $\left(i,j\right)$, which is in $i^{th}$ row and $j^{th}$ column, is a vertex $\left(i,j\right)$.

Now we are allowed to connect only those points which are atmost $1$ distance apart (in both horizontal and vertical direction). So we will connect only horizontal neighbours, vertical neighbours, and diagonal neighbours.

So horizontal edges on each row are $11$ i.e. $11\times 12 = 132$ horizontal edges. Similarly we have $132$ vertical edges.

To count diagonal edges, think of $1\times1$ square boxes in which diagonals meet each other. There are $11\times 11$ such square boxes, and each box contains $2$ diagonals, so total diagonals $= 242$.

So total edges $= 132 + 132 + 242 = 506.$
answered by Boss (11.3k points)
edited by
+3

 not getting this why (There are 11*11 such square boxes, and each box contains 2 diagonals, so total diagonals = 242.) if there are 12 *12 kindly explain 
 

+7
consider it like a matrix .... we have diagonals and anti diagonals ...

diagonals sum of lengths will be  1+2+3+....11+ 10+9+8+.....1 =121

similarly anti diagonals sum of edges will be 121

that sums up to 242
0
nice approach
+1
nice explanation @Happy mittal
0

The Condition mentioned in the question is :

If |a−c|≤1AND |b−d|≤1

Dont u think edges are only along diagonals because both conditions should be satisfied. If the condition were having OR instead of AND then your answer was correct..

Please correct me if I am wrong

+73 votes
Total number of vertices $= 12\times 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\times 3+40\times 5+100\times 8= 1012.$

$|E| = \frac{1012}{2} = 506$  edges.
answered by Loyal (6.1k points)
edited by
0
how you find out no of vertices are degree 3, and 5.....??
+11

It is 12x12 table/matrix , where each row has 12 vertices and there are 12 row , so total number of vertices = 12*12 = 144 , 
 

can you figure out ...

0
o yeah ... thanks :)
0
@Sonam plz chk one thing

if abcd is a rectangle and each of it's side is 1

then diagonal must be $\sqrt{1^{2}+1^{2}}=\sqrt{2}$

and root(2) is greater than 1

So, each diagonal is greater than 1

Then how can we take diagonals in calculation?

We must take each edge less than 1

right?

plz help
+1
@srestha

Let (1,1) and (2,2) be two pairs.

Now,

$\left | 1 - 2 \right |$ = 1 and $\left | 1 - 2 \right |$ = 1

Hence the condition, There is an edge between (a,b) and (c,d) if |a−c|≤1 and |b−d|≤1 holds true.

There will be an edge between these two pairs.

They are calculating the value, not the length.
0
yes , u r correct:)

but it is showing like the length |a-c|<=1

how do u know it is value?
+2
@srestha

The concept of length should be among the points.

This is a point (a, b). This is another point (c, d).

But single 'c' or 'a' is not a point.

I think this will clear your doubt :)
0
.

please explain me  this point  .......40(external) vertices of degree 55
and  100 (remaining) vertices of degree 8
0

The graph formed by the description contains 44 (corner) vertices of degree 33 and 40(external) vertices of degree 55 
and  100 (remaining) vertices of degree 8.

 Hemant Parihar  pls explain this 

0
chk the diagram above.
0
explain pls
0
first edit ur comment plz :)

See

1<=i<=12 what does it means ?

there are 12 lines of length 1

Now, how many such 12 lines possible?11

So, total number of 1 length line possible in vertical 11*12=132

Similarly find horizontal and diagonal

U will get ans
+1
@mithlesh...wonderful explanation :)
0
what a nice approach @mithelesh
0
@Mithlesh Upadhyay
But , the 4 corner edges are - (1,1),(12,1),(12,12) and (1,12). Here (12,1) and( 1,12) are same. Rest all others are same. But (1,1) and (12,12) are not same. Please see into it.
+6 votes

image:o111.PNG

There will be ‘11’ edges in a horizontal line, so for 12 horizontal lines, 11×12=132
There are ‘11’ edges in vertical line, so for 12 vertical lines, 11×12=132
There are ‘2’ diagonals ‘⊠’ in each square box.
There are 11×11 square boxes available. So 11×11×2=242
------------------------------------------
Total: 132+132+242
=506 edges

answered by Active (4.4k points)
edited by
0
11*11*2 not 12 please correct it..
+3 votes

Given:
The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}.
There is an edge between (a, b) and (c, d) if |a − c| <= 1 and
                                              |b − d| <= 1.

There can be total 12*12 possible vertices. The vertices are (1, 1),
(1, 2) ....(1, 12) (2, 1), (2, 2), ....

The number of edges in this graph?
Number of edges is equal to number of pairs of vertices that satisfy
above conditions. For example, vertex pair {(1, 1), (1, 2)} satisfy
above condition.

For (1, 1), there can be an edge to (1, 2), (2, 1), (2, 2). Note that
there can be self-loop as mentioned in the question.
Same is count for (12, 12), (1, 12) and (12, 1)

For (1, 2), there can be an edge to (1, 1), (2, 1), (2, 2), (2, 3),
                                    (1, 3)
Same is count for (1, 3), (1, 4)....(1, 11), (12, 2), ....(12, 11)

For (2, 2), there can be an edge to (1, 1), (1, 2), (1, 3), (2, 1),
                                    (2, 3), (3, 1), (3, 2), (3, 3)
Same is count for remaining vertices.

For all pairs (i, j) there can total 8 vertices connected to them if
i and j are not in {1, 12}

There are total 100 vertices without a 1 or 12.  So total 800 edges.  

For vertices with 1, total edges = (Edges where 1 is first part) +
                    (Edges where 1 is second part and not first part)   

                                =  (3 + 5*10 + 3) + (5*10) edges

Same is count for vertices with 12

Total number of edges:
= 800 + [(3 + 5*10 + 3) + 5*10]  + [(3 + 5*10 + 3) + 5*10]
= 800 + 106 + 106
= 1012

Since graph is undirected, two edges from v1 to v2 and v2 to v1
should be counted as one.

So total number of undirected edges = 1012/2 = 506. 

answered by Loyal (8.7k points)
0 votes
Satisfying conditions for |a -c 1| ≤1

 1.  condition type1 :a=c

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

 total number of pairs (a,c) satisfying condition1 : 12
 total number of pairs (a,c) satisfying condition2 : 11

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
http://yougeeks.blogspot.com/2015/01/consider-undirected-graph-g-where-self.html
answered by Active (3.5k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,252 questions
49,744 answers
164,047 comments
65,843 users