Mostrar código-fonte de Vizinhança (teoria dos grafos)

[[Imagem:6n-graf.svg|thumb|Um grafo consistindo de 6 vértices e 7 arestas]]

Em [[teoria dos grafos]], um '''vértice adjacente''' de um [[Vértice (teoria dos grafos)| vértice]] ''v'' em um [[Grafo]] é um vértice que está ligado a ''v'' por uma [[grafo|aresta]].<ref name=even>{{citar livro|autor=Even, Shimon|título=Graph Algorithms|subtítulo=|idioma=|edição=|local=Rockville, Maryland|editora=Computer Science Press|ano=1979|páginas=249|volume=|isbn= 0-914894-21-8}}</ref><ref name=szwarcfiter>{{citar livro|autor=Szwarcfiter, Jayme Luiz|título=Grafos e algoritmos computacionais|subtítulo=|idioma=|edição=|local=Rio de Janeiro|editora=Campus|ano=1988|páginas=|volume=|isbn= 85-7001-341-8}}</ref> 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 ''N''<sub>''G''</sub>(''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 ''N''<sub>''G''</sub>[''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 (teoria dos grafos)|vértice isolado]] não tem vértices adjacentes. O [[Grau (teoria dos grafos)|grau]] de um vértice é igual ao número de vértices adjacentes. Um caso especial é um [[Laço (teoria dos grafos)|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==
[[Image:Octahedron graph.png|thumb|No grafo [[Octaedro|octaédrico]], a vizinhança de qualquer vértice é um 4-[[Ciclo (teoria de grafos)|ciclo]].]]
Se todos os vértices em ''G'' tem adjacências que são [[isomorfismo de grafos|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 grafos''F'', ''G'' é dito ser localmente ''F''(Hell 1978, Sedlacek, 1983). Por exemplo, no grafo [[Octaedro|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 ''C''<sub>4</sub>.

Por exemplo:

* Qualquer [[grafo completo]] ''K''<sub>''n''</sub> é localmente ''K''<sub>''n-1''</sub>. 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 [[grafo periplanar|periplanar]]. No entanto, nem todos os grafos localmente periplanares são planares.

* Um grafo é [[Grafo livre de triângulos (teoria dos grafos)|livre de triângulos]] [[sse]] é localmente [[Conjunto independente (teoria dos grafos)|independente]].

* Todo grafo ''k''-[[Número cromático|cromático]] é localmente (''k''-1)-cromático. Todo grafo localmente ''k''-cromático tem um número cromático <math>O(\sqrt{kn})</math>.<ref name="Wigderson">{{citar jornal |autor=Wigderson, Avi|data= |ano=1983|mes= |titulo=Improving the performance guarantee for approximate graph coloring|jornal=[[Journal of the ACM]] |volume=30 |numero=4 |paginas=729–735|editora= |local= |issn= |pmid= |doi=10.1145/2157.2158|bibcode= |oclc= |id= |url=|língua= |formato= |acessadoem=2010-06-27|aspas= }}</ref>

* 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 [[grafo cordal|grafos cordais]] são localmente cordais; cada [[grafo perfeito]] é localmente perfeito; todos os [[grafo de comparabilidade|grafos de comparabilidade]] são localmente comparáveis.

* Um grafo é localmente cíclico se cada vizinhança é um [[Grafo ciclo|ciclo]]. Por exemplo, o [[octaedro]] é o único grafo localmente ''C''<sub>4</sub>, o [[icosaedro]] é o único grafo localmente ''C''<sub>5</sub> e o [[gráfico Paley]] de ordem 13 é localmente ''C''<sub>6</sub>.

{{Referências}}

[[Categoria:Teoria dos grafos]]