Teoría de grafos

Teoría de Grafos
Información sobre la plantilla
Teor-a-de-grafos-n.jpg
Concepto:Rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos.

Teoría de Grafos. Es la rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos. Son un conjunto de elementos no vacíos, que se conocen como vértices y una recopilación de aristas (pares de vértices) que pueden ser o no orientados. La representación del grafo, por lo general, es una gráfica de puntos conectados por líneas.

Definición

El origen de la palabra grafo es griego y su significado etimológico es “trazar» (del griego grafos: dibujo, imagen). La Teoría de Grafos, una rama de la Topología, es el estudio de estructuras matemáticas que se usan para modelar relaciones entre objetos de una colección.

Un grafo es un par de conjuntos G = (V, A), donde “V” es el conjunto de vértices y “A “ es el conjunto de aristas. Los grafos pueden ser simples, conexos, completos o bipartitos.

El término grafo en matemática, proviene de la expresión inglesa graphic notation notación gráfica, Edward Frankland fue el primero en usarlo 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.

Representación Gráfica

Un grafo se representa mediante un diagrama en el cual a cada vértice le corresponde un punto y si dos vértices son adyacentes se unen sus puntos correspondientes mediante una línea.

Grafo Conexo y no conexo~2.jpg

Historia

El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convirtió en la ciudad rusa de Kaliningrado, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel, 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 relativo a la geometría de la posición en 1736, se considera como el primer resultado de la teoría de grafos y topológicos en geometría (sin depender de medida alguna). Este ejemplo muestra la profunda conexión entre la teoría de grafos y la topología.

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

En el año 1852, Francis Guthrie planteó el problema de los cuatro colores, afirmando que utilizando solamente cuatro colores, se puede colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, no fue resuelto hasta 1976 por Kenneth Appel y Wolfgang Hake, 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.

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

Componentes de un grafo

Aristas. Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Aristas Adyacentes. Se dice que dos aristas son adyacentes si coinciden en el mismo vértice.

Aristas Paralelas. Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. Aristas Cíclicas. Arista que parte de un vértice para entrar en el mismo.

Cruce. Son dos aristas que cruzan en un puntos.

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

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

Vértices Adyacentes. si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

Vértice Aislado. Es un vértice de grado cero.

Vértice Terminal. Es un vértice de grado 1.

Lazo. es una arista cuyos extremos inciden sobre el mismo vértice.

Valencia de un vértice. Es el numero de lados que salen o entran a un vértice.

Partes de un grafo.png

Tipos de Grafos

  • Grafo simple
  • Grafos Conexos. Un grafo es conexo si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. La propiedad de un grafo de ser fuertemente conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes fuertemente conexos", es decir, porciones del grafo, que son fuertemente conexas cuando se consideran como grafos aislados.
Grafo Conexo y no conexo.jpg

Teoría de grafos

La teoría de grafos tiene sus fundamentos en las matemáticas discretas y de las matemáticas aplicadas. 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, etc, se generó toda una nueva teoría que se conoce como análisis de redes.

La teoría de grafos es una mezcla de historia, cultura y soluciones a problemas complejos desde el mundo de las matemáticas. Con esta teoría se busca representar de forma visual conjuntos de datos abstractos en formas de nodos o vértices y la unión o relaciones que estas pueden tener con otros nodos a través de aristas. Gracias a esta teoría se han podido lograr grandes avances en el análisis de amplios volúmenes de datos. Hay distintas maneras de almacenar los grafos en un computador. La estructura de datos que se utilice va a depender tanto de los rasgos del grafo, como del algoritmo que se utilice. Las estructuras más empleadas son las listas y las matrices e, incluso, combinadas. Las listas se prefieren en grafos dispersos porque hacen uso eficiente de la memoria.

Aplicaciones de la Teoría de Grafos

Al abordar aspectos básicos de la teoría de grafos se descubre que estos presentan características y prestaciones para resolver diversos tipos de problemas. Ellos brindan soluciones de dibujo computacional, perfeccionar técnicas de PERT (Program Evaluation and Review Technique –Técnica de evaluación y revisión de programas) en el área gerencial o potenciar el estudio de las relaciones en ambientes biológicos complejos.

Esta teoría permite aprovechar al máximo el potencial de las redes sociales. Con el análisis de grafos es posible comprender las relaciones, preferencias y similitudes entre los usuarios. Ha sido de utilidad para las empresas del sector, aunque se ha avanzado más en la detección de fraude bancario. Las herramientas de grafos permiten analizar miles de millones de datos de forma rápida, también pueden usarse softwares complementarios para determinar de forma eficiente comportamientos que puedan orientar a la presencia de un fraude.

Véase También

Fuentes

  • Introducción a la teoría de grafos, Jesús García Miranda. [1].
  • Teoría de grafos. Una introducción histórica-técnica, Víctor Manuel Castaño Meneses.[2]
  • UNA INTRODUCCION A LA TEORÍIA DE GRAFOS,Germán Combariza. Disponible en :[3].
  • Matemática Discreta TEORIA DE GRAFOS, Mercé Claverol, Ester Simó, Marisa Zaragozá. Disponible en: [4].