Provas com Grafos

Prévia do material em texto

Provas com grafos
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica, UFF
Outubro de 2010
Suma´rio
• Verificac¸a˜o de incluso˜es e igualdades na a´lgebra de relac¸o˜es.
• Provas com grafos.
• Construc¸a˜o de contraexemplos usando grafos.
Sharon Curtis
• Provas com grafos.
Verificac¸a˜o de incluso˜es
Para todas as relac¸o˜es R, S e T em um conjunto A,
temos que R ◦ (S ∩ T ) ⊆ (R ◦ S) ∩ (R ◦ T ).
Prova (discursiva):
Seja (x , y) ∈ R ◦ (S ∩ T ).
Da´ı, (x , z) ∈ R e (z , y) ∈ S ∩ T , para algum z ∈ A.
Como (z , y) ∈ S ∩ T , temos que (z , y) ∈ S e (z , y) ∈ T .
Como (x , z) ∈ R e (z , y) ∈ S , temos que (x , y) ∈ R ◦ S .
Da mesma forma, como (x , z) ∈ R e (z , y) ∈ T , temos que
(x , y) ∈ R ◦ T .
Agora, como (x , y) ∈ R ◦ S e (x , y) ∈ R ◦ T , temos que
(x , y) ∈ (R ◦ S) ∩ (R ◦ T ).
Prova por grafos
Para todas as relac¸o˜es R, S e T em um conjunto A,
temos que R ◦ (S ∩ T ) ⊆ (R ◦ S) ∩ (R ◦ T ).
Para fazer uma prova por grafos, executamos duas tarefas:
1. Associamos um di-grafo rotulado a cada lado da inclusa˜o
G [R ◦ (S ∩ T )] e G [(R ◦ S) ∩ (R ◦ T )]
2. Comparamos os di-grafos rotulados.
Ca´lculo de G [R ◦ (S ∩ T )]
− +R◦(S∩T ) //
Ca´lculo de G [R ◦ (S ∩ T )]
− +•R // S∩T //
G [R ◦ (S ∩ T )]
− +•R //
S
((
T
66
Ca´lculo de G [(R ◦ S) ∩ (R ◦ T )]
− +(R◦S)∩(R◦T ) //
Ca´lculo de G [(R ◦ S) ∩ (R ◦ T )]
− +
R◦S
++
R◦T
33
G [(R ◦ S) ∩ (R ◦ T )]
− +
•
•
R
::
S
$$
R $$ T
::
Comparac¸a˜o de G [R ◦ (S ∩ T )] com
G [(R ◦ S) ∩ (R ◦ T )]
− +•R //
S
**
T
44 − +
•
•
R
::
S
$$
R $$ T
::

__
Homomorfismo
Dados dois di-grafos rotulados G e H, comparar G com H consiste
em procurar um homomorfismo de H em G .
Um homomorfismo de G em H e´ uma func¸a˜o h que leva cada no´
de H em um no´ de G de modo que:
(a) O no´ − de H e´ levado no no´ − de G .
(b) O no´ + de H e´ levado no no´ + de G .
(c) Para cada arco uAv de H, temos que h(u)Ah(v) e´ um arco de
G .
O homomorfismo h identificado entre G [(R ◦ S) ∩ (R ◦ T )] e
G [R ◦ (S ∩ T )] pode ser apresentado atrave´s de uma tabela. Para
fazer isto, rotulamos os no´s dos grafos.
− +•
a
R //
S
**
T
44 − +
•
•
b
c
R
::
S
$$
R $$ T
::
x h(x)
b a
c a
Na tabela, na˜o representamos as imagens dos no´s − e + de
G [(R ◦ S) ∩ (R ◦ T )].
Prova com grafos
Dadas as relac¸o˜es R e S , tais que R ⊆ S , a prova por grafos da
inclusa˜o deve seguir o seguinte modelo de redac¸a˜o:
(1) Escreva “Prova por grafos:” ao iniciar a prova;
(2) Desenhe os esboc¸os de G [R] e de G [S ];
(3) Rotule os no´s dos grafos de G [R] e de G [S ];
(4) Para cada grafo G de G [R], encontre um grafo H de G [S ] e
um homomorfismo de G em H e fac¸a as tabelas que
apresentam estes homomorfismos;
(5) Escreva “ ” para terminar a prova.
Voltando ao exemplo
R ◦ (S ∩ T ) ⊆ (R ◦ S) ∩ (R ◦ T ).
Prova com grafos:
− +•
a
R //
S
((
T
66
G [R ◦ (S ∩ T )]
− +
•
•
b
c
R
::
S
$$
R $$ T
::
G [(R ◦ S) ∩ (R ◦ T )]
x h(x)
b a
c a
Inclusa˜o de Lyndon
R. Lyndon (1917 – 1988) mostrou que a inclusa˜o R ⊆ S , onde:
R = A ∩ (((B ◦ C ) ∩ D) ◦ (E ∩ (F ◦ G )))
e
S = B ◦ ( (((B−1 ◦ A) ∩ (C ◦ E )) ◦ G−1)
∩
(C ◦ F )
∩
(B−1 ◦ ((A ◦ G−1) ∩ (D ◦ F ))) ) ◦ G
vale, mas na˜o pode ser provada algebricamente a partir das
igualdades e incluso˜es ba´sicas propostas por Tarski.
Inclusa˜o de Lyndon
Na˜o existe uma prova alge´brica da inclusa˜o de Lyndon a partir de
igualdades e incluso˜es ba´sicas simples.
E, com tantas letras, quem se anima a tentar uma prova
discursiva?
Uma prova com grafos, no entanto, e´ simples e ate´ divertida.
− +A∩((B◦C)∩D)◦(E∩(F◦G)) //
− +
((B◦C)∩D)◦(E∩(F◦G))
11
A
--
•
− +
(B◦C)∩D
%%
A //
E∩(F◦G)
99
•
− +
D
##
B◦C
((
A //
E
77
F◦G
;;
• • •
− +
D
%%
B
��
C
//
A //
E
99
F
//
G
OO
− +B◦((((B
−1◦A)∩(C◦E))◦G−1)∩(C◦F )∩(B−1◦((A◦G−1)∩(D◦F ))))◦G //
− +• •B // (((B
−1◦A)∩(C◦E))◦G−1)∩(C◦F )∩(B−1◦((A◦G−1)∩(D◦F ))) // G //
− +• •
B
//
((B−1◦A)∩(C◦E))◦G−1
&&
B−1◦((A◦G−1)∩(D◦F ))
88
C◦F // G //
− +• •
•
•
•
B
//
(B−1◦A)∩(C◦E)
55
B−1
%%
C //
(A◦G−1)∩(D◦F )
55F //
G−1
%% G //
− +• •
•
•
•
D◦F
AAB
//
B−1◦A --
B−1
%%
C◦E
55
C //
A◦G−1
55F //
G−1
%% G //
− +• •
•
•
•
•
•
D◦F
AAB
//
B−1◦A --
B−1
%%
C
55
C //
A
55
E
55
F //
G−1
%%
G−1
55 G //
− +• •
•
•
•
•
•
•
•
D
//
B
//
B−1
OO
B−1
%%
C
55
C //
A //
A
55
E
55
F //
F
OO
G−1
%%
G−1
55 G //
− +• •
•
•
•
•
•
•
•
D
//
B
//
B
��
B
ee
C
55
C //
A //
A
55
E
55
F //
F
OO
G
ee
G
uu
G //
− +• •
•
•
•
•
•
•
•
D
//
B
//
B
��
B
ee
C
55
C //
A //
A
55
E
55
F //
F
OO
G
ee
G
uu
G //
• • •
− +
D
%%
B
��
C
//
A //
E
99
F
//
G
OO
Contraexemplos
A inclusa˜o (R ◦ S) ∩ (R ◦ T ) ⊆ R ◦ (S ∩ T ) na˜o e´ verdadeira para
todas as relac¸o˜es R, S e T .
Na˜o e´ poss´ıvel encontrar um homomorfismo de G [R ◦ (S ∩ T )] em
G [(R ◦ S) ∩ (R ◦ T )].
− +
•
•
R
::
S
$$
R $$ T
::
G [(R ◦ S) ∩ (R ◦ T )]
− +•R //
S
((
T
66
G [R ◦ (S ∩ T )]
Contraexemplos
Para obter um contraexemplo, rotulamos os no´s de
G [(R ◦ S) ∩ (R ◦ T )].
− +
•
•
a
b
R
::
S
$$
R $$ T
::
Contraexemplos
Contraexemplo:
Considere A como o conjunto
de no´s do grafo:
A = {−, a, b, +}.
Defina R, S e T conforme as
informac¸o˜es contidas no grafo:
R = {(−, a), (−, b)},
S = {(a, +)},
T = {(b, +)}.
Assim, temos que
− +
•
•
a
b
R
::
S
$$
R $$ T
::
(R ◦ S) ∩ (R ◦ T ) = {(−, +)} 6⊆ ∅ = R ◦ (S ∩ T ).
Contraexemplos
Dadas as relac¸o˜es R e S , tais que R 6⊆ S , podemos obter um
contraexemplo com a ajuda dos grafos, seguindo o seguinte roteiro:
(1) Desenhe os esboc¸os de G [R] e de G [S ];
(2) Encontre um grafo G de G [R] tal que na˜o existe um grafo H
de G [S ] e um homomorfismo de G em H;
(3) Rotule os no´s do grafo G de G [R] encontrado;
(4) Para construir o contraexemplo, defina o conjunto A como
sendo o conjunto cujos elementos sa˜o os ro´tulos de G e as
relac¸o˜es como sendo o conjunto de pares ordenados de ro´tulos
de G tais que um par (x , y) pertence a uma relac¸a˜o R, e
somente se, G possui um arco com ro´tulo R do no´ de ro´tulo x
para o no´ de ro´tulo y .
Exerc´ıcios
1. Dadas R e S as relac¸o˜es da inclusa˜o de Lyndon, rotule os no´s
de G [R] e de G [S ] e fac¸a a tabela do homomorfismo que
garante que R ⊆ S e´ uma inclusa˜o verdadeira.
2. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
3. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo, 2006).
4. Exerc´ıcios da Lista 10.
	Verificação de inclusões
	Prova por grafos
	Inclusão de Lyndon
	Contraexemplos