Sejam ( X1, R1 ) e ( X2, R2 ) ordens parciais isomorfas, e associe a elas seus respectivos grafos G1 e G2, como na Definição 2.5. Prove que G1 e G2 são grafos isomorfos.

Passo 1

O enunciado afirma que temos dois posets isomorfos (X1,R1) e (X2,R2). Por definição, existe uma bijeção
fcolon X1to X2
tal que, para todos x,yin X1,
(x,y)in R1Long<=ftrightarrowl(f(x),f(y)r)in R2
A cada poset associamos um grafo Gi (Definição 2.5), cujo conjunto de vértices é Xi e cujas arestas representam a relação (ou a cobertura, dependendo da definição). Queremos provar que G1 e G2 são isomorfos, ou seja, existe uma bijeção entre vértices que preserva as arestas.

Passo 2

Definimos
phicolon V(G1)=X1;longrightarrow;V(G2)=X2 por phi(x)=f(x)
Como f é bijetora, phi também é bijeção entre os conjuntos de vértices de G1 e G2.

Passo 3

Agora verificamos que phi preserva adjacência. Seja x,y uma aresta de G1. Dois casos comuns de definição de Gi são:
  1. Grafos de comparabilidade: x,y é aresta se e somente se x,R1,y ou y,R1,x.
  2. Grafos de Hasse (grafo de cobertura): x,y é aresta se e somente se um cobre o outro em R1, i.e., x,R1,y e não existe z tal que x,R1,z,R1,y, ou vice-versa.
Em ambos os casos, a condição de isomorfismo de posets garante:
– Se x,R1,y então f(x),R2,f(y).
– Se não existe intermediário z em R1 entre x e y, então, por sobrejetividade de f, também não existe intermediário entre f(x) e f(y) em R2.
Portanto,
x,y é aresta em G1 Longrightarrow phi(x),phi(y) é aresta em G2 éé
O mesmo raciocínio na direção inversa (usando f^-1) mostra que nenhuma outra aresta é criada ou destruída. Logo, phi é um isomorfismo de grafos.

Resposta

Os grafos G1 e G2 são isomorfos via a bijeção phi(x)=f(x), que preserva exatamente as arestas.

Exercícios de Livros Relacionados