public class No implements Comparable{

    private String identificador;
    private Set adjacentes;
    private boolean visitado;

Material do professor Paulo Feofiloff

Suponha dado um digrafo G e uma função  f  que atribui um número não-negativo a cada arco de G.  Diremos que o valor de f num arco é o fluxo no arco.  Para qualquer vértice v de G,  o  influxo em v  (= inflow into v)  é a soma dos fluxos nos arcos que entram em v.  O  efluxo de v  (= outflow from  v) é a soma dos fluxos nos arcos que saem de v.  O saldo em v  é a diferença

ef(v) - inf(v)

entre o efluxo de v e o influxo em v.  (Não confunda essa diferença com  inf(v) - ef(v).)  Portanto, o saldo em v é o que sai de v menos o que entrou em v.

O enunciado do problema que estudaremos a seguir especifica dois vértices do digrafo:  um vértice inicial e um vértice final. Esses vértices serão denotados por  s  e  t  respectivamente.  [Os vértices escolhidos para fazer o papel de s e t não precisam ter quaisquer propriedades especiais. Na prática, entretanto, não há mal em supor que s é uma fonte e t é um sorvedouro. Poderíamos até mesmo supor que s é a única fonte e t o único sorvedouro do digrafo.]

Num digrafo G com vértice inicial s e vértice final t, um   fluxo   (= flow)  é uma função f que atribui números não-negativos aos arcos de G de tal modo que

o saldo de f em todo vértice distinto de s e t é nulo

e o saldo em s não é negativo.   É fácil mostrar a seguinte

Propriedade do Fluxo (Property 22.1, p.362, Sedgewick):  Para qualquer fluxo num digrafo com vértice inicial s e vértice final t, o saldo em t é igual ao saldo em s com sinal trocado.

A  intensidade  de um fluxo f é o saldo de f em s.  De acordo com a propriedade acima, a intensidade de f é igual ao negativo do saldo em t.   Em geral (mas nem sempre) o influxo em s é nulo e o efluxo de t é nulo. Quando isso acontece, a intensidade do fluxo é igual ao efluxo de s e portanto também igual ao influxo em t.

Exemplo trivial: A função que associa 0 a cada arco é um fluxo. A intensidade desse fluxo nulo é 0.

Uma árvore é um grafo conexo sem circuito. Note que como um grafo precisa conter no mínimo um vértice, uma árvore contém no mínimo um vértice. Também temos que uma árvore é um grafo simples, pois laços e arestas paralelas formam circuitos. Um grafo não conexo que não contém circuitos será nomeado floresta. Nesse caso temos um grafo onde cada componente é uma árvore.

Um caminho simples ou um circuito simples é dito euleriano se ele contém todas as arestas de um grafo. Um grafo que contém um circuito euleriano é um grafo euleriano. Um grafo que não contém um circuito euleriano, mas contém um caminho euleriano será chamado grafo semi-euleriano.

Dado um grafo G=(V,E) com pesos nas arestas w: E → R e dois vértices u e v de V, o objetivo é encontrar um caminho mínimo de u para v, isto é, encontrar um caminho de u para v cuja a soma dos pesos das arestas é mínimo.

Vamos denotar por δ(u, v) o valor da soma dos pesos das arestas de um caminho de peso mínimo de u para v, sendo δ(u, v)= ∞ se não existe caminho de u para v.

Um motorista deseja encontrar a rota mais curta possível entre Porto Alegre e Brasília. Dado um mapa rodoviário do Brasil no qual a distância entre todos os pares de interseções adjacentes seja conhecida, como podemos encontrar essa rota mais curta?

Na literatura podemos encontrados vários algoritmos para a determinação do caminho mínimo entre dois vértices.

Material de autoria de

Prof. Ademir A. Constantino

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices. Consideremos por exemplo o problema do caminho mais curto. Os algoritmos apresentados para resolver esse problema fazem um percurso exaustivo de todos os vértices. Não precisa ser assim se, por exemplo, queremos o caminho mais curto até um vértice em particular. Nesse caso, assim que ele se encontra no conjunto dos vértices já visitado, não é preciso continuar o algoritmo.

Basicamente, existem duas técnica de busca em grafos: a busca em profundidade (depthfirst search) e a busca em largura (breadth-first search).

Grafo Um grafo é uma estrutura definida por G = (V,E), onde V é um conjunto não-vazio de elementos são denominados vértices, e E é um conjunto de elementos denominados arestas. Portanto, um grafo pode ser definido informalmente com um conjunto de elementos (vértices) e suas relações (arestas). Normalmente, utiliza-se uma representação gráfica de um grafo.

Material do Prof. Ademir Aparecido Constantino