Teoria dos grafos - Tipos de grafos
Existem vários tipos de gráficos, dependendo do número de vértices, número de arestas, interconectividade e sua estrutura geral. Discutiremos apenas alguns tipos importantes de gráficos neste capítulo.
Gráfico Nulo
A graph having no edges é chamado de Gráfico Nulo.
Exemplo
No gráfico acima, existem três vértices chamados 'a', 'b' e 'c', mas não há arestas entre eles. Portanto, é um gráfico nulo.
Gráfico Trivial
UMA graph with only one vertex é chamado de Gráfico Trivial.
Exemplo
No gráfico mostrado acima, há apenas um vértice 'a' sem outras arestas. Portanto, é um gráfico Trivial.
Gráfico não direcionado
Um gráfico não direcionado contém arestas, mas as arestas não são direcionadas.
Exemplo
Neste gráfico, 'a', 'b', 'c', 'd', 'e', 'f', 'g' são os vértices, e 'ab', 'bc', 'cd', 'da ',' ag ',' gf ',' ef 'são as arestas do gráfico. Por ser um gráfico não direcionado, as arestas 'ab' e 'ba' são iguais. Da mesma forma outras arestas também consideradas da mesma maneira.
Gráfico Direcionado
Em um gráfico direcionado, cada aresta tem uma direção.
Exemplo
No gráfico acima, temos sete vértices 'a', 'b', 'c', 'd', 'e', 'f' e 'g', e oito arestas 'ab', 'cb', ' dc ',' ad ',' ec ',' fe ',' gf 'e' ga '. Por ser um gráfico direcionado, cada aresta traz uma marca de seta que mostra sua direção. Observe que em um gráfico direcionado, 'ab' é diferente de 'ba'.
Gráfico Simples
Um gráfico with no loops e não parallel edges é chamado de gráfico simples.
O número máximo de arestas possíveis em um único gráfico com 'n' vértices é n C 2 onde n C 2 = n (n - 1) / 2.
O número de gráficos simples possíveis com 'n' vértices = 2 n c 2 = 2 n (n-1) / 2 .
Exemplo
No gráfico a seguir, existem 3 vértices com 3 arestas que é o máximo excluindo as arestas paralelas e loops. Isso pode ser provado usando as fórmulas acima.
O número máximo de arestas com n = 3 vértices -
O número máximo de gráficos simples com n = 3 vértices -
Estes 8 gráficos são mostrados abaixo -
Gráfico Conectado
Um gráfico G é dito estar conectado if there exists a path between every pair of vertices. Deve haver pelo menos uma aresta para cada vértice do gráfico. Para que possamos dizer que está conectado a algum outro vértice do outro lado da aresta.
Exemplo
No gráfico a seguir, cada vértice tem sua própria aresta conectada a outra aresta. Portanto, é um gráfico conectado.
Gráfico desconectado
Um grafo G está desconectado, se não contiver pelo menos dois vértices conectados.
Exemplo 1
O gráfico a seguir é um exemplo de um gráfico desconectado, onde há dois componentes, um com 'a', 'b', 'c', 'd' vértices e outro com 'e', 'f', 'g', vértices 'h'.
Os dois componentes são independentes e não conectados um ao outro. Por isso é chamado de gráfico desconectado.
Exemplo 2
Neste exemplo, existem dois componentes independentes, abfe e cd, que não estão conectados um ao outro. Portanto, este é um gráfico desconectado.
Gráfico Regular
Um gráfico G é considerado regular, if all its vertices have the same degree. Em um gráfico, se o grau de cada vértice é 'k', então o gráfico é chamado de 'gráfico regular k'.
Exemplo
Nos gráficos a seguir, todos os vértices possuem o mesmo grau. Portanto, esses gráficos são chamados de gráficos regulares.
Em ambos os gráficos, todos os vértices têm grau 2. Eles são chamados de gráficos 2-regulares.
Gráfico Completo
Um gráfico simples com 'n' vértices mútuos é chamado de gráfico completo e é denoted by ‘Kn’. No gráfico,a vertex should have edges with all other vertices, então chamado de gráfico completo.
Em outras palavras, se um vértice está conectado a todos os outros vértices em um gráfico, ele é chamado de gráfico completo.
Exemplo
Nos gráficos a seguir, cada vértice no gráfico está conectado com todos os vértices restantes no gráfico, exceto por ele mesmo.
No gráfico I,
| uma | b | c | |
|---|---|---|---|
| uma | Não conectado | Conectado | Conectado |
| b | Conectado | Não conectado | Conectado |
| c | Conectado | Conectado | Não conectado |
No gráfico II,
| p | q | r | s | |
|---|---|---|---|---|
| p | Não conectado | Conectado | Conectado | Conectado |
| q | Conectado | Não conectado | Conectado | Conectado |
| r | Conectado | Conectado | Não conectado | Conectado |
| s | Conectado | Conectado | Conectado | Não conectado |
Gráfico de Ciclo
Um gráfico simples com 'n' vértices (n> = 3) e 'n' arestas é chamado de gráfico de ciclo se todas as suas arestas formarem um ciclo de comprimento 'n'.
Se o grau de cada vértice no gráfico for dois, ele é chamado de Gráfico de Ciclo.
Notation- C n
Exemplo
Dê uma olhada nos gráficos a seguir -
O gráfico I possui 3 vértices com 3 arestas que estão formando um ciclo 'ab-bc-ca'.
O gráfico II possui 4 vértices com 4 arestas que estão formando um ciclo 'pq-qs-sr-rp'.
O gráfico III possui 5 vértices com 5 arestas que estão formando um ciclo 'ik-km-ml-lj-ji'.
Portanto, todos os gráficos fornecidos são gráficos de ciclo.
Gráfico de roda
Um gráfico de roda é obtido de um gráfico de ciclo C n-1 adicionando um novo vértice. Esse novo vértice é chamado deHubque está conectado a todos os vértices de C n .
Notação - W n
Nº de arestas em W n = Nº de arestas do cubo para todos os outros vértices +
Número de arestas de todos os outros nós no grafo de ciclo sem hub.
= (n – 1) + (n – 1)
= 2 (n – 1)
Exemplo
Dê uma olhada nos gráficos a seguir. Eles são todos gráficos de roda.
No gráfico I, ele é obtido de C 3 adicionando um vértice no meio denominado 'd'. É denotado como W 4 .
Número de arestas em W4 = 2 (n-1) = 2 (3) = 6
No gráfico II, ele é obtido de C4 adicionando um vértice no meio denominado 't'. É denotado como W 5 .
Número de arestas em W5 = 2 (n-1) = 2 (4) = 8
No gráfico III, é obtido a partir de C 6 adicionando um vértice no meio denominado 'o'. É denotado como W 7 .
Número de arestas em W4 = 2 (n-1) = 2 (6) = 12
Gráfico Cíclico
Um gráfico with at least one ciclo é chamado de gráfico cíclico.
Exemplo
No gráfico de exemplo acima, temos dois ciclos abcda e cfgec. Por isso é chamado de gráfico cíclico.
Gráfico Acíclico
Um gráfico with no cycles é chamado de gráfico acíclico.
Exemplo
No gráfico de exemplo acima, não temos nenhum ciclo. Portanto, é um gráfico não cíclico.
Gráfico Bipartido
Um grafo simples G = (V, E) com partição de vértice V = {V 1 , V 2 } é chamado de grafo bipartidoif every edge of E joins a vertex in V1 to a vertex in V2.
Em geral, um grafo Bipertite possui dois conjuntos de vértices, digamos, V1 e V2, e se uma aresta for desenhada, ela deve conectar qualquer vértice do conjunto V 1 a qualquer vértice do conjunto V 2 .
Exemplo
Neste gráfico, você pode observar dois conjuntos de vértices - V 1 e V 2 . Aqui, duas arestas chamadas 'ae' e 'bd' estão conectando os vértices de dois conjuntos V 1 e V 2 .
Gráfico Bipartido Completo
Um grafo bipartido 'G', G = (V, E) com partição V = {V 1 , V 2 } é considerado um grafo bipartido completo se cada vértice em V 1 estiver conectado a cada vértice de V 2 .
Em geral, um grafo bipartido completo conecta cada vértice do conjunto V 1 a cada vértice do conjunto V 2 .
Exemplo
O gráfico a seguir é um grafo bipartido completo porque possui arestas conectando cada vértice do conjunto V 1 a cada vértice do conjunto V 2 .
Se | V 1 | = me | V 2 | = n, então o grafo bipartido completo é denotado por K m, n .
- K m, n tem (m + n) vértices e (mn) arestas.
- K m, n é um gráfico regular se m = n.
Em geral, um complete bipartite graph is not a complete graph.
K m, n é um gráfico completo se m = n = 1.
O número máximo de arestas em um grafo bipartido com n vértices é -
[n 2 /4]
Se n = 10, k5, 5 = [n2 / 4] = [10 2 /4] = 25.
Da mesma forma, K6, 4 = 24
K7, 3 = 21
K8, 2 = 16
K9, 1 = 9
Se n = 9, k5, 4 = [n2 / 4] = [92/4] = 20
Da mesma forma, K6, 3 = 18
K7, 2 = 14
K8, 1 = 8
'G' é um gráfico bipartido se 'G' não tem ciclos de comprimento ímpar. Um caso especial de grafo bipartido é o grafo estrela.
Gráfico Estelar
Um grafo bipartido completo da forma K1, n-1 é um grafo estrela com n-vértices. Um grafo estrela é um grafo bipartido completo se um único vértice pertencer a um conjunto e todos os vértices restantes pertencerem ao outro conjunto.
Exemplo
Nos gráficos acima, de 'n' vértices, todos os 'n – 1' vértices estão conectados a um único vértice. Portanto, está na forma de K 1 , n-1 que são gráficos de estrelas.
Complemento de um gráfico
Seja 'G−' um grafo simples com alguns vértices como o de 'G' e uma aresta {U, V} está presente em 'G−', se a aresta não estiver presente em G. Isso significa que dois vértices são adjacentes em 'G−' se os dois vértices não forem adjacentes em G.
Se as arestas que existem no gráfico I estão ausentes em outro gráfico II, e se ambos os gráficos I e II são combinados para formar um gráfico completo, então o gráfico I e o gráfico II são chamados de complementos um do outro.
Exemplo
No exemplo a seguir, graph-I tem duas arestas 'cd' e 'bd'. Seu complemento gráfico-II tem quatro arestas.
Observe que as arestas no gráfico I não estão presentes no gráfico II e vice-versa. Portanto, a combinação de ambos os gráficos fornece um gráfico completo de 'n' vértices.
Note - Uma combinação de dois gráficos complementares fornece um gráfico completo.
Se 'G' for qualquer gráfico simples, então
| E (G) | + | E ('G -') | = | E (Kn) |, onde n = número de vértices no gráfico.
Exemplo
Seja 'G' um gráfico simples com nove vértices e doze arestas, encontre o número de arestas em 'G-'.
Você tem, | E (G) | + | E ('G -') | = | E (Kn) |
12 + | E ('G -') | =
9 (9-1) / 2 = 9 C 2
12 + | E ('G -') | = 36
| E ('G -') | = 24
'G' é um gráfico simples com 40 arestas e seu complemento 'G−' tem 38 arestas. Encontre o número de vértices no gráfico G ou 'G−'.
Seja o número de vértices no gráfico 'n'.
Temos, | E (G) | + | E ('G -') | = | E (Kn) |
40 + 38 = n (n-1) / 2
156 = n (n-1)
13 (12) = n (n-1)
n = 13