Universidade regional de blumenau



Baixar 1,07 Mb.
Página3/12
Encontro01.07.2018
Tamanho1,07 Mb.
1   2   3   4   5   6   7   8   9   ...   12

Propriedades dos grafos


Existem diversas propriedades ou classificações de grafos. Saber com que tipo de grafo se está trabalhando pode ser fundamental para escolher o algoritmo certo e chegar na resposta de um problema de maneira eficiente e não errônea (SKIENA; REVILLA, 2003, p. 237).

Dentre as propriedades principais de um grafo citam-se:



  1. grafo trivial: segundo Gross e Yellen (2006, p. 3), um grafo é dito trivial (Figura 4 (a)) se contém apenas um vértice e nenhuma aresta;

  2. grafo nulo: Rabuske (1992, p. 9) afirma que para um grafo ser nulo (Figura 4 (b)) é necessário que o conjunto de arestas seja vazio;

  3. densidade: para Lipschutz e Lipson (2004, p. 204), um grafo G com m vértices e n arestas é dito denso (Figura 4 (c)) quando m é maior ou igual a n², caso contrário é chamado de esparso (Figura 4 (d));

  4. grafo bipartido: segundo Kocay e Kreher (2005, p. 47), um grafo G é dito bipartido (Figura 4 (e)) se pode ser dividido em dois conjuntos X e Y tal que cada aresta tem uma ponta em X e um fim em Y e/ou vice-versa;

  5. grafo bipartido completo: para Scheinerman (2003, p. 433), um grafo bipartido completo (Figura 4 (f)) Kn,m é um grafo cujos vértices podem ser particionados em dois conjuntos X e Y, onde |X| = n e |Y| = m, de modo que para todo vértice u pertencente a X e para todo v pertencente a Y, uv é uma aresta. Nenhuma aresta tem ambas as extremidades em X ou em Y;

  6. conexidade: de acordo com Rabuske (1992, p. 21), um grafo é dito conexo (Figura 4 (h)) se for possível visitar qualquer vértice, partindo de um outro e passando por arestas. Caso não seja possível, então é considerado desconexo (Figura 4 (g));

  7. grafo regular: Kocay e Kreher (2005, p. 9) definem um grafo pertencente a esta classe como tendo todos os vértices com o mesmo grau. Um grafo regular de grau igual a dois é mostrado na Figura 4 (i);

  8. grafo completo: para Alsuwaiyel (2003, p. 106) um grafo não-dirigido é completo se há exatamente uma aresta ligando cada par de vértices. Em outras palavras, Rabuske (1992, p. 7) afirma que um grafo completo é um grafo simples em que cada par distinto de vértices é adjacente. A Figura 4 (j) mostra dois grafos completos, sendo um formado por apenas um vértice e outro formado por quatro vértices;

  9. grafo fortemente conexo: Cormen et al. (2001, p. 1082) afirma que um grafo é fortemente conexo quando é composto por apenas uma componente fortemente conexa, ou seja, se cada dois vértices do grafo são alcançáveis entre si. Tal classificação aplica-se somente a grafos dirigidos. A Figura 4 (l) mostra um grafo fortemente conexo, enquanto que a Figura 4 (k) mostra um grafo não fortemente conexo;

  10. grafo simples ou multigrafo: de acordo com Lau (2007, p. 4), um grafo simples (Figura 4 (m)) é o que não possui laços ou arestas paralelas, caso contrário é multigrafo (Figura 4 (n) e Figura 4 (o));

  11. grafo cordal: segundo Gross e Yellen (2006, p. 437), um grafo é dito cordal (Figura 4 (p)) se possui número de vértices maior ou igual a quatro e se para cada subciclo de quatro ou mais vértices há uma corda, ou seja, uma aresta que não pertence ao ciclo e liga dois vértices não adjacentes;

  12. grafo ciclo: segundo Braun (2009, p. 20), um grafo ciclo é formado por um único vértice com um laço, ou um grafo simples e conexo, sendo que todos os vértices e arestas existentes formam um único circuito fechado. A Figura 4 (q) mostra dois exemplos de grafos ciclos, sendo um formado por apenas um vértice, enquanto que o outro é formado por cinco vértices;

  13. grafo acíclico dirigido: Goodrich e Tamassia (2004, p. 327) definem um grafo acíclico dirigido (Figura 4 (r)) como sendo um digrafo que não possui ciclos;

  14. grafo planar: Rabuske (1992, p. 129) afirma que para um grafo ser planar (Figura 4 (s)) é necessário que tenha uma forma de ser representado geometricamente num plano, de tal modo que nenhuma aresta do grafo cruze com outra, caso contrário o grafo é dito não planar (Figura 4 (t)).

Figura 4 – Exemplos de grafos




1   2   3   4   5   6   7   8   9   ...   12


©livred.info 2017
enviar mensagem

    Página principal