Re: [obm-l] subgrafo induzido

[Fernando Aires <fernandoaires@xxxxxxxxx>]

On 18/11/05, Tiago <jaspier@gmail.com> wrote:
> alguem conhece alguma boa definição para subgrafo induzido?

   Eu não sei o que você quer dizer com "boa definição". Um subgrafo
induzido de G é um subconjunto de vértices de G, com todas as arestas
de G que ligam dois vértices desse subconjunto.
   Matematicamente, podemos dizer:

   Seja G(V,E) um grafo. G'(V',E') é subgrafo induzido de G se e somente se:
V' está contido e pode ser igual a V
E' := { {x,y} | Quaisquer x,y, (x,y pertence à V' e {x,y} pertence à E) }

   Isso, claro, prá grafos não-dirigidos. Prá grafos dirigidos,
substitua o par não-ordenado {x,y}, pelo par ordenado (x,y).

   Espero que tenha ajudado. Ajudou? Ou você queria outra coisa?

Beijos,

--
-><-
Fernando Aires
fernandoaires@gmail.com
"Em tudo Amar e Servir"
-><-

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================