4.1. Introducción y definiciones.
Ciclo: es un camino en el cual el primer y el último vértice son iguales. Se llama ciclo simple si el camino es simple. En grafos no dirigidos es necesario que las aristas sean diferentes.
Dados dos vértices v, w, se dice que están conectados si existen un camino de v a w.
Un grafo es conexo (o conectado) si hay un camino entre cualquier par de vértices. Si es un grafo dirigido, se llama fuertemente conexo.
Un grafo es completo si existe una arista entre cualquier par de vértices. Para n nodos, ¿cuántas aristas tendrá el grafo?
Grado de un vértice v: número de arcos que inciden en él. Para grafos dirigidos, grado de entrada: nº de aristas con <x, v> grado de salida: nº de aristas con <v, x>.
Un grafo está etiquetado si asociamos a cada arista un peso o valor.
Grafo con pesos: grafo etiquetado con valores numéricos.
Un subgrafo (o componente) de G=(V, A) es un grafo G’=(V’, A’) tal que V’?V y A’?A.