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.
invólucro de texto css
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, r1,r2,r3,r4,r5.
Existem quatro regiões finitas no gráfico, ou seja, r2,r3,r4,r5.
Existe apenas uma região finita, ou seja, r1
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 Kné planar se e somente se n<5.< li>
- Um gráfico bipartido completo Khomemé planar se e somente se m3.
Exemplo: Prove que o gráfico completo K4é planar.
Solução: O gráfico completo K4contém 4 vértices e 6 arestas.
Sabemos que para um gráfico planar conectado 3v-e≧6.Portanto, para K4, temos 3x4-6=6 que satisfaz a propriedade (3).
quantas semanas por mês
Assim K4é 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 K5ou K3.3
camadas do modelo osi
Exemplo 1: Mostre que K5é não-plano.
Solução: O gráfico completo K5contém 5 vértices e 10 arestas.
Agora, para um gráfico planar conectado 3v-e≧6.
Portanto, para K5, temos 3 x 5-10=5 (o que não satisfaz a propriedade 3 porque deve ser maior ou igual a 6).
Assim, K5é 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 K5ou K3.3.
Solução: Se removermos as arestas (V1,EM4),(EM3,EM4)e (V5,EM4) o gráfico G1, torna-se homeomorfo a K5.Portanto, não é plano.
Se removermos a aresta V2,V7) o gráfico G2torna-se homeomorfo a K3.3.Portanto, é um não plano.
bytes para string python
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 Kné n.
Solução: Uma coloração de Knpode 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 Kn=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∈Vgrau(v)=2e
Prova: Seja G = (V, E) um gráfico onde V = {v1,em2, . . . . . . . . . .} seja o conjunto de vértices e E = {e1,e2. . . . . . . . . .} 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∈Vgrau(v)=2e
'o que é 10 de 100'