説明されたアプローチの著者は、V.A。Institute of Semiconductor Physics SB RASの主任研究員です。 メレンティエフ。 グラフの正式な記述のための新しい方法は、2000年に「グラフの記述のためのブレース形式と粘り強いコンピューティングシステムの構造研究での使用」で彼に最初に提案されました。
だからポイントは何ですか？
グラフ記述には、グラフィカルとマトリックスの2つのよく知られた形式があります。 グラフィック形式は、ノード（ポイント）とこれらの頂点を直接接続する通信ライン（アーク、エッジ）の形式で列挙可能な頂点のセットの平面上のマッピングです。 行列を形成する行と列の選択に応じた行列形式は、隣接行列（行と列がグラフの頂点に対応する）、入射行列（行-頂点、列-エッジ）、エッジの隣接行列（行と列の要素はグラフのエッジ）と呼ばれます。 グラフィカル形式とは対照的に、マトリックスは、番号付けなど、グラフの対応する要素の明確な指定の導入を前提としていることは明らかです。
矛盾を避けるために、いくつかのよく知られている定義と、この記事で使用されているグラフ画像に関する基本的な情報を提供します。
グラフGは順序付けられたペアG（V、E）で、 Vは空でない頂点またはノードのセット、 Eはエッジと呼ばれる頂点のペアのセットです。
頂点uおよびvは、エッジe = {u、v}の終了頂点（または単に終了）と呼ばれます。 リブは、これらのピークを接続します。 同じエッジの2つの終了頂点は隣接と呼ばれます。
頂点v の次数deg（v）は、頂点であるエッジの数です。 簡単に言えば、これは上から発するエッジの数です。
グラフG（V、E） の画像 P（v i ）は、括弧内のグラフの記述であり、その開始点（角度の頂点）は頂点v i∈Vです。
集合N（w）は、 s（w）= deg（w）頂点で構成される頂点wの環境です。
セットM iは、投影のi番目のレベルにある頂点のセットです。
C i - i番目のレベルの投影の頂点の総数。
調査の対象は、原則として、複数のエッジとループのない、同じ重みのエッジを持つ無向グラフに接続されています。 単位立方体の例を使用して、ブラケット投影の構成を示しましょう。
画像の視覚的認識を向上させ、画像を操作しやすくするために、有限のレベルセットの形式でグラフのブラケット記述を構造化します。 最初の頂点を選択し（選択は任意または動機付け、 v 0 = 0の場合）、レベル0に配置し、隣接する頂点を最初のレベルの右上の第1レベルに配置します。 角度頂点N（0） = {1、2、3}の環境は、第1レベルの頂点のセットです。M1 = {1、2、3}、| M 1 | = C 1 = 3。
0 {1、2、3}
したがって、問題のグラフのイメージのゼロレベルと最初のレベルでは、|からの1つの頂点 V | = 8および3つのエッジ| E | = 12。
説明を第2レベルまで続けます。 第2レベルの頂点のセットM 2は、第1レベルの3つの頂点の環境（これらのサブセットの直前に頂点0がない）であるC 1 = 3サブセットを結合します。
M 2 = M 21 U M 22 U M 23 = {4、5} U {4、6} U {5、6} = {4、5、6}、 C 2 = 6、および| M 2 | = 3。
取得するもの：
0 {1 {4、5} 、2 {4、6} 、3 {5、6} }
一般的なケースでは、2番目のレベルから開始し、後続の各レベルは頂点のセットではなくコレクションになります。これは、反復する要素を含む場合があるためです。 M 1 U M 2 ≠ Vであるため、次のレベルまで投影の構築を継続する必要があることに注意してください。
3番目のレベルの頂点のセットM 3は 、2番目のレベルの対応する6つの頂点の環境である6つのサブセットで構成されます。各サブセットは、この環境に先行する頂点のセットを減算することによって変更されます。
M 3 = M 34 1 U M 35 1 U M 34 2 U M 36 1 U M 35 2 U M 36 2 。
ここで、下のインデックスの最初の数字は対応する投影レベルに属することを示し、2番目のインデックスはグラフの頂点を識別し、上のインデックスは考慮される投影レベルで同じ頂点のいくつかのインスタンスに追加のインデックスを付けます。 このように構築された投影から
0 {1 {4 {2、7} 、5 {3、7} } 、2 {4 {1、7} 、6 {3、7} } 、3 {5 {1、7} 、6 {2、7 } } }
3番目のレベルでのみ頂点7が表示され、前のレベルのサブセットには含まれないことがわかります。M3 = {2、7} U {3、7} U {1、7} U {3、7} U {1,7} U {2、7} = {1、2、3、7}。 C 3 = 12。 M 3 | = 4.単一行バージョンでの同じ投影の記録の形式は
P 3 （0） = 0 {1 {4 {2、7}、5 {3、7}}、2 {4 {1、7}、6 {3、7}}、3 {5 {1、7} 、6 {2、7}}}。
頂点の1つまたは別のサブセットの前にある開き括弧はそのネストを示し、閉じて「クリアされない」括弧の数は、先行セットのこのサブセットのネストのレベルを決定します。 角度頂点の子孫のセットのサブセットのネストレベル（投影のレベル番号）は、対応するサブセットの頂点からの距離を決定します。
グラフP k （v o ）の射影は、このグラフのすべての頂点とすべてのエッジ（隣接関係）を定義している場合、完全と見なされます。 上記の投影P 3 （0）から、頂点とエッジの両方の完全性条件は、ここでは3番目のレベルでのみ満たされることがわかります。
M 0 U M 1 U M 2 U M 3 = V 、| M 0 U M 1 U M 2 U M 3 | = | V | = 8
E 0 U E 1 U E 2 U E 3 = E 、| E 0 U E 1 U E 2 U E 3 | = | E | = 12
ブラケット画像のいくつかのプロパティ
重み付けされていないグラフのブラケットイメージの各レベルには、長さがこのレベルの数に等しい最初の頂点から発生するすべての一意の（繰り返しのない）単純なチェーンの一連の終了頂点が含まれます。
k番目のレベルの頂点のセットを考えます。 指定されたセットには、画像の初期頂点からの距離がこのレベルの数に等しい頂点を含む、長さがこのレベルの数に等しい初期頂点から発するすべての単純なチェーンの終了頂点が含まれます。 これには、初期頂点からの距離がレベル番号kを超える頂点を含めることはできません。
グラフがハミルトニアンの場合、その頂点のセットには、ゼロを含む最大画像のレベルの数がグラフの頂点の数と等しくなるように存在します。
そして、それを使用する方法は？
よく知られているグラフィカルな表示やマトリックス表示とは対照的に、グラフのブラケット画像は、グラフの頂点とエッジのセットおよびそれらの隣接または出現に関する明示的に指定された情報に加えて、明示的または簡単に取得可能な情報に関する情報がブラケット画像に表示されるため、情報量が増加していますピーク間のルートのセット、その長さなど。 グラフの説明に追加情報が存在することで、たとえば最短ルートの検索、頂点のペアの互いに素なパスの検索、グラフの半径、直径、トラバース、頂点の離心率、およびグラフ上のその他の多くの典型的な問題を必要な量を選択するという単純な操作で特定するなど、かなり手間のかかるアルゴリズムを置き換えることができますそのような記述の「表面に横たわっている」オブジェクト。
いくつかのサブグラフのセットを相互に比較すると、労働集約度の大幅な向上がさらに明白になります。これは、提案された形式の表現により、以前に実行されたブランチまたはセクションの複数の繰り返しを除外できるためです。 中間結果として後で使用するために通常のアルゴリズムのそのようなセクションを修正しようとすると、特に複雑なグラフのこれらのアルゴリズムのロジックが不当に複雑になり、逆の効果が生じる可能性があります：透明性が不十分で予測できない結果を伴うそのようなアルゴリズムの複雑さの増加「。
ブラケット画像の装置は、特に最短およびばらばらのルート、頂点の離心率、グラフの直径などに関するグラフ理論のいくつかの古典的な問題を解決する上で、メレンティエフによって正常にテストされました。
文学
V.A.の作品リスト メレンティエヴァ