download,links & banners

Download, Links & Banners

ＷＷＷ上の膨大な資料は，相互参照して１個のハイパーテキストと呼ばれる巨大な有向グラフを構成している．リンク・オブジェクトはこの有向グラフの枝であり，資料ないしテキストの位置はその節点（ノード）である．この有向グラフは時々刻々，その内容とトポロジーを変化させるダイナミックなグラフ体である．

インターネットはその下部構造となる世界規模の通信システムである．インターネットはトポロジー的には双方向に連結しているから無向グラフを構成する．（ダイアルアップは単方向のように見えるが，一時的にではあっても上り・下りのチャンネルを持っているからやはり無向グラフの一部である）一般に重み付きグラフはネットワークと呼ばれる．ＷＷＷは現在，地上に存在する（世界それ自体を除いて）最大のネットワークである．

「汝の隣人を愛せ」というのは，イエスのことばであった．このことばを発したとき，イエスの念頭に「ネットワーク」という概念があったことは間違いない．イエスは理想的な王国を建設するための構想とスケジュールを提示したわけであるが，それは当然に実践可能なものでなくてはならなかった．

イエスの提示したプランは極めて限定された局所的な行動指針である．そこには，包括的なシステム設計もなければ大域的な組織構成図も存在しない．もちろん具体的な資金計画も何も無かった．ただ，手の届く範囲のあなたの「隣人を愛する」ことが可能なら，そのネットワークはやがて世界を覆うものになり得るというのが，彼の構想の根幹であり，確信であった．一見，消極的，かつ観念的な空想に聞こえるかもしれないが，これはまったく現実的な提案であり，科学的な根拠に基づくものである．

（この構想の実現を阻む障害要因はもちろん存在する．これは，イエスの構想がネットワークというグラフ理論的枠組みに依拠するという意味において，ネットワークないしコミュニケーションに関わる障害である．イエスはこれをサタンと呼んでいるのだが，グラフ理論的にサタンを再定義することができるだろうか？「邪悪なもの」をグラフ的に示すことができるだろうか？）

Download

Hamiltonian Circuit Experiment Program : Ariadne100rev1.3
download : SetupAriadne.exe for Windows95/98/NT, 153KB

The Hardest SAT Problem : hajo1-3.cnf.dimacs

download : hajo1-3.cnf.zip DIMACS CNF file format, 61KB

A very hard HCP example for SAT01 : Hajo graph sample

download : hajo1-3.sat01 SAT01 file format, 225KB

HCP→SAT01 converter for Baba Labo format : C++ source file

download : hcp2sat01.cpp plain text file, 4KB

Graph Isomorphism Experiment : Narcissus

download : Narcissus.exe for Windows 98/XP/2000, 216KB

Old version for Graph Isomorphism Experiment : Narkissos

download : SetupNarkissos.exe for Windows 98/XP/2000, 116KB

Provable Polynomial Time Algorithm for Matrix Isomorphism : ELSIE

download : ELSIE.exe for Windows 98/XP/2000, 112KB

Summary: Matrix & Graph Isomorphism (include Elsie Manual) : Article

download : MatrixIsomorphism.txt plain text format, 64KB

Full Source Files for ELSIE, ZIP format 44KB : C++ source files

download : ElsieSource.zip plain text file, 33KB

Strongly Intransitive Graphs and the Perfect Graph Conjecture : Article

download : Transitive.pdf Adobe PDF file, 283KB

On the Perfect Graph Conjecture Proof by Jeremy Spinrad : Article

download : skewout.ps Postscript format file, 324KB

16-64 vertices all strongly regular graphs (containing 12 files) : samples

download : Strongly.zip zero-one matrix form, 167KB

Bug-fix for the dimacs-standard-max-clique-solver dfmax.c : C source file

download : dfmax.zip Zip compressed file, 49KB

The NP-Completeness of the Hamiltonian Cycle Problem
in Planar Digraphs with Degree Bound Two by Jan Plesnik : Article

download : Plesnik 8.4.192-196.pdf Adobe PDF format, 390KB