[Mixi]Mixiの参加者同士が繋がっている事の証明

先日、笠原社長とどの程度で繋がっているかを示す指標「笠原数」を提唱したが、そもそもすべての参加者が笠原社長と繋がっているのか自分で疑問に思った。そこで、今日はMixiの参加者同士が繋がっている事を証明する。（条件つき）

□条件
・参加者は誰かから招待される（一番最初に招待した人を除く）
・招待された人のIDよりも、招待した人のIDの方が小さい
・一番最初に招待する人はID=1の人
（あるいは最初に招待する人はID＝１を含めて複数の人だが、必ずID＝１とマイミクである）
・マイミクが０の人はMixiの利用ができなくなる（条件１)
・Mixiにおいて、参加者Pが招待者からマイミクをはずされてない事（条件２）または参加者Pが招待者からマイミクをはずされているが、PよりもIDが小さいマイミクが存在する場合（条件３）

次のようなアルゴリズムを考える
参加者AがID=1に辿りつくアルゴリズム

STEP☆
Aのマイミクの中で一番IDが小さく且つAよりもIDが小さい人をPとする
STEP★
Pが存在する場合⇒A＝PとしてSTEP☆に戻る
Pが存在しない場合：AさんのID=1の場合：終了

証明：
マイミクの中には原則招待者がいる。つまり、Aさんのマイミクは（招待者からマイミクをはずされない限り）AさんよりIDが小さい人（Bさん）が存在する。また招待者からマイミクをはずされても条件３であれば、同様の議論ができる。今、Aさん⇒BさんのようにIDが一番小さいマイミクを辿るIDに対する関数をfとすると、ｆは単調減少である。fの下限はID=１であるから、上記アルゴリズムを行えばID=1の人に辿りつく。

これによって、ある制約下のおいて、Mixi参加者は全てID=1の参加者と繋がっている。
つまり、Mixiの参加者同士は必ず繋がっている事になる。

問題は招待者からマイミクをはずされたPさんで、マイミクのIDにおいて全てPよりも大きい場合が存在した場合である。

この場合は結論から言えば、先ほどのアルゴリズムを改良すれば、同様のアルゴリズムでID=1の人と辿れる（場合がある）。例えば、STEP★においてAさんのマイミクの中で複数マイミクを持っていて且つその中でIDが一番小さい人がPさんとなるのが妥当である。本当のSTEP★の処理はもっとややこしいが。

Mixiで孤立するグラフが現れるのはどういう場合だろうか？例を挙げてみよう。
今、AさんとBさんとCさんがいる。AさんはBさんを招待し、BさんはCさんを招待する。ここで、AさんはBさんとのマイミクを止め、且つBさんとCさんは他に招待しない等の場合が考えられる。かなりのレアケースだし、このようなことがMixiで認められているかどうかは私は知らない。

招待者からマイミクをはずされた人が存在した場合のグラフは、一般に複雑になる。場合分けも非常に複雑だろう。本当はMixiの参加者同士が必ず繋がっている事の証明を書きたかったのだが、これについてはきちんとした考察が必要だろう。今問題なのは条件２、条件３をより弱い条件にすることだ。皆様の考察求む！