Homomorfismos de grafos

HOMOMORFISMOS DE GRAFOS Y SEMIGRUPOS SOBRE REDES DE RELACIONES DOUGLAS R. WHITE y KARL P. REITZ

1. Redes de relaciones simples 1.1 Los grafos y sus imágenes

Definición 1. Un grafo (al que normalmente nos referiremos como digrafo) es un par ordenado G = (P, R) donde P es un conjunto finito de puntos (puntos, objetos, actores) y R es una relación (un tipo de vínculo) definida sobre P, estoes, un subconjunto de pares ordenados de puntos perteneciente a P × P. Definición 2. Una función f: P→ P′ es una aplicación de cada elemento a perteneciente al conjunto P en un elemento imagen f(a) perteneciente al conjunto P′. Una función suprayectiva es una aplicación en la que todos los elementos de P′ son imágenes de elementos de P. Definición 3. Una equivalencia ≡ definida sobre P es unarelación tal que para cualesquiera a, b y c pertenecientes a P, se cumple que a≡a si a ≡ b entonces b ≡ a si a ≡ b y b ≡ c entonces a ≡ c Estas son las propiedades reflexiva, simétrica y transitiva. Lema 1. Toda función f: P→ P′ produce una relación de equivalencia ≡f sobre P, esto es, que para cualesquiera a, b ∈ P, a ≡f b si y solo si f(a) = f(b). La prueba de este lema puede encontrarse en los textosal uso. Todas las demás pruebas de lemas y teoremas se ofrecen en el Apéndice. Definición 4. Sea G = (P, R) un grafo y f: P→ P′ una aplicación suprayectiva. Sea R′ una relación definida en P′ tal que R′ = {(f(a), f(b)) : (a, b) ∈ R}. Decimos que R′ es la relación de P′ producida por R y f.

1.2

Homomorfismos de grafos e imágenes de blockmodel

Los homomorfismos son aplicaciones quepreservan la estructura. El mínimo homomorfismo de un grafo es una función que transforma los puntos de un grafo en

puntos en una imagen del grafo y preserva las aristas o conexiones como aristas o conexiones imagen. Expresado en forma de diagrama: Grafo: Todas las aristas  f → Imagen: Arista (Homomorfismo)

Hay diferentes tipos de homomorfismos que preservan rasgos adicionales de la estructurade un grafo. La estructura que se preserva puede definirse de acuerdo con las propiedades de f en términos de su aplicación inversa f-1 desde la imagen a la preimagen a través de diferentes tipos de homomorfismos. Más abajo se ofrecen las definiciones formales de los tipos de homomorfismos que resultan más útiles en el análisis reticular de las estructuras de roles. Comenzaremos con el homomorfismocompleto en el que cada arista de la imagen está producida por alguna arista en la preimagen. Dado que no hay en la imagen aristas que vengan de fuera, este y todos los homomorfismos que vienen a continuación generan el modelo estructural de una red. Los homomorfismos regulares y estructurales son modelos de especial importancia en el estudio de los sistemas de roles. En el caso de unhomomorfismo regular, los puntos que tienen la misma imagen necesariamente ocupan la misma posición abstracta o “rol” en la red total o grafo. Dos puntos tienen la misma imagen (rol) en un homomorfismo regular si y solo si, cuando uno tiene una relación con un segundo conjunto imagen (o rol), el otro tiene una relación idéntica con un homólogo en ese conjunto. Este es el principio de los paralelos de rol.Dos puntos tiene la misma imagen en un homomorfismo estructural si y solo si están relacionado de manera idéntica a todos los demás puntos. Definición 5. Sean G =(P, R) y G′ =(P′, R′) dos grafos, f G → G′ es un homormorfismo del grafo completo si y solo si f: P→ P′ es una aplicación suprayectiva tal que para cualesquiera a, b ∈ P y x, y ∈ P′ aRb implica que f(a) R′ f(b), y xR′y implica que existenc,d ∈ P tales que cRd, f(c)=x, y f(d)=y. A la imagen homomórfica completa de un grafo, BOORMAN, ARABIE y LEAVITT (1978:31-32) la han denominado blockmodel. Proposición A. Sean G =(P, R) un grafo y f: P→ P′ una aplicación suprayectiva en un conjunto P′. Si R′ es la relación definida sobre P′ que ha sido inducida por f y R, y G′=(P′, R′), entonces la aplicación f G → G′ es un homormorfismo del...