Graph Theory

Graph is

Graph G = (V, E), where:

• V - set of vertices

• E - set of directed edges

Simple directed graph

graph without self-loops and parallel directed edges

Simple undirected graph

A graph G = (V, B) where B is a subset of V² is called simple undirected graph.

Order of graph

The order of graph G = (V, B) is the number |V| = n.

Empty graph

The graph G = (V, 0) is called empty graph and is denoted as O_n

Null graph

The graph G = (0, 0) is null graph.

Trivial graph

The graph G = ({v}, 0) is trivial graph.

Complete graph

A graph with all n * (n - 1) / 2 edges, where n is order of graph, is Complete graph and denoted as K_n

Neighborhood of vertix

For a graph G = (V, B) the neighborhood of vertex v in V is the set of all adjacent vertices:

Degree of vertex

The degree of vertex v is the number p(v) = |Г(v)|

Isolated vertex

A vertex v is called isolated if p(v) = 0.

Pendant vertex

The vertex v is called pendant if p(v) = 1.

Regular graph

A graph is called regular if all its vertices have the same degree

Adjacent vertices

Two vertices u and v in a graph G = (V, B) are called adjacent if there exists an edge {u, v} in B connecting them

Adjacent edge

Two edges in graph G = (V, B) are called adjacent if they share a common vertix.

Incident vertex and edge

A vertex v and an edge e are called incident if v is one of the endpoints of e.

Adjacency matrix

The adjacency matrix of graph G = (V, E) with n = |V| is an n*n matrix where:

Incident matrix

The incident matrix of graph G = (V, E) with n = |V| and m = |E| is an n*m matrix where:

Union of two graphs

Intersection of two graphs

The complement of a graph

The difference of two graphs

The cyclic sum of two graphs

Subgraph

Walk

A walk on the graph is a sequence of vertices and edges in a graph G = (V, E), where each edge connects the preceding and following vertices.

A chain

A chain (or trail) is a walk on a graph where no edges are repeated.

Open walk

Walk is open, if first and last vertices are different.

Closed walk

If walk start and ends with the same vertex, it called a close walk

Path

Path is a open walk in the graph where no edges and no vertices are repeated.

Cycle

A cycle is a closed walk in the graph where no edges are repeating and where only the initial and the terminal vertices are the same

Connected graph

A graph is called connected if any two vertices can be connected by a path.

Connected component

Connected component is the maximal connected subgraph of G = (V, B).

Length of path

Length of a path is defined as a number of edges in the path.

Vertex deletion operation

Edge deletion operation

Cut vertex

A vertex v in V of graph G = (V, E) is called a cut vector (articulation point) if the graph G - v has more connected components than G

Non-separable graph

A graph without cut vertices is called non-separable graph

Separable graph

Graph is called separable if it has a cut vertex

Block

A block of a graph G is a maximal connected non-separable graph of G.

Bridge

An edge of a graph is called bridge (cut edge) if removing it increases the number of connected components of the graph.

Separating set

A subset S sub B of the edge set of a connected graph G = (V, B) is called a separating set if the graph ((V, B \ S) is disconnected.

A cut

A cut (or minimal separating set) is a separating set from which no edge can be removed without making it connected again. Thus: K sub B a cut if:

• K is separating set

• For any P sub K with P ≠ K: P is not separating set.