El paquete graphs proporciona estructuras de datos de grafos y dígrafos para Maxima. Los grafos y dígrafos son simples (no tienen aristas múltiples ni bucles), aunque los dígrafos pueden tener una arista dirigida de u a v y una arista dirigida de v a u.
Para trabajar con graphs es necesario cargar el paquete graphs. A continuación, utilizamos el comando
create_graph (v_list, e_list): Creates a new graph on the set of vertices v_list and with edges e_list.
y lo mostramos con
draw_graph (graph, option1, …, optionk): Draws the graph using the draw package.
Proposición: Sea \( n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r} \) la factorización en números primos de un entero positivo \( n \). Entonces, el número de aristas del grafo de los divisores de \(n\) viene dado por
\[
E(n)=\tau(n)\sum_{i=1}^r \frac{a_i}{a_i+1},
\]
donde
\[
\tau(n)=\prod_{i=1}^r (a_i+1)
\]
es el número de divisores positivos de \(n\).
Ejercicio: Construye una función que nos devuelva el número de aristas del grafo de los divisores de \(n\)
(%i2)
num_aristas_divisores(n):=block( [factores,d_n,suma,i,e_i], /* 1. Obtenemos la factorización: [[p1, e1], [p2, e2], …] */ factores:ifactors(n), /* 2. Calculamos el número total de divisores d(n) */ d_n:length(divisors(n)), /* 3. Aplicamos la fórmula combinatoria */ suma:0, for i:1 thru length(factores) do ( e_i:factores[i][2], suma:suma+(e_i·d_n/(e_i+1)) ), return(suma) )$ num_aristas_divisores(24);
\[\operatorname{ }10\]
Ejercicio: Dibuja el grafo de coprimalidad de $S = \{12,2,34,35,4,41,29\}$
(%i1)
load(graphs)$
Dibujemos el grafo de coprimalidad de S = {12,2,34,35,4,41,29}
Ejercicio: Utilizando la definición, construye un algoritmo que nos determine el número de aristas de un grafo de coprimalidad de un conjunto de números naturales $S$ y aplícalo para calcular las aristas de $\{12,2,34,35,4,41,29\}$
Veamos cuántas serían las aristas del grafo de coprimalidad de S = {12,2,34,35,4,41,29} Primero definimos una función para el mcd:
(%i1)
mcd(n,m):=if m=0 then abs(n) else mcd(m,mod(n,m))$
Ahora definimos el algoritmo que nos proporcionará el número de aristas:
(%i2)
num_aristas(v):=block([s], s:0, for i:1 thru length(v)−1 do ( for j :(i+1) thru length(v) do ( if (mcd(v[i],v[j])=1) then s:s+1 ) ), return(s) )$
(%i4)
V:[12,2,34,35,4,41,29]$ num_aristas(V);
\[\operatorname{ }15\]
Ejercicio: Dibuja el grafo de factorización de $S = \{4,6,9,10,15,21,32\}$
(%i1)
load(graphs)$
Dibujemos el grafo de factorización de S = {4,6,9,10,15,21,32}
Ejercicio: Modifica el algoritmo anterior para ofrecer un algoritmo que nos determine el número de aristas de un grafo de factorización de un conjunto de números naturales $S$
