Índice general
Introducción. 3
1. El lenguaje de las gráficas. 5
1.1. Definiciones básicas. . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2. Conexidad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Apuntes de Álgebra Lineal. 19
2.1. Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1. Rango de una matriz. . . . . . . . . . . . . . . . . . . . . . 21
2.2. Determinantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3. Valores y vectores propios. . . . . . . . . . . . . . . . . . . . . . . 37
2.3.1. Teorema de Cayley-Hamilton. . . . . . . . . . . . . . . . . 39
3. El espectro de una gráfica 43
3.1. La matriz de adyacencia y su polinomio caracterı́stico. . . . . . . 43
3.2. El álgebra de adyacencia. . . . . . . . . . . . . . . . . . . . . . . . 46
1
, ÍNDICE GENERAL
4. Gráficas regulares 53
4.1. Matriz de adyacencia de una gráfica regular. . . . . . . . . . . . . 53
4.2. Gráficas y matrices circulantes. . . . . . . . . . . . . . . . . . . . 56
4.2.1. Gráficas completas. . . . . . . . . . . . . . . . . . . . . . . 63
4.2.2. Ciclos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.3. Gráficas cóctel. . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3. Gráficas de lı́neas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5. Ciclos y cortes. 77
5.1. El espacio de vértices y el espacio de aristas. . . . . . . . . . . . . 77
5.2. La matriz de incidencia. . . . . . . . . . . . . . . . . . . . . . . . 80
5.3. El subespacio-ciclo y el subespacio-corte. . . . . . . . . . . . . . . 86
5.4. Matriz Laplaciana. . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6. Árboles generadores y estructuras asociadas 95
6.1. Ciclos y cortes asociados a árboles generadores. . . . . . . . . . . 95
6.2. Matriz de incidencia y árboles generadores. . . . . . . . . . . . . . 99
6.3. Cantidad de árboles generadores. . . . . . . . . . . . . . . . . . . 100
2
,Introducción.
La presente tesis de Licenciatura se compone de 6 capı́tulos, en los cuales bus-
caremos estudiar la relación que existe entre el Álgebra Lineal y la Teorı́a de
Gráficas, codificando las gráficas y las gráficas dirigidas mediante las matrices
de adyacencia e incidencia respectivamente. Usando herramientas y técnicas del
Álgebra Lineal revisaremos resultados referentes a las gráficas, analizando sus
propiedades en términos de propiedades algebraicas como por ejemplo los valores
y vectores propios de las matrices o buscando el número de árboles generadores
de una gráfica calculando determinantes.
Deseamos proporcionar al lector, un panorama general acerca de la conexión que
existe entre estas dos áreas de la matemática, presentando las demostraciones
de manera detallada, incluyendo ejemplos y motivando con ellos los resultados a
tratar.
El Capı́tulo 1, El lenguaje de las gráficas, y el Capı́tulo 2, Apuntes de Álgebra Li-
neal, nos proporcionarán de definiciones básicas y resultados que serán empleados
a lo largo de este trabajo. Las demostraciones de aquellos resultados de Álgebra
Lineal que se enseñan en los cursos básicos de la carrera de matemáticas se omi-
ten, pero se muestra la referencia para el lector que esté interesado en revisarlos
pueda hacerlo.
La intención de estos primeros dos capı́tulos es que el trabajo sea en medida de
lo posible autocontenido, pero para no alargar de manera innecesaria el texto y
no perder de vista el objetivo final, se enuncian solamente los resultados que se
utilizarán en los capı́tulos posteriores.
En el Capı́tulo 3, El espectro de una gráfica, estableceremos la relación entre una
gráfica y un objeto algebraico, pues codificaremos la gráfica mediante una matriz
3
, ÍNDICE GENERAL
cuadrada llamada matriz de adyacencia. El desarrollo del polinomio caracterı́stico
nos brindará datos de la gráfica en cuestión.
Dentro del Capı́tulo 4, Gráficas regulares, seguiremos trabajando con la matriz
de adyacencia pero de un tipo especial de gráficas, llamadas regulares. También
dotaremos de la cualidad de ser matriz circulante a la matriz con la que hemos ve-
nido trabajando. Los valores propios de las matrices circulantes pueden obtenerse
a partir de las raı́ces n − ésimas de la unidad y del primer renglón de su matriz
de adyacencia; esto nos permitirá conocer el espectro de la gráfica. Estudiaremos
además la relación entre los polinomios caracterı́sticos de una gráfica y la gráfica
de lı́neas derivada de ella.
En el Capı́tulo 5, Ciclos y cortes, introduciremos una nueva matriz que codifica
los elementos que definen una gráfica orientada, los vértices y las aristas, además
de tomar en cuenta la orientación, esta matriz se conocerá como la matriz de inci-
dencia. De la relación entre las matrices de adyacencia e incidencia, contruiremos
la matriz Laplaciana.
Finalmente, en el Capı́tulo 6, Árboles generadores y estructuras asociadas, con
toda la información que hemos estado manejando, podremos saber el número
de árboles generadores de una gráfica mediante las matrices y las operaciones
algebraicas que podemos hacer con ellas.
4
Introducción. 3
1. El lenguaje de las gráficas. 5
1.1. Definiciones básicas. . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2. Conexidad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Apuntes de Álgebra Lineal. 19
2.1. Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1. Rango de una matriz. . . . . . . . . . . . . . . . . . . . . . 21
2.2. Determinantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3. Valores y vectores propios. . . . . . . . . . . . . . . . . . . . . . . 37
2.3.1. Teorema de Cayley-Hamilton. . . . . . . . . . . . . . . . . 39
3. El espectro de una gráfica 43
3.1. La matriz de adyacencia y su polinomio caracterı́stico. . . . . . . 43
3.2. El álgebra de adyacencia. . . . . . . . . . . . . . . . . . . . . . . . 46
1
, ÍNDICE GENERAL
4. Gráficas regulares 53
4.1. Matriz de adyacencia de una gráfica regular. . . . . . . . . . . . . 53
4.2. Gráficas y matrices circulantes. . . . . . . . . . . . . . . . . . . . 56
4.2.1. Gráficas completas. . . . . . . . . . . . . . . . . . . . . . . 63
4.2.2. Ciclos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.3. Gráficas cóctel. . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3. Gráficas de lı́neas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5. Ciclos y cortes. 77
5.1. El espacio de vértices y el espacio de aristas. . . . . . . . . . . . . 77
5.2. La matriz de incidencia. . . . . . . . . . . . . . . . . . . . . . . . 80
5.3. El subespacio-ciclo y el subespacio-corte. . . . . . . . . . . . . . . 86
5.4. Matriz Laplaciana. . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6. Árboles generadores y estructuras asociadas 95
6.1. Ciclos y cortes asociados a árboles generadores. . . . . . . . . . . 95
6.2. Matriz de incidencia y árboles generadores. . . . . . . . . . . . . . 99
6.3. Cantidad de árboles generadores. . . . . . . . . . . . . . . . . . . 100
2
,Introducción.
La presente tesis de Licenciatura se compone de 6 capı́tulos, en los cuales bus-
caremos estudiar la relación que existe entre el Álgebra Lineal y la Teorı́a de
Gráficas, codificando las gráficas y las gráficas dirigidas mediante las matrices
de adyacencia e incidencia respectivamente. Usando herramientas y técnicas del
Álgebra Lineal revisaremos resultados referentes a las gráficas, analizando sus
propiedades en términos de propiedades algebraicas como por ejemplo los valores
y vectores propios de las matrices o buscando el número de árboles generadores
de una gráfica calculando determinantes.
Deseamos proporcionar al lector, un panorama general acerca de la conexión que
existe entre estas dos áreas de la matemática, presentando las demostraciones
de manera detallada, incluyendo ejemplos y motivando con ellos los resultados a
tratar.
El Capı́tulo 1, El lenguaje de las gráficas, y el Capı́tulo 2, Apuntes de Álgebra Li-
neal, nos proporcionarán de definiciones básicas y resultados que serán empleados
a lo largo de este trabajo. Las demostraciones de aquellos resultados de Álgebra
Lineal que se enseñan en los cursos básicos de la carrera de matemáticas se omi-
ten, pero se muestra la referencia para el lector que esté interesado en revisarlos
pueda hacerlo.
La intención de estos primeros dos capı́tulos es que el trabajo sea en medida de
lo posible autocontenido, pero para no alargar de manera innecesaria el texto y
no perder de vista el objetivo final, se enuncian solamente los resultados que se
utilizarán en los capı́tulos posteriores.
En el Capı́tulo 3, El espectro de una gráfica, estableceremos la relación entre una
gráfica y un objeto algebraico, pues codificaremos la gráfica mediante una matriz
3
, ÍNDICE GENERAL
cuadrada llamada matriz de adyacencia. El desarrollo del polinomio caracterı́stico
nos brindará datos de la gráfica en cuestión.
Dentro del Capı́tulo 4, Gráficas regulares, seguiremos trabajando con la matriz
de adyacencia pero de un tipo especial de gráficas, llamadas regulares. También
dotaremos de la cualidad de ser matriz circulante a la matriz con la que hemos ve-
nido trabajando. Los valores propios de las matrices circulantes pueden obtenerse
a partir de las raı́ces n − ésimas de la unidad y del primer renglón de su matriz
de adyacencia; esto nos permitirá conocer el espectro de la gráfica. Estudiaremos
además la relación entre los polinomios caracterı́sticos de una gráfica y la gráfica
de lı́neas derivada de ella.
En el Capı́tulo 5, Ciclos y cortes, introduciremos una nueva matriz que codifica
los elementos que definen una gráfica orientada, los vértices y las aristas, además
de tomar en cuenta la orientación, esta matriz se conocerá como la matriz de inci-
dencia. De la relación entre las matrices de adyacencia e incidencia, contruiremos
la matriz Laplaciana.
Finalmente, en el Capı́tulo 6, Árboles generadores y estructuras asociadas, con
toda la información que hemos estado manejando, podremos saber el número
de árboles generadores de una gráfica mediante las matrices y las operaciones
algebraicas que podemos hacer con ellas.
4
