trabalho pronto TEORIA DE GRAFOS

Prévia do material em texto

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 – v2 – v6 (distância = 2).
Exemplo de outros caminhos que ligam v4 e v6:
• v4 – v8 – v7 – v6 (três arestas – caminho ímpar);
• v4 – v1 – v5 – v8 – v7 – v6 (cinco arestas – caminho ímpar);
• v4 – v1 – v5 – v3 – v6 (quatro arestas – 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 – v5 – v3 – v6 – v2 – 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 arestaconectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
Grafo nulo é o grafo cujo conjunto de vértices é vazio.
Grafo vazio é o grafo cujo conjunto de arestas é vazio.
Grafo trivial é o grafo que possui apenas um vértice e nenhuma aresta.
Grafo regular é um grafo em que todos os vértices tem o mesmo grau.
Multigrafo é um grafo que permite múltiplas arestas ligando os mesmos vértices (arestas paralelas).
Pseudografo é um grafo que contém arestas paralelas e laços.
Grafo conexo um grafo é conexo se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo. Em um grafo genérico G, o corte associado a um conjunto X de vértices é o conjunto de todas as arestas que têm uma ponta em Xe outra em V(G) - X, onde V(G) é o conjunto de todos os vértices pertencentes ao grafo G.
Ponto de articulação ou Vértice de corte é um vértice cuja remoção desliga um grafo. Uma ponte é uma aresta cuja remoção desliga um grafo. Um componente biconectado é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O contorno de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, infinito.
Árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz. As árvores são muito usadas como estruturas de dadosem informática (veja estrutura de dados em árvore).
Floresta é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.
Subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G
Subgrafo gerador é aquele obtido pela remoção de uma ou mais arestas de um outro grafo, dizemos então que este novo grafo obtido é gerador do primeiro,
Subgrafo induzido é obtido pela remoção de vértices e consequente das arestas relacionadas com ele de um outro grafo, dizemos que este novo grafo é um grafo induzido do original.
Grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.
Clique em um grafo é um subgrafo que também é um grafo completo. No grafo do exemplo acima, os vértices 1, 2 e 5 formam um clique.
Conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.
Grafo planar é aquele que pode ser representado em um plano sem qualquer intersecção entre arestas. O grafo do exemplo é planar; o grafo completo de nvértices, para n> 4, não é planar.
Grafo bipartido é o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Para um grafo ser bipartido ele não pode conter circuitos de comprimento ímpar.
Se um grafo G é bipartido, todo o circuito de G possui comprimento par.Sejam V1 e V2 os dois conjuntos em que, de acordo com a definição de grafo bipartido, se particiona V(G). Toda a aresta de G conecta um vértice em V1 com outro em V2. Assim sendo, se X for um vértice de V1, para “voltar” a esse vértice terá de se ir a V2 e voltar a V1 um número indeterminado de vezes, e de cada vez serão percorridas duas arestas, uma de um vértice em V1 para um vértice em V2 e outra de um vértice em V2 para um vértice em V1. Logo, o número de arestas a percorrer será par, ou seja, o comprimento do circuito é par.
Se todo o circuito de um grafo G possui comprimento par, então o grafo é bipartido.Seja G um grafo em que todo o circuito tem comprimento par, e seja X um vértice de G. Denotemos por V1 o conjunto formado por X e por todos os vértices cuja distância a X é par. Seja V2 = V(G)\V1 (isto é, o conjunto formado pelos vértices de G que não pertencem a V1). Pretende mostrar-se que não existe qualquer aresta que conecte vértices de V1 ou vértices de V2. Suponhamos a existência de tal aresta, isto é, suponhamos a existência de dois vértices em V1 (ou V2), digamos Xi e Xj, conectados por uma aresta. Ora existe já um caminho de comprimento par entre Xi e Xj, já que existem caminhos, ambos de comprimento par (ou ímpar, no caso de Xi e Xj pertencerem a V2), entre Xi e X e entre X e Xj. Se a esse caminho juntarmos a aresta {Xi;Xj} obtemos um circuito de comprimento ímpar o que contraria a hipótese de apenas existirem circuitos de comprimento par.
Grafo bipartido completo é o grafo bipartido, cujo qualquer vértice do primeiro conjunto é adjacente a todos vértices do segundo conjunto
Grafo k-partido ou grafo de k-coloração é um grafo cujos vértices podem ser particionados em k conjuntos disjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Um grafo 2-partido é o mesmo que grafo bipartido.
Emparelhamento de grafos consiste em partir o grafo em conjuntos de vértices a qual não compartilham nenhuma aresta entre eles.
Teorema das quatro cores é baseado no problema das cores necessárias para se colorir um mapa sem que os países vizinhos compartilhem da mesma cor. Transformando o mapa em um grafo pode-se provar que pode-se representar qualquer mapa (um grafo planar) com apenas 4 cores (4 partições).
3 HISTÓRIA
A Literatura afirma que a teoria dos grafos começou na cidade de Königsberg em 1736 pelo grande matemático suíço Leonhard Euler (1707-1783). A cidade era cortada pelo rio Pregel, que possuía duas ilhas (figura 1.1). Como era muito complicado fazer o transporte de cargas e pessoas através de barcos, algumas pontes foram construidas para auxiliar neste deslocamento entre as ilhas e as duas margens. Após algum tempo as pessoas começaram a se perguntar se era possível sair de sua casa, passar por cada ponte exatamente uma vez e voltar para a segurança de seu lar.
 
Figura 1.1: Mapa de Königsberg
Para resolver o problema, Euler montou um diagrama que representasse o mapa da cidade. Ele o fez da seguinte maneira: A cada ilha e margem ele associou a um ponto que chamaremos de vértice e a cada ponte uma ligação que chamaremos de aresta. Com isso, ele obteve a figura 1.2: 
Figura 1.2: Diagrama de Euler
Essa figura com vários pontos (vértices) e algumas ligações (arestas) que denominamos um grafo. Para finalizar seu raciocínio, Euler percebeu que existiam vértices com exatamente três arestas incidentes. Por outro lado, como os moradores queriam atravessar cada ponte apenas uma vez, cada vértice deveria ter um número par arestas. Logo, se tornaria impossível fazer um percurso seguindo as regras impostas pelos moradores.
4 APLICAÇÃO DE GRAFOS NA COMPUTAÇÃO
Muitas aplicações em computação necessitam considerar conjunto de conexões entre pares de objetos: –Existe um caminho para ir de um objeto a outro seguindo as conexões? –Qual é a menor distância entre um objeto e outro? –Quantos outros objetos podem ser alcançados a partir de um determinado objeto? Grafos são utilizados para modelar tais problemas São possivelmente as estruturas matemáticas mais utilizadas na ciência .
Algumas Aplicações e problemas práticos que podem ser resolvidos através de uma modelagem em grafos:
 –Ajudar máquinas de busca a localizar informação relevante na Web.
 –Descobrir qual é o roteiro mais curto para visitar as principais cidades deuma região turística. –Dentre diversas outras 
4 Conceito Básicos – Definição G
5 CONSIDERAÇÕES FINAIS
O conteúdo Grafos não era do conhecimento dos participantes da oficina, relataram que não tinham o conhecimento deste ramo da matemática, inclusive na graduação não tiveram. Nessa oficina foram analisados conceitos de vértice, arestas de forma contextualizada e com aplicação. A partir desta oficina foi observado o interesse dos participantes em introduzir estes conceitos e a sua aplicabilidade para as turmas onde são professores regentes. Com o trabalho desenvolvido foi possível introduzir o assunto de grafos de forma significativa.