Grafos: Conceitos e Propriedades

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
*
Pontes de Königsberg
Em Königsberg, a ex-capital da Prússia, atual Kaliningrado, sete pontes atravessavam o rio Pregel. Os habitantes locais queriam saber como seria possível fazer um trajeto que passasse pelas sete pontes sem atravessar uma delas mais de uma vez.
*
*
Figura 1: O Problema das Pontes de Königsberg
Entre as regiões A, B, C e D há sete pontes interligando-as. O objetivo desse problema era encontrar um caminho que atravessasse cada uma das sete pontes uma única vez.
*
*
Proposta de Euler
Para demonstrar que um trajeto desse tipo era impossível, Euler criou um gráfico em que cada porção de terra era representada por um ponto, ou nódulo, e cada ponte por uma linha, ou ligação. Depois elaborou um teorema que relacionava o número de ligações que passava por cada nódulo para saber se era possível fazer o trajeto do gráfico , o que nesse caso se mostrou impossível.
*
*
Figura 2: Gráfico criado por Euler
Note que as regiões foram representadas por pontos e as pontes por segmentos de retas e arcos.
*
*
Abordagem Conceitual
O salto conceitual dado por Euler foi perceber que o importante para resolver o problema não era a informação sobre a posição exata das pontes, mas como elas se ligavam. O mapa do metrô de Londres utilizou essa ideia, e embora não geometricamente exato, é fiel à maneira como as linhas do metrô se interligam. O teorema de Euler inaugurou a teoria gráfica e pressagiou o desenvolvimento da topologia, uma área muito fértil da matemática que estuda as propriedades de objetos que não se alteram quando são comprimidos, distorcidos ou alongados.
*
*
Figura 3: Mapa do Metrô de Londres
Observe que cada uma das estações são representadas por pontos (nós) e o que as liga são segmentos de retas ou arcos (arestas).
*
*
O problema citado serve de orientação e ao mesmo tempo de motivação para o estudo de Grafos. Antes de aprofundar no estudo de Grafos, vamos entender alguns conceitos básicos, tais como: definição, representações e algumas propriedades essenciais.
*
*
Definição
Um grafo é um conjunto não vazio de nós (vértices) e um conjunto de arcos (arestas) tais que cada arco conecta dois nós
Um grafo é uma tripla ordenada (N, A, g), onde
N = um conjunto não vazio de nós (vértices)
A = um conjunto de arcos (arestas)
g = uma função que associa a cada arco a um par não ordenado x-y de nós, chamamos de extremidades de a.
*
*
Grafo Direcionado
Um grafo direcionado (dígrafo) é uma tripla ordenada (N, A, g), onde
N = um conjunto não vazio de nós
A = um conjunto de arcos
g = uma função que associa a cada arco um par ordenado (x, y) de nós, onde x é o ponto inicial (extremidade inicial) e y é o ponto final (extremidade final) de a.
*
*
Terminologia da Teoria dos Grafos
Dois nós em um grafo são ditos adjacentes se ambos são as extremidades de algum arco.
Um laço em um grafo é um arco com extremidades n-n para algum nó n.
Usaremos a terminologia grafo sem arcos no caso em que o grafo não tiver nenhum laço.
Dois arcos com as mesmas extremidades são ditos arcos paralelos.
*
*
Figura 4: Exemplo de Grafo
Note que este grafo apresenta 5 nós (vértices) e 6 arcos (arestas), das quais podemos observar a presença de um laço no vértice de número 2, arcos paralelos com extremidades nos vértices 1 e 2 e um nó isolado que seria o nó de número 5.
*
*
Um grafo simples é um grafo sem laços nem arcos paralelos.
Um nó isolado é um nó que não é adjacente a nenhum outro.
O grau de um nó é o número de extremidades de arcos naquele nó.
Um grafo completo é um grafo no qual dois nós distintos quaisquer são adjacentes.
Um subgrafo de um grafo consiste em um conjunto de nós e um conjunto de arcos que são subconjuntos do conjunto original de nós e arcos.
*
*
Figura 5: Exemplos de Subgrafos do Grafo da Figura 4
Note que o primeiro subgrafo é um grafo simples e completo.
*
*
Caminho, Comprimento e Ciclo
Um caminho do nó n0 para o nó nk é uma sequência n0, a0, n1, a1, ... , nk-1, ak-1, nk de nós e arcos onde, para cada i, as extremidades do arco ai são ni - ni+1.
O comprimento de um caminho é o número de arcos que ele contém; se um arco for usado mais de uma vez, ele é contado cada vez que é usado.
Um ciclo em um grafo é um caminho de algum nó n0 para ele mesmo tal que nenhum arco aparece mais de uma vez, n0 é o único nó que aparece mais de uma vez e n0 aparece nas extremidades. Um grafo sem ciclo é dito acíclico.
*
*
Grafos Conexos e Grafos Simples e Completos
Um grafo é denominado conexo quando existe um caminho de qualquer nó para qualquer outro. Ambos os grafos na Figura 5 são conexos, mas o grafo da Figura 4 não é.
Um grafo simples e completo com n vértices é denotado por Kn, quando n for maior ou igual a 4, um dos desenhos possíveis para esses grafos simples e completos seria o polígono convexo de n lados com todas as diagonais.
*
*
Grafo Bipartido Completo
Um grafo é um grafo bipartido completo se seus nós podem ser divididos em dois conjuntos disjuntos não vazios N1 e N2 tais que dois nós são adjacentes se, e somente se, um deles pertence a N1 e o outro pertence a N2. Se | N1| = m e | N2| = n, um tal grafo é denotado por Km,n.
*
*
Figura 6: Exemplo de um Grafo Bipartido Completo
O grafo é denotado por K4,3, pois seus nós podem ser divididos em dois grupos de nós, um contendo 4 nós e o outro contendo 3 nós. 
*
*
Caminho para Grafo Direcionado
O conceito de caminho pode ser estendido a um grafo direcionado de maneira natural: um caminho de um nó n0 para um nó nk em um grafo direcionado é uma sequência 
n0, a0, n1, a1, ... , nk-1, ak-1, nk
	onde, para cada i, ni é acessível de n0. A definição de ciclo também pode ser estendida para grafos direcionados.
*
*
Exercícios de Fixação
1) Esboce um grafo com nós {1, 2, 3, 4, 5}, arcos {a1, a2, a3, a4, a5, a6} e função g dada por g(a1) = 1-2, g(a2) = 1-3, g(a3) = 3-4, g(a4) = 3-4, g(a5) = 4-5 e g(a6) = 5-5.
2) Considere o grafo do problema anterior.
	a) Encontre dois nós que não são adjacentes.
	b) Encontre um nó adjacente a si mesmo.
	c) Encontre um laço.
	d) Encontre dois arcos paralelos.
	e) Encontre o grau do nó 3.
	f) Encontre um caminho de comprimento 5.
	g) encontre um ciclo.
	h) Esse grafo é completo? Ele é conexo? 
*
*
3) Esboce uma figura para cada um dos seguintes grafos.
	a) um grafo simples com três vértices, cada qual com grau 2.
	b) quatro vértices, com ciclos de tamanho 1, 2, 3 e 4.
4) Desenhe K5.
5) Encontre uma fórmula para o número de arestas de Kn.
6) Desenhe K3,3.
7) Prove que todo grafo completo é conexo.
8) Encontre um grafo conexo que não é completo.
9) Use o grafo direcionado da figura a seguir para responder as perguntas abaixo.
	a) Qual o comprimento do menor caminho entre 3 e 6?
	b) Qual é o caminho do vértice 1 ao vértice 6 com comprimento 8?
*
*
Figura 7: Grafo referente ao exercício 8.
*
*
Vídeos sobre Grafos e a Solução de Euler
Vídeo 1: Solução do Problema das Pontes.
Vídeo 2: Situação-Problema relacionada com Grafos.
*