Digrafos simétricos

Um digrafo simétrico é um tipo muito comum e muito importante de digrafo.  Um grafo é essencialmente o mesmo que um digrafo simétrico.

Digrafos simétricos

Um digrafo é simétrico se não tem laços e, para cada arco uv, o par vu também é um arco.  Diremos que o arco vu é inverso do arco uv.

As listas de adjacência de um digrafo simétrico têm a seguinte propriedade:  para cada par (u,v) de vértices, v está em Adj[u] se e somente se u está em Adj[v].  A matriz de adjacência de um digrafo simétrico é simétrica (ou seja, M[u,v] = M[v,u] para todo par (u,v) de vértices) e tem diagonal nula (ou seja, M[u,u] = 0 para todo vértice u).

Propriedade importante de digrafos simétricos: existe passeio de r a s se e somente se existe passeio de sr.  Consequência:  num digrafo simétrico, o território de qualquer vértice é um componente forte do digrafo.  Segue daí que todo digrafo simétrico fracamente conexo é fortemente conexo.

Diremos que um digrafo simétrico é conexo se ele for fracamente conexo (e portanto também fortemente conexo).  Em outras palavras, um digrafo simétrico é conexo se o território de qualquer vértice é o conjunto de todos os vértices.  Um componente de um digrafo simétrico é o mesmo que um componente forte do digrafo.

Exercícios

  1. Escreva um algoritmo que decida se um digrafo simétrico é (fracamente) conexo. Que certificado o algoritmo pode devolver para provar que o digrafo é conexo? Que certificado pode devolver para provar que o digrafo não é conexo?
  2. [IP 365]  Um digrafo simétrico é bicromático (ou bipartido) se for possível atribuir uma de duas cores a cada um de seus vértices de tal modo que as pontas de cada arco tenham cores diferentes. Escreva um algoritmo que decide se um dado grafo é ou não bicromático. O algoritmo pode consumir Ο(n+m) unidades de tempo, ao processar um grafo com n vértices e m arcos. Sugestão: use busca em profundidade.

Grafos

Um grafo ou digrafo não orientado ou digrafo não dirigido consiste em um conjunto de vértices e um conjunto de arestas. Cada aresta é um par não ordenado de vértices, ou seja, um conjunto com exatamente dois vértices. 

Para todos os efeitos práticos, um grafo é o mesmo que um digrafo simétrico:  uma aresta {u,v} se confunde com o par de de arcos {uv,vu}.

Valid HTML 4.01 Strict Valid CSS!