Ambigüedad en la definición de homomorfismo gráfico.

Question

Gráfico dado $G$ $H$ y una función entre el $f : G \rightarrow H$ entre el vértice de conjuntos, podemos decir que $f$ es un gráfico homomorphism iff para todos los vértices $x$ $y$ $G$ tal que $xy$ es un borde de $G$, sostiene que $f(x)f(y)$ es un borde de $H$.

Sin embargo, algunos autores definen los gráficos como el no tener bucles, mientras que otros permiten a los bucles. Estos conducen a diferentes nociones de homomorphism. Hay un correcto?

En particular, rechazando bucles conduce a una más estricta de la noción de homomorphism, porque significa que si $f$ es un homomorphism, a continuación, para todos los vértices $x$ $y$ $G$ tal que $xy$ es un borde de $G$, sostiene que $f(x) \neq f(y)$. (Porque de lo contrario $f(x)f(y)$ sería un bucle en $H$).

Por otro lado, lo que permite bucles conduce a una más leve noción de homomorphism: en virtud de esta definición, un homomorphism puede contraer una enorme gráfico de $G$ a un pequeño gráfico de $H$ con sólo un vértice y uno de los bordes.

Answer 1

Su observación de que los extremos de una arista no se puede asignar a un mismo vértice si uno no permite bucles (es decir, considera sólo los gráficos sin bucles) proviene de la propiedad que $H$ no tiene bucles. Permitiendo no inyectiva mapa (vértice) todavía no puede llevar a un colapso si $H$ no tiene ningún adecuado de bucles. Tenga en cuenta que todavía tenemos no inyectiva homomorphisms por ejemplo, cuando la asignación de ciclo de gráficos de $C_6\to C_3$ por ejemplo, de modo tal de "colapso" en sí mismo no es un problema per se.

Sin embargo, con los no-gráficas simples, es decir, si permitimos que los bucles y tal vez también de múltiples aristas (posiblemente dirigida), me gustaría sugerir a definir un morfismos como un mapa de $f\colon V_G\to V_H$ en los vértices junto con un mapa de $g\colon E_G\to E_H$ en los bordes, que si $e$ es un borde de$v$$w$, $g(e)$ es un borde de $f(v)$ $f(w)$.

Answer 2

La definición es la misma en ambos casos: con o sin bucles. La pregunta es si usted desea aplicar a los gráficos sin bucles, o gráficos con bucles (o incluso gráficos). Técnicamente tenemos una selección de categorías, cada una con sus propias colecciones de los resultados y teoremas. Puedes elegir la clase de "gráficos" se va a trabajar.

La mayoría de la gente conoce en primer lugar es gráficos sin bucles, y los problemas que surgen no pueden ser vistos como generalizaciones de colorear problemas.