Graph Theory - basic definitions

From Algorithmist
Jump to: navigation, search

Graph types[edit]

A finite simple graph is an ordered pair G=[V,E], where V is a finite set and each element of E is a 2-element subset of V.

Unless otherwise stated throughout this article graph refers to a finite simple graph. There are several variations, for instance we may allow V to be infinite. We define other graph types:

  • directed graph (also called digraph): edges are ordered pairs of vertices as opposed to a two element set.
  • multigraph: a pair of vertices may be connected by more than one edge, formally E is not a set, but an unorder vector/sequence of edges
  • weighted graph: each edge is associated with a numerical value usually associated with some real life property (e.g., length).

When describing the complexity of graph algorithms, the number of vertices is denoted N, the number of edges is denoted M.

Vertices and edges[edit]

The complement of a graph is a graph with the same set of vertices, and a "complement" of the edge set, in the sense that if in the original graph a pair of vertices wasn't connected by an edge, in the complement they are connected, and vice versa.

The degree of a vertex is the number of edges incident with it. For directed graphs we may define the in-degree (number of edges leading into the vertex) and the out-degree (number of edges leaving a vertex).

If two vertices are connected by an edge, they are called neighbors. For simple graphs, the degree of a vertex is the number of its neighbors.

The smallest and largest degree of a vertex in a given graph are usually denoted as \delta and \Delta , respectively.

Paths, tours, walks[edit]

A sequence v_{0},e_{1},v_{1},e_{2},\dots ,v_{{n-1}},e_{n},v_{n} where v_{i} are vertices, e_{i} are edges, and for all i the edge e_{i} connects the vertices v_{{i-1}} and v_{i} is called a walk. Note that if we imagine the graph as cities and roads, the sequence specifies a unique way of travelling along the roads.

Note that for simple graphs a walk is uniquely determined by its sequence of vertices.

A walk with no repeated edges is called a tour. A walk with no repeated vertices is called a path.

A walk or a tour where v_{0}=v_{n} is called closed, other walks and tours are called open. Specifically, a walk with no repeated vertices except for v_{0}=v_{n} is called a cycle.

Connectivity[edit]

If there is a path from the vertex u to the vertex v, we say that v is reachable from u. A graph is called connected if each vertex is reachable from each other vertex. (For directed graphs, we use the term strongly connected.)

Each undirected graph can be uniquely split into non-empty subgraphs such that vertices u and v are in the same subgraph if and only if u is reachable from v. These subgraphs are called (connected) components of the graph. Note that there are no edges leading between the components.

Similarly, each directed graph can be uniquely split into non-empty subgraphs such that vertices u and v are in the same subgraph if and only if both u is reachable from v and vice versa. These subgraphs are called strongly connected components.

In undirected graphs, an edge is called a bridge if by removing it from the graph we increase the number of components. Similarly, a vertex such that its removal increases the number of components is called a cutvertex (or an articulation point).

Trees, forests, bipartite graphs[edit]

A graph that doesn't contain a cycle is called acyclic, or a forest. A connected acyclic graph is called a tree. (Note that the connected components of a forest are trees.)

It can be shown that a graph is a tree iff it is connected and M=N-1.

If the vertices of a graph can be divided into two sets A, B such that each edge connects a vertex from A and a vertex from B, the graph is called bipartite.

It can be shown that a graph is bipartite if and only if it doesn't contain a cycle with an odd number of edges.