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

119 bytes adicionados ,  21h30min de 18 de maio 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|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 é [[vértice-transitivo]] se ele tiver simetrias que mapeiam qualquer vértice para qualquer outro vértice. No contexto da [[enumaeração (teoria dos grafos)|enumeração de grafos]] e [[isomorfismo (teoria dos grafos)|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.
<!--
 
<!--
A graph is [[vertex-transitive graph|vertex-transitive]] if it has symmetries that map any vertex to any other vertex. In the context of [[graph enumeration]] and [[graph isomorphism]] it is important to distinguish between '''labeled vertices''' and '''unlabeled vertices'''. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information.
 
Vertices in graphs are analogous to, but not the same as, [[vertex (geometry)|vertices of polyhedra]]: the [[skeleton (topology)|skeleton]] of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The [[vertex figure]] of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.