Infografía Grafos

Teoria de grafos

Grafo

Es un conjunto de vértices unidos a través de líneas llamadas aristas.

Medida de un grafo

Tipos de grafos

No conexo

Conexo

Camino:Es el recorrido que se realiza de un vertice a otro vertice a través de las aristas

Camino en un grafo

Circuito: Es el recorrido que se realiza a través de la aristas, que inicia y ternima en el mismo vértice.

Circuito en un grafo

Origen

Medida de un grafo

Un grafo se mide de acuerdo al número de vértices, arista y lazos que tenga

Vértices: 6 Aristas: 7 Lazos: 0

Vértices: 6 Aristas: 7 Lazos: 1

Ejemplos

Ejercicio

Considerando las siguientes imagenes determina el tipo y tamaño de cada grafo.

Regresar

Teoria de grafos

Origen de la teoria

El problema de los siete puentes

Mapa de Königsberg en la época de Leonhard Euler, que muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en celeste).

01

02

04

03

05

06

Nota

Regresar

El problema de los siete puentes

La teoría de grafos se inició gracias a un problema turístico que resolvió Leonhard Euler. Dice la historia que en 1736 el eminente matemático se detuvo, en uno de sus viajes en K ̈nigsberg, hoy Kaliningrado situada junto al río Pergel en la costa del Mar Báltico, en la Prusia oriental (Rusia), famosa por sus puentes, ya que cuenta con siete de ellos que unen a la Isla Mayor con la margen derecha y otros dos con la margen izquierda. La Isla menor está conectada por dos puentes a cada lado y el séptimo puente une ambas islas.

Grafo no conexo o disconexo:

Es aquel grafo de esta formado por dos o mas partes (no todos sus vértices esta unidos entre sí).

La ordenada y lógica mente matemática de Euler plantea el siguiente problema: ¿Será posible planear un paseo de manera que saliendo de casa cruce los siete puentes una sola vez cada uno antes de regresar a casa?

Grafo conexo:

Se define como aquel grafo que tiene todos sus vértices unidos a través de aristas.