Teoria de grafos

Teoria de grafos

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típica mente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Definiciones

• Vértices:  Son los puntos o nodos con los que esta conformado un grafo.

• Aristas dirigidas y no dirigidas: Las aristas, son las lineas que unen dos vértices, se clasifican en 2: las dirigidas y las no dirigidas. Las dirigidas son las que solo pueden ser recorridas en la dirección definida por el usuario, las no dirigidas pueden ir de un lado a otro sin ningún impedimento.

• Ciclos y caminos hamiltonianos: Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene ademas de recorrer todos los vértices exactamente una vez. Se habla también de camino hamiltoniano si no se impone regresar al punto de partida.
• Camino: Se denomina camino de un grafo a un conjunto de vértices interconectados por aristas. Dos vértices están conectados si hay un camino entre ellos.

Tipos de grafos

• Grafo simple. Es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

• Multigrafo. Es el que acepta más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos. Los grafos simples son una subclase de esta categoría de grafos. 

• Pseudografo. Si incluye algún lazo.

• Grafo orientado, grafo dirigido o digrafo. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha.

• Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas o un etiquetado a los vértices.

• Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.

• Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

• Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

• Grafo plano. Los grafos planos son aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Podemos establecer que un grafo es plano gracias al Teorema de Kuratowski.

• Grafo regular. Un grafo es regular cuando todos sus vértices tienen el mismo grado de valencia.

Fuentes: https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
                http://www.unipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general/11072012/grafo3.pdf