Autor da ata: Vinicius José Fortuna
Referente à aula de 11/11/2002. Redigida em 21/11/2002.
Um grafo G é perfeito se c( H ) = w( H ) para todo subgrafo induzido H de G. (Definição 8.1.1)
Um grafo é perfeito se e somente se seu complemento é perfeito. (Teorema 8.1.6)
Tal teorema acaba com a distinção entre grafos a- e g-perfeitos.
Um grafo G é perfeito se e somente se ambos G e seu complemento G não possuem como subgrafo induzido um ciclo de tamanho pelo menos 5. (Conjectura 8.1.2)
Uma representação por intersecção (intersection representation) de um grafo é uma família de conjuntos {Sv : v em V(G)} tal que (u,v) está em E(G) se e somente se a intersecção de Su e Sv contém pelo menos um elemento. (Definição 8.1.9)
Um grafo é cordal se e somente se ele tem uma representação por intersecções usando subárvores de uma árvore como os conjuntos da representação. (Teorema 8.1.11)
Todo grafo de intervalo é um grafo cordal, pois os intervalos podem ser representados por caminhos que se sobrepõem e os caminhos são subárvores de uma árvore. Por exemplo:
|
|
No entanto, nem todo grafo cordal é um grafo de intervalos. O professor provou que o grafo abaixo não é de intervalos por meio de um algoritmo não visto em aula, mas, como podemos ver, ele pode ser representado por interseções de subárvores, sendo, portanto cordal.
  |
O algoritmo MCS retorna uma ordenação dos vértices de um grafo que é uma ordem de construção simplicial do mesmo se e somente se ele é cordal. (Teorema 8.1.14)
O algoritmo funciona da seguinte forma. Inicialmente nenhum dos vértices estão numerados e todos eles estão rotulados com o valor zero. Faça i = 0. A cada passo numere com o valor i qualquer um dos vértices ainda não numerados de maior rótulo e incremente i e o rótulo de cada um dos vizinhos. Repita até que todos os vértices estejam numerados. A numeração dos vértices forma a ordenação de saída. (Algoritmo 8.1.12)
O algoritmo lembra uma busca em largura, mas a fila FIFO seria trocada por uma fila de prioridade baseada no número de vizinhos já numerados de cada vértice. Contudo, esta fila de prioridade faria com que o algoritmo deixasse de ser linear.
É possível fazer com que a complexidade do algoritmo permaneça O( n(G) + e(G) ). Ao invés de fila de prioridade, mantemos n(G) "sacolas"(buckets), uma para cada valor do rótulo. Como os rótulos (que seriam as prioridades) assumem apenas valores entre 1 e n(g), as sacolas substituem a fila de prioridade, com a vantagem de deixarem o algoritmo linear.
Verificar sa a ordenação de saída é a de uma construção simplicial também pode ser feito em tempo polinomial.
Análise de cadeias de DNA e seriação arqueológica são aplicações que foram mencionadas, mas que haviam sido explicadas em outra aula.
Nessa aula apresentou-se a aplicação em temporização de sinais de trânsito. Em um cruzamento, cada sinal de trânsito, estando aberto ou fechado, permite ou impede, respectivamente, a passagem seguindo uma determinada rota. Modelamos então um grafo em que os vértices são os sinais de trânsito e, para cada par de semáforos, existe uma aresta entre eles se e somente se eles dizem respeito a rotas incompatíveis. Rotas incompatíveis são aquelas que se cruzam. Portanto a aresta significa que ambos os sinais não podem estar abertos simultaneamente.
A partir de um momento em que todos os semáforos estão fechados, podemos definir intervalos no tempo em que cada um estará aberto, de forma que, a qualquer instante, os sinais abertos formem um conjunto independente no grafo modelado acima. Tal grafo modela as restrições do problema e pode ser usado como base para a otimização da temporização dos semáforos.
Uma ordem perfeita de um grafo é uma ordenação de seus vértices tal que a coloração gulosa seguindo tal ordem de qualquer um de seus subgrafos induzidos é ótima. (Definição 8.1.23)
Um grafo perfeitamente ordenável é um grafo que possui uma ordem perfeita. (Definição 8.1.23)
Em uma orientação de G, uma obstrução é um caminho induzido de 4 vértices tal que a primeira e a última aresta estão orientadas na direção das folhas.
Uma orientação associada a uma ordenação de vértices orienta uma aresta de u para v se u > v.
Um ordenação de vértices é livre de obstruções se a orientação associada a ela não possui obstruções.
É importante notar que a direção da ordenação é importante. Uma ordenação crescente é diferente de uma ordenação decrescente. Por exemplo, o caminho (b, a, c, d) é uma obstrução para ordenação a > b > c > d, mas não é para a ordenação a < b < c < d.
Uma ordenação dos vértices de um grafo simples é uma ordenação perfeita se e somente se é livre de obstruções. Todo grafo com tal ordenação é perfeito. (Teorema 8.1.26)
Um grafo arco-circular é o grafo de intersecção de uma família de arcos de uma circunferência. (Definição 8.1.47)
Um grafo de círculo é um grafo de intersecção de uma família de cordas de um círculo. (Definição 8.1.47)
Um grafo livre de garra (claw-free) é um grafo que não possui o grafo garra (K1,3) como um subgrafo induzido. Também é chamado de livre de K1,3 (K1,3 -free). (Definição 8.1.47)
Todo ciclo é um grafo de círculo e um grafo arco circular, mas nenhuma dessas classes contém uma a outra.
A SPGC vale para grafos arco-circulares. (Teorema 8.1.49)
A SPGC vale para grafos livres de garra. (Corolário 8.1.53)
A SPGC vale para grafos de círculo. (Página 344)