Redes In Inalambricas

TEMA : Caminos y Conexión


Semana: 01
Curso:
Matemática Discreta





Caminos, distancia, ciclo

Un camino en un grafo G es una sucesión de vértices y aristas. El vértice inicial puede coincidir con el vértice final; en ese caso, el camino es cerrado. En caso contrario el camino es abierto.

Longitud de un camino es el total de aristas que lo componen. Cuandola longitud es cero el camino es trivial.

Recibe el nombre de circuito todo camino cerrado en un grafo que no repite aristas. Un ciclo es un camino cerrado sin vértices repetidos.

Un ciclo de longitud n en G recibe el nombre de n-ciclo. Cuando a un n-ciclo se le añade un vértice distintos de los que forman el ciclo pero adyacente con ellos, se forma una rueda [pic].Conectividad

Consideremos un grafo conexo que representa una red telefónica. Los vértices del grafo son "estaciones" y las ramas "conexiones". Una o más conexiones pueden fallar o pueden fallar algunas estaciones dejando a la red disconexa. Estos apuntes tratan de la conectividad de un grafo.

Definición

Sea G=(V,E) un grafo conexo. Decimos que u V es un vértice de corte si G\u es disconexo.Decimos que e E es una rama de corte si G\e es disconexo.

Lema 1

u es un vértice de corte sii existe v y w en G tal que todo camino de v a w pasa por u.

Demostración

Si se da la condición al suprimir u no hay camino entre v y w así que G se desconecta. Si al suprimir u no se da la condición eso significa que todo v, w están unidos por un camino así que G\u sería conexo.Ejercicio


e es una rama de corte sii existe v y w tal que todo camino de v a w pasa por e.

Si no existe un vértice de corte en un G conexo se necesitará suprimir más de un vértice para desconectar G. Si no existe una rama de corte se necesitará suprimir más de una rama para desconectar G. Esto nos lleva a la siguiente definición.





Definición

Llamamos conectividad (G)al mínimo número de vértices que deben suprimirse para desconectar a G o reducirlo a un vértice.

Si G tiene un vértice de corte entonces =1. (K3)= 2.

Llamamos -conectividad (G) al mínimo número de ramas que deben suprimirse para desconectar a G. Por ejemplo, si G tiene una rama de corte entonces =1. (K3)=2.
Indicamos con (G) al mínimo de grad(u) para uV. Tenemos que (K3)=2

Ejemplo Consideremos Kn. Si suprimimos un vértice se reduce a Kn-1. Si suprimimos n-1 vértices se reduce a un vértice. Por lo tanto, (Kn)=n-1. (Kn)=n-1 porque para aislar un vértice debemos suprimir todas las ramas que inciden en él. También se tiene que (Kn)=n-1. Concluimos que (Kn)= (Kn)= (Kn)=n-1.

Ejemplo de =2, =3, =4Lema 2

(G) (G) (G)

Demostración

Consideremos un vértice de grado (G). Si suprimimos las ramas que inciden en él quedará aislado. Por lo tanto, (G) (G).

Supongamos que e1,...,en desconectan a G donde n= (G). Sean v1,...,vn extremos de las ramas mencionadas. Entonces suprimiendo dichos vértices se desconecta G. Por lo tanto (G) n υ



DefiniciónUn grafo conexo se dice biconexo si para desconectarlo no alcanza con suprimir un vértice, es decir, si no tiene vértices de corte. O también si 2.



Teorema 3 (Whitney)

Sea G conexo con V 3. G es biconexo sii para cualesquier u, v existen dos caminos disjuntos que los unen (sii cualesquier u, v están contenidos en un mismo ciclo).Demostración

Supongamos que existen 2 caminos disjuntos pero no fuera biconexo. Entonces hay un vértice de corte u y dos vértices, tal que todo camino de v a w pasa por u. Contradiccion.

Supongamos ahora que G es biconexo: queremos mostrar que hay 2 caminos disjuntos entre dos vértices.

a) Si u y v son adyacentes y no hubiera otro camino entonces la supresión de...