Portada de Introducción a la teoría de grafos: conceptos, algoritmos y aplicaciones
Declaración de Prestigio Académico E-book

Introducción a la teoría de grafos: conceptos, algoritmos y aplicaciones

Ismael Gutiérrez García · Yesneri Maider Zuleta Saldarriaga

Editorial Universidad del Norte

Sinopsis

La teoría de grafos o teoría de gráficas es considerada una de las ramas más importantes de las matemáticas modernas. Tiene muchas aplicaciones, ya que es posible utilizar grafos para resolver problemas en diversas áreas. En este libro se dan a conocer definiciones y nociones básicas, se definen formalmente los diferentes tipos de grafos, se desarrolla el tema de representación matricial, se clasifican los distintos tipos de paseos, se introduce la idea de conexidad, se presentan algunas definiciones y resultados alrededor de los grafos eulerianos y hamiltonianos, así como los conceptos de emparejamiento y cubrimiento en un grafo, y se explica un tipo especial de grafo denominado árbol. Cada capítulo cuenta con ejemplos y una sección de ejercicios.

Sobre los autores

Ismael Gutiérrez García

Ismael Gutiérrez García

Ismael Gutierrez Garcia es Licenciado en Matemáticas y Física de la Universidad del Atlántico, Magíster en Matemáticas de la Universidad del Valle y Doctor en Ciencias Naturales de la Universidad Johannes Gutenberg de Mainz. Profesor titular de la universidad del Norte. Posee una amplia experiencia como docente Universitario y además ha liderado proyectos de Investigación en el área de matemáticas discretas y sus aplicaciones, concretamente en teoría clásica de códigos y en códigos de subespacios.
Yesneri Maider Zuleta Saldarriaga

Yesneri Maider Zuleta Saldarriaga

Matemática Magister en Matemática

Contenido

Prólogo 7

1. Algunos problemas modelados con grafos 9

2. Definiciones básicas sobre grafos 15

2.1. Algunos tipos de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2. Propiedades de los vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3. Algunas familias de grafos no dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4. Operaciones entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5. Isomorfía entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3. Representación matricial de grafos y conexión 41

3.1. Recorridos en grafos no dirigidos y dirigidos . . . . . . . . . . . . . . . . . . . . . . . 41

3.2. Matriz de adyacencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.3. Matriz de incidencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.4. Matriz laplaciana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.5. Conexión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4. Grafos eulerianos, hamiltonianos y planos 63

4.1. Circuitos eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.2. Algoritmos para hallar circuitos eulerianos . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3. Circuitos hamiltonianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4. Algoritmo para determinar todos los caminos hamiltonianos . . . . . . . . . . . . . . 72

4.5. Grafos planos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5. Emparejamientos y cubrimientos 83

5.1. Emparejamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.2. Un algoritmo para aumentar un emparejamiento . . . . . . . . . . . . . . . . . . . . 89

5.3. Cubrimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.4. Algunos algoritmos de cubrimiento por vértice . . . . . . . . . . . . . . . . . . . . . 93

5.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6. Árboles 97

6.1. Árbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.2. Árboles enraizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.3. Algunos algoritmos para obtener un árbol generador mínimo . . . . . . . . . . . . . 104

6.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7. Coloración de grafos 121

7.1. Coloreando vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7.2. Algunas aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

7.3. Coloreando aristas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

7.4. Algunos algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

7.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

8. ANEXOS 147

8.1. Principio de inducción matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

8.2. Principio de adición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

8.3. Principio de las cajas o principio del palomar . . . . . . . . . . . . . . . . . . . . . . 152


Materias

BISAC

  • MAT030000. MATEMÁTICAS > Estudio y enseñanza

Thema

  • PB. Matemáticas
  • JNU. Enseñanza de una materia específica

Dewey

  • 519.5. Ciencias naturales y matemáticas > Matemáticas > Probabilidades y matemática aplicada > Matemática Estadística

Declaración de Prestigio Académico

Lo que la editorial declara sobre la evaluación de esta obra.

Recepción de la propuesta2022-12-16
Decisión editorial2024-04-10
Revisión por paresSimple ciego
Control de plagioVerificado por la editorial

Más de Editorial Universidad del Norte

Ver todas