[過去ﾛｸﾞ] 分からない問題はここに書いてね426 [無断転載禁止]©2ch.net (1002ﾚｽ)

分からない問題はここに書いてね426 [無断転載禁止]©2ch.net http://rio2016.5ch.net/test/read.cgi/math/1493648300/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

790: １３２人目の素数さん [] 2017/05/24(水) 19:57:43.86 ID:DFToadP5 A = (a_i_j) を n 次正方行列とする。 σ、 τ ∈ S_n とする。 n 次正方行列 (a_σ(i)_τ(j)) が上三角行列となるような σ、 τ ∈ S_n が存在するための 必要十分条件をグラフ理論的に述べよ。 この問題の解答をお願いします。 http://rio2016.5ch.net/test/read.cgi/math/1493648300/790

821: １３２人目の素数さん [] 2017/05/25(木) 18:19:43.37 ID:/hDMwyS6 >>790 Philip N. Klein "Coding the matrix" p.207 Problem 4.6.12: (For the student with knowlege of graph algorithms) Design an algorithm that, for a given matrix, finds a list of a row-labels and a list of column-labels with respect to which the matrix is triangular (or report that no such lists exist). ↑の問題を解きたくて質問しました。 ちなみに、↑の本での実行列の定義は、 U, V を有限集合とするとき、 U × V から R への写像のことを実行列という です。 U が行ラベルで V が列ラベルです。 で、答えが分かりました。 O(n!) のアルゴリズムは分かりました。 U = {u_1, u_2, …, u_n} V = {v_1, v_2, …, v_n} 行ラベルの順序を固定する。 [u_1, u_2, …, u_n] 列ラベルの n! 個ある順列 [v_τ(1), v_τ(2), …, v_τ(n)] のそれぞれに対して、 以下の画像の問題の答えとなるアルゴリズムを修正（セルフループの除去）して使えばよい。 http://imgur.com/TpGdpyd.jpg http://rio2016.5ch.net/test/read.cgi/math/1493648300/821

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.049s