/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 04/11/09
*/
In the branch of mathematics called Graph Theory, a graph bears no relation to the graphs that chart data, such as the progress of the stock market or the growing population of the planet. Graph paper is not particularly useful for drawing the graphs of Graph Theory.
In Graph Theory, a graph is a collection of dots that may or may not be connected to each other by lines. It doesn’t matter how big the dots are, how long the lines are, or whether the lines are straight, curved, or squiggly. The “dots” don’t even have to be round!
All that matters is which dots are connected by which lines.
Two dots can only be connected by one line. If two dots are connected by a line, it’s not “legal” to draw another line connecting them, even if that line stretches far away from the first one.
If you look at a graph and your eyes want to zip all around it like a car on a race course, or if you notice shapes and patterns inside other shapes and patterns, then you are looking at the graph the way a graph theorist does.
Here are some of the special words graph theorists use to describe what they see when they are looking at graphs:
1. Edges & vertices of a graph :
A graph is made up of dots connected by lines.
A “dot” is called a vertex .
When there is more than one vertex, they are called vertices .
A “line” is called an edge. (The plural is simply edges)
2. The degree of a vertex in a graph :
The degree of a vertex in a graph is the number of edges that touch it.
The number on each vertex of this graph is the degree of that vertex.
3. Size of a graph :
The size of a graph is the number of vertices that it has.
4. Regular graphs :
A graph is regular if every vertex has the same degree.
5. Paths & cycles in a graph :
A path is a route that you travel along edges and through vertices in a graph. All of the vertices and edges in a path are connected to one another.
A cycle is a path which begins and ends on the same vertex. A cycle is sometimes called a circuit.
The number of edges in a path or a cycle is called the length of the path. Is the length of the path also the number of vertices?
6. A Hamiltonian path in a graph :
A hamiltonian path in a graph is a path that passes through every vertex in the graph exactly once. A hamiltonain path does not necessarily pass through all the edges of the graph, however.
A hamiltonian path which ends in the same place in which it began is called a hamiltonian circuit or a hamiltonain cycle .
7. An Eulerian path in a graph :
An eulerian path in a graph is a path that travels along every edge of the graph exactly once. An eulerian path might pass through individual vertices of the graph more than once.
An eulerian path which begins and ends in the same place is called an eulerian circuit or an eulerian cycle
8. Planar graphs :
A planar graph is a graph that can be drawn so that the edges only touch each other where they meet at vertices.
You can usually re-draw a planar graph so that some of the edges cross. Even so, it is still a planar graph. When it is drawn so that the edges cross, the drawing is called a non-planar representation of a planar graph.
9. Non-planar graphs :
The graph above is nonplanar. No matter how you stretch the edges around, you cannot redraw the graph so that none of the edges cross each other between the vertices .
A non-planar graph should not be confused with a planar graph that just happens to be drawn in such a way that two or more edged cross. The graph below is a planar graph, but it is drawn here in a nonplanar representation.
10. Distance in a graph :
Distance in a graph isn’t measured in inches or kilmoters. This isn’t surprising, because you don’t do any measuring in inches or kilometers when you draw a graph in the first place.
Still, when you look at a graph, you can see how it might be possible to say that some vertices are closer together then others.
The distance between two vertices is a count of the number of edges along which you must travel to get from one of the verticesto the other.
If there is more than one path between two vertices, the number of edges in the shortest path is the distance.
The number of edges in a path is called the length of the path.
11. The diameter of a graph :
The diameter of a graph is the longest distance you can find between two vertices.
When you are measuring distances to determine a graph’s diameter, recall that if 2 vertices have many paths of different distances connecting them, you can only count the shortest one.
An interesting problem in graph theory is to draw graphs in which both the degrees of the vertices and the diameter of the graph are small. Drawing the largest graphs possible that meet these criteria is an open problem .
12. Isomeric graphs :
Two graphs are isomorphic if you can re-draw one of them so that it looks exactly like the other.
To re-draw a graph, it helps to imagine the edges as infinitely stretchable rubber bands. You can move the vertices around and stretch the edges any way you like — as long as they don’t become disconnected.
Sometimes it is very hard to tell whether two graphs are isomorphic or not. In fact, no one knows a simple method for taking two graphs and determining quickly whether or not they are isomorphic.
13. Complete graphs :
In a complete graph, every pair of vertices is connected by an edge . It is impossible to add an edge to a complete graph because every possible edge has been drawn.
Complete graphs always have diameter 1.
14. Neighboring vertices in a graph :
In a graph, the neighbors of a vertex are all the vertices which are connected to that vertex by a single edge.
The distance between two vertices which are neighbors is always 1.
15. Dominating sets in graphs :
In a graph, the neighbors of a vertex are all the vertices which are connected to that vertex by a single edge. A dominating set for a graph is a set of vertices whose neighbors, along with themselves, constitute all the vertices in the graph.
Read Full Post »