証明の概要とは何？わかりやすく解説 Weblio辞書

証明の概要

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)

「マトロイド」の記事における「証明の概要」の解説

c ( G ) ≥ q ( E , F ) c ( O P T ) {\displaystyle c(G)\geq q(E,F)c(OPT)} の証明の概要を述べる。 G {\displaystyle G} を最良選択貪欲法で得られる解、 O P T {\displaystyle OPT} を最適解とする。 E = { e 1 , … , e n } {\displaystyle E=\{e_{1},\ldots ,e_{n}\}} は、 c ( e 1 ) ≥ c ( e 2 ) ≥ ⋯ ≥ c ( e n ) {\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})} となるようにソート済みであるとし、 E j = { e 1 , … , e j } {\displaystyle E_{j}=\{e_{1},\ldots ,e_{j}\}} とする。また、 d j = { c ( e n ) , if j = n c ( e j ) − c ( e j + 1 ) , otherwise {\displaystyle d_{j}={\begin{cases}c(e_{n}),&{\mbox{if }}j=n\\c(e_{j})-c(e_{j+1}),&{\mbox{otherwise}}\end{cases}}} とし、任意の X ⊆ 2 E {\displaystyle X\subseteq 2^{E}} に対して、 X j = X ∩ E j {\displaystyle X_{j}=X\cap E_{j}} と置く。このとき、次の事実が成り立つ。任意の X ⊆ 2 E {\displaystyle X\subseteq 2^{E}} において、 c ( X ) = ∑ j = 1 n | X j | d j {\displaystyle c(X)=\sum _{j=1}^{n}|X_{j}|d_{j}} 任意の 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} において、 ρ ( E j ) ≤ | G j | {\displaystyle \rho (E_{j})\leq |G_{j}|} 任意の X ⊆ E {\displaystyle X\subseteq E} において、 r ( X ) q ( E , F ) ≤ ρ ( X ) {\displaystyle r(X)q(E,F)\leq \rho (X)} 任意の 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} において、 | O P T j | ≤ r ( E j ) {\displaystyle |OPT_{j}|\leq r(E_{j})} 以上のことから、 c ( G ) = ∑ j = 1 n | G j | d j ≥ ∑ j = 1 n ρ ( E j ) d j ≥ q ( E , F ) ∑ j = 1 n r ( E j ) d j ≥ q ( E , F ) ∑ j = 1 n | O P T j | d j = q ( E , F ) c ( O P T ) {\displaystyle c(G)=\sum _{j=1}^{n}|G_{j}|d_{j}\geq \sum _{j=1}^{n}\rho (E_{j})d_{j}\geq q(E,F)\sum _{j=1}^{n}r(E_{j})d_{j}\geq q(E,F)\sum _{j=1}^{n}|OPT_{j}|d_{j}=q(E,F)c(OPT)} となる。

※この「証明の概要」の解説は、「マトロイド」の解説の一部です。
「証明の概要」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。

証明の概要

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/21 04:12 UTC 版)

「最大フロー最小カット定理」の記事における「証明の概要」の解説

証明は、以下のようにしてできる。最大フローはフォード・ファルカーソンのアルゴリズムにより、以下のようにして見つけることができる。二端子フローネットワーク Ν (G(V, E), c, s, t) が与えられたとする。最大フローを見つけるために、s から t への道を見つける。この道を構成するすべてのエッジの容量の最小値を、エッジの流量として割り当てると、これはこのネットワークのフローになる。流量の余裕を容量とする順方向のエッジと、現在の流量を容量とする逆方向のエッジからなるネットワークで、容量が 0 となるエッジを取り除いたものを残余ネットワーク (residual network) もしくは補助ネットワークと呼ぶ。この残余ネットワークの中で、同じように道を見つける。道の構成要素のうち、順方向のエッジでは流量を増加させ、逆方向のエッジでは流量を減少させることで、より流量の大きな新しいフローを得ることができる。（このような、フロー f の残余ネットワークにおける s から t への道を、f の増加道と呼ぶ。）増加道がなくなれば、このフローが Ν の最大フローである。最大フローの残余ネットワークは、 s {\displaystyle s} から到達可能なノード群 S {\displaystyle S} と到達不可能なノード群 T {\displaystyle T} に分けることができる。増加道がないので、t は T に含まれる。定義より、残余ネットワーク上では S から T へのエッジは存在しない。もとのネットワークに戻って考えると、S から出るエッジ (u, v) はすべて、残余ネットワークに存在しないことから、流量の余裕がない、すなわち f ( u , v ) = c ( u , v ) {\displaystyle f(u,v)=c(u,v)} となっていることが分かる。また、S に入るエッジは逆方向のエッジが残余ネットワークにないことから、流量が 0 であることが分かる。これらのことより、 c ( S , T ) = | f m a x | {\displaystyle c(S,T)=|f_{\mathrm {max} }|} となる。したがって、 | f m a x | = c ( S , T ) ≥ c ( ( S , T ) m i n ) {\displaystyle |f_{\mathrm {max} }|=c(S,T)\geq c((S,T)_{\mathrm {min} })} といえる。次に c ( ( S , T ) m i n ) ≥ | f m a x | {\displaystyle c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|} も成り立つことをみる。任意のフロー f に対して、T へ流れこむエッジ (u, v) の流量は最大で c(u, v) であり、これの和は (S, T) のカットの容量の定義そのものである。一方、T から S へ逆流するエッジの流量は、当然ながら最小値は 0 以上である。フローの流量は流量保存により、T に流入する流量から逆流する流量を引いたものであることを確認したが、このことよりfの流量は最大でカット (S, T) の容量となる。このことより、 c ( S , T ) ≥ | f | {\displaystyle c(S,T)\geq |f|} 、特に c ( ( S , T ) m i n ) ≥ | f m a x | {\displaystyle c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|} である。

※この「証明の概要」の解説は、「最大フロー最小カット定理」の解説の一部です。
「証明の概要」を含む「最大フロー最小カット定理」の記事については、「最大フロー最小カット定理」の概要を参照ください。

証明の概要

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/05 05:24 UTC 版)

「最大値原理」の記事における「証明の概要」の解説

調和関数に対する「弱最大値原理」は、単純な計算による事実の帰結である。証明において重要となるのは、調和関数の定義から、f のラプラシアンがゼロであるという事実である。 x 0 {\displaystyle x_{0}\,} が f(x) の非退化な臨界点であるなら、鞍点が存在する。実際、もしそうでないなら、f の二階微分の和がゼロとなることがなくなるからである。これはもちろん、証明としては完全ではなく、 x 0 {\displaystyle x_{0}\,} が退化点である場合も残されているが、本質的な証明のアイデアである。「強最大値原理」はホップの補題（英語版）に依るものであり、これはまたさらに複雑である。