18 Grafos em GAP

Neste projeto iremos trabalhar com grafos.

18.1 O grafo de Petersen

O grafo de Petersen é um grafo com muitas propriedades interessantes.

O grafo de Petersen pode ser construído como o grafo com o conjunto de vértices \[ V=\{\{x,y\}\mid 1\leq x<y\leq 5\} \] onde dois vértices \(\{x,y\}\) e \(\{u,v\}\) são conectados se e só se \(\{x,y\}\cap \{u,v\}=\emptyset\).

Vamos construir o grafo de Petersen em GAP. Primeiro construímos o conjunto de vértices.

gap> ver := Combinations( [1..5], 2 );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], 
  [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ]

O conjunto de vértices de um grafo em GAP tem de ser uma lista [1..k]. No nosso caso, o conjunto de vértices será [1..10]. Dois vértices i e j serão conectados se Intersection( ver[i], ver[j] ) = [].

gap> ares := Filtered( Tuples( [1..10], 2 ), x->Intersection( ver[x[1]], ver[x[2]] ) = [] );
[ [ 1, 8 ], [ 1, 9 ], [ 1, 10 ], [ 2, 6 ], [ 2, 7 ], [ 2, 10 ], [ 3, 5 ], [ 3, 7 ], [ 3, 9 ], [ 4, 5 ], [ 4, 6 ], [ 4, 8 ], [ 5, 3 ], 
  [ 5, 4 ], [ 5, 10 ], [ 6, 2 ], [ 6, 4 ], [ 6, 9 ], [ 7, 2 ], [ 7, 3 ], [ 7, 8 ], [ 8, 1 ], [ 8, 4 ], [ 8, 7 ], [ 9, 1 ], [ 9, 3 ], [ 9, 6 ], [ 10, 1 ], [ 10, 2 ], [ 10, 5 ] ]

Para construir o grafo de Petersen, nós precisamos do pacote GRAPE de GAP. O grafo vai ser construído pela função

gap> LoadPackage( "grape" );
true
gap> G := EdgeOrbitsGraph( Group(()), ares, 10 );
rec( adjacencies := [ [ 8, 9, 10 ], [ 6, 7, 10 ], [ 5, 7, 9 ], [ 5, 6, 8 ], 
      [ 3, 4, 10 ], [ 2, 4, 9 ], [ 2, 3, 8 ], [ 1, 4, 7 ], [ 1, 3, 6 ], 
      [ 1, 2, 5 ] ], group := Group(()), isGraph := true, order := 10, 
  representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ], 
  schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 ] )
gap>

gap> IsConnectedGraph( G );
true
gap> Diameter( G );
2
gap> Girth( G );
5
gap> IsConnectedGraph( G );
true

18.2 Tarefa

Se \(G\) é um grupo, então definimos o grafo não comutante de \(G\) como sendo o grafo cujo conjunto de vértices é \(G\setminus Z(G)\) e dois vertices \(g,\ h\) são conectados se e só se \(xy\neq yx\); ou seja, \([x,y]=x^{-1}y^{-1}xy\neq 1\).

Escreva uma função non_commuting_graph( G ) que devolve o grafo não comutante para um grupo finito \(G\).
Use a função non_commuting_graph( G ) para investigar grafos associados a grupos finitos de ordem pequena (use a função SmallGroup). Verifique se os grafos são conexos, determine o diâmetro.

Algumas propriedades interessentas de grafos não comutantes são demonstradas neste artigo.