-2
$\begingroup$

just confuse with this problem. What is n × n grid graph and how many edges it has?

$\endgroup$
  • 3
    $\begingroup$ What have you tried? What research have you done? Let me help with Google toss - grid graph. Besides easily found definition it is pure basic math, so this is not the best possible question here. $\endgroup$ – Evil Aug 24 '16 at 15:01
  • $\begingroup$ @Evil All other faults of the question aside, I think graph theory is firmly ontopic here. $\endgroup$ – Raphael Aug 26 '16 at 0:24
  • $\begingroup$ You should only ask one question per post. Chances are that once you know what a grid graph is you can solve the second question for yourself. $\endgroup$ – Raphael Aug 26 '16 at 0:25
  • $\begingroup$ @Raphael sure, the graph theory certainly is, but counting edges on grid - is it really? $\endgroup$ – Evil Aug 26 '16 at 0:29
  • $\begingroup$ @Evil It is a combinatorics question but would be part of analysing many a graph algorithm's performance on grid graphs. $\endgroup$ – Raphael Aug 26 '16 at 8:08
0
$\begingroup$

a quick google search shows a grid graph to be http://mathworld.wolfram.com/GridGraph.html

so given that a 5 x 5 grid graph would have 25 nodes we can calculate the number of edges using this formula

A grid graph G_(m,n) has mn nodes and (m-1)n+(n-1)m=2mn-m-n edges

(5-1)5+(5-1)5=2(5)(5)-5-5 = 50 - 10 = 40

the formula itself generalized to nxn is the answer for the second portion

(n-1)n+(n-1)n=2nn-n-n = 2n^2-2n

$\endgroup$
  • $\begingroup$ thanks this really helpful.but if this equation is solve further then it give zero answer is this correct or not? $\endgroup$ – alma Aug 24 '16 at 15:10
  • $\begingroup$ order of operations, you have to resolve the exponent before the subtraction. $\endgroup$ – James Aug 24 '16 at 15:12
  • $\begingroup$ additionally, sanity check your assumptions, there is no way that the general formula can equal zero if n is non 0 -> let nxn = 0, let n = 5, 5x5 grid = 40, 0 != 40 $\endgroup$ – James Aug 24 '16 at 15:21
  • $\begingroup$ ok thanks alot . My problem is solved ! $\endgroup$ – alma Aug 24 '16 at 15:24
  • 1
    $\begingroup$ Where does this formula come from? Why is it correct? $\endgroup$ – Raphael Aug 26 '16 at 0:25
6
$\begingroup$

The $a \times b$ grid graph has the vertex set $[a] \times [b]$, and edges of two types: horizontal edges $(i,j),(i+1,j)$ (of which there are $(a-1)b$) and vertical edges $(i,j),(i,j+1)$ (of which there are $a(b-1)$), for a total of $ab$ vertices and $(a-1)b+a(b-1)=2ab-a-b$ edges.

$\endgroup$
1
$\begingroup$

Start by counting the left edges and top edges, then add in the missing right and bottom edges.

For a $m \times n$ grid graph, there are $m \times n-1$ left edges (a left edge for each column at each row). Similarly, there are $m-1 \times n$ top edges. At this point, we are still missing the bottom edges for the last row, and the right edges for the last column. There are $n-1$ remaining right edges, and $m-1$ remaining bottom edges. Hence, the number of edges of an $m \times n$ grid graph is $|E_{m \times n \text{ grid}}| = m(n-1) + (m-1)n = mn-m+mn-n = 2mn-m-n$.

$\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.