Diferenças entre edições de "Teoria dos grafos"

752 bytes adicionados ,  00h10min de 7 de junho de 2013
 
== Glossário dos conceitos básicos de teoria dos grafos ==
=== Representação gráfica (layout do grafo) ===
 
[[Imagem:6n-graf.svg|thumb|Um grafo com 6 vértices e 7 arestas]]
 
Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta.
 
Note que essa representação gráfica (o layout) não deve ser confundida com o grafo em si (a estrutura abstrata, não-gráfica). Vários diferentes layouts podem corresponder ao mesmo grafo.<ref>Ver por exemplo, [http://www.aisee.com/gallery/graph23.htm]</ref> O que importa é quais vértices estão conectados entre si por quantas arestas.
O grafo de exemplo exibido à direita é um grafo simples com o conjunto de vértices ''V'' = {1, 2, 3, 4, 5, 6} e um conjunto de arestas ''E'' = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} } (com o mapeamento ''w'' sendo a [[função inclusão|identidade]]).
 
 
Em um grafo genérico ''G'', o '''corte''' associado a um conjunto ''X'' de vértices é o conjunto de todas as arestas que têm uma ponta em ''X'' e outra em ''V(G) - X'', onde ''V(G)'' é o conjunto de todos os vértices pertencentes ao grafo ''G''.
 
===Tipos de Grafos===
 
* '''[[Grafo simples]]''' é um grafo não direcionado, sem laços e que existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.
49

edições