Diferencia entre revisiones de «Grafo»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Deshecha la edición 30765389 de 190.40.184.135 (disc.) |
||
Línea 2:
[[Imagen:6n-graf.svg|thumb|250px|Grafo etiquetado con 6 vértices y 7 aristas.]]
En [[matemática]]s y [[ciencias de la computación]], un '''grafo''' (del [[Idioma_griego|griego]] ''grafos'': dibujo, imagen) o '''gráfica''' es el principal objeto de estudio de la [[Teoría_de_grafos|teoría de grafos]].
Informalmente, un grafo es un conjunto de objetos llamados [[Vértice (teoría de grafos)|vértices]] o [[Vértice (teoría de grafos)|nodos]] unidos por enlaces llamados [[Arista (teoría de grafos)|aristas]] o [[Arista (teoría de grafos)|arcos]], que permiten representar [[Relación binaria|relaciones binarias]] entre elementos de un [[Conjunto|conjunto]].
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
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 [[Terminal de computadora|terminales]] y las aristas representan conexiones (las cuales, a su vez, pueden ser [[cable]]s o [[Red inalámbrica|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|ciencias sociales]].
== Historia y problema de los puentes de Königsberg ==
[[Imagen:Konigsberg bridges.png|frame|right|Los siete puentes de Königsberg.]]El primer artículo científico relativo a grafos fue escrito por el [[matemático]] [[Suiza|suizo]] [[Leonhard Euler]] en 1736. Euler se basó en su artículo en el ''[[problema de los puentes de Königsberg]]''. La ciudad de [[Kaliningrado]], originalmente ''Königsberg'', es famosa por sus siete [[puente]]s que unen ambas márgenes del río [[Pregel]] con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible, partiendo de un lugar arbitrario, regresar al lugar de partida cruzando cada puente una sola vez?
| |||