O QUE É UM GRAFO PLANAR?

[pic 1]

THALES RIPA USAN

PLANARIDADE DE GRAFOS

Assis/SP

                            2017

SUMÁRIO

INTRODUÇÃO        3

O QUE É UM GRAFO PLANAR?        4

TEOREMA DE KURATOWSKI        6

CARACTERÍSTICA DE EULER        7

TESTE DE PLANARIDADE        8

CONCLUSÃO        9

REFERÊNCIAS BIBLIOGRÁFICAS        10

INTRODUÇÃO

Grafos planares são grafos em que suas arestas não se sobrepõe umas as outras, e essa pesquisa tem o objetivo de esclarecer o que é, onde são usados e como podem sem identificados atraves de testes os grafos planares.

Apesar de simples, a pesquisa é objetiva em relação ao tema, dando detalhes principais e de fácil entendimento pelo leitor.

A falta de conteúdo dos algoritmos atrapalha o entendimento dos testes de planaridade, porém, apesar do pouco conteúdo, explica o que é o teste de forma clara.

O QUE É UM GRAFO PLANAR?

Em teoria dos grafos, um grafo plano é, basicamente, um grafo cujas arestas não se sobrepõe, ou seja, não se cruzam. Um grafo é plano quando ele é realizável em um plano.

Porém, há alguns grafos que ocorre o cruzamento de arestas que pode se tornar um grafo plano, fazendo uma representação semelhante, porém de outro ângulo, como mostra o exemplo abaixo.

[pic 2]

 (Imagem: Prof. Flávio Humberto Cabral Nunes, UFMG)

Sendo assim, na figura a esquerda vemos um grafo planar, que significa que ele pode se tornar um grafo sem arestas sem cruzando.

Já o da direita é um grafo plano, já que não há cruzamento de arestas.

Um exemplo de uma aplicação de um grafo planar seria a representação de mapas de estradas e rodovias com ausência de viadutos, podendo assim, serem representadas numa folha, sem que as arestas se cruzem.

        [pic 3]

(Imagem: DevMedia)

Outro exemplo é a aplicação de grafos em uma placa de circuito impresso, que deve ser representada por um grafo planar, onde os circuitos não se cruzam.

[pic 4]

(Imagem: Antônio Alfredo Ferreira Loureiro, UFMG)

TEOREMA DE KURATOWSKI

Kazimierz Kuratowski (Varsovia, 2 de fevereiro de 1896 - 18 de junho de 1980) foi um matemático e lógico polonês.

Kuratowski mostrou que um grafo é planar se e somente se ele não contém um subgrafo que é uma subdivisão do K5 e nem do K3,3.

Uma subdivisão de um grafo consiste em colocar vértices “no meio” das arestas. Por exemplo, na Figura 3 temos uma subdivisão do K3,3 e segundo o teorema de Kuratowski, este não é um grafo planar.

[pic 5]

(Imagem: Blog do Kunigami)

CARACTERÍSTICA DE EULER

Leonhard Euler (Basileia, 15 de abril de 1707 - 18 de setembro de 1783) foi um matemático e físico suiço.

O teorema de Euler diz que para todo poliedro V - A + F = 2, onde V é o número de vértices, A as arestas e F as faces. Esse teorema funciona perfeitamente com grafos planos, porém possui falhas com objetos sólidos.

Um poliedro é uma reunião de um número finito de polígonos convexos, chamados de Faces do Poliedro. Os lados desses polígonos chama-se arestas  do poliedro, e os vértices, também de vértices do poliedro.

Exige-se ainda que a interseção de duas faces quaisquer do poliedro seja uma aresta comum a essas faces, ou um vértice comum, ou seja, vazia.

Um poliedro é convexo quando qualquer reta, não paralela a nenhuma de suas faces, o corta em no máximo 2 pontos. A imagem abaixo mostra um poliedro convexo á esquerda e um não-convexo á direita.

[pic 6]

(Fonte: Gildeci José Justino, UFPB)

Assim, a Característica de Euler mostra se o poliedro é sólido ou plano através de suas fórmulas.

TESTE DE PLANARIDADE

O teste de planaridade serve para determinar se um dado grafo pode ser desenhado no plano de tal forma que suas arestas só se intersectem nos pontos extremos.