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

145 bytes removidos ,  16h45min de 17 de maio de 2010
sem resumo de edição
O [[grau (teoria dos grafos)|grau]] de um vértice em um grafo é o número de arestas incidentes a ele<ref name=cormen>{{Referência a livro|autor=Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford|título=Algoritmos|subtítulo=Teoria e Prática|idioma=|edição=2ª|local=Rio de Janeiro|editora=Campus|ano=2002|páginas=916|volumes=|volume=|id=ISBN 85-352-0926-3}}</ref>. Um '''vértice isolado''' é um vértice com grau zero, isto é, um vértice que não é um ponto final de toda a aresta. Um '''vértice folha''' (também '''vértice pendente''') é um vértice de grau um. Em um grafo direcionado, pode-se distinguir o grau de saída (número de arestas divergentes) do grau de entrada (número de arestas convergentes); uma '''fonte''' é um vértice com grau de entrada zero, enquanto um '''sumidouro''' (ou poço) é um vértice com grau de saída nulo<ref name=szwarcfiter />.
 
Um [[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]] é 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.
 
<!--
 
A [[cut vertex]] is a vertex the removal of which would disconnect the remaining graph; a [[vertex separator]] is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A [[k-vertex-connected graph]] is a graph in which removing fewer than ''k'' vertices always leaves the remaining graph connected. An [[Independent set (graph theory)|independent set]] is a set of vertices no two of which are adjacent, and a [[vertex cover]] is a set of vertices that includes the endpoint of each edge in the graph. The [[vertex space]] of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.
 
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.