Índice

Primeros pasos

La teoría de grafos comprende muchos conceptos, teoremas y notaciones muy precisas, pero algo preocupantes, pues estas definiciones varían en función de los autores. No definiremos matemáticamente todos los conceptos subyacentes a nuestro uso de los grafos, pues no bastaría con un capítulo. Aquí encontrará una selección de los términos clave y de definiciones «en español» bastante fiables que nos permitirán manipular los grafos en un contexto operacional. En caso de duda, diríjase a las fuentes citadas en la introducción del libro.

1. Algunas nociones y notaciones complementarias básicas

Le conviene empaparse de las siguientes nociones y tratar de reconocerlas en los grafos que encuentre.

Un Grafo:finito no orientado sin buclegrafo finito no orientado sin bucle (loop), es decir, un grafo simple (undirected simple) se escribe G(V, E). Preste atención, en ocasiones se llama de la misma manera a los grafos de otra naturaleza (no simples, orientados, hipergrafos...). Grafo:simple undirected simple

Sus Nodosnodos o vertices se escriben V(G) = {v1,,..., vn}. Vertices

Nota de vocabulario: en inglés, vertices es el plural de vertexvertex.

Sus Aristasaristas o edges se escriben E(G) = {e1,,...,en}. Edges

Cuando no existe ambigüedad, resulta inútil escribir la (G).

Las aristas ...