Teoria dos grafos - Guia rápido

No domínio da matemática e da ciência da computação, a teoria dos grafos é o estudo dos grafos que se preocupa com a relação entre arestas e vértices . É um assunto popular com suas aplicações em ciência da computação, tecnologia da informação, biociências, matemática e linguística, para citar alguns. Sem mais delongas, vamos começar definindo um gráfico.

O que é um gráfico?

Um gráfico é uma representação pictórica de um conjunto de objetos onde alguns pares de objetos são conectados por links. Os objetos interconectados são representados por pontos denominados comovertices, e os links que conectam os vértices são chamados edges.

Formalmente, um gráfico é um par de conjuntos (V, E), Onde Vé o conjunto de vértices e E é o conjunto de arestas, conectando os pares de vértices. Dê uma olhada no gráfico a seguir -

No gráfico acima,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Aplicações da Teoria dos Grafos

A teoria dos grafos tem suas aplicações em diversos campos da engenharia -

Electrical Engineering- Os conceitos da teoria dos grafos são amplamente usados ​​no projeto de conexões de circuitos. Os tipos ou organização de conexões são nomeados como topologias. Alguns exemplos de topologias são topologias em estrela, ponte, série e paralela.

Computer Science- A teoria dos grafos é usada para o estudo de algoritmos. Por exemplo,

• Algoritmo de Kruskal
• Algoritmo de Prim
• Algoritmo de Dijkstra

Computer Network - As relações entre computadores interligados na rede seguem os princípios da teoria dos grafos.

Science - A estrutura molecular e a estrutura química de uma substância, a estrutura do DNA de um organismo, etc., são representadas por gráficos.

Linguistics - A árvore de análise de um idioma e a gramática de um idioma usa gráficos.

General- As rotas entre as cidades podem ser representadas por meio de gráficos. A representação de informações ordenadas hierárquicas, como a árvore genealógica, pode ser usada como um tipo especial de gráfico chamado árvore.

Um gráfico é um diagrama de pontos e linhas conectadas aos pontos. Ele tem pelo menos uma linha unindo um conjunto de dois vértices sem nenhum vértice se conectando. O conceito de grafos na teoria dos grafos se sustenta em alguns termos básicos como ponto, linha, vértice, aresta, grau dos vértices, propriedades dos grafos, etc. Aqui, neste capítulo, cobriremos esses fundamentos da teoria dos grafos.

Ponto

A pointé uma posição particular em um espaço unidimensional, bidimensional ou tridimensional. Para melhor compreensão, um ponto pode ser denotado por um alfabeto. Ele pode ser representado com um ponto.

Exemplo

Aqui, o ponto é um ponto denominado 'a'.

Linha

UMA Lineé uma conexão entre dois pontos. Ele pode ser representado por uma linha sólida.

Example

Aqui, 'a' e 'b' são os pontos. A ligação entre esses dois pontos é chamada de linha.

Vértice

Um vértice é um ponto onde várias linhas se encontram. Também é chamado denode. Semelhante aos pontos, um vértice também é denotado por um alfabeto.

Example

Aqui, o vértice é nomeado com um alfabeto 'a'.

Beira

Uma aresta é o termo matemático para uma linha que conecta dois vértices. Muitas arestas podem ser formadas a partir de um único vértice. Sem um vértice, uma aresta não pode ser formada. Deve haver um vértice inicial e um vértice final para uma aresta.

Example

Aqui, 'a' e 'b' são os dois vértices e a ligação entre eles é chamada de aresta.

Gráfico

Um gráfico 'G' é definido como G = (V, E) Onde V é um conjunto de todos os vértices e E é um conjunto de todas as arestas do gráfico.

Example 1

No exemplo acima, ab, ac, cd e bd são as arestas do gráfico. Da mesma forma, a, b, c e d são os vértices do gráfico.

Example 2

Neste gráfico, existem quatro vértices a, b, c e d e quatro arestas ab, ac, ad e cd.

Ciclo

Em um gráfico, se uma aresta é desenhada do vértice até ela mesma, é chamada de loop.

Example 1

No gráfico acima, V é um vértice para o qual possui uma aresta (V, V) formando um loop.

Example 2

Neste gráfico, há dois loops que são formados no vértice a e no vértice b.

Grau de Vértice

É o número de vértices adjacentes a um vértice V.

Notation - deg (V).

Em um gráfico simples com n número de vértices, o grau de quaisquer vértices é -

deg (v) ≤ n - 1 ∀ v ∈ G

Um vértice pode formar uma aresta com todos os outros vértices, exceto por ele mesmo. Portanto, o grau de um vértice será até onumber of vertices in the graph minus 1. Este 1 é para o autovértex, pois ele não pode formar um loop por si mesmo. Se houver um loop em qualquer um dos vértices, então não é um gráfico simples.

O grau de vértice pode ser considerado em dois casos de gráficos -

• Gráfico não direcionado

• Gráfico Direcionado

Grau de vértice em um gráfico não direcionado

Um gráfico não direcionado não possui arestas direcionadas. Considere os seguintes exemplos.

Example 1

Dê uma olhada no gráfico a seguir -

No gráfico não direcionado acima,

• deg (a) = 2, pois há 2 arestas que se encontram no vértice 'a'.

• deg (b) = 3, pois há 3 arestas que se encontram no vértice 'b'.

• deg (c) = 1, pois há 1 aresta formada no vértice 'c'

• Então, 'c' é um pendent vertex.

• deg (d) = 2, pois há 2 arestas que se encontram no vértice 'd'.

• deg (e) = 0, pois existem 0 arestas formadas no vértice 'e'.

• Então, 'e' é um isolated vertex.

Example 2

Dê uma olhada no gráfico a seguir -

No gráfico acima,

deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 e deg (e) = 0.

O vértice 'e' é um vértice isolado. O gráfico não possui vértices pendentes.

Grau de vértice em um gráfico direcionado

Em um gráfico direcionado, cada vértice tem um indegree e um outdegree.

Indegree de um gráfico

• Indegree do vértice V é o número de arestas que entram no vértice V.

• Notation - deg− (V).

Outdegree of a Graph

• Outdegree do vértice V é o número de arestas que estão saindo do vértice V.

• Notation - deg + (V).

Considere os seguintes exemplos.

Example 1

Dê uma olhada no seguinte gráfico direcionado. O vértice 'a' tem duas arestas, 'ad' e 'ab', que vão para fora. Conseqüentemente, seu grau externo é 2. Similarmente, existe uma aresta 'ga', vindo em direção ao vértice 'a'. Portanto, o indegree de 'a' é 1.

O indegree e outdegree de outros vértices são mostrados na tabela a seguir -

Vértice	Indegree	Outdegree
uma	1	2
b	2	0
c	2	1
d	1	1
e	1	1
f	1	1
g	0	2

Example 2

Dê uma olhada no seguinte gráfico direcionado. O vértice 'a' tem uma aresta 'ae' saindo do vértice 'a'. Portanto, seu grau de diferença é 1. Similarmente, o gráfico tem uma aresta 'ba' vindo em direção ao vértice 'a'. Portanto, o indegree de 'a' é 1.

O indegree e outdegree de outros vértices são mostrados na tabela a seguir -

Vértice	Indegree	Outdegree
uma	1	1
b	0	2
c	2	0
d	1	1
e	1	1

Vértice Pendente

Ao usar o grau de um vértice, temos dois tipos especiais de vértices. Um vértice com grau um é chamado de vértice pendente.

Example

Aqui, neste exemplo, o vértice 'a' e o vértice 'b' têm uma aresta conectada 'ab'. Portanto, com relação ao vértice 'a', há apenas uma aresta em direção ao vértice 'b' e, da mesma forma, em relação ao vértice 'b', há apenas uma aresta em direção ao vértice 'a'. Finalmente, o vértice 'a' e o vértice 'b' têm grau como um, que também são chamados de vértices pendentes.

Vértice Isolado

Um vértice com grau zero é chamado de vértice isolado.

Example

Aqui, o vértice 'a' e o vértice 'b' não têm conectividade entre si e também com quaisquer outros vértices. Portanto, o grau de ambos os vértices 'a' e 'b' são zero. Eles também são chamados de vértices isolados.

Adjacência

Aqui estão as normas de adjacência -

• Em um gráfico, dois vértices são considerados adjacent, se houver uma aresta entre os dois vértices. Aqui, a adjacência dos vértices é mantida pela única aresta que está conectando esses dois vértices.

• Em um gráfico, duas arestas são ditas adjacentes, se houver um vértice comum entre as duas arestas. Aqui, a adjacência das arestas é mantida pelo único vértice que conecta duas arestas.

Example 1

No gráfico acima -

• 'a' e 'b' são os vértices adjacentes, pois existe uma aresta comum 'ab' entre eles.

• 'a' e 'd' são os vértices adjacentes, pois existe uma aresta comum 'ad' entre eles.

• ab 'e' be 'são as arestas adjacentes, pois existe um vértice comum' b 'entre elas.

• be 'e' de 'são as arestas adjacentes, pois existe um vértice comum' e 'entre elas.

Example 2

No gráfico acima -

• 'a' e 'd' são os vértices adjacentes, pois existe uma aresta comum 'ad' entre eles.

• 'c' e 'b' são os vértices adjacentes, pois existe uma aresta comum 'cb' entre eles.

• 'ad' e 'cd' são as arestas adjacentes, pois existe um vértice comum 'd' entre elas.

• 'ac' e 'cd' são as arestas adjacentes, pois existe um vértice 'c' comum entre elas.

Bordas Paralelas

Em um gráfico, se um par de vértices é conectado por mais de uma aresta, essas arestas são chamadas de arestas paralelas.

No gráfico acima, 'a' e 'b' são os dois vértices que são conectados por duas arestas 'ab' e 'ab' entre eles. Por isso é chamado de aresta paralela.

Multi Graph

Um gráfico com arestas paralelas é conhecido como Multigraph.

Example 1

No gráfico acima, existem cinco arestas 'ab', 'ac', 'cd', 'cd' e 'bd'. Uma vez que 'c' e 'd' têm duas arestas paralelas entre eles, é um multigrafo.

Example 2

No gráfico acima, os vértices 'b' e 'c' possuem duas arestas. Os vértices 'e' e 'd' também possuem duas arestas entre eles. Portanto, é um Multigraph.

Sequência de Graus de um Gráfico

Se os graus de todos os vértices de um gráfico forem organizados em ordem decrescente ou crescente, a seqüência obtida é conhecida como a seqüência de graus do gráfico.

Example 1

Vértice	UMA	b	c	d	e
Conectando à	b, c	de Anúncios	de Anúncios	c, b, e	d
Grau	2	2	2	3	1

No gráfico acima, para os vértices {d, a, b, c, e}, a sequência de graus é {3, 2, 2, 2, 1}.

Example 2

Vértice	UMA	b	c	d	e	f
Conectando à	estar	a, c	b, d	c, e	de Anúncios	-
Grau	2	2	2	2	2	0

No gráfico acima, para os vértices {a, b, c, d, e, f}, a sequência de graus é {2, 2, 2, 2, 2, 0}.

Os gráficos vêm com várias propriedades que são usadas para caracterização de gráficos dependendo de suas estruturas. Essas propriedades são definidas em termos específicos pertencentes ao domínio da teoria dos grafos. Neste capítulo, discutiremos algumas propriedades básicas que são comuns em todos os gráficos.

Distância entre Dois Vértices

É o número de arestas em um caminho mais curto entre o vértice U e o vértice V. Se houver vários caminhos conectando dois vértices, o caminho mais curto é considerado como a distância entre os dois vértices.

Notação - d (U, V)

Pode haver qualquer número de caminhos presentes de um vértice para outro. Entre eles, você precisa escolher apenas o mais curto.

Example

Dê uma olhada no gráfico a seguir -

Aqui, a distância do vértice 'd' ao vértice 'e' ou simplesmente 'de' é 1, pois há uma aresta entre eles. Existem muitos caminhos do vértice 'd' ao vértice 'e' -

• da, ab, ser
• df, fg, ge
• de (é considerado para distância entre os vértices)
• df, fc, ca, ab, be
• da, ac, cf, fg, ge

Excentricidade de um vértice

A distância máxima entre um vértice e todos os outros vértices é considerada como a excentricidade do vértice.

Notação - e (V)

A distância de um determinado vértice a todos os outros vértices do gráfico é tomada e, entre essas distâncias, a excentricidade é a maior das distâncias.

Example

No gráfico acima, a excentricidade de 'a' é 3.

A distância de 'a' a 'b' é 1 ('ab'),

de 'a' a 'c' é 1 ('ac'),

de 'a' a 'd' é 1 ('anúncio'),

de 'a' a 'e' é 2 ('ab' - 'ser') ou ('ad' - 'de'),

de 'a' a 'f' é 2 ('ac' - 'cf') ou ('ad' - 'df'),

de 'a' a 'g' é 3 ('ac' - 'cf' - 'fg') ou ('ad' - 'df' - 'fg').

Portanto, a excentricidade é 3, que é um máximo do vértice 'a' da distância entre 'ag', que é o máximo.

Em outras palavras,

e (b) = 3

e (c) = 3

e (d) = 2

e (e) = 3

e (f) = 3

e (g) = 3

Raio de um gráfico conectado

A excentricidade mínima de todos os vértices é considerada como o raio do Gráfico G. O mínimo entre todas as distâncias máximas entre um vértice e todos os outros vértices é considerado como o raio do Gráfico G.

Notação - r (G)

De todas as excentricidades dos vértices em um gráfico, o raio do gráfico conectado é o mínimo de todas essas excentricidades.

Example

No gráfico acima, r (G) = 2, que é a excentricidade mínima para 'd'.

Diâmetro de um gráfico

A excentricidade máxima de todos os vértices é considerada como o diâmetro do Gráfico G. O máximo entre todas as distâncias entre um vértice e todos os outros vértices é considerado como o diâmetro do Gráfico G.

Notation − d(G) - De todas as excentricidades dos vértices de um gráfico, o diâmetro do gráfico conectado é o máximo de todas essas excentricidades.

Example

No gráfico acima, d (G) = 3; que é a excentricidade máxima.

Ponto central

Se a excentricidade de um gráfico é igual ao seu raio, ela é conhecida como o ponto central do gráfico. E se

e (V) = r (V),

então 'V' é o ponto central do gráfico 'G'.

Example

No gráfico de exemplo, 'd' é o ponto central do gráfico.

e (d) = r (d) = 2

Centro

O conjunto de todos os pontos centrais de 'G' é denominado centro do gráfico.

Example

No gráfico de exemplo, {'d'} é o centro do gráfico.

Circunferência

o number of edges in the longest cycle of ‘G’ é chamada de circunferência de 'G'.

Example

No gráfico de exemplo, a circunferência é 6, que derivamos do acfgeba ou acfdeba de ciclo mais longo.

Cilha

O número de arestas no ciclo mais curto de 'G' é chamado de circunferência.

Notation: g (G).

Example - No gráfico de exemplo, a circunferência do gráfico é 4, que derivamos do ciclo mais curto acfda ou dfged ou abeda.

Teorema da Soma dos Graus de Vértices

Se G = (V, E) for um gráfico não direcionado com vértices V = {V ₁ , V ₂ , ... V _n } então

n Σ i = 1 grau (V _i ) = 2 | E |

Corollary 1

Se G = (V, E) for um gráfico direcionado com vértices V = {V ₁ , V ₂ , ... V _n }, então

n Σ i = 1 grau + (V _i ) = | E | = n Σ i = 1 deg− (V _i )

Corollary 2

Em qualquer gráfico não direcionado, o número de vértices com grau ímpar é par.

Corollary 3

Em um gráfico não direcionado, se o grau de cada vértice é k, então

k | V | = 2 | E |

Corollary 4

Em um gráfico não direcionado, se o grau de cada vértice for pelo menos k, então

k | V | ≤ 2 | E |

| Corollary 5

Em um gráfico não direcionado, se o grau de cada vértice for no máximo k, então

k | V | ≥ 2 | E |

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 são 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 se tratar de 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 é ⁿ C ₂ onde ⁿ C ₂ = n (n - 1) / 2.

• O número de gráficos simples possíveis com 'n' vértices = 2 _{ⁿ 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 -

ⁿ C ₂ = n (n – 1) / 2

= 3 (3–1) / 2

= 6/2

= 3 arestas

O número máximo de gráficos simples com n = 3 vértices -

2 _{ⁿ C 2} = 2 ^{n (n-1) / 2}

= 2 ^{3 (3-1) / 2}

= 2 ³

8

Esses 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 ele 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 é 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 for 'k', o gráfico é chamado de 'gráfico regular k'.

Exemplo

Nos gráficos a seguir, todos os vértices têm 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 ‘K_n’. 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 seguintes gráficos -

• 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 a partir 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º 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 ₃ adicionando um vértice no meio denominado 'd'. É denotado como W ₄ .

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 ₅ .

Número de arestas em W5 = 2 (n-1) = 2 (4) = 8

No gráfico III, ele é obtido de C ₆ adicionando um vértice no meio denominado 'o'. É denotado como W ₇ .

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 ₁ , V ₂ } é chamado de grafo bipartidoif every edge of E joins a vertex in V1 to a vertex in V₂.

Em geral, um grafo bipertita 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 ₁ a qualquer vértice do conjunto V ₂ .

Exemplo

Neste gráfico, você pode observar dois conjuntos de vértices - V ₁ e V ₂ . Aqui, duas arestas chamadas 'ae' e 'bd' estão conectando os vértices de dois conjuntos V ₁ e V ₂ .

Gráfico Bipartido Completo

Um grafo bipartido 'G', G = (V, E) com partição V = {V ₁ , V ₂ } é considerado um grafo bipartido completo se cada vértice em V ₁ estiver conectado a todos os vértices de V ₂ .

Em geral, um grafo bipartido completo conecta cada vértice do conjunto V ₁ a cada vértice do conjunto V ₂ .

Exemplo

O gráfico a seguir é um grafo bipartido completo porque tem arestas conectando cada vértice do conjunto V ₁ a cada vértice do conjunto V ₂ .

Se | V ₁ | = me | V ₂ | = 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 ² /4]

Se n = 10, k5, 5 = [n2 / 4] = [10 ² /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 ¹ , ^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 = ⁹ C ₂

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

Árvores são gráficos que não contêm nem mesmo um único ciclo. Eles representam a estrutura hierárquica de forma gráfica. As árvores pertencem à classe mais simples de gráficos. Apesar de sua simplicidade, eles possuem uma estrutura rica.

As árvores fornecem uma gama de aplicações úteis, tão simples como uma árvore genealógica a tão complexas quanto árvores em estruturas de dados de ciência da computação.

Árvore

UMA connected acyclic graphé chamado de árvore. Em outras palavras, um gráfico conectado sem ciclos é chamado de árvore.

As bordas de uma árvore são conhecidas como branches. Os elementos das árvores são chamados de nós. Os nós sem nós filhos são chamadosleaf nodes.

Uma árvore com 'n' vértices possui 'n-1' arestas. Se ele tiver mais uma aresta extra do que 'n-1', então a aresta extra deve obviamente emparelhar com dois vértices que levam a formar um ciclo. Então, ele se torna um gráfico cíclico, o que é uma violação do gráfico da árvore.

Example 1

O gráfico mostrado aqui é uma árvore porque não tem ciclos e está conectado. Possui quatro vértices e três arestas, ou seja, para 'n' vértices 'n-1' arestas conforme mencionado na definição.

Note - Cada árvore possui pelo menos dois vértices de grau um.

Example 2

No exemplo acima, os vértices 'a' e 'd' possuem grau um. E os outros dois vértices 'b' e 'c' têm grau dois. Isso é possível porque, para não formar um ciclo, deve haver pelo menos duas arestas únicas em qualquer lugar do gráfico. Não são nada além de duas arestas com grau de um.

Floresta

UMA disconnected acyclic graphé chamado de floresta. Em outras palavras, uma coleção desconexa de árvores é chamada de floresta.

Example

O gráfico a seguir se parece com dois subgráficos; mas é um único gráfico desconectado. Não há ciclos neste gráfico. Portanto, claramente é uma floresta.

Árvores Medidas

Seja G um grafo conectado, então o subgráfico H de G é chamado de árvore geradora de G se -

• H é uma árvore
• H contém todos os vértices de G.

Uma árvore geradora T de um grafo não direcionado G é um subgrafo que inclui todos os vértices de G.

Example

No exemplo acima, G é um gráfico conectado e H é um subgráfico de G.

É claro que o grafo H não tem ciclos, é uma árvore com seis arestas que é um a menos que o número total de vértices. Portanto, H é a árvore de abrangência de G.

Classificação do circuito

Seja 'G' um gráfico conectado com 'n' vértices e 'm' arestas. Uma árvore geradora 'T' de G contém (n-1) arestas.

Portanto, o número de arestas que você precisa excluir de 'G' para obter uma árvore geradora = m- (n-1), que é chamada de classificação de circuito de G.

Esta fórmula é verdadeira, porque em uma árvore abrangente você precisa ter 'n-1' arestas. Fora das 'm' arestas, você precisa manter 'n – 1' arestas no gráfico.

Portanto, deletar 'n – 1' arestas de 'm' fornece as arestas a serem removidas do gráfico para obter uma árvore geradora, que não deve formar um ciclo.

Example

Dê uma olhada no gráfico a seguir -

Para o gráfico dado no exemplo acima, você tem m = 7 arestas en = 5 vértices.

Então, a classificação do circuito é -

G = m - (n - 1)

= 7 - (5 - 1)

= 3

Example

Seja 'G' um grafo conectado com seis vértices e o grau de cada vértice é três. Encontre a classificação do circuito de 'G'.

Pela soma do teorema do grau dos vértices,

n Σ i=1grau (V _i ) = 2 | E |

6 × 3 = 2 | E |

| E | = 9

Classificação do circuito = | E | - (| V | - 1)

= 9 - (6 - 1) = 4

Teorema de Kirchoff

O teorema de Kirchoff é útil para encontrar o número de árvores geradoras que podem ser formadas a partir de um grafo conectado.

Example

A matriz 'A' deve ser preenchida como, se houver uma aresta entre dois vértices, ela deve ser fornecida como '1', caso contrário, '0'.

$$A=\begin{vmatrix}0 & a & b & c & d\\a & 0 & 1 & 1 & 1 \\b & 1 & 0 & 0 & 1\\c & 1 & 0 & 0 & 1\\d & 1 & 1 & 1 & 0 \end{vmatrix} = \begin{vmatrix} 0 & 1 & 1 & 1\\1 & 0 & 0 & 1\\1 & 0 & 0 & 1\\1 & 1 & 1 & 0\end{vmatrix}$$

Usando o teorema de Kirchoff, ele deve ser alterado substituindo os valores principais da diagonal pelo grau dos vértices e todos os outros elementos por -1.A

$$=\begin{vmatrix} 3 & -1 & -1 & -1\\-1 & 2 & 0 & -1\\-1 & 0 & 2 & -1\\-1 & -1 & -1 & 3 \end{vmatrix}=M$$ $$M=\begin{vmatrix}3 & -1 & -1 & -1\\-1 & 2 & 0 & -1\\-1 & 0 & 2 & -1\\-1 & -1 & -1 & 3 \end{vmatrix} =8$$ $$Co\:\:factor\:\:of\:\:m1\:\:= \begin{vmatrix} 2 & 0 & -1\\0 & 2 & -1\\-1 & -1 & 3\end{vmatrix}$$

Portanto, o número de árvores abrangentes = 8.

Se é possível atravessar um gráfico de um vértice para outro, é determinado pela forma como o gráfico é conectado. Conectividade é um conceito básico da Teoria dos Grafos. Conectividade define se um gráfico está conectado ou desconectado. Possui subtópicos baseados em aresta e vértice, conhecidos como conectividade de aresta e conectividade de vértice. Vamos discuti-los em detalhes.

Conectividade

Um gráfico é dito ser connected if there is a path between every pair of vertex. De cada vértice para qualquer outro vértice, deve haver algum caminho a ser percorrido. Isso é chamado de conectividade de um gráfico. Um gráfico com vários vértices e arestas desconectados é considerado desconectado.

Example 1

No gráfico a seguir, é possível viajar de um vértice para qualquer outro vértice. Por exemplo, pode-se atravessar do vértice 'a' ao vértice 'e' usando o caminho 'ab-e'.

Example 2

No exemplo a seguir, atravessar do vértice 'a' para o vértice 'f' não é possível porque não há um caminho entre eles direta ou indiretamente. Portanto, é um gráfico desconectado.

Cut Vertex

Seja 'G' um gráfico conectado. Um vértice V ∈ G é chamado de vértice de corte de 'G', se 'G-V' (Excluir 'V' de 'G') resulta em um gráfico desconectado. Remover um vértice de corte de um gráfico divide-o em dois ou mais gráficos.

Note - Remover um vértice cortado pode tornar um gráfico desconectado.

Um grafo conectado 'G' pode ter no máximo (n – 2) vértices de corte.

Example

No gráfico a seguir, os vértices 'e' e 'c' são os vértices cortados.

Ao remover 'e' ou 'c', o gráfico se tornará um gráfico desconectado.

Sem 'g', não há caminho entre o vértice 'c' e o vértice 'h' e muitos outros. Portanto, é um gráfico desconectado com vértice de corte como 'e'. Da mesma forma, 'c' também é um vértice de corte para o gráfico acima.

Borda cortada (ponte)

Seja 'G' um gráfico conectado. Uma aresta 'e' ∈ G é chamada de aresta de corte se 'G-e' resulta em um gráfico desconectado.

Se a remoção de uma borda em um gráfico resultar em dois ou mais gráficos, essa borda é chamada de Corte de Borda.

Example

No gráfico a seguir, a borda de corte é [(c, e)].

Ao remover a aresta (c, e) do gráfico, ele se torna um gráfico desconectado.

No gráfico acima, remover a aresta (c, e) divide o gráfico em dois, que nada mais é do que um gráfico desconectado. Portanto, a aresta (c, e) é uma aresta de corte do gráfico.

Note - Seja 'G' um gráfico conectado com 'n' vértices, então

• uma aresta de corte e ∈ G se e somente se a aresta 'e' não fizer parte de qualquer ciclo em G.

• o número máximo de arestas de corte possível é 'n-1'.

• sempre que houver arestas de corte, vértices de corte também existem porque pelo menos um vértice de uma aresta de corte é um vértice de corte.

• se um vértice de corte existe, então uma aresta de corte pode ou não existir.

Corte o conjunto de um gráfico

Seja 'G' = (V, E) um gráfico conectado. Um subconjunto E 'de E é chamado de conjunto de corte de G se a exclusão de todas as arestas de E' de G faz G desconectar.

Se a exclusão de um determinado número de arestas de um gráfico o desconecta, então essas arestas excluídas são chamadas de conjunto de corte do gráfico.

Example

Dê uma olhada no gráfico a seguir. Seu conjunto de corte é E1 = {e1, e3, e5, e8}.

Depois de remover o conjunto de corte E1 do gráfico, ele aparecerá da seguinte forma -

Da mesma forma, existem outros conjuntos de corte que podem desconectar o gráfico -

• E3 = {e9} - Menor conjunto de corte do gráfico.

• E4 = {e3, e4, e5}

Edge Connectivity

Seja 'G' um gráfico conectado. O número mínimo de arestas cuja remoção faz 'G' desconectado é chamado de conectividade de aresta de G.

Notation - λ (G)

Em outras palavras, o number of edges in a smallest cut set of G é chamada de conectividade de borda de G.

Se 'G' tem uma borda de corte, então λ (G) é 1. (conectividade de borda de G.)

Example

Dê uma olhada no gráfico a seguir. Ao remover duas arestas mínimas, o gráfico conectado se desconecta. Portanto, sua conectividade de borda (λ (G)) é 2.

Aqui estão as quatro maneiras de desconectar o gráfico removendo duas arestas -

Vertex Connectivity

Seja 'G' um gráfico conectado. O número mínimo de vértices cuja remoção torna 'G' desconectado ou reduz 'G' a um grafo trivial é chamado de conectividade de vértice.

Notation - K (G)

Example

No gráfico acima, remover os vértices 'e' e 'i' faz com que o gráfico se desconecte.

Se G tem um vértice de corte, então K (G) = 1.

Notation - Para qualquer gráfico conectado G,

K (G) ≤ λ (G) ≤ δ (G)

Conectividade de vértices (K (G)), conectividade de borda (λ (G)), número mínimo de graus de G (δ (G)).

Example

Calcule λ (G) e K (G) para o gráfico a seguir -

Solution

No gráfico,

δ (G) = 3

K (G) ≤ λ (G) ≤ δ (G) = 3 (1)

K (G) ≥ 2 (2)

Excluindo as arestas {d, e} e {b, h}, podemos desconectar G.

Portanto,

λ (G) = 2

2 ≤ λ (G) ≤ δ (G) = 2 (3)

De (2) e (3), conectividade de vértice K (G) = 2

Um gráfico de cobertura é um subgrafo que contém todos os vértices ou todas as arestas correspondentes a algum outro gráfico. Um subgrafo que contém todos os vértices é chamado deline/edge covering. Um subgrafo que contém todas as arestas é chamado devertex covering.

Cobertura de Linha

Seja G = (V, E) um gráfico. Um subconjunto C (E) é chamado de cobertura de linha de G se cada vértice de G incidente com pelo menos uma aresta em C, ou seja,

deg (V) ≥ 1 ∀ V ∈ G

porque cada vértice está conectado a outro vértice por uma aresta. Portanto, tem um grau mínimo de 1.

Example

Dê uma olhada no gráfico a seguir -

Seus subgráficos com cobertura de linha são os seguintes -

C ₁ = {{a, b}, {c, d}}

C ₂ = {{a, d}, {b, c}}

C ₃ = {{a, b}, {b, c}, {b, d}}

C ₄ = {{a, b}, {b, c}, {c, d}}

A linha de cobertura de 'G' não existe se e somente se 'G' tem um vértice isolado. A cobertura da linha de um gráfico com 'n' vértices tem pelo menos [n / 2] arestas.

Cobertura mínima de linha

Uma linha cobrindo C de um gráfico G é considerada mínima if no edge can be deleted from C.

Example

No gráfico acima, os subgráficos com cobertura de linha são os seguintes -

C ₁ = {{a, b}, {c, d}}

C ₂ = {{a, d}, {b, c}}

C ₃ = {{a, b}, {b, c}, {b, d}}

C ₄ = {{a, b}, {b, c}, {c, d}}

Aqui, C ₁ , C ₂ , C ₃ são coberturas de linha mínimas, enquanto C ₄ não é, porque podemos excluir {b, c}.

Cobertura mínima de linha

Também é conhecido como Smallest Minimal Line Covering. Uma cobertura de linha mínima com número mínimo de arestas é chamada de cobertura de linha mínima de 'G'. O número de arestas em uma linha mínima cobrindo em 'G' é chamado deline covering numberde 'G' (α ₁ ).

Example

No exemplo acima, C ₁ e C ₂ são a linha de cobertura mínima de G e α ₁ = 2.

• Cada cobertura de linha contém uma cobertura de linha mínima.

• Cada cobertura de linha não contém uma cobertura de linha mínima (C ₃ não contém nenhuma cobertura de linha mínima.

• Nenhuma cobertura de linha mínima contém um ciclo.

• Se uma linha cobrindo 'C' não contém caminhos de comprimento 3 ou mais, então 'C' é uma linha mínima cobrindo porque todos os componentes de 'C' são gráfico de estrela e de um gráfico de estrela, nenhuma aresta pode ser excluída.

Cobertura de vértices

Seja 'G' = (V, E) um gráfico. Um subconjunto K de V é chamado de cobertura de vértice de 'G', se cada aresta de 'G' incide ou é coberta por um vértice em 'K'.

Example

Dê uma olhada no gráfico a seguir -

Os subgráficos que podem ser derivados do gráfico acima são os seguintes -

K ₁ = {b, c}

K ₂ = {a, b, c}

K ₃ = {b, c, d}

K ₄ = {a, d}

Aqui, K ₁ , K ₂ e K ₃ têm cobertura de vértices, enquanto K ₄ não tem cobertura de vértices, pois não cobre a aresta {bc}.

Cobertura mínima de vértices

Um vértice 'K' do gráfico 'G' é considerado um vértice mínimo cobrindo se nenhum vértice puder ser excluído de 'K'.

Example

No gráfico acima, os subgráficos com cobertura de vértices são os seguintes -

K ₁ = {b, c}

K ₂ = {a, b, c}

K ₃ = {b, c, d}

Aqui, K ₁ e K ₂ são coberturas de vértices mínimas, enquanto em K ₃ , o vértice 'd' pode ser deletado.

Cobertura mínima do vértice

É também conhecido como a menor cobertura mínima do vértice. Uma cobertura mínima de vértices do gráfico 'G' com um número mínimo de vértices é chamada de cobertura mínima de vértices.

O número de vértices em um vértice mínimo cobrindo 'G' é chamado de vértice cobrindo o número de G (α ₂ ).

Example

No gráfico a seguir, os subgráficos com cobertura de vértices são os seguintes -

K ₁ = {b, c}

K ₂ = {a, b, c}

K ₃ = {b, c, d}

Aqui, K ₁ é uma cobertura mínima de vértices de G, pois tem apenas dois vértices. α ₂ = 2.

A matching graph is a subgraph of a graph where there are no edges adjacent to each other. Simply, there should not be any common vertex between any two edges.

Matching

Let ‘G’ = (V, E) be a graph. A subgraph is called a matching M(G), if each vertex of G is incident with at most one edge in M, i.e.,

deg(V) ≤ 1 ∀ V ∈ G

which means in the matching graph M(G), the vertices should have a degree of 1 or 0, where the edges should be incident from the graph G.

Notation − M(G)

Example

In a matching,

if deg(V) = 1, then (V) is said to be matched

if deg(V) = 0, then (V) is not matched.

In a matching, no two edges are adjacent. It is because if any two edges are adjacent, then the degree of the vertex which is joining those two edges will have a degree of 2 which violates the matching rule.

Maximal Matching

A matching M of graph ‘G’ is said to maximal if no other edges of ‘G’ can be added to M.

Example

M1, M2, M3 from the above graph are the maximal matching of G.

Maximum Matching

It is also known as largest maximal matching. Maximum matching is defined as the maximal matching with maximum number of edges.

The number of edges in the maximum matching of ‘G’ is called its matching number.

Example

For a graph given in the above example, M1 and M2 are the maximum matching of ‘G’ and its matching number is 2. Hence by using the graph G, we can form only the subgraphs with only 2 edges maximum. Hence we have the matching number as two.

Perfect Matching

A matching (M) of graph (G) is said to be a perfect match, if every vertex of graph g (G) is incident to exactly one edge of the matching (M), i.e.,

deg(V) = 1 ∀ V

The degree of each and every vertex in the subgraph should have a degree of 1.

Example

In the following graphs, M1 and M2 are examples of perfect matching of G.

Note − Every perfect matching of graph is also a maximum matching of graph, because there is no chance of adding one more edge in a perfect matching graph.

A maximum matching of graph need not be perfect. If a graph ‘G’ has a perfect match, then the number of vertices |V(G)| is even. If it is odd, then the last vertex pairs with the other vertex, and finally there remains a single vertex which cannot be paired with any other vertex for which the degree is zero. It clearly violates the perfect matching principle.

Example

Note − The converse of the above statement need not be true. If G has even number of vertices, then M1 need not be perfect.

Example

It is matching, but it is not a perfect match, even though it has even number of vertices.

Independent sets are represented in sets, in which

• there should not be any edges adjacent to each other. There should not be any common vertex between any two edges.

• there should not be any vertices adjacent to each other. There should not be any common edge between any two vertices.

Independent Line Set

Let ‘G’ = (V, E) be a graph. A subset L of E is called an independent line set of ‘G’ if no two edges in L are adjacent. Such a set is called an independent line set.

Example

Let us consider the following subsets −

L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}

In this example, the subsets L2 and L3 are clearly not the adjacent edges in the given graph. They are independent line sets. However L1 is not an independent line set, as for making an independent line set, there should be at least two edges.

Maximal Independent Line Set

An independent line set is said to be the maximal independent line set of a graph ‘G’ if no other edge of ‘G’ can be added to ‘L’.

Example

Let us consider the following subsets −

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L₂ and L₃ are maximal independent line sets/maximal matching. As for only these two subsets, there is no chance of adding any other edge which is not an adjacent. Hence these two subsets are considered as the maximal independent line sets.

Maximum Independent Line Set

A maximum independent line set of ‘G’ with maximum number of edges is called a maximum independent line set of ‘G’.

Number of edges in a maximum independent line set of G (β1)
   = Line independent number of G
   = Matching number of G

Example

Let us consider the following subsets −

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L₃ is the maximum independent line set of G with maximum edges which are not the adjacent edges in graph and is denoted by β1 = 3.

Note − For any graph G with no isolated vertex,

α1 + β1 = number of vertices in a graph = |V|

Example

Line covering number of K_n/C_n/w_n,

$$\alpha 1 = \lceil\frac{n}{2}\rceil\begin{cases}\frac{n}{2}\:if\:n\:is\:even \\\frac{n+1}{2}\:if\:n\:is\:odd\end{cases}$$

Line independent number (Matching number) = β₁ = [n/2] α₁ + β₁ = n.

Independent Vertex Set

Let ‘G’ = (V, E) be a graph. A subset of ‘V’ is called an independent set of ‘G’ if no two vertices in ‘S’ are adjacent.

Example

Consider the following subsets from the above graphs −

S1 = {e}

S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

Clearly S₁ is not an independent vertex set, because for getting an independent vertex set, there should be at least two vertices in the from a graph. But here it is not that case. The subsets S₂, S₃, and S₄ are the independent vertex sets because there is no vertex that is adjacent to any one vertex from the subsets.

Conjunto de vértices independentes máximos

Seja 'G' um gráfico, então um conjunto independente de vértices de 'G' é considerado máximo se nenhum outro vértice de 'G' puder ser adicionado a 'S'.

Example

Considere os seguintes subconjuntos dos gráficos acima.

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

S ₂ e S ₃ são conjuntos de vértices independentes máximos de 'G'. Em S ₁ e S ₄ , podemos adicionar outros vértices; mas em S ₂ e S ₃ , não podemos adicionar nenhum outro vértice.

Conjunto de vértices independentes máximo

Um conjunto máximo de vértices independente de 'G' com o número máximo de vértices é chamado de conjunto máximo de vértices independentes.

Example

Considere os seguintes subconjuntos do gráfico acima -

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

Apenas S ₃ é o conjunto máximo de vértices independentes, pois cobre o maior número de vértices. O número de vértices em um conjunto máximo de vértices independentes de 'G' é chamado de número de vértices independentes de G (β ₂ ).

Example

Para o gráfico completo K _n ,

Número de cobertura do vértice = α ₂ = n − 1

Número independente do vértice = β ₂ = 1

Você tem α ₂ + β ₂ = n

Em um gráfico completo, cada vértice é adjacente a seus (n - 1) vértices restantes. Portanto, um conjunto máximo independente de K _n contém apenas um vértice.

Portanto, β ₂ = 1

e α ₂ = | v | - β ₂ = n-1

Note - Para qualquer gráfico 'G' = (V, E)

• α ₂ + β ₂ = | v |
• Se 'S' é um conjunto de vértices independente de 'G', então (V - S) é uma cobertura de vértices de G.

A coloração do gráfico nada mais é do que uma maneira simples de rotular os componentes do gráfico, como vértices, arestas e regiões, sob algumas restrições. Em um gráfico, dois vértices adjacentes, arestas adjacentes ou regiões adjacentes não são coloridas com um número mínimo de cores. Este número é chamado dechromatic number e o gráfico é chamado de properly colored graph.

Durante a coloração do gráfico, as restrições que são definidas no gráfico são as cores, a ordem de coloração, a forma de atribuir cor, etc. Uma coloração é dada a um vértice ou uma região particular. Assim, os vértices ou regiões com as mesmas cores formam conjuntos independentes.

Coloração de vértices

A coloração de vértices é uma atribuição de cores aos vértices de um gráfico 'G' de forma que dois vértices adjacentes não tenham a mesma cor. Simplificando, dois vértices de uma aresta não devem ser da mesma cor.

Número Cromático

O número mínimo de cores necessárias para a coloração do vértice do gráfico 'G' é chamado de número cromático de G, denotado por X (G).

χ (G) = 1 se e somente se 'G' for um gráfico nulo. Se 'G' não for um gráfico nulo, então χ (G) ≥ 2.

Example

Note - Diz-se que um gráfico 'G' é n-cobrível se houver uma coloração de vértices que usa no máximo n cores, ou seja, X (G) ≤ n.

Coloração da região

A coloração da região é uma atribuição de cores às regiões de um gráfico planar, de modo que duas regiões adjacentes não tenham a mesma cor. Diz-se que duas regiões são adjacentes se tiverem uma aresta comum.

Example

Dê uma olhada no gráfico a seguir. As regiões 'aeb' e 'befc' são adjacentes, pois há uma borda comum 'be' entre essas duas regiões.

Da mesma forma, as outras regiões também são coloridas com base na adjacência. Este gráfico é colorido da seguinte forma -

Example

O número cromático de Kn é

• n
• n–1
• [n/2]
• [n/2]

Considere este exemplo com K ₄ .

No gráfico completo, cada vértice é adjacente aos vértices restantes (n - 1). Portanto, cada vértice requer uma nova cor. Daí o número cromático de K _n = n.

Aplicações da coloração de grafos

A coloração de grafos é um dos conceitos mais importantes na teoria dos grafos. É usado em muitas aplicações em tempo real da ciência da computação, como -

• Clustering
• Mineração de dados
• Captura de imagem
• Segmentação de imagem
• Networking
• Alocação de recursos
• Agendamento de processos

Um gráfico pode existir em diferentes formas com o mesmo número de vértices, arestas e também a mesma conectividade de arestas. Esses gráficos são chamados de gráficos isomórficos. Observe que rotulamos os gráficos neste capítulo principalmente com o propósito de fazer referência a eles e reconhecê-los uns dos outros.

Gráficos Isomórficos

Dois gráficos G ₁ e G ₂ são considerados isomórficos se -

• Seu número de componentes (vértices e arestas) é o mesmo.

• Sua conectividade de ponta é mantida.

Note- Resumindo, dos dois gráficos isomórficos, um é uma versão ajustada do outro. Um gráfico sem etiqueta também pode ser considerado um gráfico isomórfico.

There exists a function ‘f’ from vertices of G1 to vertices of G2
   [f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.

Note

Se G ₁ ≡ G ₂ então -

| V (G ₁ ) | = | V (G ₂ ) |

| E (G ₁ ) | = | E (G ₂ ) |

As sequências de graus de G ₁ e G ₂ são iguais.

Se os vértices {V ₁ , V ₂ , .. Vk} formam um ciclo de comprimento K em G ₁ , então os vértices {f (V ₁ ), f (V ₂ ),… f (Vk)} devem formar um ciclo de comprimento K em G ₂ .

Todas as condições acima são necessárias para que os gráficos G ₁ e G ₂ sejam isomórficos, mas não o suficiente para provar que os gráficos são isomórficos.

• (G ₁ ≡ G ₂ ) se e somente se (G ₁ - ≡ G ₂ -) onde G ₁ e G ₂ são gráficos simples.

• (G ₁ ≡ G ₂ ) se as matrizes de adjacência de G ₁ e G ₂ forem iguais.

• (G ₁ ≡ G ₂ ) se e somente se os subgráficos correspondentes de G ₁ e G ₂ (obtidos pela exclusão de alguns vértices em G1 e suas imagens no gráfico G ₂ ) são isomórficos.

Example

Quais dos seguintes gráficos são isomórficos?

No gráfico G ₃ , o vértice 'w' tem apenas grau 3, enquanto todos os outros vértices do gráfico têm grau 2. Logo, G3 não é isomórfico a G ₁ ou G ₂ .

Tomando complementos de G ₁ e G ₂ , você tem -

Aqui, (G ₁ - ≡ G ₂ -), portanto (G ₁ ≡ G ₂ ).

Gráficos Planares

Um gráfico 'G' é considerado plano se puder ser desenhado em um plano ou esfera de modo que nenhuma aresta se cruze em um ponto não vértice.

Example

Regiões

Cada gráfico plano divide o plano em áreas conectadas chamadas regiões.

Example

Grau de uma região limitada r = deg(r) = Número de arestas envolvendo as regiões r.

deg(1) = 3
deg(2) = 4
deg(3) = 4

deg(4) = 3
deg(5) = 8

Grau de uma região ilimitada r = deg(r) = Número de arestas envolvendo as regiões r.

deg(R1) = 4
deg(R2) = 6

Em gráficos planos, as seguintes propriedades são válidas -

Em um gráfico planar com 'n' vértices, a soma dos graus de todos os vértices é -

n Σ i = 1 grau (V _i ) = 2 | E |

De acordo com Sum of Degrees of Regions/ Teorema, em um gráfico planar com 'n' regiões, a soma dos graus das regiões é -

n Σ i = 1 grau (ri) = 2 | E |

Com base no teorema acima, você pode tirar as seguintes conclusões -

Em um gráfico planar,

Se o grau de cada região for K, então a soma dos graus das regiões é -

K | R | = 2 | E |

Se o grau de cada região for pelo menos K (≥ K), então

K | R | ≤ 2 | E |

Se o grau de cada região for no máximo K (≤ K), então

K | R | ≥ 2 | E |

Note - Suponha que todas as regiões tenham o mesmo grau.

De acordo com Euler’s Formulae em gráficos planares,

Se um gráfico 'G' é um plano conectado, então

| V | + | R | = | E | + 2

Se for um gráfico planar com componentes 'K', então

| V | + | R | = | E | + (K + 1)

Onde, | V | é o número de vértices, | E | é o número de arestas e | R | é o número de regiões.

Edge Vertex Inequality

Se 'G' é um gráfico planar conectado com o grau de cada região pelo menos 'K', então,

| E | ≤ k / (k-2) {| v | - 2}

Você sabe, | V | + | R | = | E | + 2

K. | R | ≤ 2 | E |

K (| E | - | V | + 2) ≤ 2 | E |

(K - 2) | E | ≤ K (| V | - 2)

| E | ≤ k / (k-2) {| v | - 2}

Se 'G' é um gráfico plano simples conectado, então

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

Existe pelo menos um vértice V • ∈ G, tal que deg (V) ≤ 5.

Se 'G' é um gráfico plano simples conectado (com pelo menos 2 arestas) e sem triângulos, então

|E| ≤ {2|V| – 4}

Teorema de Kuratowski

Um grafo 'G' é não planar se e somente se 'G' tem um subgrafo que é homeomorfo a K ₅ ou K _3,3 .

Homomorfismo

Dois gráficos G ₁ e G ₂ são ditos homomórficos, se cada um desses gráficos puder ser obtido a partir do mesmo gráfico 'G' dividindo algumas arestas de G com mais vértices. Dê uma olhada no seguinte exemplo -

Divida a aresta 'rs' em duas arestas adicionando um vértice.

Os gráficos mostrados abaixo são homomórficos ao primeiro gráfico.

Se G ₁ é isomórfico a G ₂ , então G é homeomorfo a G2, mas o inverso não precisa ser verdadeiro.

• Qualquer gráfico com 4 ou menos vértices é plano.

• Qualquer gráfico com 8 ou menos arestas é plano.

• Um gráfico completo K _n é plano se e somente se n ≤ 4.

• O grafo bipartido completo K _{m, n} é planar se e somente se m ≤ 2 ou n ≤ 2.

• Um grafo simples não plano com número mínimo de vértices é o grafo completo K ₅ .

• O grafo não plano simples com número mínimo de arestas é K _{3, 3} .

Gráfico poliédrico

Um gráfico plano conectado simples é chamado de gráfico poliédrico se o grau de cada vértice for ≥ 3, ou seja, grau (V) ≥ 3 ∀ V ∈ G.

• 3 | V | ≤ 2 | E |

• 3 | R | ≤ 2 | E |

Um gráfico é percorrível se você pode desenhar um caminho entre todos os vértices sem refazer o mesmo caminho. Com base nesse caminho, existem algumas categorias, como o caminho de Euler e o circuito de Euler, que são descritas neste capítulo.

Caminho de Euler

O caminho de Euler contém cada aresta de 'G' exatamente uma vez e cada vértice de 'G' pelo menos uma vez. Um grafo conectado G é considerado percorrível se contiver o caminho de Euler.

Example

Caminho de Euler = dcabde.

Circuito de Euler

No caminho de Euler, se o vértice inicial é igual ao vértice final, ele é chamado de circuito de Euler.

Example

Euler’s Path = abcdagfeca.

Teorema do Circuito de Euler

Um grafo conectado 'G' é percorrível se e somente se o número de vértices com grau ímpar em G for exatamente 2 ou 0. Um grafo conectado G pode conter um caminho de Euler, mas não um circuito de Euler, se tiver exatamente dois vértices com um grau estranho.

Note - Este caminho de Euler começa com um vértice de grau ímpar e termina com o outro vértice de grau ímpar.

Example

Euler’s Path- beabdca não é um circuito de Euler, mas é um caminho de Euler. Claramente, ele tem exatamente 2 vértices de grau ímpar.

Note - Em um grafo conectado G, se o número de vértices com grau ímpar = 0, então o circuito de Euler existe.

Gráfico Hamiltoniano

Um grafo conectado G é considerado um grafo hamiltoniano, se existir um ciclo que contenha todos os vértices de G.

Cada ciclo é um circuito, mas um circuito pode conter vários ciclos. Esse ciclo é chamado deHamiltonian cycle de G.

Caminho Hamiltoniano

Um grafo conectado é considerado hamiltoniano se ele contém cada vértice de G exatamente uma vez. Esse caminho é chamado deHamiltonian path.

Example

Hamiltonian Path- edbac.

Note

• O circuito de Euler contém cada aresta do gráfico exatamente uma vez.

• Em um ciclo hamiltoniano, algumas arestas do gráfico podem ser ignoradas.

Example

Dê uma olhada no gráfico a seguir -

Para o gráfico mostrado acima -

• Existe um caminho de Euler - falso

• Existe circuito de Euler - falso

• Existe ciclo hamiltoniano - verdadeiro

• Existe caminho hamiltoniano - verdadeiro

G possui quatro vértices com grau ímpar, portanto, não é percorrível. Ao pular as arestas internas, o gráfico tem um ciclo hamiltoniano passando por todos os vértices.

Neste capítulo, cobriremos alguns exemplos padrão para demonstrar os conceitos que já discutimos nos capítulos anteriores.

Exemplo 1

Find the number of spanning trees in the following graph.

Solução

O número de árvores abrangentes obtido a partir do gráfico acima é 3. Eles são os seguintes -

Essas três são as árvores geradoras dos gráficos fornecidos. Aqui, os gráficos I e II são isomórficos entre si. Claramente, o número de árvores geradoras não isomórficas é dois.

Exemplo 2

How many simple non-isomorphic graphs are possible with 3 vertices?

Solução

Existem 4 gráficos não isomórficos possíveis com 3 vértices. Eles são mostrados abaixo.

Exemplo 3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

Solução

Pela soma do teorema dos graus,

20 Σ i = 1 grau (Vi) = 2 | E |

20 (3) = 2 | E |

| E | = 30

Pela fórmula de Euler,

| V | + | R | = | E | + 2

20+ | R | = 30 + 2

| R | = 12

Portanto, o número de regiões é 12.

Exemplo 4

What is the chromatic number of complete graph K_n?

Solução

Em um gráfico completo, cada vértice adjacente aos vértices restantes (n – 1). Portanto, cada vértice requer uma nova cor. Daí o número cromático K _n = n.

Exemplo 5

What is the matching number for the following graph?

Solução

Número de vértices = 9

Podemos combinar apenas 8 vértices.

O número correspondente é 4.

Exemplo 6

What is the line covering number of for the following graph?

Solução

Número de vértices = | V | = n = 7

Número de cobertura da linha = (α ₁ ) ≥ [n / 2] = 3

α ₁ ≥ 3

Usando 3 arestas, podemos cobrir todos os vértices.

Portanto, o número que cobre a linha é 3.