teste

Relatório 4 - Grafos 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.2 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 identidade).
Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta. A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas. Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada.
Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjacentes a ele