Unidad #5: Grafos

Unidad #4

Teoría de Grafos

Lcda. Tatiana Quezada. Msc

Pueden unir cuatro puntos sin levantar el lápiz?Pueden hacer un triángulo con una línea en el medio, sin levantar el lápiz?

Introducción

Grafos

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)​ 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.

Representación

Se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas o arcos).

Estudian las interrelaciones entre unidades que interactúan unas con otras

Definiciones básicas

• Aristas: Son las líneas que unen los vértices de un grafo.
• Aristas adyacentes: Dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas paralelas: Dos aristas son paralelas si los vértices iniciales y finales son el mismo vértice
• Aristas cíclicas: Aristas que parten de un vértice para entrar en el mismo.
• Cruce: Punto donde dos aristas se cruzan.
• Vértices: Los vértices son los elementos que forman un grafo. Cada uno lleva asociada una valencia característica según la situación, que se corresponde con la cantidad de aristas que confluyen en dicho vértice.
• Camino: Se denomina camino a un conjunto de vértices interconectados por aristas. Dos vértices están conectados si hay un camino entre ellos.

Historia

Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución

Leonhard Euler en 1736

Problema de los puentes de Königsberg.

¿Es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?

De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como «grado» al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par.

Estructura

Un grafo G es un par ordenado G=(V,E), donde:

V es un conjunto de vértices o nodos.

El grado de un vértice es el número de arcos que inciden en un vértice g(x)

E es un conjunto de aristas o arcos, que relacionan estos nodos.

Un grafo formado exclusivamente por vértices aislados es un grafo vacío.

El Lema del apretón de manos determina que la suma de los grados de un grafo simple (es decir, sin bucles) y no dirigido equivale al doble de su número de aristas:

Un bucle es una arista que relaciona al mismo nodo

Se llama orden del grafo G a su número de vértices IVI

Tipos de grafos principales

VS

No dirigido

Dirigido

Caracterización de grafos

una arista cualquiera es la única que une dos vértices específicos.

Es un grafo simple donde cada par de vértices está conectado por una arista. Tiene n(n-1)/2 aristas

si cada par de vértices está conectado por un camino

+ Simple

+ Conexo

+ completo

Representación de Grafos

Representar el siguiente grafo por medio de conjuntos, matriz de adyacencia, incidencia, secunecia de grafos y lista de adyacencia

Grafos

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)​ 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.

Escribe untítulo aquí

Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh.

Escribe un título aquí

Grafo no drigido

1. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
2. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
3. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
4. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.

1. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
2. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
3. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
4. Lorem ipsum dolor sit amet, consectetuer adipiscing elit.

VS

Procesos

Paso 3

Paso 2

Paso 1

Euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation.

Euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation.

Euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation.

+ Info

+ Info

+ Info

Galería

Euismod tincidunt

Euismod tincidun

Euismod tincidunt

Euismod tincidunt

Euismod tincidunt

Euismod tincidunt

Escribe un título aquí

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut sit amet egestas sem, tempor venenatis augue. Praesent et lacus quis ante interdum tempus. Cras et enim facilisis, posuere ipsum in, aliquam velit.

+ info

" Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat "

Nombre autor/a

Escribe tu sección aquí

Escribe un subtítulo aquí

+ 190

Escribe un título genial aquí

Lorem ipsum dolor sit amet, consectetuer adipiscing

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut sit amet egestas sem, tempor venenatis augue. Praesent et lacus quis ante interdum tempus. Cras et enim facilisis, posuere ipsum in, aliquam velit.

+ 45k

Lorem ipsum dolor sit amet, consectetuer adipiscing

+ 85k

Lorem ipsum dolor sit amet, consectetuer adipiscing

+ info

Gráficos

título aquí

título aquí

título aquí

9.280

17.520

17.520

Tabla

Vídeo

Lorem Ipsum

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut sit amet egestas sem, tempor venenatis augue. Praesent et lacus quis ante interdum tempus.

+ info

35%

Mapa

25%

Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh.

Lorem ipsum dolor sit amet

Equipo

Nombre

Nombre

Nombre

Nombre

Lorem ipsum dolor sit amet, consectetuer

Lorem ipsum dolor sit amet, consectetuer

Lorem ipsum dolor sit amet, consectetuer

Lorem ipsum dolor sit amet, consectetuer

¡Gracias!