User:Extra999/Selected article/3

A directed graph

Graph theory is a field of mathematics about graphs. A graph is an abstract representation of: A number of points are connected by lines. 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. Graph theory is an important part of mathematics and computer science. To many such problems, exact solutions do exist. Many times however, they are very hard to calculate. Therefore, very often, approximations are used. There are two kinds of such approximations, Monte-Carlo algorithms and Las-Vegas algorithms.

Graphs are normally represented by two different sets, typically set a graph G would be represented as the collection of the sets V and E. The set V is a discrete set containing all vertices of the graph. The set E is a binary set, whose pairwise elements are elements of set V. Each pair in set E represents an edge connecting two vertices. If any two nodes have an edge between them, then the graph is called the complete graph.

Read more...