graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a mixed graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

consisting of a set of vertices , a set of (undirected) edges , and a set of

directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...

edges (or arcs) .

Definitions and notation

Consider adjacent vertices

u,v \in V

. A directed edge, called an arc, is an edge with an orientation and can be denoted as

\overrightarrow

(u,v)

(note that

u

is the tail and

v

is the head of the arc). Also, an undirected edge, or edge, is an edge with no orientation and can be denoted as

uv

,v /math>. For the purpose of our application example we will not be considering loops or multiple edges of mixed graphs.

A

walk Walking (also known as ambulation) is one of the main gaits of terrestrial locomotion among legged animals. Walking is typically slower than running and other gaits. Walking is defined by an 'inverted pendulum' gait in which the body vaults ov ...

in a mixed graph is a sequence

v_0,c_1,v_1,c_2,v_2,\dots,c_k,v_k

of vertices and edges/arcs such that for all indices

i

, either

c_i=v_v_

is an edge of the graph or

c_i=\overrightarrow

is an arc of the graph. This walk is a

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire ...

if it does not repeat any edges, arcs, or vertices, except possibly the first and last vertices. A path is closed if its first and last vertices are the same, and a closed path is a cycle