Wikipédia

Vértice (teoria dos grafos): diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
m fim de tradução
Xqbot (discussão | contribs)
Robôs
426 329 edições
m Bot: Modificando: sv:Hörn (grafteori); mudanças triviais
Linha 1:
{{nota:|Para outros usos veja [[Vértice]]}}
 
[[ImageFicheiro:6n-graf.svg|thumb|Um grafo com 6 vértices e 7 arestas onde o vértice da extrema-direita é um '''vértice-folha''' ou um '''vértice-pendente'''.]]
 
Em [[teoria dos grafos]], um '''vértice''' (plural '''vértices''') ou '''nodo''' é a unidade fundamental da qual os grafos são formados: um [[Grafo|grafo não dirigido]] consiste de um conjunto de vértices e um conjunto de arestas (pares de vértices não ordenados), enquanto um [[Quiver|digrafo]] é constituído por um conjunto de vértices e um conjunto de arcos (pares ordenados de vértices). Do ponto de vista da teoria dos grafos, vértices são tratados como objetos inexpressivos e indivisíveis, embora possam ter uma estrutura adicional, dependendo da aplicação a partir da qual surge o grafo; por exemplo, uma [[rede semântica]] é um grafo no qual os vértices representam conceitos ou classes de objetos.
 
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>{{Referência a 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|volumes=|volume=|id=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>{{Referência a 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=|volumes=|volume=|id=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>{{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 (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_grafosteoria 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.
Linha 47:
* {{Cite book | author=Harary, Frank; Palmer, Edgar M. | authorlink= | coauthors= | title=Graphical enumeration | date=1973 | publisher=New York, Academic Press | location= | isbn=0-12-324245-2 | pages=}}
 
== {{Ver Também}} ==
[[Teoria dos grafos]]
 
Linha 53:
 
[[ar:رأس (نظرية المخططات)]]
[[en:Vertex (graph_theorygraph theory)]]
[[es:Vértice (teoría de grafos)]]▼
[[eo:Vertico (grafeteorio)]]
▲[[es:Vértice (teoría de grafos)]]
[[fa:رأس (نظریه گراف)]]
[[it:Vertice (teoria dei grafi)]]
[[no:Nod]]
[[pl:Wierzchołek izolowany]]
[[sv:NodHörn (grafteori)]]
Obtida de "https://pt.wikipedia.org/wiki/Vértice_(teoria_dos_grafos)"