Graph theory

In mathematics and computer science, graph theory studies the properties of graphs. Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs) which can be directed (assigned a direction). Typically, a graph is designed as a set of dots (the vertices) connected by lines (the edges).

Related Topics:
Mathematics - Computer science - Graphs - Vertices - Edge

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of Wikipedia could be represented by a directed graph: the vertices are the articles in Wikipedia and there's a directed edge from article A to article B if and only if A contains a link to B. The development of algorithms to handle graphs is therefore of major interest in computer science.

Related Topics:
Wikipedia - Algorithm - Computer science

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A graph structure can be extended by assigning a weight to each edge. Graphs with weights can be used to represent many different concepts; for example if the graph represents a road network, the weights could represent the length of each road1. Another way to extend basic graphs is by making the edges to the graph directional (A links to B, but B does not necessarily link to A, as in webpages), technically called a directed graph or digraph. A digraph with weighted edges is called a network.

Related Topics:
1 - Directed graph - Network

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks or to discover the shape of the internet -- see Applications below). However, it should be noted that within network analysis, the definition of the term "network" may differ, and may often refer to a simple graph.

Related Topics:
Network analysis - Applications

~ ~ ~ ~ ~ ~ ~ ~ ~ ~