しゅく‐やく【縮約】
縮約
縮約
縮約
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/19 13:50 UTC 版)
複数の音節が一音節に縮められて発音されることを縮約という。 秋田方言では、係助詞の /wa/ （ワ）が直前の音節と縮約されて発音される場合がある。コンドワ（今度は）がコンダとなるように /dowa/ が /da/ に縮約したり、コレワ（これは）がコリャ、ソレワ（それは）がソリャとなるように /rewa/ が /rja/ に縮約される場合がある。 中年層以下の若い世代を中心として、コレデワ（これでは）をコレジャ、ソレデワ（それでは）がソレジャとなるように /dewa/ （デワ）から /zja/ （ジャ）への縮約が見られるが、これは東京の口語の影響であり、高年層はほとんど用いない。「～では」にあたる形は、「～ンダンバ」や「～ンデ」などの形で表すのが一般的である。 動詞の語尾の /ru/ と、助詞の /no/ が縮約して、/runo/ が撥音になることがよく見られる。例えばミデルノンダ（見ているのだ）がミデンダになる。
※この「縮約」の解説は、「秋田弁の音韻」の解説の一部です。
「縮約」を含む「秋田弁の音韻」の記事については、「秋田弁の音韻」の概要を参照ください。
縮約
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
グラフ G の縮約 G / u v {\displaystyle G/uv} とは、グラフ内の頂点 u と v を特定し、それらの間の辺を全て除去し、その2つの頂点を1つの新たな頂点 w に置き換え、u や v と接合していた全ての辺を w に繋ぎかえることでできるグラフである。この操作はグラフ彩色の解析において重要な役割を演じる。 Zykov (1949) によれば、彩色数は次の漸化式を満たす。 χ ( G ) = min { χ ( G + u v ) , χ ( G / u v ) } {\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}} u と v が隣接した頂点でない場合、 G + u v {\displaystyle G+uv} は辺 u v {\displaystyle uv} を加えたグラフを意味する。この漸化式を評価することに基づくアルゴリズムもいくつかあり、それによって形成される計算木を Zykov 木と呼ぶこともある。実際にかかる時間は頂点 u と v の選択のしかた（ヒューリスティック）に依存する。 彩色多項式は次の漸化式を満たす。 P ( G − u v , k ) = P ( G / u v , k ) + P ( G , k ) {\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)} u と v が隣接した頂点の場合、 G − u v {\displaystyle G-uv} は辺 u v {\displaystyle uv} を除去したグラフを意味する。 P ( G − u v , k ) {\displaystyle P(G-uv,k)} はそのグラフの彩色の組み合わせ数を表し、u と v が同色の場合もそうでない場合も含まれる。上の式から、彩色の組み合わせ数は2つのグラフの彩色組み合わせ数の和で表される。頂点 u と v の色が異なる場合、u と v が1つの辺で結ばれたグラフでも同じ彩色が可能である。u と v が同色の場合、u と v を縮約したグラフと同じとみなすことができる。W・T・タットはこの漸化式を満たすグラフの属性について興味を持ち、彩色多項式を一般化したタット多項式を発見した。 これらから、再帰的な手続きが考えられ、それを削除・縮約アルゴリズム (deletion–contraction algorithm) と呼び、多くのグラフ彩色アルゴリズムの基盤となっている。すなわち、与えられたグラフを辺が1つ少ない2つのグラフに変換し、それを再帰的に繰り返すのである。これはフィボナッチ数と同様の再帰属性を持ち、最悪でも ( ( 1 + 5 ) / 2 ) n + m = O ( 1.6180 n + m ) {\displaystyle ((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})} の処理時間となる。さらに入力されたグラフのスパニング木の数 t ( G ) {\displaystyle t(G)} の多項式の係数を応用することで解析を改善することができる。実際には、分枝限定法を使い、同型のグラフを排除することで再帰回数を減らすことができ、処理時間は2つの頂点を選ぶ際のヒューリスティックに依存する。
※この「縮約」の解説は、「グラフ彩色」の解説の一部です。
「縮約」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
「縮約」の例文・使い方・用例・文例
品詞の分類
- >> 「縮約」を含む用語の索引
- 縮約のページへのリンク
