Trabalho De Mat

Teoria dos Grafos

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V, A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele mesmo e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.

Histórico

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Konigsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

Exemplos

Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e planar.

Um grafo com 6 vértices e 7 arestas

Grafo Orientado

Um grafo orientado, grafo dirigido, grafo direcionado ou digrafo é um par G= (V.A).

Um conjunto V, cujos elementos são chamados de vértices ou nodos.

Um conjunto A de pares ordenados de vértices, chamados arcos, arestas direcionadas, ou setas.

Ele difere de um grafo não direcionado comum, em que o último é definido em termos de pares não ordenados de vértices, que são normalmente chamados arestas.

Por exemplo, ser possível ir de um nó A para um nó B, mas não o contrário através desse arco.

Ás vezes, um digrafo é chamado de um digrafo simples para distingui-los de um multigrafo direcionado, em que os arcos constituem um multiconjunto, em vez de um conjunto, de pares ordenados de vértices. Além disso, em um digrafo simples laços