Apostila De Teoria Dos Grafos

AUTARQUIA EDUCACIONAL DO VALE DO SÃO FRANCISCO – AEVSF
FACULDADE DE CIÊNCIAS APLICADAS E SOCIAIS DE PETROLINA – FACAPE
CIÊNCIAS DA COMPUTAÇÃO

APOSTILA DE TEORIA DOS GRAFOS
VERSÃO 1.0

bel. lea. Roberto Tenorio Figueiredo

PETROLINA, 2010

APOSTILA DE GRAFOS

Prof. TENORIO

SUMÁRIO

INTRODUÇÃO À TEORIA DOS GRAFOS ......................................................................... 6
1.1. DEFINIÇÃO............................................................................................................... 6
1.2. CONCEITOS ASSOCIADOS .................................................................................. 7
1.2.1. ADJACÊNCIA (VIZINHANÇA) ............................................................................ 7
1.2.2. ISOMORFISMO ...................................................................................................... 7
1.2.3. TRIVIAL .................................................................................................................. 9
1.2.4. GRAFO DE ARESTAS ........................................................................................... 9
1.2.5. LAÇO ....................................................................................................................... 9
1.2.6. MULTIGRAFO........................................................................................................ 9
1.2.7. GRAU..................................................................................................................... 10
1.2.8. CAMINHO ............................................................................................................. 10
1.2.9. DISTÂNCIA .......................................................................................................... 10
1.2.10. CICLO .................................................................................................................... 11
1.2.11. CONEXO