Un grafo es un conjunto de puntos (vértices) en el espacio,
que están conectados por un conjunto de líneas (aristas). Otros conceptos
básicos son:
Dos vértices son adyacentes si comparten la misma arista.
Los extremos de una arista son los vértices que comparte
dicha arista.
Un grafo se dice que es finito si su numero de vértices es
finito.
Clases de grafos
Un multigrafo es un grafo con varias aristas entre dos
vértices.
Un pseudografo es un grafo en el que hay aristas (lazos)
que tienen el mismo extremo.
Un digrafo es un grafo donde a cada arista se le indica un
sentido mediante una flecha.
Los multidigrafos o pseudomultidigrafos son combinaciones
de los anteriores.
Teoremas
Dos grafos son isomorfos si tienen el mismo numero de
vértices y aristas y, estas se corresponden con los mismos extremos.
El grado del vértice de un grafo (gr) es el numero de
aristas que tienen por extremo dicho vértice.
Si dos grafos son isomorfos, los vértices que se
corresponden tienen el mismo grado.
Primer Teorema de la Teoría de Grafos: todo grafo
contiene un numero par o cero de vértices de grado impar.
Un subgrafo es un grafo que esta contenido dentro de otro
grafo y que se obtiene eliminando algunas aristas y vértices del grafo
principal.
Un grafo es regular si todos sus vértices tienen el mismo
grado k (k-regular).
Un grafo es completo si cada par de vértices son los
extremos de una arista.
Dos grafos completos con el mismo numero de vértices son
isomorfos.
Un camino en un grafo es una sucesión finita en la que
aparecen alternadamente vértices y aristas de dicho grafo. Otras definiciones
básicas son:
Los extremos son los vértices inicial y final del camino.
La longitud de un camino es el numero de aristas que
contiene.
Un camino es cerrado si sus extremos coinciden.
Un camino es simple si en la sucesión de vértices no hay
ninguno repetido.
Un ciclo es un camino cerrado donde los únicos vértices
repetidos son el primero y el ultimo.
Un circuito es un camino cerrado que no repite aristas.
Si en un grafo existe un camino que conecta dos vértices
distintos, entonces existe un camino simple con extremos en dichos vértices.
Un grafo es conexo si para cada par de vértices, existe un
camino con extremos en dichos vértices.
Tipos de caminos
Camino euleriano: es un camino o circuito que contiene
todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo
que admite dicho circuito se denomina grafo euleriano, y sus vértices o
tienen grado par o dos de los vértices tienen grado impar.
Camino hamiltoniano: es un camino simple que contiene
todos los vértices apareciendo cada uno de ellos exactamente una vez. Un
ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y
un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.
