Teoria dos grafos

Universidade Federal de Santa Maria Engenharia de Controle e Automação

Trabalho Final de Disciplina
-Etapa 2-

Nome: Charles Haab e Kevim Iochims

Disciplina: Matemática Discreta

Professora: Alice Kozakevicius

Santa Maria, 5 de junho de 2012
Teoria dos grafos:

O que é um grafo:

Trata-se de uma maneira de modelar um problema ou estudo via diagramas em que pontos, chamados vértices, se ligam entre si através de linhas, chamadas arestas. É um ramo muito utilizado na matemática para estudar relações entre os objetos de um determinado conjunto.

Um grafo G consiste de:

* O conjunto V dos vértices, | V | = número de vértices. * O conjunto A das arestas, | A | = número de arestas. * Uma função de incidência ψ que associa a cada aresta α de G um par não ordenado de vértices de G chamados extremos de α. * O número de vezes que as arestas incidem sobre um vértice v é chamado grau de v (d(v)).

Grau de um vértice:

O grau de um vértice é determinado pelo número de arestas incidentes no vértice. A soma dos graus dos vértices de um grafo é dada por:

v eV(G).dv=2.|A|

Ou seja, o grau é dado pelo dobro do número de arestas do grafo G em questão. Onde v é um vértice, V(G) é o conjunto de vértices do grafo G, e d(v) é o número de arestas incidente sobre um vértice.

Tipos de Grafos:

* Grafo Conexo: Um grafo G é conexo quando existe um caminho "entre cada par" de vértices de G, caso contrário, G é desconexo.
Obrigatoriamente, a representação geométrica de G é descontínua, se G for desconexo.

* Grafo completo: Um grafo é completo quando existe uma aresta entre cada par de seus vértices. Um grafo completo de n vértices é denotado por Kn.

* Grafo nulo ou vazio: A(G) = ∅.

* Grafo regular: todos os vértices têm o mesmo grau.

(Grafos completos e Regulares.)

* Ciclo: é um caminho que começa e acaba com o mesmo vértice. Notação: Cn.

(Exemplo de Ciclo.)

* Caminho: Ciclo no qual retiramos uma