log10(得点)の表．下記algorithmたちのmaxをとった

グラフと文字列を変換する関数$\mathtt{graph\_to\_str}, \mathtt{str\_to\_graph}$ を用意しておく．

algorithm1 - 次数多い頂点を$i$個用意

$N=100$とする．

構成

• $i\leq N/2$のとき
  • 頂点集合を$S=[0,i), T=[i,N)$と分ける．
  • $\forall x,y\in S$で辺$(x,y)$，$\forall x\in S, \forall y\in T$で辺$(x,y)$を張る．
  • $\forall x\in S$で$\mathrm{deg}(x)=N-1$，$\forall x\in T$で$\mathrm{deg}(x)=|S|=i$となる．
• $i> N/2$のとき
  • 頂点集合を$S=[0,i), T=[i,N)$と分ける．
  • $\forall x,y\in S$で辺$(x,y)$を張る．
  • $\forall x\in S$で$\mathrm{deg}(x)=|S|-1=i-1$，$\forall x\in T$で$\mathrm{deg}(x)=0$となる．

判定

$\mathbf{d}=(\mathrm{deg}(v_1),\dots,\mathrm{deg}(v_N))$とし$\mathbf{d}$を降順ソートする．

$i^*=\argmax\{d_i-d_{i+1}\}$を推定値とする．

✅ $N=100$である必要はない（特に小さい$\epsilon$）

→最適な$N\in [m,100]$を求めたい

$m=10,30,50,70,90,100$で各$N\in[m,100]$を試し 最大値をとる$N^*$を見つけ，他の$m$は線形補完で$N$を求める．

algorithm2 - ラベルなしグラフを列挙

頂点数$N$のラベルなしグラフの数を$g(N)$とすると，

$g(1)=1$ ([o]より)

$g(2)=2$ ([o o], [o-o]より)

$g(3)=4$ ([o o o], [o-o o], [o-o-o], [△]より)