Vértice (teoria dos grafos): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
← nova página: {{nota:|Para outros usos veja Vértice}} {{em tradução}} [[Image:6n-graf.svg|thumb|Um grafo com 6 vértices e 7 arestas onde o vértice da extrema-direita é ... |
|||
Linha 7:
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. 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 />.
▲<!--
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.
Linha 56:
-->
{{ref-section}}
=={{Ligações Externas}}==
| |||