Ejer_grafo01

(%i1)

load ( "graphs") $

(%i3)

g : create_graph( makelist([ i, i], i, 1, 8), [[ 1, 2], [ 2, 3],[ 2, 5],[ 3, 4],[ 3, 7],[ 4, 3],[ 4, 8],[ 5, 1],[ 6, 7],[ 7, 6],[ 8, 4]],
directed = true) $
draw_graph( g, show_vertices = makelist( i, i, 1, 8), show_label =true) $

\begin{matrix} (%t3) \end{matrix}

El grafo subyacente simple del diagrafo anterior será:

(%i5)

g2 : create_graph( makelist([ i, i], i, 1, 8), [[ 1, 2], [ 2, 3],[ 2, 5],[ 3, 4],[ 3, 7],[ 4, 8],[ 5, 1],[ 6, 7]]) $
draw_graph( g2, show_vertices = makelist( i, i, 1, 8), show_label =true) ;

\begin{matrix} (%t5) \end{matrix}

\begin{matrix} (%o5) & done \end{matrix}

Contruimos su matriz de adyacencia del digrafo original:

(%i6)

m : adjacency_matrix( g) ;

\begin{matrix} (m) & (\begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{matrix}) \end{matrix}

Veamos cuántos caminos de logitud 3 hay

(%i8)

m3 : m ^ ^ 3 ;
sum( sum( m3[ i, j], i, 1, 8), j, 1, 8) ;

\begin{matrix} (m3) & (\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 & 1 & 0 & 0 & 0 \\ 1 & 0 & 2 & 0 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 2 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 2 & 0 & 0 & 0 & 0 \end{matrix}) \end{matrix}

\begin{matrix} (%o8) & 23 \end{matrix}

Created with wxMaxima.