Andrés Mauricio Romero Mora. GF

TEORIA DE GRAFOS (I)

Andrés Mauricio Romero Mora. GF

UNA EXRAÑA CIUDAD

Problema de los puentes de Königsberg [Euler]

Andrés Mauricio Romero Mora. GF

La ciudad de KÖNIGSBERG

Andrés Mauricio Romero Mora. GF

Los siete puentes de KÖNIGSBERG En Königsberg se juntan dos ríos, formando una isla en su confluencia. Siete puentes unían (ya no, pues la ciudad fue parcialmente destruida durante la Segunda Guerra Mundial) las diferentes partes de la ciudad. Un ciudadano de Königsberg (Prusia) se propuso dar un paseo cruzando cada uno de los siete puentes que existen sobre el río Pregel una sola vez. Los dos brazos del río rodean a una isla llamada Kneiphof. ¿Cómo debe cruzar los puentes para realizar el paseo?

Andrés Mauricio Romero Mora. GF

DE LA CIUDAD AL GRAFO

–

Andrés Mauricio Romero Mora. GF

Teoría de Grafos (I) - Definición y terminología

• ¿Qué es un Grafo? DEF: Un grafo es una representación gráfica

de objetos y relaciones binarias entre éstos

Andrés Mauricio Romero Mora. GF

Elementos de un GRAFO

Son una terna que está compuesta por dos conjuntos finitos:

 •  un conjunto |A| aristas, (línea)•  un conjunto |V| vértices (punto - nodo)•  j una relación de incidencia, que asocia a cada

elemento de |A| un par de elementos de |V|• Se denota G = { A, V, j } 

Andrés Mauricio Romero Mora. GF

DEFINICIÓN TÉCNICA• Se denomina Grafo G al par

(V(G), E(G)), en el que V(G) es un conjunto no vacío de elementos denominados vértices, (también llamados nodos o puntos), y E(G) es un conjunto finito de pares no ordenados de elementos de V(G) denominados aristas (igualmente, líneas). Al conjunto de elementos de V(G) se le denomina conjunto de vértices, y al conjunto de elementos de E(G) conjunto de aristas A = {a, b, c, d, e, f, g, h, i, j}

V = {1, 2, 3, 4, 5}

aj {1,1}; bj {2,1}; dj {5,4}; etc...

Andrés Mauricio Romero Mora. GF

GENERALIDADES

• Se dice que dos vértices u y v de un grafo G son adyacentes si el grafo contiene una arista que los une. También se dice que son adyacentes dos vértices si tienen, al menos, un vértice en común.

1k 5 ; 2 d 4 ; 6 m 4

Andrés Mauricio Romero Mora. GF

Se denomina Grado o Valencia de un Vértice (G) al número de aristas que inciden en v.

Un subgrafo de un grafo G, es un grafo cuyos vértices pertenecen a V(G) y cuyas aristas pertenecen a E(G).

G ( 1 ) = 5 ; G ( 2 ) = 3 ; G ( 3 ) = 4 ; G ( 4 ) = 4

Andrés Mauricio Romero Mora. GF

• Vértice Aislado Es un vértice de grado cero.

• Vértice Pendiente Es aquel grafo que contiene sólo una arista, es decir tiene grado 1.

• Vértice Terminal o Punto Extremo A un vértice de grado 1 se le denomina vértice terminal o extremo.

Andrés Mauricio Romero Mora. GF

• El orden en un grafo esta determinado por el número de vértices y el tamaño por el número de aristas G orden 5 tamaño 6

G´ orden 4 tamaño 3 G`` orden 3 tamaño 3

Andrés Mauricio Romero Mora. GF

• Aristas Múltiples o Paralelas Dos aristas de un Grafo G se dice que son paralelas si tienen el mismo vértice inicial y el mismo vértice final.

• Lazo o Aristas Cíclicas Es una arista que parte

de un vértice y llega al mismo vértice.

• Cruce Son intersecciones de las aristas en puntos diferentes a los vértices.

Andrés Mauricio Romero Mora. GF

• Grafo Regular

Un grafo G simple se dice que es K-regular, si en todo vértice de G incide exactamente K-aristas, donde K es una constante.

TIPOS DE GRAFOS

Este es un Grafo 3-Regular

Andrés Mauricio Romero Mora. GF

• Grafo Sencillo o Simple

Se dice que un Grafo G es Simple si no tiene aristas cíclicas y existe una sola arista entre dos vértices.

Andrés Mauricio Romero Mora. GF

• Grafo Completo

Un Grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que componen el grafo.

• Para saber el número máximo de aristas que posee un grafo completo está dada por:

• A= (n*(n-1))/2

Andrés Mauricio Romero Mora. GF

• Grafo Nulo

Se dice que un Grafo es Nulo si todos sus vértices son aislados. Es decir el conjunto de aristas es un conjunto vacío.

Andrés Mauricio Romero Mora. GF

TAREA• Construir un grafo de orden 5 cuyos vértices tengan grados 1,2,2,3,4.

¿Cuál es el tamaño del grafo?• En un mapa de carreteras de una región aparecen 25 tramos de

carretera. Sabiendo que los cruces de carretera se producen siempre en una población y que de cada lugar parten al menos cuatro caminos, ¿Cuántos lugares aparecen en el mapa?

• Se disponen de 6 computadores y 9 cables de conexión. Se quiere que cada computador se conecte con otros 3. ¿Existe alguna forma de conectarlos?¿Es la única?

• Cuantas aristas tiene un grafo simple si sus vértices tienen los siguientes grados: 4,3,3,2,2?