Resumo MACS - Grafos

6451 palavras 26 páginas
Introdução

Muitas vezes as grandes descobertas surgem das mais humildes e inesperadas origens. É esta a ideia matemática a desenvolver neste trabalho, o estudo matemático de como as coisas estão interligadas.
A noção de grafo aparece geometricamente quando se pensa em linhas e extremos de linhas: toda a figura formada com estes elementos pode ser encarada como um grafo. Algébricamente, a noção de grafo aparece quando se associa a um conjunto qualquer uma relação binária, em particular uma relação de ordem.
É portanto perfeitamente natural que a ciência se tenha debruçado sobre esta noção e não só a procurasse definir em termos matemáticos como também a tenha utilizado ao serviço das aplicações práticas. De facto é um conceito
…exibir mais conteúdo…
Ponte: Aresta de um grafo G conexo que ao ser retirada o torna desconexo.

“Burn a bridge behind you and you’ll never be able to get back”

Nota: Como vimos ao retirar a aresta AE o grafo da figura 1 tornou-se desconexo assim sendo à aresta AE damos o nome de ponte.

Caminho: Sequência de vértices vi tais que vi e vi+1 são adjacentes.

Nota: Um vértice pode aparecer várias vezes num caminho, no entanto cada aresta só pode aparecer uma única vez.

DABCAE é um caminho de D para E

Circuito: Caminho que começa e termina no mesmo vértice.

GEFG é um circuito

Leonhard Euler (1707-1783) nasceu em Basel na Suiça. Mostrou ,desde muito cedo, um incrível talento para a realização de cálculos mentais. Apenas este aspecto não descreve um grade matemático mas Euler acrescentava-lhe um incrível talento criativo e uma ética de trabalho tremenda.
Hoje em dia Euler é considerado como um dos maiores matemáticos de sempre, sendo a sua obra composta por quase 100 volumes. Nas palavras de um biografo, Euler é o Shekespeare da matemática. E é graças a ele que temos os seguintes conceitos.

Caminho de Euler: Caminho que percorre por todas as arestas de um grafo conexo uma única vez.

ddabcaegfe é um caminho de Euler

Circuito de Euler:

Relacionados

  • WEP, WPA e EAP
    6137 palavras | 25 páginas
  • Montagem de uma rede cabeada e seus componentes
    10803 palavras | 44 páginas