MO405 - Atas - 2002-08-07

Modificada: 2002-08-15 - tamanho da matriz incidencia O(n^3)

Ata - Aula do dia 07/08/2002
Dia da digitação: 09/08/2002
Arthur Bispo de Castro 992659

Definição de Grafos - Alberto
- Dois conjuntos: um de vértices outro de arestas.
- Um grafo é o relacionamento entre estes conjuntos de vértices e de arestas.
- Existência de laços, arestas múltiplas, grafos orientados.
- Grafo nulo: sem vértices.
- Grafo vazio: sem arestas.

Grafos bipartidos - Cláudio
- Separa os vértices em dois conjuntos de tal maneira que um corte entre os conjuntos quebra todas as arestas.
- Podemos pintar com duas cores.
- Dois conjuntos em que só haja aresta entre conjuntos diferentes.
- Bipartição não é única.
	- Quando a bipartição não é única? Quando o grafo não for conexo.

Grafo completo - Cibele
- Existe uma aresta unindo cada par de vértices.
- Existência de arestar multiplas... não é grafo completo.

Matriz de incidência - Cleber
- As linhas indicam os vértices e as colunas as arestas.
- 0 se não ocorre no grafo, 1 caso contrário.
- Tamanho: O(n^3).

Matriz de adjacência - Diogo
- As linhas e as colunas indicam os vértices.
- 0 indica a não existencia de aresta entre os vértices.
- 1 há aresta entre os vértices.
- Permite outros números - arestas múltiplas.
- Diagonal é nula (não existência de laços).
- Soma da linha/coluna dá o grau do vértice.
- Tamanho: n^2.
- Grafos orientados: matriz não simétrica.

Grau - Desiree
- Número de arestas que incidem num vértice
- Para um grafo: grau máximo (delta maiúsculo) e grau mínimo (delta minusculo).

Complemento de um grafo - Evandro
- Cópia dos vértices, cria as arestas não existentes no original.
- Trocar 0 por 1 na matriz de adjacencia (exceto na diagonal).
- União dos grafos -> uso complicado do termo 'união'!!!
- Só vale para grafo simples.

Isomorfismos - Fernando
- Existência de uma bijeção entre os conjuntos de vértices e arestas entre dois grafos, que preserve a incidência.
- Como se a gente trocasse o nome dos vértices e arestas.
- Costume de desenhar grafos sem nomes -> representa a classe.
- Contagem de grafos - com (existem mais) ou sem (existem menos) nomes.
- Sem nome - agrupa os isomorfos.
- Isomorfismos implica em uma mesma lista de graus.

Cintura - Guilherme
- Tamanho do menor ciclo.
- Sem ciclo -> infinito.
- Circunferência: tamanho do maior ciclo.

Decomposição - Gilberto
- Separa o conjunto de arestas em várias partes.
- Conceito bem amplo.
- Vértices podem repetir.

Aplicação - João Paulo
- Alocação de registradores pelas instruções.
- Coloração dos registradores.
- Vértices -> registradores; Arestas -> ligam as instruções que o registrador usa.