Main Index Discrete mathematics Graph theory
 Subject Index
comment on the page

Basic notions

A graph is an abstract representation of a set of objects representing certain interconnections between objects of sets. Depicted in a diagrammatic form, the objects are usually represented as points, called vertices or nodes which are graphically connected by links represented by line segment or curves, called edges, or simply lines. The links represent studied interconnection between objects of sets.

Combinatorial and topological properties of graphs are the basic subject studied by graph theory.

The simplest formal definition says that a graph is an ordered pair , where is the set of vertices, and is the set of edges, usually represented by (unordered) two-elements subsets of relation of incidence that associates with each edge two vertices.

The set of edges defines a relation of incidence that associates with each edge two vertices.The vertices incident with an edge are called the ends, endpoints, or end vertices of the edge. There is possible that there exist vertices that do not belong to an edge. An edge which endpoints coincide is called a loop.

A generalization of the above definition of graph allows the set to be  a multiset of unordered pairs of (not necessarily distinct) vertices. The corresponding graph is called a multigraph or pseudograph.

A graph is called simple if it is undirected and no loops and no more than one edge between any two different vertices.

The sets and are usually finite, in which case the graph is called finite, otherwise we say that the graph is infinite. The number of vertices is called the order of the graph , the number of edges is called the size of the graph .  The degree of a vertex is the number of edges that are incident with the vertex . If the vertex is the endpoint of a loop then  it is counted twice.

The edges E of a (undirected) graph induce a symmetric binary relation on the set of vertices , called the adjacency relation of G. More precisely, if we take an edge , , then the vertices and are called adjacent to one another, and it is denoted by .

A path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex, or simply the end or terminal vertices of the path. Non-terminal  vertices in the path are called internal. A cycle is a path such that the start vertex and end vertex coincide.

A path with no repeated vertices is called a simple, and cycle with no repeated vertices aside from the start/end vertex is also called simple.

A simple cycle that includes every vertex of the graph is called a Hamiltonian cycle.

The number of edges that the path uses, counting multiple edges multiple times is called the length of the path. The length is zero if the path consists from a single vertex.

In the above definition of a graph the edges are defined as unordered pairs, therefore the defined graphs are called unoriented or undirected.

In a hypergraph, an edge can join more than two vertices.

A directed graph or digraph is an ordered pair where

• a set of  vertices or nodes, and
• a set of ordered pairs of vertices, called arcs, directed edges (since in this case the edges are represented by arrow, the directed edges are also called arrows).

If an arc is considered to be directed from to , the is called the head of , and is called the tail of the arc . In another terminology ; y is said to be a direct successor of x, and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x and reachable from x, and x is said to be a predecessor of y. The arc (y,x) is called the arc (x,y) inverted.

A weighted graph associates a value (called the weight) with every edge in the graph. The weight of a path in a weighted graph is the sum of the weights of the traversed edges.

As elements of a set, the vertices of a graph are distinguishable. In this case the graph is called vertex-labeled. In many situations (problems) however, it is more convenient to treat vertices as indistinguishable. Then the graph may be called unlabeled.

The same notions also apply to edges, so that graphs which have labeled edges are called edge-labeled graphs, etc.

Cite this web-page as: