可到達行列について教えてください！

質問

自分の中では、
「隣接行列に単位行列を足したものを累乗していき、いくら累乗しても変わらなくなったものが可到達行列。そうなるまでにN回累乗したとすると、行列が1の成分のところにはN回以下の移動で行けて、0のところは何回移動しても行けない」
と整理していたんですが、
授業で、テニス選手の対戦成績表が与えられて、『強さの順序を可到達行列から求めよ』という問題が出され、対応できないことがわかりました。

どう解けばいいんでしょうか。困っています！

回答No.7

hrsmmhr · ベストアンサー

すみません。#6は取り下げさせてください。

私の思っているようなすっきりとしたランク付けはできそうにないとはまだ思うし
質問者さんも同様に思われているんだと思うんですが
それでもそこを考えろというのが、課題を出された方の意図なのかもしれませんし
ここに書かれただけの話なら、私にはこれ以上のアドバイスはできません

回答No.6

hrsmmhr

お伺いしますがプール代数でどうやってランクづけするのですか？
累乗しても0,1しかないし多分何乗しても値が変わらないのではないかと思います

回答No.5

Tacosan

「検討せよ」という設問なんだから, その辺は「自分で考えろ」ってことなんじゃないですかね.

「引き分け」といってもいいし「どっちが強いかわからない」と書いてもいいし.

回答No.4

Tacosan

他の人とあまり変わらないんだけど, そもそもあなたの言う「可到達行列」をどう求めているのかが分からないんだよね. {0, 1}行列であっても, 普通の「行列の累乗」を計算したら成分に 0 でも 1 でもない数が現れるのが普通だし.

この辺はよろしくできるんだけど, その結果として「同じ人間同士の対戦なのに、どちらにも1がついたり」することは当然考えられます. 逆に, どのようなときに「そうなるのか」は考えましたか?

補足

下の方への補足にも書いた通り、ブール代数を使って計算しました。そうすると0と1だけの行列になります。

「同じ人間同士の対戦なのに、どちらにも1がついたり」することがあるのはわかるんです。力が拮抗してるってことですよね？でもそうなると強さの決め方がよくわからなくなるんです。

力が拮抗しているところは引き分けとして、無限回対戦を繰り返したとき勝ち越した相手の数で強さを決めるだけで良いんでしょうか？
例えば、Aは勝ち越し人数が一番多いけれど、Cには負けているってことを考えると、何かスッキリしません…
穿ちすぎですかね？(^_^;)

回答No.3

hrsmmhr

補足を読み誤っていたので答えなおします

対戦相手より勝手いる要素を1とし、対戦相手より負けているか同数の場合を0とする可達行列

の意味は対戦表の行列を(a_ij)と書くとき
a_ijがiがjに対する優位点と読んだとして
a_ij>a_jiなら 可達行列のij成分を１に
a_ij<=a_jiなら　可達行列のij成分を０にする

の意味と思います。

累乗の計算で１と０ばかりの行列にはならないですし
可達行列を上の方法で作れば同じ人間同士でどちらも１にはならないです

何かを勘違いされていませんでしょうか？

補足

可達行列への理解が甘いせいで誤解を与えてしまってすみません(^_^;)
普通に行列を累乗するものも可達行列というのですか？
授業でブール代数和・積を可達行列と同時に習って、可達行列を求めるときは必ずそれを使うのだと思っていました……

回答No.2

hrsmmhr

二項関係なんですから二人の間の何かを可達行列の成分に１を入れる必要がありその行列のijの成分かjiの成分かもしくは二つの比較のどれかを隣接行列に反映させるのだと思います

何がいいかはあなたの課題ですから考えてお試しください
(誰かが正解を知っているとかそういう類いの課題ではない気がします)

回答No.1

hrsmmhr

対戦成績表はどんなデータでしょうか？
隣接行列（可到達行列）への反映の仕方をどうするかはそれからでないとなんともいえない気がします

例えば1年間の対戦結果が４勝３敗のようなデータなら、
隣接関係を負けたほうから勝ったほうへの成分に１を振ることにすれば、
可到達行列の何回か繰り返した値の大きさの順番に強さの順序にすればいいように思います

でもデータの取り扱い方（解釈の仕方）はいろいろですし、これでいいのかどうかは解りかねます

補足

AさんBさんCさん…Hさんがいるとして、対戦成績表には次のように勝数のみ示されています。
　　A　B　C　D　E　F　G　H
A　 \　8　5　7　4　6　7　8
B　 2　\　1　3　3　2　3　3
C　 4　2　\　4　5　6　2　5
D　 5　7　5　\　5　7　8　2
E　 0　0　2　0　\　0　6　3
F　 0　0　3　2　1　\　0　2
G　 0　1　1　0　0　3　\　3
H　 4　8　7　7　6　7　6　\

で最後に「対戦相手より勝手いる要素を1とし、対戦相手より負けているか同数の場合を0とする可達行列(可到達行列の誤植だと思います)から検討せよ」と書いてあるのですが、
可到達行列を作ってみると、
同じ人間同士の対戦なのに、どちらにも1がついたりして、よくわからなくなってしまいました…