grafos.qmd

---
title: "Grafos em GAP"
number-sections: true
lang: pt-BR
---

Neste projeto iremos trabalhar com grafos. 

## O grafo de Petersen


:::{.subexample}
O [grafo de Petersen](http://pt.wikipedia.org/wiki/Grafo_de_Petersen) é um grafo com muitas  propriedades interessantes. 


![Petersen graph](pics/Petersen1_tiny.svg)

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. 

```matlab
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] ) = []`.

```matlab
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

<!--http://www.gap-system.org/Manuals/pkg/grape/htm/CHAP002.htm#SECT002</Link><LinkText><Code>EdgeOrbitsGraph( G, ares, n )</Code></LinkText></URL>. 
O argumento <Arg>G</Arg> é um grupo que age sobre o conjunto de vértices, 
<Arg>ares</Arg> é um conjunto de arestas, e <Arg>n</Arg> é o número de 
vértices. O grafo construído pela função vai ter <Code>[1..n]</Code>
como conjunto de vértices, e o <M>G</M>-fecho de <Arg>ares</Arg> como 
conjunto de arestas. Nos nossos exemplos nós vamos trabalhar com <M>G=1</M>, 
e neste caso o conjunto de arestas vai ser <Arg>ares</Arg>.

-->
```matlab
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> 
```

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

## Tarefa


:::{.subproblem}
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$.


1. Escreva uma função `non_commuting_graph( G )` que devolve o grafo não comutante para um grupo finito $G$.
2. 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](http://www.sciencedirect.com/science/article/pii/S002186930600113X#).
:::