Relaciones

5. Relaciones
Una relación , de los conjuntos es un subconjunto del producto cartesiano

Una Relación binaria es una relación entre dos conjuntos.
El concepto de relación implica la idea de enumeración, de algunos de los elementos, de los conjuntos que forman tulas.

Un caso particular es cuando todos los conjuntos de la relación son iguales: en este caso se representa como ,pudiéndose decir que la relación pertenece a a la n.


5.1 conceptos básicos
• Conexión de grafos. En efecto, si tomamos 2 vertices cualquiera, siempre hay 2 caminos distintos (sin vertices comunes a excepción de los vertices extremos) que los conectan. Luego, por el Teorema de Whitney (1932), los ciclos tienen índice de conexión: .
Los ciclos son también 2-conexo por aristas, en efecto, dado 2vertices cualquiera, siempre hay 2 caminos distintos (sin aristas comunes entre ambos) que los conectan. Luego, por el Teorema de Menger (1927), los ciclos tienen índice de arista conexión: .
Los ciclos al tener el índice de arista conexión igual a 2 carecen de aristas puentes.

• Grafos eulerianos y hamiltonianos.
Euleriano
En efecto, los ciclos al ser conexos y 2-regulares satisfacen elTeorema de Euler(1736)-Hierholzer(1873). Luego, los ciclos contienen un Circuito euleriano.
Hamiltoniano
Es fácil ver que también contienen un ciclo hamiltoniano.



• Grafos planos.
En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser"incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.
Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de genero arbitrario. En esta terminología, los grafos planos tienen genero 0, por ser elplano y la esfera de genero 0

• Árboles.
En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.
• Grafos dirigidos.
Un grafo dirigido o digrafo es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida1, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.
Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos , donde:
• , un conjunto no vacío de objetos simples llamados vértices o nodos.
• es un conjunto de pares ordenados de elementos de denominados aristas o arcos, donde por definición un arco va del primernodo (a) al segundo nodo (b) dentro del par.
A veces un digrafo es denominado digrafo simple para distinguirlo del caso general del multigrafo dirigido, donde los arcos constituyen un multiconjunto, en lugar de un conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de arcorepresenta relaciones de amistad mientras que el otro tipo representa mensajes enviados recientemente entre los nodos), o por un atributo como por ejemplo su importancia o peso.
A menudo también se considera que un digrafo simple es aquél en el que no están permitidos los bucles. Un bucle es un arco que une un vértice consigo mismo.







5.2 "Propiedades de las relaciones"

Propiedadreflexiva:
Una relación es reflexiva si se observa que para todos los valores a:
un R
En otras palabras, todos los valores están relacionadas entre sí.
La relación de igualdad "=" es reflexiva. Obsérvese que para, por ejemplo, todos los números a (el dominio es R):
a = a
por lo que "=" es reflexiva.
En una relación reflexiva, que tienen flechas para todos los valores en el dominio que apuntan...