|
|
| A labeled graph on 6 vertices and 7 edges |
Informally speaking, a
graph is a set of objects called
points,
nodes, or
vertices connected by links called
lines or
edges. In a proper graph, which is by default
undirected, a line from point
A to point
B is considered to be the same thing as a line from point
B to point
A. In a
digraph, short for
directed graph, the two directions are counted as being distinct
arcs or
directed edges. Typically, a graph is depicted in diagrammatic form as a set of dots (for the points, vertices, or nodes), joined by curves (for the lines or edges). Graphs have applications in both
mathematics and
computer science, and form the basic object of study in
graph theory.
Applications of graph theory are generally concerned with labeled graphs and various specializations of these. Many problems of practical interest can be represented by graphs. The link structure of a website could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page A to page B exists if and only if A contains a link to B. A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example if a graph represents a road network, the weights could represent the length of each road. A digraph with weighted edges in the context of graph theory is called a network. Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks).
