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$
Ecuación de congruencias Recordemos, para resolver la ecuación \(aX\equiv b {\pmod {n}}\), \((aX \equiv b (n))\), cuando \(\mathbf{mcd}(a,n)=1\), utilizamos bien solución de Bézout, bien la función \(\varphi\) de Euler. Ejemplo: Resolver la…
Restos potenciales Veamos el siguiente ejercicio: Ejemplo: Dado \(n=71\cdots 71\), donde la pareja 71 se repite 10 veces, ¿cuál es su resto al dividirlo por 17? Solución: El número en cuestión es…
El pasado día vimos que el algoritmo de Euclides se fundamenta en el teorema: Teorema: Si \(a\) y \(b\) son números enteros, \[\mathbf{mcd}(a,b)=\mathbf{mcd}(b,r),\] donde \(r\) es el resto del algoritmo de la…
1. El algoritmo de la división Dados dos números enteros \(a\) y \(b\), con \(a\) no nulo, la división euclídea asocia un cociente \(q\in\mathbb{Z}\) y un resto \(r\in\mathbb{Z}\), únicos, que verifican: \[b=q\,a+r,\quad…
