Resumo de Discretas GRAFOS

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

>>>>>>>>>>>>>> ESTUDO DISCRETAS <<<<<<<<<<<<<<<<
---> Códigos de Gray
---> Corolários do teorema de Euler
---> Aplicações de coloração de grafos
---> Algoritmo caminho mais curto
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
---> Grafos e modelos de grafos:
-> Grafo Simples: quando cada aresta conecta
dois vértices diferentes e duas arestas nunca conectam o mesmo
par de vértice.
-> Multigrafos: grafos que possuem arestas múltiplas, ou seja, arestas que
conectam mesmos vértices.
-> Laços: arestas que conectam o mesmo vértice.
-> Pseudografos: grafos que possuem laços e arestas múltiplas.
-> Grafo não orientado: as arestas não possuem direção.
-> Grafo orientado: as arestas possuem direção.
-> Grafo misto: um grafo com tanto arestas orientadas quanto não orientadas.
---> Terminologia básica:
-> Adjacência: dois vértices em um grafo não orientado são ditos adjacentes se eles são extremidades de uma aresta.
-> Grau: o grau de um vértice é o número de arestas incidentes a ele mesmo.
Obs: Um laço contribui com 2 graus. 
Obs2: Um vértice é dito isolado se ele tem grau 0.
Obs3: Um vértice é dito pendente se ele tem grau 1.
---> Grafos simples especiais:
-> Kn: É um grafo completo de n vértices, ele possui uma aresta entre cada
par de vértice distintos.
-> Cn: É um ciclo, no qual n >= 3.
-> Wn: É uma roda, no qual n >= 3. Ele pode ser considerado um Cn com um vértice
a mais no centro.
-> Qn: É um n-Cubo, no qual pode ser feito Qn+1 a partir do Qn, copiando Qn e ligando os vértices correspondentes.
---> Bipartição de grafos: 
-> Bipartido: um grafo simples é bipartido se somente se for possível associar
uma de duas cores diferentes a cada vértice do grafo de modo que nenhum par de vértices adjacentes tenha a mesma cor associada.
---> Grafos planares:
-> Grafo planar: um grafo é dito planar se ele puder ser desenhado no plano
sem que quaisquer arestas se cruze.
-> O grau de uma região é no mínimo 3, pois estamos tratando de grafos simples.
-> Fórmula de Euler: nºregiões = arestas - vértices + 2 (r = a - v + 2)
---> Corolários do teorema de Euler:
-> Corolário 1: Se o número de v vértices for v >= 3, então a quantidade a de arestas é a <= 3v - 6.
-> Obs: A soma dos graus das das regiões é exatamente duas vezes o número de
arestas no grafo. (2a = Grau da região 1 + Grau da região 2 + ... + Grau na região n).
-> Corolário 2: Um grafo simples planar conexo deve possuir um vértice que não exceda grau 5.
-> Corolário 3: Se um grafo simples planar conexo com v >=3, e nenhum ciclo de
comprimento 3, então a <= 2v -4.
---> Coloração de grafos:
-> Uma coloração de um grafo simples é a associação de uma cor a cada vértice
do grafo de modo que dois vértices adjacentes não estejam associados à mesma
cor.
-> Número cromático: é o menor número de cores necessárias para a coloração de um grafo.
-> TEOREMA DAS QUATRO CORES: O número cromático de um grafo planar não é maior 
do que quatro.
-> APLICAÇÕES: Bipartição de grafos, Horários dos Exames Finais, Registros de índices...
---> Código de gray:
-> Um código de Gray é uma designação dos arcos do círculo tal que arcos adjacentes são designados por cadeias de bits que diferem exatamente em um bit.
-> Utilize um Qn para representação. Toda vez que ir fazendo cópias do Qn para construir Qn+1, deve-se atribuir um 0 no ínicio dos vértices da origem (Qn) e um 1 nos das cópias (Qn+1).
-> Em seguida encontre o ciclo hamiltoniano, que é um ciclo no qual é possível
sair de um vértice e retornar a ele passando por todos os outros vértices.
---> Caminho mais curto: 
-> Utiliza grafos que contém a associação de um peso em suas arestas.
-> Comprimento de um caminho: É a soma dos pesos das arestas desse caminho.
-> Algoritmo de Dijkstra:
1º Associa-se 0 ao primeiro vértice (de origem).
2º Aos vértices não adjacentes ao de origem, associa-se o infinito.
3º Em seguida o algoritmo analisa cada vértice percorrendo em largura. 
4º Para cada vértice analisado, é atualizado o valor do comprimento do caminho até 
os demais vértices adjacentes. 
5º Essa atualização é de acordo com o valor de quanto foi necessário pra chegar no vertice analisado somado com o peso da aresta correspondente ao outro vértice adjacente. Obs.: Lembre-se de que sempre prevalece-rá o menor valor. 
6º Esse procedimento vai se repetir até chegar ao vértice de destino, e assim terá o menor caminho.