Prof.

Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

GRAFOS

La ciudad de Königsberg (hoy Kaliningrado) es atravesada por el río Pregel,

debido a esto y a la existencia de dos islas, la ciudad está dividida en cuatro
zonas conectadas por siete puentes.

Leonhard Euler (1736) se plantea el siguiente problema: partir de cualquier

lugar, caminar por cada puente una sola vez y volver al lugar inicial.
Para ello simplifica y modela la situación, renunciando a las distancias, formas,
etc., reduciendo a puntos unidos por líneas. Los puntos representan la tierra
firme y las líneas los puentes. Quedando representado de la siguiente manera:

Este problema de Euler es considerado el primer resultado sobre teoría de

grafos, así como también uno de los primeros resultados topológicos en
geometría, que no depende de medida alguna.
Gustav Kirchoff en 1847, utilizó la teoría de grafos para trabajar sobre circuitos
eléctricos.

1
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

En el año 1920 comienza el interés por los grafos y en 1936, aparece el primer
texto sobre teoría de grafos.
Los grafos son aplicados en química, computación, economía, lingüística, etc.
Qué tienen en común estos ejemplos? En ellos simbolizamos un problema
concreto mediante un esquema gráfico o grafo formado por puntos y líneas que
los unen y luego se estudian soluciones al problema inicial, mediante el análisis
de las condiciones sobre el esquema gráfico asociado.
Observaciones:
- Problemas distintos pueden tener los mismos esquemas gráficos, por lo
tanto estudiando estos en general, se pueden encontrar soluciones
aplicables a diversos problemas.
- Como el grafo debe ser un esquema simple, se renuncia a muchas
condiciones y características, pero a la vez en un grafo resaltan con
claridad las “relaciones”, ”conexiones” o “enlaces” entre pares de
elementos.
La teoría de grafos debe ser esencialmente abstracta y formal.

GRAFOS NO ORIENTADOS:

Definición: Es una terna G= (V, A,ϕ ); donde los elementos de V se llaman

vértices o nodos de G, los elementos de A se llaman aristas de G y ϕ es una
función de incidencia que asigna a cada arista un par no ordenado de vértices
llamados sus extremos.
ϕ (a 1)
= (v1, v2)

v2

a1
v1

DEFINICIONES

 Arista incidente: Si v1 es un extremo de a1 entonces a1 y v1 son

incidentes.
 Vértices adyacentes: Dos vértices son adyacentes si existe una arista
que los une.
 Aristas adyacentes: Dos aristas son adyacentes si existe un vértice que
las une.
 Grado de un vértice: es el número de aristas que inciden en él.
 Vértice aislado: Si el grado del vértice es cero.
 Vértice pendiente: Si el grado del vértice es uno.
 Lazo: es una arista cuyos extremos coinciden.
 Aristas paralelas: dos aristas son paralelas cuando tienen el mismo
vértice inicial y final.
 Cadena: es una sucesión finita de aristas.
 Longitud de una cadena: es el número de aristas que la componen.
 Cadena sencilla: es cuando no se repiten aristas.
2
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

 Cadena elemental: es cuando no se repiten vértices.

 Ciclo: es una cadena donde el vértice inicial coincide con el vértice final.
 Grafo simple: es un grafo sin lazos ni aristas paralelas.

 Un vértice vj se dice accesible desde un vértice v i si existe una cadena

entre ellos. Todo vértice es accesible desde sí mismo.

GRAFOS ORIENTADOS:

Definición: Es una terna G:(V, A, Φ ), donde los elementos de V se llaman

vértices o nodos, los elementos de A se llaman arcos y Φ es una función
(llamada función de incidencia orientada en G), que asigna a cada arco un par
ordenado de vértices llamados sus extremos.

Φ : A →VxV

DEFINICIONES

 Rizo o bucle: es un arco cuyo vértice final coincide con el vértice inicial.
 Arcos estrictamente paralelos: dos arcos son estrictamente paralelos si
tienen el mismo vértice inicial y el mismo vértice final.
 Arcos adyacentes: dos arcos son adyacentes si tienen un vértice común.
 Vértices adyacentes: dos vértices son adyacentes si existe un arco que
los une.
 Arcos incidentes:
dado un arco a decimos que es incidente a un vértice
Incidencia positiva:
vi hacia el exterior (o positivamente a vi) si Φ(a )=( v i , v j ) y (v i ≠v j )
.
Esto significa que el vértice vi es origen de dicho arco.
Incidencia negativa: dado un arco a decimos que es incidente a un
vértice vj hacia el interior (o negativamente a v j ) si Φ(a )=( v i , v j ) y
(v i ≠v j ) .
Esto significa que el vértice vj es extremo de dicho arco.

+ -

a1 incide positivamente en v1 y negativamente en v2

 Grado Total: es la suma de los grados positivos y negativos del vértice.

3
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

gt (v)= g+(v) + g-(v)

 Grado Neto: es la diferencia entre los grados positivos y negativos del

vértice.
gn(v)= g+(v) – g-(v)

Propiedades de los grados de un vértice:

i) ∑ v ∈V
g+ ( v )=∑ v ∈V g− (v )=|A|
, Siendo | A| el número de arcos del grafo

ii) ∑ v ∈V
gt ( v )=2|A|

iii) ∑ v ∈ V
g n (v )=0

 Camino: es una secuencia de arcos.

 Camino sencillo: es el camino en el que no se repiten arcos.
 Camino elemental: es el camino en el que no se repiten vértices.
 Circuito: es un camino donde el vértice inicial coincide con el vértice final
 Circuito sencillo: es el circuito donde no se repiten arcos.
 Circuito elemental: es el circuito donde no se repiten vértices, con
excepción del primero y el último.
 Longitud de un camino: es la cantidad de arcos que lo componen.

MATRICES ASOCIADAS A UN GRAFO

Matrices de Adyacencia de vértices:

Para grafos No orientados:

mij=1 Si v es adyacente a v

{ ¿ {¿ ¿
i j
mij=0 Si v no es adyacente a v
i j
m ii=1 Si en v hay un lazo
i
mij=n Si hay n aristas

Esta matriz es cuadrada y simétrica.

Ejemplo:

4
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

[ ]
1 1 0 0
1 0 2 0
M=
0 2 0 1
0 0 1 0

- La suma de los elementos distintos de cero de la matriz es igual a 2

veces el número de aristas (2|A|) (los elementos de la diagonal principal
se cuentan dobles).

Teorema: Si M es la matriz de adyacencia de un grafo G, entonces el

elemento mij¿ 0 de la matriz M , λ ∈ N , indica la existencia de por lo
λ

menos, un camino de longitud λ entre vi y vj .

Corolario: En un grafo existe por lo menos un camino de longitud λ , si

M λ≠¿ ¿de la matriz nula.

Para grafos orientados:

{ ¿ {¿ ¿
mij=1 Si hay un arco de v a v
i j
mij=0 Si no hay un arco de v a v
i j
m ii=1 Si en v hay un bucle
i
mij=n Si hay n arcos de v a v
i j
Esta matriz es simétrica sólo si el grafo lo es. Es cuadrada.

Ejemplo:

[ ]
0 1 0
M= 0 0 1
0 1 1
5
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

- La suma de los elementos distintos de cero es igual al número de arcos.

Matrices de Incidencia: (Sin lazos ni bucles)

Incidencia de aristas:

{¿ ¿¿¿ mij=1 Si v y a son incidentes

i

i
j
mij=0 Si v y a no son incidentes
j

Esta matriz es rectangular de Clasenxr : |V|=n (número de vértices) y |A|=r

(número de aristas).

[ ]
1 0 0
1 1 1
M=
0 1 1
0 0 0
g(v 1)= 1 ; g(v2)= 3 ; g(v3)= 2 ; g(v4)= 0

Teorema: En la matriz de incidencia de un grafo no orientado cada columna

presenta exactamente dos unos (correspondientes a las filas de los vértices
que son extremos de dicha arista) y cada fila tantos unos como el grado del
vértice correspondiente a dicha fila.

Matriz de Incidencia de arcos:

{¿ ¿ ¿
mij=1 Si v es orígen de a
i j
mij=−1 Si v es extremo de a
i j
mij=0 Si v y a no son incidentes
i j

6
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Esta matriz es rectangular de Clasenxr : |V|=n (número de vértices) y |A|=r

(número de arcos).

[ ]
1 −1 0 1
M= −1 1 −1 0
0 0 1 −1

- En cada columna hay un 1 y un -1, los demás elementos son ceros.

- La suma de los elementos de cada fila es igual al grado neto del vértice
correspondiente.
- La suma de los valores absolutos de estos elementos es igual al grado
total (sin signo) de dicho vértice.

Subgrafos

En ciertas ocasiones necesitamos solo una parte de un grafo para resolver un

determinado problema.
Por ejemplo si solo estamos interesados en una parte de una gran red
informática que involucre varias ciudades. En este caso podemos ignorar
algunos centros informáticos.
En el grafo que representa la red total podemos eliminar los vértices que
corresponden a todos los centros informáticos excepto los que estamos
interesados, luego debemos suprimir todas las aristas que inciden en los
vértices descartados. Se dice que este grafo es un subgrafo del grafo original.

S= ( V 1 , A , ϕ 1 )
Definición: El grafo es un subgrafo de G= (V , A , ϕ ) sí y solo sí se
verifican las siguientes condiciones:
i) V 1 ⊂V
ii) A1 ⊂ A
iii) ϕ 1 es una restricción de ϕ a A1
El subgrafo S se obtiene del grafo G suprimiendo de éste, vértices y/o aristas.
Ejemplos:

7
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

De este grafo podemos obtener el siguiente subgrafo por ejemplo

Casos particulares de subgrafos

 Subgrafo restante respecto del vértice v i: (G – vi): es el subgrafo de G

que se obtiene al suprimir únicamente el vértice vi
 Subgrafo restante respecto de la arista a i: (G – ai): es el subgrafo de G
que se obtiene al suprimir únicamente la arista ai

 Subgrafo generado por un subconjunto de vértices W: es el subgrafo

que tiene a W como conjunto de vértices y cuyo conjunto de aristas está
formado por todas las aristas del grafo original G que tienen ambos
extremos en W.

 Subgrafo minimal: un subgrafo S de G que goce de una propiedad P se

llama minimal respecto de P, si ningún subgrafo estrictamente menor
que S (es decir con menos vértices y/o aristas) goza de la propiedad P.

Ejemplo: supongamos que P es la propiedad “tener un solo ciclo” y

consideramos el siguiente grafo:

8
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

El subgrafo minimal es el S2

 Subgrafo Maximal: un subgrafo S de G que goce de una propiedad P se

llama maximal respecto de P, si ningún subgrafo estrictamente mayor
que S (es decir con más vértices y/o aristas) goza de la propiedad P.

 Subgrafo cobertor: un subgrafo S de G se llama cobertor si contiene a

todos los vértices de G.

Grafo Complementario

' '
Sea G=(V , A , ϕ ) , se llama grafo complementario de G, CG=(V , A , ϕ ) al que
tiene el mismo conjunto de vértices de G y cuyas aristas son las que le faltan a
G para ser completo.
Ejemplo:

9
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Conexidad

Grafo No orientado Conexo: un grafo G es conexo si dados cualesquiera dos

vértices v y w en G, existe una cadena de v a w. Ejemplos:

Los grafos G1 y G2 son conexos, el grago G3 no es conexo

En el grafo G= (V , A , ϕ ) definimos la siguiente relación: “el vértice v j es

alcanzable desde el vértice vi si existe una cadena que va de vi a vj”.

Componente conexa: es el subgrafo generado por el conjunto de vértices

C vn ={ v ∈V /∃ una cadena de v n a v } ¿ { v n }

10
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Es decir que una componente conexa es el grafo generado por

v n y todos los
vértices que están unidos a
v n por medio de una cadena.

Teorema: La relación “es alcanzable desde” definida en el conjunto V de

vértices de un grafo G, induce una partición en V, tal que cada clase de
equivalencia es el subconjunto de vértices que genera una componente
conexa.

Corolario: Un grafo no orientado es conexo sí y solo sí tiene una sola

componente conexa.
Demostración:
⇒) G es conexo ⇒ tiene una sola componente conexa.
Suponemos que G tiene 2 componentes conexas distintas
C vi y C vj ⇒ v y v no
i j

estarán unidos por una cadena ⇒ G no sería conexo (absurdo), luego vale ⇒)
⇐) G tiene una sola componente conexa ⇒ G es conexo.
Suponemos que G es no conexo, entonces existen, por lo menos, 2 vértices v i
C C
y vj no conectados ⇒ hay por lo menos 2 componentes conexas vi y vj (lo
que contradice la hipótesis), vale ⇐) .

Grafo Orientado Conexo

Sea G=(V , A , Φ ) , es conexo si para todo par de vértices distintos

v i≠v j del
mismo existe un camino que los une por lo menos en un sentido.

G1 es conexo G 2 no es conexo

Grafo Orientado Fuertemente Conexo

Definición: un grafo orientado G es fuertemente conexo cuando todo par de

vértices distintos del mismo está unido en ambos sentidos por un camino.

Ejemplo:

11
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Componentes conexas: es todo subgrafo maximal conexo. (El que tiene mayor
número de vértices y aristas que cumple la condición).

Componente fuertemente conexa: es todo subgrafo maximal fuertemente

conexo.

Ejemplo:

Matriz de conexión

C=[ c ij ]
La matriz de conexión de un grafo G de m vértices, es la matriz de
dimensión mxm donde:

{¿ ¿¿¿ c =1
ij si i=j o si existe una trayectoria de vi a vj
c ij =0 en otro caso
Notemos que G es conexo sí y sólo sí la matriz C no tiene ningún elemento
igual a cero.

Ej.:

[ ]
1 1 1
C= 1 1 1
1 1 1

12
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

[ ]
1 1 0
C= 1 1 0
0 0 1 El grafo tiene 2 c.c.

Para grafos orientados vale la misma definición de matriz de conexión.

Ej.:

[ ]
1 1 1
C= 1 1 1
1 1 1 El grafo es f.c.

Otro ej. :

[ ]
1 1 1
C= 0 1 0
1 1 1
Como existen elementos de C iguales a cero el grafo no es fuertemente conexo
Para ver si G es conexo debemos hacer la suma booleana de C y CT

13
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

[ ][ ][ ]
v 1 1 1 v 1 0 1 1 1 1
T
C+C = 0 1 0 + 1 1 1 = 1 1 1
1 1 1 1 0 1 1 1 1 el grafo es conexo porque todos los
elementos de C son iguales a uno

Para ver las componentes fuertemente conexas debemos hacer el producto

booleano de C y CT, elemento a elemento (no es el producto habitual entre
matrices). Luego mediante la permutación de filas y/o columnas buscamos
bloques de 1, cada bloque es una componente fuertemente conexa.

[ ][ ] [ ]
¿ 1 1 1 ¿1 0 1 1 0 1
C . C= 0 1 0 . 1 1 1 = 0 1 0 =
1 1 1 1 0 1 1 0 1 permutamos 2ª y 3ª columna

[ ] [ ]
1 1 0 1 1 0
=0 0 1= 1 1 0
1 1 0 permutamos 2ª y 3ª fila 0 0 1 nos queda así 2 c.f.c.

Grafo bipartito

El grafo G= (V,A,φ) es bipartito si existe una partición (V1, V2) en V tal que toda
arista de G tenga un vértice en V1 y el otro en V2.

Ejemplo:

14
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Es una partición porque cumple las condiciones: ¿ de vacío, disjuntos y su

unión es V .

Grafo bipartito completo

Cuando todo vértice de V 1 está conectado con todo vértice de V 2 .

El grafo se indica Kp,q (p = nro. de vértices de V 1 ; q = nro. de vértices de V 2 ).

Ejemplos:

Cadenas, caminos, ciclos y circuitos Hamiltonianos y Eulerianos

En las cadenas, caminos, ciclos y circuitos Hamiltonianos, nos interesan sus

recorridos por medio de vértices.

En grafos no orientados :

 Cadena Hamiltoniana: i j
v ≠v , ∀ i , j , es la cadena que recorre todos los
vértices del grafo sin repetirlos.
 Ciclo Hamiltoniano:
v ≠v , ∀ i , j
i j , es el ciclo que recorre todos los
vértices del grafo sin repetirlos excepto el inicial y final.

15
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

En grafos orientados:

 Camino Hamiltoniano: i j
v ≠v , ∀ i , j , es el camino que recorre todos los
vértices del grafo sin repetirlos
 Circuito Hamiltoniano: i j
v ≠v , ∀ i , j
, es el circuito que recorre todos los
vértices del grafo sin repetirlos excepto el inicial y final.

En las cadenas, caminos, ciclos y circuitos Eulerianos, nos interesan sus

recorridos por medio de aristas.

En grafos no orientados :

 Cadena Euleriana:
a ≠a ,∀ i, j , es la cadena que recorre todas las
i j
aristas del grafo sin repetirlas.
a ≠a ,∀ i, j , es el ciclo que recorre todas las aristas
 Ciclo Euleriano: i j
del grafo sin repetirlas.

En grafos orientados:

 Camino Euleriano:
a ≠a ,∀ i, j , es el camino que recorre todos los
i j
arcos del grafo sin repetirlos.
a ≠a ,∀ i, j , es el circuito que recorre todos los
 Circuito Euleriano: i j
arcos del grafo sin repetirlos.

Teorema 1: Un grafo G admite una cadena Euleriana sí y sólo sí es conexo y

el número de vértices de grado impar es cero o dos.

Teorema 2: Un grafo G admite ciclo Euleriano sí y sólo sí es conexo y todos

sus vértices son de grado par.

Teorema 3: Un grafo G orientado admite un circuito Euleriano sí y sólo sí el

grado neto de los vértices es cero.

Ejemplos:

16
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

ÁRBOLES

Árbol libre o árbol no orientado

Un árbol libre es un grafo conexo y acíclico.

Ejemplo:

Bosque: es un conjunto de árboles.

Árbol trivial: es el árbol formado por un único vértice.

Número Cíclico

Si G es un grafo conexo, se llama número cíclico al número natural

ϕ ( G )=|A|−|V|+1
|A|= número de aristas de G; |V|= número de vértices de G .
17
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Si el grafo G tiene k componentes conexas resulta:

ϕ ( G )=|A|−|V|+k
Propiedades:

 Si ϕ ( G )=0 ⇒ el grafo no tiene ciclo.

 Si ϕ ( G )=1 ⇒ el grafo tiene un ciclo.
 Si ϕ ( G ) ¿1⇒¿ el grafo tiene más de un ciclo.

Si el grafo es un árbol, entonces el número cíclico siempre es cero, porque un

árbol no tiene ciclos.

Ejemplo:

ϕ ( G )=6−4 +1=3 (No es árbol)

ϕ ( G )=7−8+1=0 (Es árbol)

Si tenemos un grafo que no es un árbol, entonces tiene más de un ciclo, pero

ϕ ( G ) no nos da la cantidad de ciclos.
Teorema: el número de aristas que hay que suprimir en un grafo conexo para
obtener un árbol maximal es el número cíclico. (Indica cuántas aristas se
pueden suprimir pero no cuáles).

18
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

ϕ ( G )=6−4 +1=3
Se debe suprimir 3 aristas para obtener un árbol maximal:
Ejemplos

Árbol orientado o con raíz

Definición: G= (V , A , Φ ) es un árbol orientado de raíz

v i si:
v
1- i no es extremo Terminal de ningún arco.
2- G no tiene circuitos.

19
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

3-
∀ v j≠v i , v j es extremo Terminal de un solo arco.

Niveles de un árbol orientado:

Los vértices de los cuales no salen otros arcos reciben el nombre de hojas o
vértices pendientes del árbol.

Árboles con raíz ordenados

Son lo árboles en los cuales las aristas están ordenadas.

Ejemplo:
Sea T un árbol ordenado y a y a’ dos aristas que parten de un vértice v 1 y van
a los vértices v2 y v3.
Si a precede a a’ en el orden de T dibujamos a a la izquierda de a’ y por lo
tanto se establece el mismo orden con los vértices: v2 precede a v3.
Este tipo de árboles ese emplea, por ejemplo para representar operaciones
aritméticas.

20
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Ejemplos:

x+ y
( x . z )+w

2 x 2 +7 y

x( y+z)
xyz

Árboles rotulados:
Rotular árboles es establecer una biyección entre el conjunto de vértices y el
intervalo natural inicial In={1,2,3,…..,n}

21
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

Suma de grafos

G1 =( V , A 1 , Φ1 ) G 2 =( V , A 2 , Φ 2 )
Sean los grafos orientados y donde
V = {v 1 , v 2 , v 3 , .. . .. . , v n } G1 +G2 =( V , A1 ∪ A2 ,Φ 1 +Φ 2 )
. Definimos el grafo suma:
donde: ( 1
Φ +Φ 2) ( a ) = { ( v i , v j ) / Φ1 ( a )=( v i , v j ) ∨Φ2 ( a )=( v i , v j ) } con a ∈ A 1 ∪A 2 .
M 1 =[ aij ]nxn M 2 =[ bij ]nxn
Si llamamos y respectivamente a las matrices de
M + M 2 =[ aij + bij ]nxn
adyacencia de los grafos G 1 y G 2 entonces: 1 es la matriz
de adyacencia de los grafos suma G 1 +G 2 .
Ejemplo:

[ ] [ ] [ ]
0 1 1 1 1 0 1 2 1
M1= 1 0 0 ; M2= 0 0 1 ; M1+M2= 1 0 1
0 0 0 0 0 0 0 0 0

22
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

[ ]
1 1 1
M 1 0 1
0 0 0

Producto de grafos

, definimos el grafo producto G 1⋅G 2

G1 =( V , A 1 , V 1 , Φ1 ) G 2 =( V , A 2 , Φ 2 )
Sean y
como el conjunto de los caminos ( vi , v j) formados por un arco ( i k ) de G 1 ,
v ,v

seguido de un arco (
vk , v j)
de G 2 .
Sean los grafos orientados 1 (
G = V , A 1 , Φ1 ) G2 =( V , A 2 , Φ 2 )
y con matrices de
n

M 1 =[ aij ]nxn M 2 =[ bij ]nxn M 1⋅M 2 = ∑ a ik⋅b kj

adyacencia y . La matriz producto k =1

es la matriz de adyacencia del grafo producto G 1⋅G2 .

⃗
G1 =( V , A 1 , Φ1 ) y ⃗
G2 =( V , A 2 , Φ2 )
Sean los grafos orientados , con
matrices de adyacencia M1=[ aij ] nxn y M2 = [ bij ] nxn. La matriz producto M1 x M2 =
n
∑ a ik⋅ b ik ⃗ ⃗
k =1 es la matriz de adyacencia del grafo producto G 1⋅G2
Hacemos el producto común y el producto booleano:

v1 v1
v2
v2
v3 v3
¿
⃗
G1⋅⃗
G2 ⃗
G1 ¿ ⃗
G2

Las matrices serán:

23
Prof. Nancy Aguilar y Graciela Del Valle Matemática Discreta- ISI

1 0 1 1 0 1
0 0 0 ¿
0 0 0
M 1⋅M 2
0 2 0 M1¿ M2 0 1 0
0 1 0 0 0 0 0 1 0 0 0 0
|1 0 0 1 0 1 |1 0 0 1 0 1
0 1 0 0 0 0 0 1 0 0 0 0

24