Grafo

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Grafo» – noticias · libros · académico · imágenes Este aviso fue puesto el 29 de mayo de 2015.

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)^[1]​ es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.^[2]​ Son objeto de estudio de la teoría de grafos.^[3]​

Típicamente, un grafo se representa gráficamente como un conjunto de puntos unidos por líneas (aristas o arcos).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Por lo general, un grafo se representa en forma de diagrama como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes. Los grafos son uno de los objetos de estudio de las matemáticas discretas.

Los bordes pueden ser dirigidos o no dirigidos. Por ejemplo, si los vértices representan personas en una fiesta y hay un borde entre dos personas si se dan la mano, entonces este grafo no está dirigido porque cualquier persona A puede darle la mano a una persona B solo si B también le da la mano a A. Por el contrario, si una ventaja de una persona A a una persona B significa que A le debe dinero a B , entonces este grafo es dirigido, porque la deuda no es necesariamente recíproca.

Los grafos son el tema básico estudiado por la teoría de grafos. La palabra «grafo» (en inglés, graph) fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 debido a una relación directa entre las matemáticas y la estructura química (lo que él llamó una imagen químico-gráfica).^[4]​^[5]​

La teoría de grafos nació en 1736 a través de un artículo científico escrito por el matemático suizo Leonhard Euler, donde resolvió el problema de los puentes de Königsberg utilizando los conceptos actualmente conocidos como caminos y grado sobre multigrafos.

1. ↑ Real Academia Española. «grafo : Diagrama que representa mediante puntos y líneas las relaciones entre pares de elementos y que se usa para resolver problemas lógicos, topológicos y de cálculo combinatorio.». Diccionario de la lengua española (23.ª edición). Consultado el 14 de agosto de 2019. 
2. ↑ Trudeau, Richard J. (1993). Dover Pub., ed. Introduction to Graph Theory (Edición corregida y aumentada.). ISBN 978-0-486-67870-2. 
3. ↑ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. edición). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archivado desde el original el 5 de mayo de 2019. Consultado el 8 de agosto de 2012. «A graph is an object consisting of two sets called its vertex set and its edge set.» 
4. ↑ See:
   • J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Archivado el 12 de abril de 2023 en Wayback Machine. Nature, 17 : 284. doi 10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
   • J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Archivado el 4 de febrero de 2023 en Wayback Machine. American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi 10.2307/2369436. JSTOR 2369436
   . The term "graph" first appears in this paper on page 65.
5. ↑ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 35. ISBN 978-1-58488-090-5. Archivado desde el original el 4 de febrero de 2023. Consultado el 16 de febrero de 2016.