Diferenças entre edições de "Vértice (teoria dos grafos)"

26 bytes adicionados ,  07h46min de 13 de outubro de 2010
sem resumo de edição
Um [[Vértice de corte (teoria dos grafos)|vértice de corte]] é um vértice cuja remoção (juntamente com as arestas a ele conectadas) provoca um redução na conexidade do grafo<ref>[http://www.inf.ufsc.br/grafos/definicoes/definicao.html Grafos - UFSC]</ref>; Um separador é uma coleção de vértices cuja remoção desconecta o grafo restante em pedaços pequenos<ref>[http://www.ime.usp.br/~pf/algoritmos_em_grafos/aulas/two-flow.html Algoritmos em Grafos - IME]</ref>. Um grafo k-conexo é um gráfico em que a remoção de menos de ''k'' vértices sempre deixa o grafo ainda conectado. Um [[conjunto independente]] é um conjunto de vértices tal que não existem dois vértices adjacentes contido neste conjunto, e uma [[Cobertura de vértices (teoria dos grafos)|cobertura de vértices]] é um conjunto de vértices, que inclui o ponto de extremidade de cada borda do grafo. O [[espaço de vértices]] de um grafo é um espaço vetorial com um conjunto de vetores de base correspondente aos vértices do gráfico.
 
Um grafo é [[grafo vértice-transitivo|vértice-transitivo]] se ele tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto da [[enumeração (teoria dos grafos)|enumeração de grafos]] e [[isomorfismo de grafos]], é importante fazer a distinção entre '''vértices rotulados''' e '''vértices sem rótulo'''. Um vértice rotulado é um vértice que está associado com informação extra que possa o distinguir de outros vértices rotulados; dois grafos podem ser considerados isomórficos somente se a correspondência entre seus vértices emparelham vértices com rótulos iguais. Um vértice não marcado é aquele que pode ser substituído por qualquer outro vértice com base apenas em suas adjacências no gráfico e não baseado em quaisquer informações adicionais.
 
Vértices em grafos são análogos, mas não o mesmo que, [[Vértice|vértices]] de [[Poliedro|poliedros]]: o esqueleto de um [[poliedro]] forma um grafo, os vértices do qual são vértices do poliedro, mas os vértices do poliedro tem uma estrutura adicional (sua localização geométrica) que não se presume estar presente na teoria dos grafos. A [[Figura de vértice]] de um vértice de um [[poliedro]] é análoga à vizinhança de um vértice em um grafo.