Gráfico Planar:
Um gráfico é dito planar se puder ser desenhado em um plano de modo que nenhuma aresta se cruze.
Exemplo: O gráfico mostrado na fig é um gráfico planar.
Região de um gráfico: Considere um gráfico planar G=(V,E). Uma região é definida como uma área do plano que é limitada por arestas e não pode ser subdividida posteriormente. Um gráfico planar divide os planos em uma ou mais regiões. Uma dessas regiões será infinita.
Região Finita: Se a área da região for finita, então essa região é chamada de região finita.
Região infinita: Se a área da região for infinita, essa região é chamada de região infinita. Um gráfico planar possui apenas uma região infinita.
Exemplo: Considere o gráfico mostrado na Fig. Determine o número de regiões, regiões finitas e uma região infinita.
Solução: Existem cinco regiões no gráfico acima, ou seja, r 1 ,r 2 ,r 3 ,r 4 ,r 5 .
Existem quatro regiões finitas no gráfico, ou seja, r 2 ,r 3 ,r 4 ,r 5 .
Existe apenas uma região finita, ou seja, r 1
Propriedades de gráficos planares:
- Se um grafo planar conectado G tem e arestas e r regiões, então r ≦
e. - Se um grafo planar conectado G tem e arestas, v vértices e r regiões, então v-e+r=2.
- Se um grafo planar conectado G tem e arestas e v vértices, então 3v-e≧6.
- Um gráfico completo K n é planar se e somente se n <5. < li>
- Um gráfico bipartido completo K homem é planar se e somente se m3.
Exemplo: Prove que o gráfico completo K 4 é planar.
Solução: O gráfico completo K 4 contém 4 vértices e 6 arestas.
Sabemos que para um gráfico planar conectado 3v-e≧6.Portanto, para K 4 , temos 3x4-6=6 que satisfaz a propriedade (3).
Assim K 4 é um gráfico planar. Portanto provado.
Gráfico Não Planar:
Um gráfico é dito não planar se não puder ser desenhado em um plano de modo que nenhuma aresta se cruze.
Exemplo: Os gráficos mostrados na fig são gráficos não planares.
Esses gráficos não podem ser desenhados em um plano de modo que nenhuma aresta se cruze, portanto, são gráficos não planares.
Propriedades de gráficos não planos:
Um grafo é não planar se e somente se contém um subgrafo homeomórfico a K 5 ou K 3.3
Exemplo 1: Mostre que K 5 é não-plano.
Solução: O gráfico completo K 5 contém 5 vértices e 10 arestas.
Agora, para um gráfico planar conectado 3v-e≧6.
Portanto, para K 5 , temos 3 x 5-10=5 (o que não satisfaz a propriedade 3 porque deve ser maior ou igual a 6).
Assim, K 5 é um gráfico não planar.
Exemplo2: Mostre que os gráficos mostrados na fig são não planares encontrando um subgrafo homeomorfo a K 5 ou K 3.3 .
Solução: Se removermos as arestas (V 1 ,EM 4 ),(EM 3 ,EM 4 )e (V 5 ,EM 4 ) o gráfico G 1 , torna-se homeomorfo a K 5 .Portanto, não é plano.
Se removermos a aresta V 2,V 7) o gráfico G 2 torna-se homeomorfo a K 3.3 .Portanto, é um não plano.
Coloração de gráfico:
Suponha que G= (V,E) seja um grafo sem arestas múltiplas. Uma coloração de vértices de G é uma atribuição de cores aos vértices de G tal que vértices adjacentes tenham cores diferentes. Um grafo G é M-Colorível se existe uma coloração de G que usa M-Cores.
Coloração adequada: Uma coloração é adequada se quaisquer dois vértices adjacentes uev tiverem cores diferentes, caso contrário, é chamada de coloração imprópria.
Exemplo: Considere o gráfico a seguir e a cor C = {r, w, b, y}. Pinte o gráfico corretamente usando todas as cores ou menos cores.
O gráfico mostrado na fig é um mínimo de 3 cores, portanto x(G)=3
Solução: A Fig mostra o gráfico devidamente colorido com todas as quatro cores.
A Fig mostra o gráfico devidamente colorido com três cores.
Número cromático de G: O número mínimo de cores necessárias para produzir uma coloração adequada de um gráfico G é chamado de número cromático de G e é denotado por x(G).
Exemplo: O número cromático de K n é n.
Solução: Uma coloração de K n pode ser construído usando n cores atribuindo cores diferentes a cada vértice. Não podem ser atribuídas as mesmas cores a dois vértices, uma vez que cada dois vértices deste gráfico são adjacentes. Daí o número cromático de K n =n.
Aplicações de coloração de gráficos
Algumas aplicações de coloração de gráficos incluem:
- Registrar Alocação
- Colorir Mapa
- Verificação de gráfico bipartido
- Atribuição de radiofrequência móvel
- Fazendo um cronograma, etc.
Enuncie e prove o Teorema do Aperto de Mão.
Teorema do aperto de mão: A soma dos graus de todos os vértices em um grafo G é igual ao dobro do número de arestas do grafo.
Matematicamente pode ser afirmado como:
∑ v∈V grau(v)=2e
Prova: Seja G = (V, E) um gráfico onde V = {v 1 ,em 2 , . . . . . . . . . .} seja o conjunto de vértices e E = {e 1 ,e 2 . . . . . . . . . .} seja o conjunto de arestas. Sabemos que cada aresta está entre dois vértices, portanto fornece grau um para cada vértice. Portanto, cada aresta contribui com o grau dois para o gráfico. Portanto, a soma dos graus de todos os vértices é igual ao dobro do número de arestas em G.
Portanto, ∑ v∈V grau(v)=2e
