Grafos

[pic 1]UNIVERSIDAD DE CÓRDOBA

FACULTAD DE INGENIERÍAS

PROGRAMA DE INGENIERÍA DE SISTEMAS

ASIGNATURA:

TEORIA DE GRAFOS

ACTIVIDAD N°1

DOCENTE:

ING. MARIO MACEA ANAYA

ESTUDIANTE:

JESUS ANTONIO RAMIREZ CORREA

LORICA – CORDOBA

2015

Tenemos el siguiente interrogante:

Si existe una cadena en un grafo , diremos que  está conectado con . La relación “estar conectado”, definida sobre el grafo  es una relación de equivalencia, ¿Por qué? [pic 2][pic 3][pic 4][pic 5][pic 6]

Respuesta

Por definición Las relaciones de equivalencia son relaciones entre los elementos de un conjunto cualquiera y su característica principal es que abstraen el concepto de igualdad. Se caracterizan porque satisfacen las propiedades de: reflexividad, simetría y transición.

Demostración 

Sea el grafo  y definimos en el conjunto  de sus vértices la siguiente relación:[pic 7][pic 8]

[pic 9]

Veamos que esta relación es de equivalencia.

1.  Reflexividad. Sea  cualquiera de  . Entonces, la cadena  conecta  con , luego [pic 10][pic 11][pic 12][pic 13][pic 14][pic 15]

Es decir, R es reflexiva.

Consideremos el siguiente grafo conexo:

[pic 16]

En pocas palabras lo que nos dice esta característica (reflexividad) es que si tenemos un grafo conexo, podemos partir de un vértice y llegar al mismo vértice.

Por ejemplo:

Partimos de Lorica y llegamos a cerete

[pic 17]

Luego nos movemos de Cerete a Sahagún

[pic 18]

Finalmente nos movemos de Sahagún a Lorica

[pic 19]

Como vemos, partimos de Lorica y llegamos a Lorica.

1. Simetría. Sean  y  dos elementos cualesquiera de  . Entonces,[pic 20][pic 21][pic 22]

[pic 23]

Luego,

[pic 24]

Es decir, R es simétrica.

Consideremos el grafo del punto anterior.

[pic 25]

Esta propiedad descrita hace referencia a que si podemos ir de un vértice 1 a un vértice 2, también podemos ir del vértice 2 al vértice 1.

Por ejemplo:

Si podemos ir de Lorica a Sahagún

[pic 26] 

Se puede también ir de Sahagún a Lorica

[pic 27]

1. Transitividad. Si ,  y  son tres vértices cualesquiera de , entonces[pic 28][pic 29][pic 30][pic 31]

[pic 32]

Bastaría, pues, con unir las cadenas  y . Por lo tanto, [pic 33][pic 34]

[pic 35]

Es decir, R es transitiva.

...