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

1 byte removido ,  21h59min de 18 de maio de 2018
m
Foram revertidas as edições de 201.78.88.167 (usando Huggle) (3.3.3)
(Trecho obscuro (tradução automática???))
m (Foram revertidas as edições de 201.78.88.167 (usando Huggle) (3.3.3))
Etiquetas: Huggle Reversão
 
Os dois vértices formando uma aresta são ditos suas extremidades e a aresta é dita que é incidente para com os vértices.<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> Um vértice ''w'' é dito ser adjacente a outro vértice ''v'' se o grafo contém uma aresta (''v'',''w'').<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 [[adjacência (teoria dos grafos)|adjacência]] de um vértice ''v'' é um [[subgrafo induzido]] do grafo, formado por todos os vértices adjacentes a ''v''.
 
O [[grau (teoria dos grafos)|grau]] de um vértice em um grafo é o número de arestas incidentes a ele.<ref name=cormen>{{citar 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|volume=|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 nenhumatoda 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 (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 aresta 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.
8 932

edições