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

610 bytes adicionados ,  03h55min de 28 de abril de 2010
sem resumo de edição
( 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 é ...)
 
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 />.
The two vertices forming an edge are said to be its endpoints, and the edge is said to be incident to the vertices. A vertex ''w'' is said to be adjacent to another vertex ''v'' if the graph contains an edge (''v'',''w''). The [[neighborhood (graph theory)|neighborhood]] of a vertex ''v'' is an [[induced subgraph]] of the graph, formed by all vertices adjacent to ''v''.
 
<!--
The [[degree (graph theory)|degree]] of a vertex in a graph is the number of edges incident to it. An '''isolated vertex''' is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge. A '''leaf vertex''' (also '''pendant vertex''') is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges) from the indegree (number of incoming edges); a '''source vertex''' is a vertex with indegree zero, while a '''sink vertex''' is a vertex with outdegree zero.
 
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.
 
-->
 
{{ref-section}}
 
=={{Ligações Externas}}==