What is Graph theory?
[[File:6n-graf.svg|thumb|300px|right|An undirected graph.]] '''Graph theory''' is a field of [[math]]ematics about graphs. A [[Graph (mathematics)|graph]] is an abstract representation of: a number of [[point (geometry)|point]]s that are connected by [[line]]s. Each point is usually called a ''vertex'' (more than one are called ''vertices''), and the lines are called ''edges''. Graphs are a tool for modelling relationships. They are used to find answers to a number of problems. Some of these questions are: * What is the best way for a [[mailman]] to get to all of the [[house]]s in the area in the least amount of [[time]]? The points could represent [[street]] corners and lines could represent the houses along the street. (see [[Chinese postman problem]]) * A salesman has to visit different customers, but wants to keep the distance traveled as small as possible. The problem is to find a way so they can do it. This problem is known as [[Travelling Salesman Problem]] (and often abbreviated ''TSP''). It is among the hardest problems to solve. If a commonly believed [[conjecture]] is true (described as '''P''' ≠ '''NP'''), then an exact solution requires one to try all possible routes to find which is shortest. * How many colors would be needed to color a map, if countries sharing a border are colored differently? The points could represent the different areas and the lines could represent that two areas are neighboring. (look at the [[Four color theorem]]) * Can a sketch be drawn in one closed line? The lines of the drawing are the lines of the graph and when two or more lines collide, there is a point in the graph. The task is now to find a way through the graph using each line one time. (look at [[Seven Bridges of Königsberg]]) == Different kinds of graphs == [[File:Directed.svg|125px|thumb|A directed graph.]] * Graph theory has many aspects. Graphs can be directed or undirected. An example of a directed graph would be the system of roads in a city. Some streets in the city are one way streets. This means, that