Re: graphs
In two graphs the vertices represent cities and the edges represent roads connecting them.In which graphs could a person located in city A choose any other city and then find a sequence of roads to get from A to that other city. I do need the answer to this problem but i also need to be able to discuss this problem too.Thanks.
I could be wrong but your description appears as though you are describing a chessboard-like grid where the corners of the grid represent cities and all the vertical and horizontal lines of the grid represent streets, or paths, from one city to another. This falls within the domain of Taxicab Geometry. The following will give you an idea of how it works.
Taxicab geometry is remarkably similar to Euclidean geometry. The coordinate plane points, lines and angles are all the same. The singular difference between the two geometries is how distance is measured. Imagine two points located at coordinates (5,6) and (2,2) on the coordinate plane. The shortest (Euclidian) distance, dE, between the two points is sqrt[(5 - 2)^2 + (6 - 2)^2] sqrt[3^2 + 4^2] = sqrt(25) = 5. In taxicab geometry, the taxicab distance, dT, between the two points is [5 - 2) + (6 - 2) = 7, regardless of how you traverse the field of straight lines between the two points. Thus, in taxicab geometry, the shortest distance between two points is not a straight line. It is most conveniently viewed as the distance that a taxicab would travel through the grid of city streets running north-south and east-west, through a system of square blocks. As a result of measuring distances in this way, various geometric shapes so familiar to us take on different shapes. For example, the locus of all points an equal dT from a given point is called a taxicab circle, the shape of which is actually a square.
A typical recreational mathematics problem involving taxicab geometry is as follows:
A large square consisting of 16 smaller squares, the upper left corner being identified as A.
The lower right corner of the upper left square is identified as B, the lower right corner of the upper left 4 squares is identified as C, the lower right corner of the upper left 9 squares is identified as D and the lower right corner of the entire 16 squares is identified as E.
Consider the intersections of the squares as points or junctions.
How many different ways are there to move from point A to point E traversing the sides of the 16 smaller squares?
This typical problem in taxicab geometry, is relatively easy to understand and enjoy. All it takes is a piece of graph paper and a pencil. Repeating, it can best be viewed in the context of a taxicab maneuvering through a city where the streets are totally straight and cross one another in the form of multiple squares. The sides of the squares represent the streets. The intersections of the squares form a lattice of points representing the numerous junctions through which a taxicab traveling from point A to point E would have to travel.
In Euclidian geometry, the shortest distance between points A and E in the described field would be the straight line joining A to E. In taxicab geometry, one must follow the lines as defined by the sides of the squares, always moving in a direction toward the target point, resulting in many paths, all equally minimum, and, in fact, all the same.
There are a few of ways of determining the number of possible paths. Lets consider them starting with the given scenario.
A...__ __ __ __
...I__I__I__I__I
...I__I__I__I__I
...I__I__I__I__I
...I__I__I__I__I
................E
The one groundrule is that all movements must be made in the general direction of getting to E from A. By this, I mean, every move must be either to the right or down from A toward E. No movements upward or to the left are allowed. Obviously, this groundrule results in the minimum distance being traveled, regardless of which path is taken.
There is a simple mathematical expression that gives you the total number of paths but I will defer that until later.
.
Lets explore smaller squares first. How many possible paths from A to B are there for a unit square? There are four points of intersection involved.
A..__ C
..I__I
D ....B
Obviously, you can move horizontally one leg from A to C and down one leg to B or vertically one leg to D and over one leg to B making 2 distinct paths.
What about a 2x2 square? There are 9 points of intersection involved.
A...__ __
...I__I__I
...I__I__I
.............C
Clearly, there are 6 paths from A to B, using h for horizontal and d for down:
1--2h + 2d
2--1h + 1d + 1h + 1d
3--1h + 2d + 1h
These three paths are mirrored about the diagonal AB giving
4--2d + 2h
5--1d + 1h + 1d + 1h
6--2d + 2h
The basic paths may be described as (1 external + 2 internal) plus their mirrors about the diagonal for a total of 6.
What about a 3x3 square? There are 16 points of intersection involved.
A..__ __ __
..I__I__I__I
..I__I__I__I
..I__I__I__I
............D
1--3h + 3d
2--2h + 1d + 1h + 2d
3--2h + 2d + 1h + 1d
4--2h + 3d + 1h
5--1h + 1d + 2h + 2d
6--1h + 2d + 2h + 1d
7--1h + 3d + 2h
8--1h + 1d + 1h + 1d + 1h + 1d
9--1h + 1d + 1h + 2d + 1h
9--1h + 2d + 1h + 1d + 1h
I'll let you work out the rest yourself. You should end up with (1 external + 9 internal) plus their mirrors for a
total of 20.
Okay, we are at the brink of your problem:
A...__ __ __ __
...I__I__I__I__I
...I__I__I__I__I
...I__I__I__I__I
...I__I__I__I__I
................E
Again, knowing what you know now, work out the number of paths. You should get (1 external + 34 internal) plus their mirrors for a total of 70.
Work out a 5x5 square if you wish, just for another data point.
We have now seen that the total number of paths is double the number of paths derived by starting out from A horizontally, or one of the two possible directions. Starting horizontally from A, there is only 1 external path to B. By examining the data you have collected so far, you should have a table looking something like this:
No. of squares No. of Intersections External paths Internal paths Total
........1.............4.........2..........0........2
........2.............9.........2..........4........6
........3............16.........2.........18.......20
........4............25.........2.........68.......70
........5............36.........2........250......252
Examination of these results might just look familiar to you. You have undoubtedly seen Pascal's triangle at one time or another. The triangle looks like this:
Row
1......................................1
2..................................1.......1
3.............................1.......2.......1
4........................1.......3.......3........1
5..../..............1........4.......6.......4.......1
6...............1........5......10.....10.......5......1
7...........1.......6......15......20.....15......6.......1
8.......1.......7......21......35......35.....21......7.......1
9...1.......8.....28......56......70......56....28.......8.......1
10............................126....126
11...............................252
Do any numbers in the triangle look familiar? Of course, right down the middle are our results derived above. The significance of the triangle in taxicab geometry is that you can draw a square or rectangle of whatever size you wish on the diagram and the lower corner of the figure indicates the number of possible paths from one corner to the diagonally opposite corner. For example, draw a square of 4 unit squares from the apex 1 down to the 2nd 1's on either side of the triangle and down through the 3's to the 6. The 6 indicates the number of taxicab geometry paths. Do the same thing with a 3x3 square, and the lowest corner of the square will fall on the 20 in the 7th row. Draw a 4x4 square on the triangle and the lowest corner of the square will fall on the 70 in the 9th row. Draw a 2x3 rectangle on the triangle and the lowest corner will fall on the 10 on the 6th row, either way you draw the rectangle. Clever? A 3x5 rectangle results in 56 paths.
It is not immediately obvious from scanning the data but the general expression that can be derived for the total number of paths from one corner of a rectangular figure, to the diagonally opposite corner, always moving in one of only two possible directions toward the target point, is given by
P = (m + n)!/m!n!
where P is the total number of paths, m is the number of squares on the long side of the rectangle, and n is the number of squares on the shorter side. Of course, ! means factorial. Another way of expressing it it terms of the number of intersections that the paths must connect is
P = [(p - 1) + (q - 1)]!/(p - 1)!(q - 1)!
where p and q are the number of intersections involved on the long and short sides respectively. Thus, for the squares we are addressing:
No. of squares No. of intersections (n + n)! n! P
1x1..........2x2....................2.......1..........2
2x2..........3x3 ..................24.......2..........6
3x3..........4x4..................720.......6.........20
4x4..........5x5.................40320.....24.........70
For a rectangle with 11 squares by 4 squares, or 12 by 5 intersections,
P = (11 + 4)!/11!(4!) = 1365 paths.
All of this falls under the fascinating subject of Taxicab Geometry, believed to be first discussed by Hermann Minkowski, a Russian mathematician. One excellaent source on the subject is Taxicab Geometry by Eugene F. Krause, Dover Publications, Inc., 1986, available from Dover Publications, Inc., Mineola, NY, Tel. No. 516-294-7000, $4.95 + tax + shipping & handling.
There is a brief chapter on the subject in The Last Recreations by Martin Gardner, Springer-Verlag, NY, 1997.
Good luck
