Teoría de grafos

En el grafo, esta arista no dirigida se representa mediante un segmento de recta que une a dichos vértices.es un par ordenado y el hecho de que la arista sea dirigida se denota comoEste ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.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.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 Frankland[4]​ 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.Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.Desafortunadamente, encontrar subgrafos máximos de un cierto tipo suele ser un problema NP-completo.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.La subdivisión del contenido está relacionada con las propiedades de los grafos tales como la "planeza".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).Un ejemplo de ciclo hamiltoniano es el grafo del dodecaedro.Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos.Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.Este problema famoso relativo a los grafos trata acerca de la cantidad de colores que son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color.Sin embargo, si el mapa tiene forma de toroide, el teorema afirma que con cuatro colores no siempre es posible realizar la coloración con las características requeridas.Un grafo es simple si a lo sumo existe una arista uniendo dos vértices cualesquiera.Las definiciones aportan una formalización lógica a hechos abstractos o naturales, muchas veces ya definidos de forma intuitiva.Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.En términos matemáticos la propiedad de un grafo (fuertemente) conexo permite establecer una relación de equivalencia para sus vértices, la cual lleva a una partición de estos en "componentes (fuertemente) conexos", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados.Esta propiedad es importante para muchas demostraciones en teoría de grafos.Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices.Es decir, todo par de vértices (a, b) debe tener una arista e que los une.En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo ponderado.Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos).Internet permite de ver desde otro enfoque la idea del diámetro: considérese por ejemplo que si se descartan los sitios que no tienen enlaces, y se escogen dos páginas web al azar, cabría preguntarse en cuántos clics se puede pasar del primer sitio al segundo.Si se supone que de cualquier sitio que enlace con otros sitios se puede llegar a cualquier otro, entonces las mayor cantidad de clics necesarios para llegar de cualquier web a otra sería el "diámetro" de la Red, vista como un grafo cuyos vértices son los sitios, y cuyas aristas son los enlaces entre los sitios.Un claro ejemplo es el Algoritmo de Dijkstra, utilizado para la determinación del camino más corto en el recorrido de un grafo con determinados pesos en sus vértices.[22]​ Los grafos son importantes en el estudio de la biología y hábitat.