trabalho pronto TEORIA DE GRAFOS
17 pág.

trabalho pronto TEORIA DE GRAFOS


DisciplinaMatemática Discreta4.135 materiais80.446 seguidores
Pré-visualização3 páginas
INTITUTO FEDERAL DE CIENCIA E TECNOLOGIA
CAMPUS COLINAS DO TOCANTINS
CURCO LICENCIATURA EM COMPUTAÇÃO
JAKELINE FEITOSA DE SOUZA COSTA
Teoria de Grafos
Colinas do Tocantins
2017
JAKELINE FEITOSA DE SOUZA COSTA
Teoria de Grafos
Trabalho apresentado ao Instituto Federal de Ciência e Tecnologia de Colinas do Tocantins para obtenção parcial de nota na disciplina de Matemática Discreta.
 
Docente:
Gislane Valente
Colinas do Tocantins
2017
RESUMO
Nesse trabalho é apresentado uma pesquisa sobre Grafos A pesquisa foi realizada pontuando a definição de Grafos ,os objetivos, o contexto histórico e a aplicação com ênfase na computação.O objetivo desta pesquisa é de adquirir os conceitos de Teoria Grafos para utilização não somente na Disciplina de Matemática Discreta ,mas também na área computacional.
Palavras-chave: computação, Grafos, pesquisa.
SUMÁRIO
1 INTRODUÇÃO
2 DEFINIÇÃO
 2.1 TIPOS DE GRAFOS
3 HISTÓRIA
4 APLICAÇÃO DE GRAFOS NA COMPUTAÇÃO
5 CONSIDERAÇÕES FINAIS
REFERÊNCIAS
1 INTRODUÇÃO
A disciplina de Matemática Discreta aborda conhecimentos específicos de técnica de demonstração, como indução matemática, recursão, teoria dos conjuntos, relações , funções ,árvores e dentre elas os grafos que é o tema desta pesquisa ,sendo que esses conhecimentos servem como fundamentos para o desenvolvimento de sistemas computacionais.
Para (RUIZ, 2009) ,as técnicas de estudo e leitura, os modos de análise, pensamento e escrita compatíveis com o rigor científico, as técnicas de produção de conhecimento válido, as normas de elaboração de resenhas, resumos e monografias com as especificidades da redação científica, os projetos de pesquisa e suas etapas, as fontes de pesquisa, os métodos de abordagem e procedimento, as tipologias da pesquisa, entre outros tópicos, tudo isso há de enriquecer a jornada do estudante em seu percurso universitário
Sendo assim este estudo consolidou Grafos como um subcampo da Matemática Discreta e Computacional, com muitas aplicações em diversas áreas do conhecimento como, por exemplo: Genética, química, pesquisa operacional, telecomunicações, engenharia elétrica, redes de computadores, conexão de voos aéreos, etc. 
 
2 DEFINIÇÃO
Denomina-se Grafo ao conjunto não vazio formado por pontos ou vértices conectados por retas chamadas de arestas. Assim, matematicamente representando, um grafo G é formado por um par (V(G)), A(G) onde V(G) é um conjunto finito e não vazio de vértices e A(G) é um conjunto de arestas conectadas aos pares de vértices V(G). (MALTA 2008; COSTA, 2011).
Ele é utilizado para modelar algumas situações ,como verificar se existe outras conexões de um caminho até um determinado objeto, encontrar a menor distancia de um objeto a outro ou quantos objetos podem ser alcançados a partir de um determinado objeto.Segundo Malta (2008) a utilidade da Teoria dos Grafos reside no fato de poder buscar soluções de inúmeros problemas de vários campos que podem ser multidisciplinar com a Matemática.
A Figura 01 seguinte apresenta exemplo de Grafo:
Alguns conceitos estão diretamente ligados a Teoria de Grafos :
Trivial que é um grafo que tem apenas um vértice e nenhuma aresta.
Figura x:Grafo trivial
Adjacencia ,são duas arestas vizinhas que possuem um vertice em comum ou se dois vertices possuirem uma aresta em comum.
Figura x:Adjacência de arestas
Laço é uma aresta que possui as duas extremidades em um mesmo vertice de G.
Figura x:Um grafo com um laço :a aresta a3.
Multigrafo é um grafo que possui ,pelo menos ,um par de arestas com vertices iguais.
Figura x:Multigrafo
Grau de vértice é a quantidade de vertices adjacentes a ele.um grafo é regular de grau quando todos os vertices possuem o mesmo grau.um grafo regular de grau N possui (V * N)2 arestas ,onde V é a quantidade de vertices.
Figura x:Grafo Regular de Grau 3 
Um vértice de grau zero é chamado de isolado. O grau máximo de um grafo, denominado de
delta, é o grau do maior vértice do grafo. Um grafo regular de grau 3 é chamado de grafo
cúbico.
 ALTAMENTE IRREGULARES
Um grafo é chamado de altamente irregular se cada um dos vértices do grafo é adjacente,
apenas, a vértices de graus diferentes do seu.
 O grafo da Figura 22.b é altamente irregular.
 RÓTULO E VALORAÇÃO (PESOS)
Um rótulo é uma cadeia de caracteres ou número que identifica um vértice ou uma aresta. Um grafo é dito rotulado, se todos os seus vértices e/ou arestas possuírem um rótulo. Os rótulos de um grafo formam o conjunto de rótulos do grafo. 
Um grafo é dito valorado ou com pesos, se seus rótulos forem numéricos e esses números
pertencerem a um conjunto devidamente especificado. Como exemplo, vamos vejamos o grafo
da Figura 8. É o grafo dos estados do nordeste brasileiro, onde cada vértice representa um estado
e dois vértices são adjacentes se os estados que representam possuírem uma fronteira comum.
Esse grafo é rotulado, sendo que os rótulos das arestas representam a distância entre as capitais
dos estados que estão nas extremidades dessas arestas, ou seja, os rótulos das arestas são
especificados pela distância real entre as capitais dos estados, isto significa que o grafo da
Figura 8 é valorado. 
1.2.8. ISOMORFISMO
Dois grafos são isomorfos entre si, se e somente se for possível alterar os nomes dos vértices
de um deles de tal modo que os dois grafos fiquem exatamente iguais, mantendo-se as mesmas
ligações. Se cada um dos grafos tem n vértices, esse algoritmo de alteração de nomes consome
tempo proporcional a n! (n fatorial). Como n! cresce explosivamente com n, esse algoritmo é
decididamente insatisfatório na prática. Infelizmente, não se conhece um algoritmo
substancialmente melhor. 
1.2.9. CAMINHO
O caminho é uma sequência de vértices, onde um vértice e seu sucessor na sequência possuem
uma aresta ligando-os. 
DISTÂNCIA
A distância entre dois vértices de um grafo é o menor comprimento dos caminhos entre esses
dois vértices. Por exemplo, na Figura 6, existem vários caminhos que ligam v4 a v6, porém, o
menor caminho entre eles, ou seja, à distância, é o caminho v4 \u2013 v2 \u2013 v6 (distância = 2).
Exemplo de outros caminhos que ligam v4 e v6:
\u2022 v4 \u2013 v8 \u2013 v7 \u2013 v6 (três arestas \u2013 caminho ímpar);
\u2022 v4 \u2013 v1 \u2013 v5 \u2013 v8 \u2013 v7 \u2013 v6 (cinco arestas \u2013 caminho ímpar);
\u2022 v4 \u2013 v1 \u2013 v5 \u2013 v3 \u2013 v6 (quatro arestas \u2013 caminho par);
1.2.11.CICLO
Um ciclo é um caminho que inicia e termina em um mesmo vértice. Na Figura 6, podemos
exemplificar um ciclo, com o caminho: v1 \u2013 v5 \u2013 v3 \u2013 v6 \u2013 v2 \u2013 v1. Se todos os vértices do
ciclo forem distintos, dizemos que o ciclo é simples ou elementar. Um grafo que não possui
ciclo é chamado de acíclico. 
CICLO FUNDAMENTAL
O ciclo fundamental de um grafo G é formado pela adição de um único elo de G, em uma de
suas árvores geradoras. Chamamos de conjunto fundamental de ciclos, o conjunto de todos
os ciclos fundamentais de G, em relação a uma de suas árvores geradoras 
CONEXO
Um grafo G é conexo se e somente se, existir um caminho entre todos os pares de vértices do
grafo G. Caso algum vértice de G não tenha caminho com algum outro vértice de G, chamamos
esse grafo de desconexo 
OPERAÇÕES COM GRAFOS
Operações são equações feitas nos grafos. Algumas operações não são aplicadas a dígrafos,
outras são mais genéricas. Algumas são aplicadas a apenas um grafo, essas são chamadas de
unárias, outras são aplicadas a pares de grafos, a essas damos o nome de binárias.
 
2.1 TIPOS DE GRAFOS
Grafo simples é um grafo não direcionado, sem laços e existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.
Grafo completo é o grafo simples em que, para cada vértice do grafo, existe uma aresta