Graphs para Matemáticas Discretas- Algunos comandos, ejemplos y ejercicios.

Resumen- Expondremos aquí algunos resultados obtenidos con el paquete de Maxima graphs, utilizando algunos conceptos extraídos en [1] y resolveremos algunas cuestiones planteadas en [2], texto basado en los contenidos referidos a la teoría de grafos incluidos en los actuales planes de estudio de la asignatura Matemáticas Discretas, los cuales requieren el concepto de grafo orientado, camino hamiltoniano, estudio de grafos planos por el Teorema de Kuratowski, etc.

Y daremos un ejemplo de construcción de grafos con los de tipo K_3,3, K_4,4 y K₅, realizando además un estudio completo de ellos. Para mayor sencillez trabajaremos con la interfaz wxMaxima para Windows.

Lo primero que debemos de hacer, al igual que con otros paquetes de Maxima es cargarlo. Para ello introducimos el siguiente comando:

load(graphs)$

Algunos comandos útiles de este paquete, que será lo que utilizaremos aquí viene dados en [1] y por el menú de ayuda de Maxima ( F1). Para tratar el tema de grafos tal como plantea la asignatura son más que suficientes. Por otra parte, el paquete tiene algunas herramientas prediseñadas que nos permiten representar algunos grafos característicos. Algunas son:

1. grid_graph(n,m) Obtenemos un grafo en forma de rejilla de dimensiones nxm.
2. complete_graph (n) Devuelve el grafo completo de n vértices.
3. cycle_digraph (n) Devuelve el ciclo dirigido de n vértices.
4. cycle_graph (n) Devuelve el ciclo de n vértices.
5. cuboctahedron_graph () Devuelve el grafo cubooctaédrico.
6. cube_graph (n) . Devuelve el cubo de n dimensiones.
7. dodecahedron_graph () Devuelve el grafo del dodecaedro.
8. empty_graph (n) Devuelve un grafo sin vértices.
9. wheel_graph (n) Devuelve el grafo de rueda de n+1 vértices.

Insistir en el que hay muchas más herramientas en el menú de ayuda de Maxima y wxMaxima ( F1). Ahora resolveremos dos problemas. 

1º- Representación de los grafos k₅ y k₇. Vemos que podemos obtener la representación gráfica de estos grafos insertando, una vez cargado los paquetes, los siguientes comandos:

l:complete_graph(5);

f:complete_graph(7) ;

draw_graph(l,show_id=false)$

draw_graph(f,show_id=false)$

en una o dos celdas de entrada (F5). Obtenemos las imágenes:

2º- Estudio de K_3,3, K_4,4 y K₅ usando una descripción gráfica, la matriz de adyacencia_. ¿Son k_3,3 y k₅ grafos planos? Teniendo en cuenta las conclusiones anteriores, ¿Es k_4,4 un grafo plano?

En la siguiente serie de comandos obtenemos el grafo k_3,3; en efecto, siguiendo el modelo que aparece en [2] ( página, 176) hemos dibujado un grafo en forma de rejilla de 3,2 y hemos construido el que aparece en la imagen; para ello hemos usado los comandos add_edges() y remove_edges(). 

En el estudio del grafo, que viene dado por los comandos print_graphs, adjancy_matrix() e is_conneceted() además de is_planar(). Siendo estos dos últimos productores de valores booleanos ( false y true). Así pues, vemos que, en el test, k3,3 es conexo pero no es planar. Lo mismo pasa con K₅. 

Con k_4,4 ocurre lo mismo que en los casos anteriores. En tal caso, podemos ver que, si le aplicamos un estudio de una subdisivisión elemental ( [2],177) tenemos que existe algunas isomorfas a k_3,3. Por el Teorema de Kuratowski, esto implica que no es planar. En la siguiente serie de instrucciones tenemos algunas de ellas. 

Bibliografia

[1] Primeros pasos en Maxima, Riotorto, Mario Rodriguez.

[2]Elementos de Matemáticas Discretas, V.V.A.A. Ed. Sanz y Torres. ISBN:84-88667-35-3