Grafos

Grafos
Apoyo SSD5

Grafos en el Mundo Real
Existen muchos ejemplos de grafos en el mundo real. Tu puedes estar usando precisamente ahora, uno de estos ejemplos, Internet. Las redesinterconectadas que forman Internet son ejemplos comunes de un grafo.

Mtl Lourdes Cahuich

2

Grafos en el Mundo Real
Las computadoras forman los nodos del grafo. Como no toda máquina está conectada acualquier otra máquina, estas ligas entre máquinas también son parte del grafo.

Mtl Lourdes Cahuich

3

Grafos en el Mundo Real
Cada liga entre un par de computadoras puede ser directa oindirecta, dependiendo de si los mensajes pueden ser enviados solamente en una dirección o en ambas.

Mtl Lourdes Cahuich

4

Mtl Lourdes Cahuich

5

Definición de Grafos
Un grafo dirigidoconsiste en un conjunto V de vértices o nodos y un conjunto E de aristas (edges). Cada arista tiene un nodo origen y un nodo destino, y la arista puede ser recorrida solamente de origen al destino.

MtlLourdes Cahuich

6

Mtl Lourdes Cahuich

7

Definición de Grafos
Muchas de las operaciones básicas de un grafo, giran alrededor de la existencia de una ruta (path). Una ruta es cualquiersecuencia de nodos conectados por las aristas. El número de aristas en una ruta es la longitud de la ruta

Mtl Lourdes Cahuich

8

Definición de Grafos
Por lo general, uno se enfrenta con grafosno dirigidos en donde cada arista puede ser recorrida en cualquier dirección. Una arista no dirigida puede ser vista como un par de aristas dirigidas, por lo que nos enfocaremos en el caso dirigidoMtl Lourdes Cahuich

9

Mtl Lourdes Cahuich

10

Definición de Grafos
Tal vez la característica más atractiva de los grafos es que éstos pueden ser identificados visualmente, y lasimágenes de grafos son a menudo útiles para motivar y describir propiedades importantes.

Mtl Lourdes Cahuich

11

Definición de Grafos
Los algoritmos de grafos usualmente se entienden mejor junto...