-- Manuela Simes -- 1

TEORIA DOS GRAFOS APLICAES PRTICAS

O porqu da escolha da Teoria dos Grafos

Os pases mais desenvolvidos tm vindo a sofrer a mudana duma sociedade industrial para uma sociedade de informao/comunicao. O ritmo desta mudana tem sido tal que actualmente possvel constatar que a produo, armazenamento, transmisso e difuso da informao (oral, escrita, grfica, numrica) muito maior que a que qualquer ser humano pode assimilar. Este movimento exige o recurso a tecnologia da mais avanada e provoca profundas transformaes no nosso dia a dia.

Os objectivos que a Escola quer alcanar devem ser o reflexo das necessidades da sociedade onde os alunos se inserem. H que reflectir profundamente sobre o tipo de conhecimento e sobretudo de competncias que vo ser exigidas aos nossos alunos. Relativamente Matemtica h que repensar os aspectos da matemtica que temos necessidade de transmitir aos alunos bem como os conceitos e processos que estes devem dominar. Assim o sistema escolar deve proporcionar um ensino que permita ao aluno:

decidir que informao relevante para o estudo e compreenso de um determinado problema e qual a melhor forma de apresentar essa informao

dar a resposta mais adequada, apesar da multiplicidade de situaes novas que iro encontrar durante a sua vida e a que tm de dar resposta imediata.

Segundo o professor Sebastio e Silva (1975), o ensino em todos os graus ter de

se tornar mais flexvel, mais adaptado, quer s solicitaes dum mundo em rpida evoluo quer s aptides dos indivduos.

Conseguir que os alunos aprendam a pensar, a resolver problemas, a

enfrentar novas situaes, a aceder informao e a trat-la de forma adequada o grande desafio do nosso sistema escolar.

O NCTM, j em 1991, nas suas Normas propunha que se inclussem tpicos de Matemtica Discreta nos currculos. Na Norma 12 para os nveis de escolaridade do 9 ao 12 anos podamos encontrar referncias tais como:

(...) em contextos geomtricos e algbricos, os alunos devem ter numerosas

oportunidades para investigar situaes problemticas deste tipo, e tambm de situaes que envolvam trs redes de comunicao, diagramas de circuitos, torneios desportivos, esquemas de produo e relaes matemticas ... que podem ser modeladas e analisadas a partir de grafos. Grafos particulares, chamados rvores, so usados frequentemente na resoluo de problemas de probabilidades e na representao da prioridade das operaes nas expresses algbricas (p. 212)

(...) O pensamento recursivo aplica-se tambm em muitos contextos geomtricos.

Por exemplo, para determinar o nmero mximo de regies que so designadas no plano por n rectas, no paralelas duas a duas e que se intersectam em pontos diferentes ...(p.213)

-- Manuela Simes -- 2

Em Portugal a preocupao em torno da Matemtica Discreta tambm j se faz sentir h algum tempo.

Paulo Abrantes (1994) refere que para as Normas, a Matemtica

Discreta diz respeito s propriedades de conjuntos e sistemas numerveis, e o seu estudo indispensvel no mundo do processamento da informao e na resoluo de problemas que envolvam mtodos computacionais. O NCTM argumenta que " os computadores so essencialmente mquinas finitas e discretas" que vm exercendo uma influncia crescente nos modos de criar e usar a Matemtica. Sendo dois dos objectivos gerais dos programas de ensino a preparao para a vida activa e aprender a aprender acreditamos que a introduo da Teoria dos Grafos nos programas de ensino teria vantagens atendendo:

s suas aplicaes em diferentes reas do saber ao seu potencial para desenvolver aspectos como a visualizao de

situaes e a esquematizao de raciocnios a que um extraordinrio meio de comunicao a que desenvolve capacidades lgicas e de preciso bem como

destrezas manuais

A importncia crescente de problemas matemticos relacionados por exemplo com questes de trnsito ou de negcios, que implicam tomada de decises leva-nos a considerar que os grafos devem ser um dos tpicos a ser integrados nos programas de Matemtica. Estes constituem uma boa ferramenta para conceptualizar situaes, para entender esquemas e transferi-los para novas situaes para alm de exigirem poucas destrezas numricas e de clculo. Permitindo trabalhar conceitos numricos e operaes bsicas. no exigem muitos conhecimentos nem tcnicas matemticas, o que pode levar a que um maior nmero de alunos os discutam sem dificuldades.

-- Manuela Simes -- 3

So apresentadas seguidamente um conjunto de problemas, sob o

nome de Grafolndia, que podero ser discutidos com os alunos de qualquer grau de ensino desde que possuam os conhecimentos bsicos necessrios sobre grafos

Houve o cuidado de escolher os problemas que pareceram mais

aliciantes e ao mesmo tempo que abarcassem uma variedade aprecivel de tpicos, a saber:

Grafos rvores Euler e Hamilton Colorir um grafo Colorir regies Algoritmos Com este tipo de actividades os alunos devem ter oportunidade de

expressar as suas ideias e desenvolv-las ao resolver os problemas. Estes devem justificar e provar as suas afirmaes sempre que possvel. A estrutura a seguinte: cada actividade escolhida apresentada com :

- uma folha com a descrio da situao a apresentar aos alunos; - uma folha para o professor com os conceitos chave e a respectiva

resoluo As diferentes situaes podem ser resolvidas individualmente (I) ou em

grupo (G) embora no final os alunos devam confrontar as suas conjecturas, justificaes, resultados com o grupo turma. A sequncia das actividades foi feita segundo uma lgica pessoal do momento da construo desta apresentao. Tambm os conceitos chave e as propostas de resoluo so apenas sugestes que cada professor poder alterar.

O importante que se compreenda que o professor tem um papel fundamental na planificao destas situaes. Deve ponderar qual o peso que devem ter no cmputo das actividades da turma e a frequncia com que devem surgir, os objectivos a atingir, o nvel etrio e o desenvolvimento matemtico dos alunos.

-- Manuela Simes -- 4

GRAFOLNDIA Actividade I

Encontra um caminho at ao centro representado por *, e a respectiva sada

-- Manuela Simes -- 5

Actividade I (Folha do Professor) Conceitos Chave: vrtices arestas grafos (definio) Resoluo: (I)

A situao apresentada pode ser resolvida recorrendo a uma representao em grafo:

Em que os vrtices representam as salas do labirinto, e as arestas unem duas dessas salas quando possvel chegar de uma a outra. A soluo da situao proposta ser ento :

Entrar em A, chegar ao centro * e sair em K ou seja , fazer o percurso : A F J * I L M K

A KF J * I ML

EC G

Actividade II

Pretendemos ligar trs casas A, B e C, a trs utilitrios, gs (g), gua (a) e electricidade (e). Por razes de segurana convm que as ligaes no se cruzem. Quantas ligaes tero de ser feitas?

A

-- Manuela Simes --

g

C

a e

B

C

C

6

-- Manuela Simes -- 7

Actividade II (Folha do Professor) Conceitos Chave: vrtices arestas grafos (definio) vrtices adjacentes vrtices incidentes Grau de um vrtice Grafo regular Grafo completo Grafo bipartido Grafo planar Grau de um vrtice igual ao nmero de arestas nele incidentes Grafo Regular aquele em que todos os vrtices tm o mesmo grau Grafo Completo aquele em que todos os vrtices so adjacentes. Um garfo G diz-se um Grafo Bipartido se o conjunto dos seus vrtices admitir uma partio {V1; V2} de tal maneira que toda a aresta de G une um vrtice de V1 e um vrtice de V2 Um Grafo Planar um grafo que pode ser desenhado no plano de forma a que as arestas no se cruzem

-- Manuela Simes -- 8

Resoluo: (I) Representao em grafo: Vrtices: A, B, C, g, a, e Arestas: Ag, Aa, Ae, Bg, Ba, Be, Cg, Ca, Ce Trata-se de um grafo regular : todos os vrtices tm grau 3 bipartido, basta considerar a partio V1= { A, B, C } V2= { g, a, e } planar porque, embora tenha sido desenhado com as arestas a intersectarem-se, pode ser desenhado sem que tal acontea :

g a e

A B C

A B

g a

C

e

-- Manue

Actividade III

A regulao do trfego automvel, em cruzamentos, por semforos, parte do princpio de que o fluxo de circulao de veculos procedente de ruas distintas no se intercepta ao confluir para o cruzamento. Esta situao representada por um esquema de pontos e linhas. Os pontos mostram a sada dum cruzamento (e a chegada ao mesmo) enquanto que as linhas indicam o(s) sentido(s) de possveis circulaes entre as entradas e sadas do cruzamento. Regula com semforos a circulao automvel de modo a evitar colises num cruzamento com dois sentidos e possibilidade de virar esquerda e direita. No permitido fazer uma volta de 180.

e1

s3

e2

s2

1

s1

e4

1 2 3 4 Ruas E1 E2 E3 E4

2

la Simes --

e3

s4

4

Entradas no Cruzamento S1 S2 S3 S4 Sadas do Cruzamento

3

9

-- Manuela Simes -- 10

Actividade III (Folha do Professor) Conceitos Chave: Subgrafo Grafo dirigido Grafos isomorfos Um grafo Gdiz-se um Subgrafo de um grafo G se o conjunto dos vrtices e o conjunto das arestas de Gso subconjuntos do conjunto de vrtices e do conjunto de arestas, respectivamente, de G Dois Grafos G1, G2, dizem-se Isomorfos se existe uma bijeco entre os conjuntos dos vrtices dos dois grafos, preservando a adjacncia desses vrtices, ou seja, se dois vrtices so adjacentes em G1, as suas imagens pela referida bijeco so adjacentes em G2. Um Grafo Dirigido um grafo em cujas arestas definido um sentido Resoluo: (G) Primeiramente explo