vizinhança

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