Teoria dos grafos - Propriedades básicas

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 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 de 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 for 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 1 , V 2 , ... 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 1 , V 2 , ... 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 |