グラフの本型及び双対埋め込みとその応用に関する研究

点击翻译按钮获取中文摘要

1.n-次元ハイパーキューブのキューナンバー(キューレイアウトに必要なキューの最小数)の上界として,Heath and Rosenbergにより(nを2以上として)n-1が与えられていたが,nが5以上のときにはn-2に改善できることを証明した.2.不完全ハイパーキューブの本型埋め込みでは,Fang and Laiにより,頂点数が2_n+Z_<n-1>の不完全ハイパーキューブがn-1ページに埋め込み可能であることが示されていたが,本研究では,頂点数が,2_n+2_<n-1>+2_<n-2>の不完全ハイパーキューブがn-1ページで埋め込み可能であることを示し,Fang and Laiの結果を改善した.また,nが大きいときには,さらに改善できることを示した.3.サイズmのグラフのスタックナンバー(スタックレイアウトに必要なスタックの最小数),キューナンバーの上界はそれぞれ,72√<m>, e√<m> (eは自然対数の底)であることが,MalitzとDujmovic and Woodにより示されていたが,スタックとキューを同時に用いた場合には,√<m>個のスタックと√<m>-1個のキューでレイアウトできることを示し,どちらか一方の場合より総数として改善できることを示した.また,スタックとキューの両方を同時に使った場合のn-次元根美薄キューブのレイアウトでは,スタックとキューの総数が,nが5以下のときには高々n-1,nが6以上のときには高々(3n-7)/2であることを示した.