La teoría de grafos o teoría de gráficas es una rama de las matemáticas, con aplicaciones en las ciencias de la computación y otras ciencias, que estudia las propiedades de los grafos. Se han denominado grafos para distinguir del concepto homónimo de gráficas, aunque también se les llama así.

Formalmente, un grafo es una pareja ordenada en la que es un conjunto no vacío de vértices y es un conjunto de aristas, donde consta de pares no ordenados de vértices, tales como , y entonces se dice que e son adyacentes. En el grafo, esta arista no dirigida se representa mediante un segmento de recta que une a dichos vértices. Si el grafo es dirigido se le llama dígrafo, se denota y se representa con una flecha que va de a , entonces el par es un par ordenado y el hecho de que la arista sea dirigida se denota como .

La teoría de grafos tiene sus fundamentos en la matemática discreta y de la matemática aplicada. Esta teoría requiere de diferentes conceptos de diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología. Actualmente ha tenido mayor influencia en el campo de la informática, las ciencias de la computación y telecomunicaciones. Debido a la gran cantidad de aplicaciones en la optimización de recorridos, procesos, flujos, algoritmos de búsquedas, entre otros, se generó toda una nueva teoría que se conoce como análisis de redes.CEPAL Charlas Sobre Sistemas Complejos Sociales (CCSSCS): Analisis de Redes1: https://www.youtube.com/watch?v=oy8YxTshZhI&list=UUQbp2yA-gyew7E_tzgOI36A & Analisis de Redes2: https://www.youtube.com/watch?v=1abtP36Wx24&list=UUQbp2yA-gyew7E_tzgOI36A; Curso completo en línea: http://www.martinhilbert.net/CCSSCS.html

Historia thumb|Los 7 puentes del río Pregel en Königsberg. El origen de la teoría de grafos se remonta al con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel () en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis (La solución de un problema relativo a la geometría de la posición) en 1736, es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.

Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.

En 1852, Francis Guthrie planteó el problema de los cuatro colores, el cual afirma que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos con idéntica composición (fórmula) pero diferente estructura molecular. Para ello representó cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos.

El término «grafo», proviene de la expresión inglesa graphic notation («notación gráfica»), usada por primera vez por Edward Franklandhttp://booklens.com/l-r-foulds/graph-theory-applications pag 7 y posteriormente adoptada por Alexander Crum Brown en 1884 y que hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula.

El primer libro sobre teoría de grafos fue escrito por Dénes Kőnig y publicado en 1936..

A fines de los años 1940 e inicios de los años 1950, junto con los primeros estudios formales de cliques o camarillas en sociomatrices y de centralidad en sociogramas, se introdujo la teoría de grafos como herramienta clave para la sociometría y el análisis de redes sociales.

Composición de un grafo Aristas: Son las líneas que unen los vértices de un grafo. Aristas adyacentes: Dos aristas son adyacentes si convergen en el mismo vértice. Aristas paralelas: Dos aristas son paralelas si los vértices iniciales y finales son el mismo vértice Aristas cíclicas: Aristas que parten de un vértice para entrar en el mismo. Cruce: Punto donde dos aristas se cruzan.

Vértices: Los vértices, también llamados "nodos", son los elementos que forman un grafo. Cada uno lleva asociada una valencia característica según la situación, que se corresponde con la cantidad de aristas que confluyen en dicho vértice.

Camino: Se denomina camino 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: O simplemente grafo 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. Es la definición estándar de un grafo. Multigrafo o pseudografo: Es el que acepta más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos general. Grafo dirigido: grafo orientado o dígrafo. 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 (número entero generalmente) 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. Grafo dual: El grafo dual de un grafo (plano), es aquel que tiene un vértice por cada región de , y una arista por cada arista en uniendo dos regiones vecinas. Representación de grafos

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.Ejemplo de una lista de incidencia

Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

Lista de grados - También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo.

Estructuras matriciales Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño , donde es el número de vértices. Si hay una arista entre un vértice y un vértice , entonces el elemento es , de lo contrario, es .

Matriz de incidencia - El grafo está representado por una matriz de (aristas) por (vértices), donde [vértice, arista] contiene la información de la arista ( significa conectado y no conectado). Grafo Conjuntos Matriz de adyacencia Matriz de incidencia Secuencia de grados Lista de adyacencia150px +vérticelista de adyacencia

Problemas de teoría de grafos

Subgrafos, subgrafos inducidos y menores Un problema común, denominado problema de isomorfismo de subgrafos, es encontrar un grafo fijo como subgrafo de un grafo dado. Una razón para estar interesado en esta cuestión es que muchas propiedades de grafos son heredadas de subgrafos, lo que significa que un grafo tiene una propiedad si y solo si todos sus subgrafos a su vez la poseen. Desafortunadamente, encontrar subgrafos máximos de un cierto tipo suele ser un problema NP-completo. Por ejemplo: Encontrar el subgrafo completo más grande se llama problema de la clique.

Un problema similar es encontrar un subgrafo inducido en un grafo dado. De nuevo, algunas propiedades importantes son heredadas con respecto a subgrafos inducidos, lo que significa que un grafo tiene una propiedad si y solo si todos los subgrafos inducidos la tienen. Encontrar subgrafos inducidos máximos de un determinado tipo es, de nuevo, un problema NP-completo. Como ejemplo: Encontrar el subgrafo inducido más grande sin bordes o conjunto independiente se denomina problema del conjunto independiente.

Otro nuevo problema es el problema del menor contenido, que es encontrar un grafo fijo como menor de un grafo dado. Un menor o subcontración de un grafo es cualquier grafo obtenido tomando un subgrafo y contrayendo algunos bordes. Muchas propiedades de grafos son heredadas de menores, lo que significa que un grafo la tiene solo si todos sus menores la tienen también. Por ejemplo, el teorema de Wagner estipula que: Un grafo es plano si contiene como menor ni el grafo bipartito completo ni el grafo completo.

Un problema de las mismas características es el problema de la subdivisión del contenido. Una subdivisión o homeomorfismo de un grafo es cualquier grafo obtenido subdividiendo algunos bordes. La subdivisión del contenido está relacionada con las propiedades de los grafos tales como la "planeza". Por ejemplo, el teorema de Kuratowski establece que: Un grafo es plano si contiene una subdivisión ni el grafo bipartito ni el grafo completo. Otro problema en la subdivisión de contenido es la conjetura de Kelmans-Seymour: Cada grafo de cinco vértices conectados que no es plano contiene una subdivisión del grafo completo de cinco vértices. Otro problemas de clases tienen que ver con el alcance para la cual varias especies y generalizaciones de grafos están determinadas por sus subgrafos de puntos eliminados. Por ejemplo, la conjetura de la reconstrucción.

Ciclos y caminos hamiltonianos

thumb|200px|Ejemplo de un ciclo hamiltoniano. 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 además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).

Por ejemplo, en un museo grande, lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).