En clase teoria, seguimos viendo los diferentes tipos de grafos, asi como sus caracteristicas:
Material dado en clase:
TEOREMA:
1. Sea G=(V, A) un grafo dirigido, entonces:
Σ ds(v)= Σ de(v)= card (A) -> ( cardinal: número de elementos que tiene un conjunto )
2. Sea G=(V, A) un grafo dirigido o no, entonces:
Σ dg(v)=2 card (A)
Corolario: el número de vértices de grado impar de un grado es par.
Definiciones:
- Una cadena es una sucesión finita W=v0e1v1…….ekvk cuyos términos son alternativamente vértices y aristas.
- La longitud de una cadena es el número de aristas que contiene.
- Una cadena simple es una cadena con todas sus aristas distintas.
- Un camino es una cadena con todos sis vértices distintos.
- Una cadena cerrada es una cadena de longitud no nula en donde el vértice inicial y final coinciden.
- Un ciclo es una cadena simple cerrada con todos sus vértices internos distintos.
- Un grafo es bipartido si no tiene ningún ciclo impar.
En el grafo anterior:
Cadena: C1=v1 e1 v2 e2 v3 e3 v5 e6 v2 Esta cadena es simple con unalongitud de 4.
Cadena: C2=v2 e6 v5 e7 v4 e4 v2 e1 v1 e1 v2 Esta cadena es cerrada.
Cadena: C3=v1 e1 v2 e2 v3 e3 v5 Esta cadena es un camino.
Cadena: C4=v2 e4 v4 e7 v5 e3 v3 e2 v2 Esta cadena es un ciclo par(longitud de 4).
Estos conceptos son los mismos para grafos dirigidos salvo que las direcciones de los arcos deben concordar con la dirección del camino o cadena. En el caso dirigido el ciclo recibe el nombre de circuito.
- Diremos que dos vértices u y v están conectados si existe un camino de u a v y viceversa.
- Un grafo es conexo si todo par de vértices están conectados.
- Un grafo dirigido es débilmente conexo si su grafo no dirigido asociado es conexo.
La relación de conexión es de equivalencia y por tanto determina una partición en el conjunto de vértices. A los elementos de dicha partición se les denomina componentes conexas del grafo. Un grafo es conexo si y sólo si el número de componentes conexas es 1.
EQUIVALENCIA:
Conexión:
u → v
Transitiva:
u → v
v → t
u → t
Reflexión:
u R u
Simétrica:
u R v
v R u
——————
Hasta aqui la entrada de hoy!!!! hasta la semana que viene!!!!! xD