Discretas-Grafo de un cuboctaedro

La teoría de grafos es visualmente muy atractiva. En este caso, me plantee la representación de un grafo que representase un cuboctaedro, un sólido de arquímedes muy interesante.

(http://es.wikipedia.org/wiki/S%C3%B3lidos_arquimedianos)

Para mi sorpresa, existe un comando en WxMaxima, paquete graphs, que permite copnstruir un grafo isomorfo a él. Yo he hecho dos, como ejemplo de isomorfismo entre grafos ( dos grafos son isomorfos sí y solo sí existe una aplicación biyectiva  que transforma todo vértice de un grafo en uno del otro y toda arista está en el otro). Introduciendo los siguientes comandos, obtenemos el resultado:

Discreta- Grafo de un icosadodecaedro

Uno de los sólidos arquimedianos más famosos es el icosadodecaedro. Se basa en un poliedro cuasiregular formado por doce caras pentagonales y veinte caras triangulares, como aparece en la imagen.

Icosadodecaedro, imagen tomada de http://commons.wikimedia.org/wiki/File:Icosidodecahedron.jpg?uselang=es 

Podemos realizar una construcción muy hermosa con WxMaxima utilizando el paquete graphs; lo que hacemos es construir el grafo isomorfo a este cuerpo, produciendo un grafo de 30 vértices y 60 aristas. Para ello introducimos los siguientes comandos.

Para más información, puede verse la siguiente entrada de Wikipedia:

http://es.wikipedia.org/wiki/S%C3%B3lido_de_Arqu%C3%ADmedes

Discreta-Uso de Scilab para el estudio de matrices de adyacencia

Se presenta aquí un ejemplo de como estudiar la posibilidad de existencia de caminos en un grafo haciendo uso de sus matrices de adyacencia. Al elevar a n la matriz de adyacencia buscamos caminos de longitud n en el grafo. La suma de estas matrices nos devuelve los caminos posibles en el grafo de un vértice otro. Veremos un ejemplo de esta posible representación de grafos usando matrices empleando el podertde computo de Scilab.

Desarrollamos el ejercicio usando los siguientes comandos desde SciNotes, un editor con las funciones  propias de Scilab que nos permite guardar el trabajo hecho con extesiones .sci o .sce.

Con M la matriz de adyacencia del grafo definido.Y como resultados obtenemos en la consola de Scilab:

Ejecución de inicio:
  cargando entorno inicial

-->M=[0,1,1,0,0;
-->zeros(1,2),1,zeros(1,2);
-->zeros(2,3),eye(2,2);
-->1,0,1,zeros(1,2)]
 M  =

    0.    1.    1.    0.    0. 
    0.    0.    1.    0.    0. 
    0.    0.    0.    1.    0. 
    0.    0.    0.    0.    1. 
    1.    0.    1.    0.    0. 

-->M^2
 ans  =

    0.    0.    1.    1.    0. 
    0.    0.    0.    1.    0. 
    0.    0.    0.    0.    1. 
    1.    0.    1.    0.    0. 
    0.    1.    1.    1.    0. 

-->M^3
 ans  =

    0.    0.    0.    1.    1. 
    0.    0.    0.    0.    1. 
    1.    0.    1.    0.    0. 
    0.    1.    1.    1.    0. 
    0.    0.    1.    1.    1. 

-->M^4
 ans  =

    1.    0.    1.    0.    1. 
    1.    0.    1.    0.    0. 
    0.    1.    1.    1.    0. 
    0.    0.    1.    1.    1. 
    1.    0.    1.    1.    1. 

-->L=M+M^2+M^3+M^4
 L  =

    1.    1.    3.    2.    2. 
    1.    0.    2.    1.    1. 
    1.    1.    2.    2.    1. 
    1.    1.    3.    2.    2. 
    2.    1.    4.    3.    2.  

Toda la teoría empleada proviene del texto Elementos de Matemática Discretas, V.V.A.A, Editorial Sanz y Torres.



Graph-Cubo en 4 dimensiones

Se presenta aquí un grafo que representa un hipercubo (un cubo en cutro dimensiones) usando, en el paquete graph, el comando cube_graph(4).

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

 

Grafos ( Paquete graphs)-

Grafo del dodecaedro, realizado con el paquete graphs de Maxima y ejecutado desde wxMaxima y el camino hamiltoniano en azul. Este grafo sirve para estudiar  una posible solución en el denominado juego de Hamilton,del cual podemos saber en: 

http://es.wikipedia.org/wiki/Camino_hamiltoniano