Visita Encydia-Wikilingue.com

Teoria de grafos

teoria de grafos - Wikilingue - Encydia

Diagrama de um grafo com 6 vértices e 7 arestas.


Em matemáticas e em ciências da computação, a teoria de grafos (também chamada teoria das gráficas) estuda as propriedades dos grafos (também telefonemas gráficos). Um grafo é um conjunto, não vazio, de objectos chamados vértices (ou nós) e uma selecção de pares de vértices, chamados arestas (edges em inglês) que podem ser orientados ou não. Tipicamente, um grafo representa-se mediante uma série de pontos (os vértices) ligados por linhas (as arestas).

Conteúdo

História

Pontes de Königsberg.

O trabalho de Leonhard Euler, em 1736 , sobre o problema das pontes de Königsberg é considerado o primeiro resultado da teoria de grafos. Também se considera um dos primeiros resultados topológicos em geometria (que não depende de nenhuma medida). Este exemplo ilustra a profunda relação entre a teoria de grafos e a topologia.

Em 1845 Gustav Kirchhoff publicou suas leis dos circuitos para calcular o voltaje e a corrente nos circuitos eléctricos.

Em 1852 Francis Guthrie propôs o problema das quatro cores que propõe se é possível, utilizando somente quatro cores, colorir qualquer mapa de países de tal forma que dois países vizinhos nunca tenham a mesma cor. Este problema, que não foi resolvido até um século depois por Kenneth Appel e Wolfgang Haken, pode ser considerado como o nascimento da teoria de grafos. Ao tratar de resolvê-lo, os matemáticos definiram termos e conceitos teóricos fundamentais dos grafos.

Estruturas de dados na representação de grafos

Artigo principal: Grafo (estrutura de dados)

Existem diferentes formas de armazenar grafos em um computador. A estrutura de dados usada depende das características do grafo e o algorítmo usado para manipulá-lo. Entre as estruturas mais singelas e usadas encontram-se as listas e as matrizes, ainda que frequentemente usa-se uma combinação de ambas. As listas são preferidas em grafos dispersos porque têm um eficiente uso da memória. Por outro lado, as matrizes proveen acesso rápido, mas podem consumir grandes quantidades de cor.

Estrutura de lista

Nesta estrutura de dados a ideia é associar à cada vertice i do grafo uma lista que contenha todos aqueles vértices j que sejam adjacentes a ele. Desta forma só reservará memória para os arcos adjacentes a i e não para todos os possíveis arcos que pudessem ter como origem i. O grafo, por tanto, representa-se por médio de um vetor de n componentes (se |V|=n) onde a cada componente vai ser uma lista de adyacencia correspondente à cada um dos vértices do grafo. A cada elemento da lista consta de um campo indicando o vértice adjacente. Em caso que o grafo seja etiquetado, terá que acrescentar um segundo campo para mostrar o valor da etiqueta.

Exemplo de lista de adyacencia 500px

Estruturas matriciales

Definições

Vértice

Artigo principal: Vértice (teoria de grafos)

Os vértices constituem um dos dois elementos que formam um grafo. Como ocorre com o resto dos ramos das matemáticas, à Teoria de Grafos não lhe interessa saber que são os vértices.

Diferentes situações nas que podem se identificar objectos e relações que satisfaçam a definição de grafo podem se ver como grafos e assim aplicar a Teoria de Grafos neles.

Grafo

Artigo principal: Grafo
Arquivo:Grafo exemplo 1isom.png
Na figura, V = { a, b, c, d, e, f }, e A = { ab, ac, ae, bc, bd, df, ef }.

Um grafo é um casal de conjuntos G = (V, A), onde V é o conjunto de vértices, e A é o conjunto de arestas, este último é um conjunto de pares da forma (u,v) tal que u,v \in V, tal que u \neq v. Para simplificar, notaremos a aresta (a,b) como ab.

Em teoria de grafos, só fica o essencial do desenho: a forma das arestas não são relevantes, só importa a que vértices estão unidas. A posição dos vértices também não importa, e pode-se variar para obter um desenho mais claro.

Muitas redes de uso quotidiano podem ser modeladas com um grafo: uma rede de estradas que liga cidades, uma rede eléctrica ou a rede de drenaje de uma cidade.

Subgrafo

Um subgrafo de um grafo G é um grafo cujos conjuntos de vértices e arestas são subconjuntos dos de G . Diz-se que um grafo G contém a outro grafo H se algum subgrafo de G é H ou é isomorfo a H (dependendo das necessidades da situação).

O subgrafo induzido de G é um subgrafo G' de G tal que contém todas as arestas adjacentes ao subconjunto de vértices de G .

Definição:

Seja G=(V, A). G’=(V’,A’) diz-se subgrafo de G se:

1- V’ \subseteq V

2- A' \subseteq A

3- (V’,A’) é um grafo

G2 é um subgrafo de G.

Arquivo:Grafos1.jpg

Arestas dirigidas e não dirigidas

Grafo ejemplo 2.png

Em alguns casos é necessário atribuir um sentido às arestas, por exemplo, se quer-se representar a rede das ruas de uma cidade com suas direcções únicas. O conjunto de arestas será agora um subconjunto de todos os possíveis pares ordenados de vértices, com (a, b) ≠ (b, a). Os grafos que contêm arestas dirigidas se denominam grafos orientados, como o seguinte:

As arestas não orientadas se consideram bidirecionais para efeitos práticos (equivale a dizer que existem duas arestas orientadas entre os nós, a cada uma em um sentido).

No grafo anterior utilizou-se uma aresta que tem seus dois extremos idênticos: é um laço (ou bucle), e aparece também uma aresta bidirecional, e corresponde a duas arestas orientadas.

Aqui V = { a, b, c, d, e }, e A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Considera-se a característica de grau" (positivo ou negativo) de um vértice v (e indica-se como (v)), como a quantidade de arestas que chegam ou saem dele; para o caso de grafos não orientados, o grau de um vértice é simplesmente a quantidade de arestas incidentes a este vértice. Por exemplo, o grau positivo (saídas) de d é 3, enquanto o grau negativo (chegadas) de d é 0.

Segundo a terminología seguida em alguns problemas clássicos de Investigação Operativa (p.ex.: o Problema do fluxo máximo), a um vértice do que só saem arestas se lhe denomina fonte (no exemplo anterior, o vértice d); tem grau negativo 0. Pelo contrário, àqueles nos que só entram arestas se lhes denomina poço ou sumidero (no caso anterior, o vértice e); tem grau positivo 0. A seguir apresentam-se as implementações em maude de grafos não dirigidos e de grafos dirigidos.Nos dois casos, as especificações incluem, além das operações generadoras, outras operações auxiliares.

Ciclos e caminhos hamiltonianos

Artigo principal: Ciclo hamiltoniano
Exemplo de um ciclo hamiltoniano.

Um ciclo é uma sucessão de arestas adjacentes, onde não se percorre duas vezes a mesma aresta, e onde se regressa no ponto inicial. Um ciclo hamiltoniano tem ademais que percorrer todos os vértices exactamente uma vez (excepto o vértice do que parte e ao qual chega).

Por exemplo, em um museu grande (ao estilo do Louvre), o idóneo seria percorrer todas as salas uma sozinha vez, isto é procurar um ciclo hamiltoniano no grafo que representa o museu (os vértices são as salas, e as arestas os corredores ou portas entre elas).

Fala-se também de caminho hamiltoniano se não se impõe regressar no ponto de partida, como em um museu com uma única porta primeiramente. Por exemplo, um cavalo pode percorrer todas as lacunas de um tabuleiro de ajedrez sem passar duas vezes pela mesma: é um caminho hamiltoniano. Exemplo de um ciclo hamiltoniano no grafo do dodecaedro.

Hoje em dia, não se conhecem métodos gerais para achar um ciclo hamiltoniano em tempo polinomial, sendo a busca por força bruta de todos os possíveis caminhos ou outros métodos excessivamente caros. Existem, no entanto, métodos para descartar a existência de ciclos ou caminhos hamiltonianos em grafos pequenos.

O problema de determinar a existência de ciclos hamiltonianos, entra no conjunto dos NP-completos.

Caracterização de grafos

Grafos simples

Um grafo é simples se 1 aresta une dois vértices quaisquer. Isto é equivalente a dizer que uma aresta qualquer é a única que une dois vértices específicos.

Um grafo que não é simples se denomina Multigráfica ou Gráfo múltiplo.

Grafos conexos

Um grafo é conexo se a cada par de vértices está ligado por um caminho; isto é, se para qualquer par de vértices (a, b), existe ao menos um caminho possível desde a para b.

Um grafo é fortemente conexo se a cada par de vértices está ligado por ao menos dois caminhos disjuntos; isto é, é conexo e não existe um vértice tal que ao o sacar o grafo resultante seja disconexo.

É possível determinar se um grafo é conexo usando um algorítmo Busca em largura (BFS) ou Busca em profundidade (DFS).

Em termos matemáticos a propriedade de um grafo de ser (fortemente) conexo permite estabelecer em base a ele uma relação de equivalencia para seus vértices, a qual leva a uma partição destes em componentes (fortemente) conexas", isto é, porções do grafo, que são (fortemente) conexas quando se consideram como grafos isolados. Esta propriedade é importante para muitas demonstrações em teoria de grafos.


Arquivo:GrafoConexo.jpg

Grafos completos

Artigo principal: Grafo completo

Um grafo é completo se existem arestas unindo todos os pares possíveis de vértices. Isto é, todo o par de vértices (a, b) deve ter uma aresta e que os une.

O conjunto dos grafos completos é denominado usualmente \mathbb{K}, sendo \mathbb{K}_n o grafo completo de n vértices.

Um \mathbb{K}_n, isto é, grafo completo de vértices tem exactamente \frac{n(n-1)}{2} arestas.

A representação gráfica dos \mathbb{K}_n como os vértices de um polígono regular dá conta de sua peculiar estrutura.

Grafos bipartitos

Artigo principal: Grafo bipartito

Um grafo G é bipartito se pode expressar-se como G = \{V_1 \cup V_2, A\} (isto é, seus vértices são a união de dois grupos de vértices), baixo as seguintes condições:

Baixo estas condições, o grafo considera-se bipartito, e pode descrever-se informalmente como o grafo que une ou relaciona dois conjuntos de elementos diferentes, como aqueles resultantes dos exercícios e puzzles nos que deve se unir um elemento da coluna A com um elemento da coluna B.

Operações em Grafos

Subdivisión elementar de uma aresta

u \stackrel{e}{\rightarrow} v converte-se em u \stackrel{e'}{\rightarrow} w \stackrel{e''}{\rightarrow} v

Substitui-se a aresta e=\left\{u,v\right\} por duas arestas e'=\left\{u,w\right\} e''=\left\{w,v\right\} e um vértice w.

Após realizar esta operação, o grafo combina com um vértice e uma aresta mais.

Eliminação débil de um vértice

Se v \in V_G e g(v)= 2 (Seja v um vértice do grafo e de grau dois) eliminá-lo debilmente significa substituir por uma aresta que une os vértices adjacentes a .. v

u \stackrel{e'}{\rightarrow} w \stackrel{e''}{\rightarrow} v converte-se em u \stackrel{e}{\rightarrow} v

Então e' e e'' desaparecem e aparece e=\left\{u,v\right\}

Homeomorfismo de grafos

Artigo principal: Homeomorfismo de grafos

Dois grafos G_1 e G_2 são homeomorfos se ambos podem se obter a partir do mesmo grafo com uma sucessão de subdivisiones elementares de arestas.

Árvores

Artigo principal: Árvore (teoria de grafos)
Exemplo de árvore.

Um grafo que não tem ciclos e que liga a todos os pontos, se chama uma árvore. Em um grafo com n vértices, as árvores têm exactamente n - 1 arestas, e há nn-2 árvores possíveis. Sua importância radica em que as árvores são grafos que ligam todos os vértices utilizando o menor número possível de arestas. Um importante campo de aplicação de seu estudo encontra-se na análise filogenético, o da filiación de entidades que derivam umas de outras em um processo evolutivo, que se aplica sobretudo à averiguación do parentesco entre espécies; ainda que usou-se também, por exemplo, no estudo do parentesco entre línguas.

Grafos ponderados ou etiquetados

Em muitos casos, é preciso atribuir à cada aresta um número específico, chamado valuación, ponderação ou custo segundo o contexto, e obtém-se assim um grafo avaliado.
Formalmente, é um grafo com uma função v: A → R+.

Por exemplo, um representante comercial tem que visitar n cidades conectadas entre si por estradas; seu interesse previsível será minimizar a distância percorrida (ou o tempo, se podem-se prever atascos). O grafo correspondente terá como vértices as cidades, como arestas as estradas e a valuación será a distância entre elas.
E, por enquanto, não se conhecem métodos gerais para achar um ciclo de valuación mínima, mas sim para os caminhos desde a até b, sem mais condição.

Teorema das quatro cores

Artigo principal: Teorema das quatro cores
Em 1852 Francis Guthrie propôs o problema das quatro cores.

Outro problema famoso relativo aos grafos: Quantos cores são necessárias para desenhar um mapa político, com a condição óbvia que dois países adjacentes não possam ter a mesma cor? Supõe-se que os países são de um sozinho pedaço, e que o mundo é esférico ou plano. Em um mundo em forma de touro; o teorema seguinte não é válido:

Quatro cores são sempre suficientes para colorir um mapa.

O mapa seguinte mostra que três cores não bastam: Se começa-se pelo país central a e se esfuerza um em utilizar o menor número de cores, então na coroa ao redor de a alternam duas cores. Chegando ao país h tem-se que introduzir uma quarta cor. O mesmo sucede em i se emprega-se o mesmo método.

A forma precisa da cada país não importa; o único relevante é saber que país toca a que outro. Estes dados estão incluídos no grafo onde os vértices são os países e as arestas ligam os que justamente são adjacentes. Então a questão equivale a atribuir à cada vértice uma cor diferente do de seus vizinhos.

Temos visto que três cores não são suficientes, e demonstrar que com cinco sempre se chega, é bastante fácil. Mas o teorema das quatro cores não é nada óbvio. Prova disso é que se tiveram que empregar computadores para acabar a demonstração (se fez um programa que permitiu verificar uma multidão de casos, o que poupou muitíssimo tempo aos matemáticos). Foi a primeira vez que a comunidade matemática aceitou uma demonstração assistida por computador, o que tem criado uma forte polémica dentro da comunidade matemática, chegando em alguns casos a se propor a questão de que esta demonstração e sua aceitação é um dos momentos que têm gerado uma das mais terríveis crises no mundo matemático.

Coloración de grafos

Artigo principal: Coloro de grafos

Definição: Se G=(V, E) é um grafo não dirigido, uma coloración própria de G, ocorre quando colorimos os vértices de G de maneira que se {a, b} é uma aresta em G então a e b têm diferentes cores. (Portanto, os vértices adjacentes têm cores diferentes). O número mínimo de cores necessários para uma coloración própria de G é o número cromático de G e escreve-se como C (G). Seja G um grafo não dirigido seja λ o número de cores disponíveis para a coloración própria dos vértices de G. Nosso objectivo é encontrar uma função polinomial P (G,λ), na variável λ, chamada polinômio cromático de G , que nos indique o número de coloraciones próprias diferentes dos vértices de G, usando um máximo de cores.

Descomposição de polinômios cromáticos. Se G=(V, E) é um grafo conexo e e pertence a Ε , então: P (G,λ)=P (G+e,λ)+P (G/e,λ), onde G/e é o grafo se obtene por contracção de arestas.

Para qualquer grafo G, o termo constante em P (G,λ) é 0

Seja G=(V, E) com |E|>0 então, a soma dos coeficientes de P (G,λ) é 0.

Seja G=(V, E), com a , b pertencentes ao conjunto de vértices V mas {a, b}=e, não pertencente à o conjunto de arestas E. Escrevemos G+e para o grafo que se obtém de G ao acrescentar a aresta e={a, b}. Ao identificar os vértices a e b em G, obtemos o subgrafo G++e de G.

Modelo:ORDENAR:=== Grafos planos ===

Artigo principal: Grafo plano
Arquivo:Grafo exemplo 6.png
Um grafo é plano se pode-se desenhar sem cruzes de arestas. O problema das três casas e os três poços tem solução sobre o touro, mas não no plano.

Quando um grafo ou multigrafo se pode desenhar em um plano sem que dois segmentos se cortem, se diz que é plano.

Um jogo muito conhecido é o seguinte: Desenham-se três casas e três poços. Todos os vizinhos das casas têm o direito de utilizar os três poços. Como não se levam bem em absoluto, não querem se cruzar jamais. É possível traçar os nove caminhos que juntam as três casas com os três poços sem que tenha cruzes?

Qualquer disposição das casas, os poços e os caminhos implica a presença de ao menos um cruze.

Seja Kn o grafo completo com n vértices, Kn, p é o grafo bipartito de n e p vértices.

O jogo anterior equivale a descobrir se o grafo bipartito completo K3,3 é plano, isto é, se pode-se desenhar em um plano sem que tenha cruzes, sendo a resposta que não. Em general, pode determinar-se que um grafo não é plano, se em seu desenho pode encontrasse uma estrutura análoga (conhecida como menor) a K5 ou a K3,3.

Estabelecer que grafos são planos não é óbvio, e é um problema que tem que ver com topologia.

Diâmetro

Arquivo:Grafo exemplo 7.png
Na figura nota-se que K4 é plano (desviando a aresta ab ao exterior do quadrado), que K5 não o é, e que K3,2 o é também (desvios em cinza).

Em um grafo, a distância entre dois vértices é o menor número de arestas de um percurso entre eles. O diâmetro, em uma figura como em um grafo, é a menor distância entre dois pontos da mesma.

O diâmetro do Kn é 1, e o do Kn,p é 2. Um diâmetro infinito pode significar que o grafo tem uma infinidad de vértices ou simplesmente que não é conexo. Também se pode considerar o diâmetro média, como a média das distâncias entre dois vértices.

O mundo de Internet tem posto de moda essa ideia do diâmetro: Se descartamos os lugares que não têm enlaces, e escolhemos duas páginas site a esmo : Em quantos cliques se pode passar da primeira à segunda? O resultado é o diâmetro da Rede, vista como um grafo cujos vértices são os lugares, e cujas arestas são logicamente os enlaces.

No mundo real há uma analogia: tomando a esmo dois seres humanos do mundo, Em quantos saltos se pode passar de um a outro, com a condição de só saltar de uma pessoa a outra quando elas se conhecem pessoalmente? Com esta definição, estima-se que o diâmetro da humanidade é de... oito somente!

Este conceito reflete melhor a complexidade de uma rede que o número de seus elementos.

Algorítmos importantes

Aplicações

Graças à teoria de grafos podem-se resolver diversos problemas como por exemplo a síntese de circuitos sequenciais, contadores ou sistemas de abertura. Utiliza-se para diferentes áreas por exemplo, Desenho computacional, em toda as áreas de Engenharia.

Os grafos utilizam-se também para modelar trajectos como o de uma linha de autocarro através das ruas de uma cidade, no que podemos obter caminhos óptimos para o trajecto aplicando diversos algorítmos como pode ser o algorítmo de Floyd .

Para a administração de projectos, utilizamos técnicas como PERT nas que se modelam os mesmos utilizando grafos e optimizando os tempos para concretar os mesmos.

A teoria de grafos também tem servido de inspiração para as ciências sociais, em especial para desenvolver um conceito não metafórico de rede social que substitui os nós pelos actores sociais e verifica a posição, centralidad e importância da cada actor dentro da rede. Esta medida permite quantificar e abstraer relações complexas, de maneira que a estrutura social pode se representar graficamente. Por exemplo, uma rede social pode representar a estrutura de poder dentro de uma sociedade ao identificar os vínculos (arestas), sua direcção e intensidade e dá ideia da maneira em que o poder se transmite e a quem.

Os grafos são importantes no estudo da biologia e hábitat. O vértice representa um hábitat e as arestas (ou "edges" em inglês) representa os caminhos dos animais ou as migraciónes. Com esta informação, os cientistas podem entender como isto pode mudar ou afectar às espécies em sua hábitat.

Pesquisadores relevantes em Teoria de grafos

Veja-se também

Referências

Enlaces externos

O conteúdo deste artigo incorpora material de uma entrada da Enciclopedia Livre Universal, publicada em espanhol baixo a licença Creative Commons Compartilhar-Igual 3.0.

Obtido de http://ks312095.kimsufi.com../../../../articles/c/ou/m/Comunicações_de_Andorra_46cf.html"