Hola vamos con más materia de matemáticas discreta que de discrena nada de nada
Sesión correspondiente al día (23/11/2010).
-
Relación entre grados y aristas: teorema y grafo corolario
Teorema
1.Sea G = (V, A) un grafo, entonces:
Σ dG(v) = 2card(A)
Recordamos que:
-La cardinalidad es el número de elementos de un conjunto.
–d g (V):número de aristas incidentes con un vértice. Cada bucle cuenta por dos.
Σ ds(v) = Σ de(v) = card(A)
Corolario
El número de vértices de grado impar de un grafo es par.
-
Caminos y conexión
Definiciones: Sea G un grafo no dirigido:
1. Una cadena es una sucesión finita W = v0e1v1….ekvk cuyos términos son alternativamente vértices y aristas.
2. La longitud de una cadena es el número de aristas que contiene.
3. Una cadena simple es una cadena con todas sus aristas distintas.
4. Un camino es una cadena con todos sus vértices distintos.
5. Una cadena cerrada es una cadena de longtud no nula en donde el vértice inicial y final coinciden.
6. Un ciclo es una cadena simple cerrada con todos sus vértices distintos.
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.
7. Diremos que dos vértices u y v están conectados si existe un camino de u a v y viceversa.
8. Un grafo es conexo si todo par de vértices están conectados.
9. Un grafo dirigido es débilmente conexo si su grafo no dirigido asociado es conexo.
EJEMPLOS
·Cadena
·Longitud: la longitud del grafo anterior sería 2.
·Cadena simple: la siguiente sería una cadena simple.
Tenemos el siguiente grafo:
Vamos a ver las distintas propiedades y ver el tipo de grafo:
a) ¿Es dirigido?
Sí lo es, como vemos tiene arcos.
b) ¿Es simple?
Sí porque no hay ningún vértice con dos arcos de la misma dirección.
c) ¿Completo?
No es completo ya que no todos los vértices están conectados con todos.
d) ¿Bipartido?
No es bipartido pues no podemos hacer dos conjuntos en los cuales no hayan uniones entre vértices.
e) Grados
| Vértice | de(v) (entrantes) | ds(v) (salientes) |
| V1 | 1 | 1 |
| V2 | 2 | 3 |
| V3 | 1 | 2 |
| V4 | 1 | 2 |
| V5 | 4 | 1 |
| V6 | 1 | 1 |
CONEXIÓN
Conexo: un grafo es conexo si todo par de vértices está conectado.
Débilmente conexo: Cuando un grafo dirigido no es conexo se puede ver si es débilmente conexo, para ello veremos si su grafo no dirigido asociado es conexo. En el caso que lo sea se podrá decir que el grafo es débilmente conexo. El grafo asociado es el mismo grafo pero no dirigido, es decir, pierde los arcos y los sustituye por aristas.
Relación binaria: Sea G=(V,A) no dirigido. En V se define la relación binaria /R: u y v ε V, u Rv, si u y v están conectados.
R= relacionado.
R es una relación de equivalencia–> determinada partición en {V1, V2,…Vv}
A cada subgrafo de G: G[V1], G[V2]…..G[R] determinado por el conjunto de vértices de cada clase de equivalencia de la relación R se le llama componente conexa del grafo G.
Las posibles relaciones son:
Conexón u->v:
1-Reflexiva: uRv
2-Simétrica: uRv, vRu
3- Transitiva: uRv, vRt, uRt
Si un grafo no es conexo, se dividirá en subgrafos que sí lo sean y que a su vez estén conectados.
Se dividirá el grafo en componentes conexas que son los mayores subgrafos conexos de un grafo G.
Cada vértice del grafo sólo puede pertenecer a una componente conexa.
Por hoy ya esta bién mañana más, to-morrow un montón y a vivir que son two days….