¿Cómo puedo saber cuántos árboles no isomórficos sin raíz con 6 aristas existen sin dibujarlos todos?

Question

Normalmente mi profesor pide que los dibujemos todos, pero me gustaría ahorrar algo de tiempo para confirmar cuántos necesito.

Answer 1

Puede utilizar geng que está empaquetado con nauty .

geng 7 6:6 -c -u

Los árboles con 6 aristas tienen 7 vértices, y cualquier grafo conectado de 7 vértices con 6 aristas debe ser un árbol. Así que llamamos a geng para generar el gráfico conectado de 7 vértices ( -c ) con 6 aristas. El -u medios para contarlos.

>A geng -cd1D6 n=7 e=6
>Z 11 graphs generated in 0.00 sec

Si quieres los gráficos en sí, podemos redirigir la salida a un archivo

geng 7 6:6 -c > temp.txt

entonces usa showg para imprimir las listas de adyacencia:

showg temp.txt

Este es el resultado:

Graph 1, order 7.
  0 : 6;
  1 : 6;
  2 : 6;
  3 : 6;
  4 : 6;
  5 : 6;
  6 : 0 1 2 3 4 5;

Graph 2, order 7.
  0 : 5 6;
  1 : 6;
  2 : 6;
  3 : 6;
  4 : 6;
  5 : 0;
  6 : 0 1 2 3 4;

Graph 3, order 7.
  0 : 5 6;
  1 : 5;
  2 : 6;
  3 : 6;
  4 : 6;
  5 : 0 1;
  6 : 0 2 3 4;

Graph 4, order 7.
  0 : 5;
  1 : 5;
  2 : 6;
  3 : 6;
  4 : 6;
  5 : 0 1 6;
  6 : 2 3 4 5;

Graph 5, order 7.
  0 : 5 6;
  1 : 5;
  2 : 5;
  3 : 6;
  4 : 6;
  5 : 0 1 2;
  6 : 0 3 4;

Graph 6, order 7.
  0 : 4 6;
  1 : 5 6;
  2 : 6;
  3 : 6;
  4 : 0;
  5 : 1;
  6 : 0 1 2 3;

Graph 7, order 7.
  0 : 4 5;
  1 : 5 6;
  2 : 6;
  3 : 6;
  4 : 0;
  5 : 0 1;
  6 : 1 2 3;

Graph 8, order 7.
  0 : 4 6;
  1 : 5 6;
  2 : 5;
  3 : 6;
  4 : 0;
  5 : 1 2;
  6 : 0 1 3;

Graph 9, order 7.
  0 : 4 6;
  1 : 5;
  2 : 5;
  3 : 6;
  4 : 0;
  5 : 1 2 6;
  6 : 0 3 5;

Graph 10, order 7.
  0 : 3 6;
  1 : 4 6;
  2 : 5 6;
  3 : 0;
  4 : 1;
  5 : 2;
  6 : 0 1 2;

Graph 11, order 7.
  0 : 3 5;
  1 : 4 6;
  2 : 5 6;
  3 : 0;
  4 : 1;
  5 : 0 2;
  6 : 1 2;