Grafos Isomorfos

Grafos Isomorfos

1. Revisão complementar de funções (veja seu material sobre conjuntos para maiores detalhes)

Para entendermos melhor o problema de analisar e descobrir isomorfismos em grafos é necessário revermos algumas propriedades das funções. A definição de uma função inclui três: o conjunto domínio S, o conjunto contradomínio T e a associação propriamente dita (veja figuras no seu seu material sobre conjuntos). Veja ilustração a seguir

ou seja, uma função f de S em T, é um subconjunto de ST onde cada elemento de S aparece exatamente uma única vez como primeiro componente de um par ordena (s,t). S é o domínio e T é o contradomínio da função. Se o par ordenado (s,t) pertence à função, então f é denotado por f(s); t é a imagem de s por f, s é a pré-imagem de t por f, e diz-se que f leva s em t. Para A  S, f(A) denota {f(a)  a  A}.

1.1. Propriedades das Funções

1.1.1. Funções Sobrejetivas

Seja f: ST uma função arbitrária com domínio S e contradomínio T. Parte da definição de uma função é que cada elemento de S tem uma imagem por f e que todas as imagens sao elementos de T; o conjunto I destas imagens é chamado conjunto imagem da função f. assim, I={f(s)  s  S}, ou I=f(S). Obviamente I  T; Se acontecer de I = T, isto é, o conjunto imagem ser igual ao contradomínio, a função é dita sobrejtiva. Para mostrarmos que uma função é sobrejetiva, precisamos mostrar que T  I e, então, teremos mostrado que I=T. Precisamos mostrar então que um elemento arbitrário do contradomínio é um elemento da imagem, isto é, que algum elemento do domínio é levado nele. Por outro lado se pudermos exibir um elemento do contradomínio que seja imagem de qualquer elemento do domínio, então teremos provado que a função é sobrejetiva.

1.1.2. Funções Injetivas

A definição de funções garante que há apenas uma imagem para cada elemento do domínio. No entanto, um dado elemento da imagem pode ter mais de uma pré-imagem (Veja ilustração no seu material sobre conjuntos). A função