『経路数問題』

『ナイトツアー Part2』の解答に必要な式をみんなで考えたほうが早いと思い まして、問題にしました。

【問題１】

G(V、E)をm頂点の無向グラフとします。
グラフG(V、E)による隣接行列Aが与えられます。
一度ずつしか頂点を通らず頂点iから頂点ｊまでのnの長さの経路数をp_ij(n)とします。

また一度ずつしか頂点を通らず頂点iを通るnの長さの閉路数をl_i(n)とします。

P_nとL_nを
{p_ij(n)}と対角行列{l₁(n),l₂(n),...,l_m(n)}と定義します。

n=1,2,3,4,5,6の時は一つの関係として次の式が成立します。

L₁=I*A,
L_n=I*(P_n-1P₁)

P₁=A-L₁

P₂=P₁²-L₂

P₃=P₂ P₁-L₃-P₁*L₂+P₁

P₄=P₃ P₁-L₄-P₁L₃+3P₁*P₂-P₂ L₂+P₂

P₅=P₄ P₁-L₅-P₁L₄+3P₁*P₃+3P₁*P₂⁽²⁾+3P₁(P₁*P₂)-3L₃+P₃-P₃*L₂-P₂ L₃-4P₁ P₂

P₆=P₅P₁-L₆-P₁L₅+3P₁*P₄+6P₁*P₂*P₃-8P₁*(P₁(P₁*P₂))-8P₁*((P₁*P₂)P₁)) -P₂L₄+P₂⁽³⁾-4P₂⁽²⁾+3P₂+3P₁(P₁*P₃)+3P₁(P₁*P₂⁽²⁾)-3L₄+21P₁*P₂-P₄ L₂-P₃ L₃ +3P₂(P₁*P₂)-3P₁(P₁*P₂)+3L₃-6I*(P₁(P₂⁽²⁾))-4P₁ L₃+P₄

ただし、Iは単位行列で、
*の演算子は、A={a_ij},B＝{b_ij}が与えられたときに、
A*B＝{a_ijb_ij}と定義します。

行列Xの(k)乗、X^(k)＝X*X*...*Xが定義され, ここで*はk-１回です。
また行列Xのk乗、X^k＝X・X・...・Xが定義され, ここで・はk-１回です。

【問題1.1】

P₇をP_r，L_s； r≦6，s≦7　で表してください。

【問題1.2】

P₈をP_r，L_s； r≦7，s≦8　で表してください。

【問題1.3】

P₉をP_r，L_s； r≦8，s≦9　で表してください。

【問題1.4】

P₁₀をP_r，L_s； r≦9，s≦10　で表してください。

【問題1.5】

P₁₁をP_r，L_s； r≦10，s≦11　で表してください。

【問題２】

G(V、E)をm頂点の有向グラフとします。
グラフG(V、E)による隣接行列Aが与えられます。

一度ずつしか頂点を通らず頂点iから頂点ｊまでのnの長さの経路数をp_ij(n)とします。
また一度ずつしか頂点を通らず頂点iを通るnの長さの閉路数をL_i(n)とします。

P_nとL_nを
{p_ij(n)}と対角行列{l₁(n),l₂(n),...,l_m(n)}と定義します。

n=1,2,3,4の時は一つの関係として次の式が成立します。

L₁=I*A,
L_n=I*(P_n-1P₁)

P₁=A-L₁

P₂=P₁²-L₂

P₃=P₂ P₁-L₃-P₁*L₂+P₁*P₁^T

P₄=P₃ P₁-L₄-P₁L₃+3P₁*P₁^T*P₂-P₂ L₂+P₂*P₂^T

ただし、X^TはXの転置行列とします。

【問題2.1】

P₅をP_r，L_s； r≦4，s≦5　で表してください。

【問題2.2】

P₆をP_r，L_s； r≦5，s≦6　で表してください。

【問題2.3】

P₇をP_r，L_s； r≦6，s≦7　で表してください。

【問題2.4】

P₈をP_r，L_s； r≦7，s≦8　で表してください。

【問題2.5】

P₉をP_r，L_s； r≦8，s≦9　で表してください。

【問題2.6】

P₁₀をP_r，L_s； r≦9，s≦10　で表してください。

【問題2.7】

P₁₁をP_r，L_s； r≦10，s≦11　で表してください。

【おまけ１】

無向グラフG(V,E)のP_nをP_r，L_s； r≦n-1，s≦n　で表してください。

【おまけ２】

有向グラフG(V，E)のP_nをP_r，L_s； r≦n-1，s≦n　で表してください。

◆解答用紙はこちらです。

　◆個数を数える問題へもどる

　数学の部屋へもどる