MO405 - Atas das Aulas

Ata de Aula: 23/09/2002

Redator: João Guilherme de Souza Lima

Vinícius: Um separating set (conjunto separador) ou um vertex cut (corte por vértices) é um conjunto de vértices de um grafo, que, quando retirado, deixa o grafo com mais de um componente.

Vinícius: Conectividade de um grafo G é o tamanho do menor conjunto de vértices de G que, se retirado, deixa G com mais de um componente ou com apenas um vértice. Isto é, conectividade de um grafo G é o tamanho do menor conjunto separador de G, ou n-1 caso não haja conjunto separador (grafo completo).

Obs.: a conectividade de um grafo G é denotada por k (G)

Vinícius: Um grafo é k-conexo se a sua conectividade é pelo menos k.

Meidanis: Num grafo k-conexo, retirando-se quaisquer k-1 vértices, mesmo bem escolhidos, não desconecta-se o grafo, nem ele fica com um único vértice. Porém, retirando-se k vértices quaisquer de um grafo k-conexo, não necessariamente desconecta-se o grafo.

Meidanis: Se um grafo não possui vértice de corte, então este grafo é 2-conexo. (Obs.: isto vale apenas para grafos com 3 ou mais vértices)

Arthur: Conectividade por arestas é o número mínimo de arestas que devem ser retiradas para deixar o grafo com mais de um componente.

Obs.: a conectividade por arestas de um grafo G é denotada por k'(G).

Arthur: Um grafo é k-aresta-conexo se a sua conectividade por arestas é pelo menos k.

Arthur: Outra definição para conectividade por arestas: a conectividade por arestas de um grafo G é o maior k tal que G é k-aresta conexo.

Meidanis: num grafo k-aresta-conexo, retirando-se quaisquer k-1 arestas, mesmo bem escolhidas, não desconecta-se o grafo. Porém, retirando-se k arestas quaisquer de um grafo k-aresta-conexo, não necessariamente desconecta-se o grafo.

Cândida: Teorema 4.1.9

a) justificativa para k'(G) <= d (G)

Cândida: Ao retirar-se todas as arestas incidentes ao vértice de menor grau do grafo, isola-se este vértice, tornando-o um novo componente do grafo. Consequentemente, para desconectar um grafo através da eliminação de arestas, não é necessário retirar mais arestas do que aquelas incidentes ao vértice de menor grau, e assim a conectividade por arestas de um grafo não é maior do que o grau do vértice de menor grau deste grafo.

b) justificativa para k (G) <= k'(G)

Cândida: Ao retirar-se um vértice de cada uma das arestas pertencentes a um disconnecting set do grafo, elimina-se também todas as arestas pertencentes a este disconnecting set, desconectando desta maneira o grafo através da eliminação de arestas. Consequentemente, para desconectar um grafo através da eliminação de vértices, não é necessário retirar mais vértices do que o tamanho do menor disconnecting set do grafo, e assim a conectividade de um grafo não é maior do que a conectividade por arestas deste grafo.

Cláudio: Um bloco de G é um subgrafo maximal de G que não possui vértice de corte. Se por si só é conexo, sem vértice de corte, então G é um bloco.

Arthur: Uma aresta de um ciclo nunca é um bloco.

Arthur: Os blocos de uma árvore são suas arestas.

Arthur: Uma aresta é um bloco se e somente se ela é uma aresta de corte.

Cléber e turma: O algoritmo para busca de blocos é linear no tamanho do grafo, isto é, roda em tempo O(m+n), onde m é o número de arestas e n é o número de vértices do grafo. Também poderia ser visto como O(n²), mas O(m+n) é "mais justo".

Meidanis: o algoritmo é realmente linear uma vez que o tempo gasto em cada vértice e em cada aresta é constante.

Turma: O grafo de blocos e vértices de corte de um grafo G é um grafo cujo conjunto de vértices é formado pelo cojunto de vértices de corte de G adicionado de mais um vértice para cada bloco de G. Existe uma aresta ligando um vértice de corte com o vértice representativo de um bloco se este vértice de corte pertence a este bloco em G.

Meidanis: O grafo de bloco de corte de um grafo G pode ser visto como a estrutura de G. Ele é sempre bipartido, e sempre uma árvore.