# Graph Theory - How can I calculate the number of vertices and edges, if given this example

An algorithm book Algorithm Design Manual has given an description:

Consider a graph that represents the street map of Manhattan in New York City. Every junction of two streets will be a vertex of the graph. Neighboring junctions are connected by edges. How big is this graph? Manhattan is basically a grid of 15 avenues each crossing roughly 200 streets. This gives us about 3,000 vertices and 6,000 edges, since each vertex neighbors four other vertices and each edge is shared between two vertices.

If it says "The graph is a grid of 15 avenues each crossing roughly 200 streets", how can I calculate the number of vertices and edges? Although the description above has given the answers, but I just can't understand.

Can anyone explain the calculation more easily?

Thanks

-

Each street crossing is a vertex of the graph. An avenue crosses about $200$ streets, and each of these crossings is a vertex, so each avenue contains about $200$ vertices. There are $15$ avenues, each of which contains about $200$ vertices, for a total of $15\cdot 200=3000$ vertices.

To make the description easier, imagine that the avenues all run north-south and the other streets east-west. Then each intersection of an avenue and a street has another intersection due north along the avenue. It also has one due south along the avenue, one due east along the cross street, and one due west along the cross street. That’s a total of four neighboring vertices. There must be an edge from the given vertex to each of those four, so we count $4\cdot 3000=12,000$ edges. But that’s counting each edge twice, once at each end, so there are really only half that many edges, or $6000$.

Now you might object that the vertex (i.e., intersection) in the northwest corner, say, has only two neighboring vertices, one to the east and one to the south, and similarly for the other three corners. You might also worry about the non-corner vertices along the edges, since they seem to have only three neighboring vertices each. But remember, the original figure of $200$ cross streets was only an approximation in the first place, so we might as well ignore these relatively minor edge effects: they probably don’t affect the result much more than the approximation in the $200$ figure already does.

-
Ha, you made the same avenue = north-south and street = east-west connection I made. I wonder if most people would... –  El'endia Starman Mar 16 '12 at 16:48
@Brian M. Scott, what means "an avenue crosses streets"? How can an avenue(a large area) cross a number of streets? I'd say "cover" at most. –  Jackson Tale Mar 17 '12 at 8:15
@Jackson: In U.S. English avenue is simply one of many terms used for streets. A street whose name is Marietta Avenue, say, might well be a rather short residential street with a curve in it. Or it might be a long, straight street that carries a lot of traffic. When it’s used as a general term, not part of a street name, I expect something called an avenue to be a fairly important street, as is the case in this problem, but it’s still just a street. –  Brian M. Scott Mar 17 '12 at 15:47
@BrianM.Scott, ah, ok. Avenue in US means that. I thought avenue means a kind of area. lol. Forgive me for my poor english. –  Jackson Tale Mar 19 '12 at 11:33

This is so simple, I mean 15 avenues crossing 200 streets, which means there are 15 * 200 = 3000 crossings, i.e. 3000 nodes.

each nodes have upper, lower, left and right neighbors, so for each node, there are 4 edges connecting to the neighbors. However, each edge has been counted twice since node 1 has an edge connected with node 2, and the node 2 has the same edge connected to node 1

So that is totally 3000*4/2 = 6000 edges

-

If you have 15 vertical and 200 horizontal lines, parallel for each direction, they'll have 15*200 crossings. An edge is a line segment between each crossing. Each crossing connects 4 line segments (ignoring the outer bounds) and each line segment connects two crossings, so it's double the number of crossings.

-

Every junction between an avenue and a street is a vertex. As there are $15$ avenues and (about) $200$ streets, there are (about) $15*200=3000$ vertices. Furthermore, every vertex has an edge along an avenue and an edge along a street that connect it to two other vertices. Hence, there are (about) $2*3000 = 6000$ edges1. Does that answer your question?

1 With regards to edges, a visual way to imagine it would be to imagine that the avenues are going north-south and the streets are going east-west. Start with the junction/vertex in the northwesternmost corner. It is adjacent to two other vertices: one south along the avenue and one east along the street. Similarly, every vertex has a vertex to the south and a vertex to the east (as well as north and west for most of them, but those are irrelevant for this). Hence, there are two edges for every vertex.

-

If you have exactly 15 columns (avenues) of vertices in 200 rows (streets) then basic properties of multiplication give $15 \times 200 = 3000$ vertices.

As for edges, there are 14 edges in each row and 199 edges in each column so there are $14 \times 200 + 199 \times 15 = 5785$ edges. $6000$ was only an approximation.

$4$ of the vertices have two edges; $2\times 198 +2 \times 13 = 422$ vertices have three edges; the other $357$4 vertices have four edges. Each edge has two vertices. So $$4 \times 2 + 422 \times 3 + 5574 \times 4 = 11570 = 2 \times 5785.$$

-