Changes

Para começar, iremos demonstrar como construir árvores em Maple. Dada uma árvore sem raiz, nós podemos construir essa árvore em Maple assim como faríamos com qualquer grafo. Nós também iremos dar um procedure que usa algumas capacidades embutidas alguns comandos do Maple que determinam se um grafo específico é uma árvore.

Antes de entrar na implementação, há dois pontos importantes que devem ser mencionados. Primeiro, notamos que o Maple difere da terminologia de texto, no senso que o Maple refere-se a ciclos simples ciclos, quando enquanto o texto se refere a circuitos simples circuitos. O segundo ponto que vale mencionar é de que uma árvore sem raiz é um grafo simples que não tem ciclos simples. Estruturalmente falando, uma árvore com raiz é exatamente a mesma coisa que uma árvore sem raiz, com a propriedade adicional de que há um vértice específico chamado de raiz, que é visto como o ponto inicial de uma árvore. Em termos de implementação Maple, representamos árvores sem raiz como grafos, e criamos árvores sem raiz a partir de árvores sem raiz utilizando comandos Maple como spantree, que serão abordados posteriormente, especificando um nó desejado uma raiz desejada para uma árvore sem nó.

Outro tipo importante de árvore é a árvore ordenada, que é uma árvore com raiz onde os filhos de um vértice ordenados de alguma maneira como 1stprimeiro, 2ndsegundo,...,mn-th ésimo filhos se houverem m n filhos de um dado vértice. Nós iremos fazer Faremos uso do peso dos vértices para determinar a ordem dos filhos de um vértice específico. Esse tipo de árvore irá aparecer posteriormente, mas é importante distinguir árvores sem raiz, com raiz e desordenadas, e árvores com raiz e ordenadas.

Como primeiro exemplo, iremos discutir árvores sem raiz. Criamos uma árvore exatamente da mesma maneira que criamos um grafo, usando o pacote networks do Maple. Como nosso primeiro exemplo, iremos criar uma árvore simples em com 4 vértices.

1.O grafo é conectadoconexo.

Usando Maple, essas propriedades são facilmente verificadas. Em particular, podemos determinar se um grafo é conectado em Maple usando o comandoscomponentscomando components, que retorna uma coleção de conjuntos de vértices, onde cada conjunto nessa coleção contém os vértices de um componente conexo do grafo. Podemos determinar se um grafo é simples usando o comando Maple gsimp, que retorna a árvore simples por baixo de um multigrafo(ou pseudografo), e então comparando o número de arestas da árvore por baixo do grafo original. Isso nos leva até o procedure IsSimple.

Note que não devemos simplificar G por si só, pois tal simplificação é um processo irreversível.