Vizinhança (teoria dos grafos)

Um grafo consistindo de 6 vértices e 7 arestas

Em teoria dos grafos, um vértice adjacente de um vértice v em um Grafo é um vértice que está ligado a v por uma aresta.[1][2] A vizinhança ou adjacência de um vértice v em um grafo G é um subgrafo induzido de G constituído por todos os vértices adjacentes a v e todas as arestas ligando esses dois vértices. Por exemplo, a imagem mostra um gráfico de 6 vértices e 7 arestas. O vértice 5 é adjacente aos vértices 1, 2 e 4, mas não é adjacente aos vértices 3 e 6. A vizinhança do vértice 5 é o grafo com três vértices, 1, 2 e 4, e uma aresta conectando os vértices 1 e 2.

A vizinhança é frequentemente denotada NG(v) ou (quando o grafo não é ambíguo) N(v). A mesma notação de vizinhança também pode ser usada para se referir a um conjunto de vértices adjacentes ao invés dos subgrafos induzidos correspondentes. A adjacência descrita acima não inclui v em si, e mais especificamente, a vizinhança aberta de v; também é possível definir uma adjacência na qual v está incluído, chamada de vizinhança fechada e denotada por NG[v]. Quando não se afirma nada, a vizinhança é considerada aberta.

Vizinhanças podem ser usadas para representar grafos em algoritmos de computador, através da representações de lista de adjacência e matriz de adjacência . Vizinhanças também são usadas no coeficiente de agrupamento de um grafo, que é uma medida da densidade média de suas adjacências. Além disso, muitas classes importantes de grafos podem ser definidas pelas propriedades de suas vizinhanças, ou por simetrias que relacionam vizinhanças umas com as outras.

Um vértice isolado não tem vértices adjacentes. O grau de um vértice é igual ao número de vértices adjacentes. Um caso especial é um laço que une um vértice a ele próprio; se tal aresta existe, o vértice pertence à sua própria vizinhança.

Propriedades locais em grafos

No grafo octaédrico, a vizinhança de qualquer vértice é um 4-ciclo.

Se todos os vértices em G tem adjacências que são isomorfas para o mesmo grafo H,G é dito ser localmente H, e se todos vértices em G tem adjacências que pertencem a alguma família de grafosF, G é dito ser localmente F(Hell 1978, Sedlacek, 1983). Por exemplo, no grafo octaédrico mostrado na figura, cada vértice tem uma adjacência isomorfa a um grafo cíclico de quatro vértices, de modo que o octaedro é localmente C4.

Por exemplo:

  • Qualquer grafo completo Kn é localmente Kn-1. Os únicos grafos que são localmente completos são uniões disjuntas de grafos completos.
  • Um grafo de Turán T(rs,r) é localmente T((r-1)s,r-1). Mais genericamente qualquer grafo Turan é localmente Turan.
  • Todo grafo planar é localmente periplanar. No entanto, nem todos os grafos localmente periplanares são planares.
  • Todo grafo k-cromático é localmente (k-1)-cromático. Todo grafo localmente k-cromático tem um número cromático .[3]
  • Se uma família de grafos F é fechada sob a operação de tomar subgrafos induzidos, então cada grafo em F é também localmente F. Por exemplo, todos os grafos cordais são localmente cordais; cada grafo perfeito é localmente perfeito; todos os grafos de comparabilidade são localmente comparáveis.
  • Um grafo é localmente cíclico se cada vizinhança é um ciclo. Por exemplo, o octaedro é o único grafo localmente C4, o icosaedro é o único grafo localmente C5 e o gráfico Paley de ordem 13 é localmente C6.

Referências

  1. ↑ Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. 249 páginas. ISBN 0-914894-21-8 
  2. ↑ Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8 
  3. ↑ Wigderson, Avi (1983). «Improving the performance guarantee for approximate graph coloring». Journal of the ACM. 30 (4). pp. 729–735. doi:10.1145/2157.2158