AEDs III 09/05/2011

// Aula da Jussara

Apresentando Grafos

CONCEITO:
Grafos são uma ferramenta extremamente útil na expressão grafica de problemas.
Pode-se usa-los para modelar um problema computacional, torna-lo mais visível e mais fácil de se trabalhar.

A forma pela qual se expressa um grafo é por um desenho composto por pontos, chamados vertices, conectados entre sí
por traços ou setas, chamadas arestas.
// Outro nome para vertice é nó, eu usarei esse nome frequentemente mais adiante.

Dependendo da aplicação que for desejada para o gráfico pode-se adicionar características à livre escolha.
À exemplo para se tratar de um problema de caminhamento entre cidades pode-se adicionar distancias as arestas,
Quando se faz isso da-se o nome Arestas com "Pesos".

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Vários Nomes e CONCEITOS que a professora citou:
-Cada aresta pode ou não ser direcionada, e pode ser também duplamente direcionada. (se direcionada a representação é uma seta)
-Uma aresta pode ligar um vertice à ele mesmo, usualmente isso ocorre apenas em grafos direcionados.

-Um vizinho de um nó é um outro nó conectado a ele via uma aresta.

-O grau de um nó é o número de vizinhos que ele possui.
-Em grafos direcionados pode-se usar os termos grau de entrada para o número de arestas que incidem no nó em questão,
 e grau de saída para o número de arestas que saem do nó em questão.
-O grau de um grafo é o maior grau de seus vertices. Portanto um grafo de grau 3, tem no maximo 3 arestas por nó.

-Um caminho entre o nó A e B é uma sequencia de arestas que deve-se seguir para se chegar do ponto A ao ponto B.
-Caminho Simples é um caminho sem repetição de nós. Ou seja um caminho direto.
-Um Ciclo em um grafo é um caminho do ponto A ao ponto A. // Bem obvio isso.
-Grupo Conexo é um grupo de nós para os quais cada nó possuí um caminho para todos os outros.
 Em um grafo direcionado chama-se de grupo conexo, um grupo que seria conexo em um grafo não direcionado.
 E reserva-se o nome "Fortemente Conexo" para os grupos que são conexos mesmo considerando as direções das arestas.
-Dois nós ligados "Diretamente" significa que existe um caminho entre eles de uma única aresta.

-Um nó "Filho" de outro nó é um nó que foi alcançado a partir deste outro diretamente.
 Um nó "Decendente" de outro nó é analogo, porém não necessáriamente foi alcançado por uma ligação direta.
-Um nó "Pai" de outro nó é um nó através do qual pode-se alcançar outro diretamente.
 Um nó "Ancestral" de outro nó é analogo, porém não necessáriamente foi leva ao outro nó por uma ligação direta.

-Um Grafo Isomorfo de outro é um grafo identico à outro em forma, ou seja, mesmo número de arestas e de nós e os mesmos
 nós possuem as mesmas arestas. Pode até ser que os nós tenham nomes diferentes mas o importante é o se o formato dos dois é analogo.

-Um Sub-grafo é um grafo formado por um subconjunto dos vertices e um subconjunto dos vertices de um outro grafo.

-Um Grafo Bipartido é um grafo do tipo "quais sites cada usuário do dcc acessou?"
 Então teremos um grupo de vertices que representarão usuários e outro grupo representará os sites.
 E teremos com isso apenas transições que vão de um grupo para o outro, nunca transições dentro do mesmo grupo.
 Genericamente: Um Grafo Bipartido é um grafo divisível em 2 grupos onde cada grupo não possuí transições internas.
// Se voce for criativo pode ate pensar em grafo tripartido e etc, depende da aplicação que voce deseja.

// Existe o conceito de Hipergrafo que é a ideia de que uma unica transição pode conectar diversos nós e nao apenas 2.
// Mas esse conceito é mais exotico e provavelmente não usaremos ele.

-Um grafo completo é um grafo em que cada nó está conectado diretamente (ou seja por uma única aresta) a cada outro nó.
 Este grafo se for não direcionado possui v*(v-1)/2 arestas.
 Se for direcionado possui v² arestas. // pq cada um pode estar conectado a sí mesmo.

-Uma arvore é um grafo sem ciclos que está conexo
 Uma floresta é um conjunto de árvores sem conexões entre sí.
 Um grafo não conexo sem ciclos pode ser visto como uma floresta, ou seja um conjunto de arvores soltas.
-Arvore geradora é um subconjunto de um grafo que conecte todos os nós sem gerar ciclos.
-Também existe a floresta geradora que é uma ideia menos útil mas é analogo a da árvore geradora.

// A aula mais legal de acordo com a professora é a aula que vem pra frente, porque veremos um a um as soluções que existem a respeito
// desses problemas.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Como um grafo pode ser expresso na memória de um computador?
-Pode ser criada uma matriz de bits, onde o bloco (x,y) indica se existe conecção entre os nós x e y.
-Pode ser também um arranjo de ponteiros onde o ponteiro de indice x aponta para uma lista contendo as transições do nó x.

// Uma implementação estatica disso também existe mesmo sem usar uma matriz.
// Isso é util quando sua plataforma tem pouca memoria e nao tem alocação dinamica.
// Da pra imaginar isso se voce entende como funciona a pilha do assemble. É uma ideia semelhante.
// Não vejo como nós iriamos vir a usar isso então não anotei.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

CONCEITO:
Busca em Profundidade é a busca em que eu passeio por toda a arvore filho a filho recursivamente,
só começo a pesquisa do irmão de um filho depois que todas os filhos do primeiro filho ja tiverem sido pesquisados até a exaustão.

// Abaixo entenda que uma "cor" é um marcador, normalmente será um número quando voce estiver programando.
Um metodo para se realizar essa pesquisa é o metodo de colorir de cinza os nós que estão sendo pesquisados,
e de preto aqueles que já foram exauridos. A vantagem de usar essas cores é que uma vez que voce encontrar uma transição
para um nó que voce já pesquisou voce percebe isso na hora, e não deixa seu programa entrar em loop.
Agora a necessidade da cor preta (ao invés de deixar tudo apenas na cor cinza),
é para denotar que se o nó ta preto, é porque ele não pode ser um "ancestral" do nó que voce está pesquisando atualmente.
Isso pode ser útil na resolução de alguns tipos de problemas.

Esse algoritimo é O(V+A) sendo V o num vertices e A o num arestas.

CONCEITO:
Busca em largura é uma pesquisa em que voce pesquisa primeiro todos os filhos do vertice de inicio,
depois todos os filhos dos filhos e assim por diante.
Utiliza-se uma unica coloração neste sistema que é preto e voce só colore de preto uma vez que todos os vizinhos ja tiverem
sido pesquisados.
Uma outra coisa que é feita nesse sistema e que pode ser útil na resolução de alguns problemas é escrever no nó
qual a sua distancia do nó inicial.

Esse sistema também é recursivo e sua complexidade é O(V+A)

// Até a proxima aula!!