Desenhe os grafos conexos de vértices



Baixar 67,71 Kb.
Encontro19.04.2018
Tamanho67,71 Kb.

  1. Desenhe os 6 grafos conexos de 4 vértices.

Fig. 01 – Todos os grafos conexos de 4 vértices

Uma outra abordagem dos mesmos grafos visto em aula, foi a seguinte:

Fig. 02 – Todos os grafos conexos de 4 vértices, em uma outra abordagem evitando-se cruzar arestas.



  1. Desenhe os 21 grafos conexos de 5 vértices.

Fig. 03 – Todos os grafos conexos de 5 vértices

Uma outra abordagem dos mesmos grafos visto em aula, foi a seguinte:

Fig. 04 – Todos os grafos conexos de 5 vértices, em uma outra abordagem evitando-se cruzar arestas



  1. Várias enzimas de restrição reconhecem sítios palindrômicos. Uma string palindrômica é aquela que é igual ao seu complemento reverso. Existem strings palindrômicas de tamanho ímpar? Se sim, mostre algumas; se não, explique porque não as há.

Um palíndromo é uma palavra, frase ou qualquer outra sequência de unidades (como uma cadeia de DNA) que tenha a propriedade de poder ser lida tanto da direita para a esquerda como da esquerda para a direita (o ajustamento de espaços entre letras é geralmente permitido). A palavra "palíndromo" vem das palavras gregas palin ("trás") e dromos ("corrida"). Pensando em DNA, temos que alinhando uma string S de tamanho ímpar com o seu reverso (sem complemento), vemos que o caractere na posição (|S|+1)/2 é alinhado sobre si mesmo. Por exemplo:

1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1
Logo, para que uma string de tamanho ímpar seja palindrômica, é preciso que o complemento da base nessa posição seja igual à própria base. Como isso não ocorre no DNA, não existem strings palindrômicas de tamanho ímpar, pois na posição (|S|+1)/2 sempre haverá cruzamento entre a base original e a complementar reversa.
Exemplo de seqüência palindroma: A G C T

A G C T


Referências

Eric W. Weisstein. "Connected Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ConnectedGraph.html



http://pt.wikipedia.org/wiki/Palindromo - ultimo acesso (23/04/2006)



©livred.info 2017
enviar mensagem

    Página principal