半順序構造

半順序構造とは、ある集合（無限集合か有限集合かは問わない）において、任意の二つの要素を取り上げた場合において、順序関係が定まらない構造をいう。

概要

一般の半順序構造としてはいろいろあるが、順序構造としては「いずれの要素に対しても、高順序である」という要素と、「いずれの要素に対しても、低順序である」という要素をつけ加えると、数学でいう束（そく。英語ではラティスという）構造と同相となる。このとき、「三すくみ」のような循環構造を持たないことを前提とするため、「ネットワーク構造」という呼称もある。社会性の野生動物においては、「群れ」「縄張り」として認識されているようである。
PERT/CPM においては、ネットワーク構造は基本とされている。
ただし、鶏を一つのケージ（檻。シャックともいう）に閉じこめると、縄張りが一つしか成立しないため、単順序構造しか理解できなくなるようである。

データ構造として

半順序構造は、数学的には「束（そく）」と捉えられるが、抽象度が高く数学的な扱いがしやすい反面、実生活に応用しづらいという側面がある。
PERT/CPM で用いるネットワーク図（PERT図）は建築や医療など多くの分野で活用されおり、全体の見通しもよくなるという利点があるものの、データ化してコンピュータで扱おうとすると、見通しのよさが損なわれやすく、ときに無限ループをひき起こして痛い目に遭う。
この点を解消するために、リスト構造に制約をかけて半順序構造を持つネットワーク的なデータ構造考えると都合がよい。すなわち、

• 節点（ノード）と矢線（アロー）からなる。
• 基点と終点というノードが、それぞれただ一つある。
• 巡回路がない。

という制約をかけたデータ構造を考える。
こう書くと抽象的すぎて想像が難しそうだが、「巡回路のない（すべて一方通行の）有料自動車道」そ考え、「すべての入口」の上に分岐点（ブランチ）と、「すべての出口」の先に合流点（ジャンクション）とを考えて抽象化したものを考えればいくらかわかりやすい。このとき、分岐点と合流点を一緒にするとややこしいことになる（記述が頭の中で追いきれなくなる）ために、間に仮想の節点を置く。これはPERT図におけるダミーノードに相当する。
ただし、大規模なソフトウェアの開発プロジェクトなどでは、途中に待ち合わせ期日を設けて結合試験を行なったりもするので、「この節点に到達するのは何月何日。結合試験が無事に終了するまでは、この先に進んではならない」といった目印をノードに立てる。これを「フラッグ・デイ」という。これがあるので銀行のオンラインシステムの統合とかではしばしば混乱が起きる。そのためこうしたプロジェクト管理自体もシステム化したいところだが、「ほどよい抽象化」のためのモデルが見当たらなかったため、三十年くらいは停滞している。