| Wikipédia em português - A enciclop... |
Vértice (teoria dos grafos)
Em teoria dos grafos, um vértice (plural vértices) ou nó é a unidade fundamental da qual os grafos são formados: um 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 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. Um vértice w é dito ser adjacente a outro vértice v se o grafo contém uma aresta (v,w). A adjacência de um vértice v é um subgrafo induzido do grafo, formado por todos os vértices adjacentes a v.
O 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 .
| Veja mais na Wikipédia.org... |
© Esse artigo usa material da Wikipédia® sob a licença Licença GNU de Documentação Livre e sob nos termos da licença Creative Commons Attribution-ShareAlike
