Understanding Directed Graphs and Matrices
Translated by
ScribdTranslationsUnderstanding Directed Graphs and Matrices
Translated by
ScribdTranslationsDigraphs
It is called a directed graph or digraph when each edge
there is an order at its ends, the order is indicated in the
graph by an arrow. The origin is called the first
vertex of the edge and end to the second.
Eurelianos
* An Eulerian digraph is one in which all can be traversed.
suspend the edges (arcs) consecutively and without repeating them.
EXAMPLES
Hamiltonians
* A cycle in a digraph D is called a Hamilton cycle or Hamiltonian cycle if
contains all the vertices of D.
* If the digraph D is connected, it is said to be Hamiltonian if it contains a cycle of
Hamilton.
* We will say that a path is Hamiltonian if it contains all the vertices of the directed graph.
Incidence matrix
Let G be a graph with vertices V = [1,2, …, n] and set
of arches A= [a1a2, ...amThe incidence matrix of D
it is the matrix M = (mi.k(i = 1, …, n; k= 1,…, m), defined
by
1 if i is the initial end of ak
mi,k-1 if i is the final endpoint of ak
0 in another case
ADJACENT MATRICES
Square matrix of order NxN associated
to a graph of order N, where its rows and
columns are identified with the vertices
of the graph and in the cells, it indicates the
number of edges to
the nodes assigned to the rows and columns
in question.
BUILDING MATRICES
1.- A zero matrix is created, whose columns and rows represent
the nodes of the graph.
2.- For each edge that connects two nodes, 1 is added to the value that
there is currently in the corresponding location of the matrix.
3.-If such an edge is a loop and the graph is undirected, then it
add 2 instead of 1.
4.-Finally, a matrix is obtained that represents the number
of edges (relationships) between each pair of nodes (elements).
There is a unique adjacency matrix for each graph and
vice versa.
Example
Matrix of
Undirected graph
adjacency
Matrix of
Directed graph adjacency
PROPERTIES
It is square and symmetrical.
The sum of each row or column is the degree of the vertex
corresponding
For an undirected graph, the adjacency matrix is symmetrical.
Sequential Representation of Graphs
Directed
• Let G(V,E) be a simple directed graph without parallel edges with ""
vertices that have been ordered and named , ,…., . Then the
The adjacency matrix A = [] of G is the matrix defined as
follow:
• • = 1 if an edge (, ) exists
• = 0 in other cases
• Observation: The adjacency matrix A = [] can be extended to
directed graphs with parallel edges when doing
• number of edges that start at and end at.
Directed Graph and its Matrix of
Adjacency
A=
Adjacency Matrix A
Directed Graph
• How does it provide the number of paths of length 1 from vertex to vertex?
to demonstrate that it provides the number of paths of length 2 from vertex to vertex.
•• Therefore, let the adjacency matrix of a graph G be. Then, the entry in the
matrix, provides the number of paths of length to (:number of vertices)
For example:
==
The matrix provides the number of paths of length or less from vertex to vertex.
= = = =
Now if we add the matrices we obtained earlier, we will generate a matrix.
where the sum of all possible paths to reach a certain point will be represented
vertex of the graph to another.
=
• And if in this matrix we replace all the numbers different from
zeros by ones, we will obtain the following matrix.
This matrix is known as the path matrix and indicates whether it is possible to reach
a certain node from another, a unit path matrix originates from a connected graph.
Example in everyday life