Embedded Files
Definición de teoría de grafos
Definición de teoría de grafos
La teoría de grafos es una teoría matemática la cuál estudia las propiedades de los grafos.
¿Qué es un grafo?
¿Qué es un grafo?
A simple vista, puede parecer que un grafo son solo puntos unidos por rayas. Pero un grafo es un conjunto matemático formado por dos conjuntos, vértices o nodos, los cuales representamos con puntos y aristas o arcos que representamos con rayas que unen los vértices. Este conjunto nos permite representar relaciones binarias entre elementos de un conjunto.
El problema de los puentes de Königsberg
El problema de los puentes de Königsberg
Para poder hablar sobre este problema, debemos remontarnos a 1736, cuando el matemático Leonhard Euler escribió el primer artículo relacionado con los grafos de la historia. Para escribir este artículo, se basó en el problema que acabamos de decir, el problema de los puentes de Königsberg. Gracias a este artículo mucha gente pudo entender los grafos sin tener demasiado conocimiento en matemáticas.
¿Qué era este problema? Muy simple, era un problema en el que se planteaba la posibilidad de dar un paseo por la ciudad de Königsberg, la cual contaba con siete puentes comenzando desde cualquier parte de la ciudad, pasando por todos los puentes, recorriendo solo una vez cada uno, y regresando al mismo punto de partida. Aunque parezca un problema muy simple, el problema duró años en resolverse hasta que Euler utilizó el primer grafo de la historia, dando paso a la teoría de grafos. Con este grafo descubrió que era imposible, pero lo más importante no fue el hecho de haberlo resuelto sino la forma en que lo resolvió, con un grafo. Gracias a él el álgebra computacional de hoy en día es lo que es y podemos resolver problemas matemáticos, por ejemplo matrices.
Transformación del problema de los puentes de Königsberg a grafo.
Propiedades de los grafos
Propiedades de los grafos
Como ya hemos podido observar los grafos son un mundo por sí solo. Entre las principales propiedades que posee un grafo está la adyacencia. La adyacencia se trata de la relación que existe entre dos aristas que comparten la conexión o relación con un vértice común.
También debemos entender las propiedades de ponderación de los grafos que corresponden a una función en la que cada arista es clasificada, cuantificada en diversos términos para aumentar la expresividad de modelo.
Y por último el etiquetado, que trata de la distinción que se realiza en los vértices mediante una marca que los hace distinguible de otros.
La valencia de un grafo
La valencia de un grafo
Llamamos valencia de un vértice al número de aristas que salen de él (número de aristas en las que interviene dicho vértice).
En cualquier grafo siempre tiene que haber, al menos, 2 vérticecon la misma valencia. Esto se demuestra gracias al principio del palomar, el cual asegura que, si tenemos más palomas que palomares, en alguno de estos habrá que meter más de una paloma. Aunque parece una afirmación simple, en la práctica son muchas las consecuencias que se pueden deducir de este principio.
Partes de un grafo
Partes de un grafo
Los grafos son estructuras discretas que constan de vértices y aristas que conectan entre si esos vértices. Por lo tanto un grafo G consta de dos partes:
Conjunto V:
El conjunto V es lo que vulgarmente describimos como puntos, a los que como hemos dicho anteriormente llamamos vértices o nodos. Un vértice o nodo es la unidad fundamental de la que están formados los grafos.
Conjunto E:
El conjunto E es lo que conocemos comúnmente como rayas pero que llamamos aristas o arcos. Así como el vértice es la unidad fundamental de la que se forman los grafos, las aristas se utilizan para establecer relaciones entre sujetos, ya sean personas, animales, lugares o situaciones. Pero sin unir esos vértices con aristas sólo podríamos hacer grafos triviales, los cuales representan el aislamiento del vértice, así que de poco nos serviría esta herramienta que son los grafos sin las aristas.
Así pues, concluyendo tenemos que una arista no puede ir sola, por lo tanto el vértice es el elemento fundamental del grafo, pero para poder establecer conexiones de unos a otros que es lo que queremos es tan necesario el conjunto V como el conjunto E.
Page updated
Report abuse