Exercício

Um grafo direcionado pode ser modelado por uma relaç ão entre vé rtices, de forma que uma aresta que liga dois vé rtices, digamos, a e b no grafo é representada pelo par (a,b) na relaç ão que modela o grafo. a é denominado o vértice origem e b o destino.
a) Especifique o modelo descrito acima de grafos com um estado apropriado.
b) Especifique as seguintes operaç ões:

• Remove. Remove um vé rtice dado atravé s da remoç ão de todos os pares que tenham este vé rtice como origem ou destino.

• Caminho. Verifica se hå caminho entre dois vé rtices dados.

• Alcance. Seja a? um vé rtice dado. Esta operaç ão retorna o conjunto de todos os vé rtices b, desde que haja um caminho de a? para b no grafo.

• Ancestral Comum. Retorna o primeiro ancestral comum a dois vé rtices dados.

• Conectividade. Verifica se o grafo é conexo.

• A respeito deste documento...