グラフのラベル付け

グラフ理論の数学的分野では、 グラフのラベル付けは、従来は整数で表されていたラベルをグラフのエッジや頂点に割り当てることです。

形式的には、グラフG =（ V 、 E ）が与えられると、 頂点ラベル付けはラベルのセットに対するVの関数です。このような関数が定義されたグラフは、 頂点ラベル付きグラフと呼ばれます 。同様に、 エッジのラベル付けは、ラベルのセットに対するEの関数です。この場合、グラフはエッジラベル付きグラフと呼ばれます 。

エッジラベルが順序付きセット（実数など）のメンバーである場合、 重み付きグラフと呼ばれる場合があります。

修飾なしで使用する場合、 ラベル付きグラフという用語は一般に、すべてのラベルが異なる頂点ラベル付きグラフを指します。このようなグラフは、連続した整数{1、…、| V |}、ここで| V |グラフ内の頂点の数です。多くのアプリケーションでは、エッジまたは頂点には、関連付けられたドメインで意味のあるラベルが付けられます。たとえば、エッジには、入射頂点間を移動する「コスト」を表す重みを割り当てることができます。

上記の定義では、グラフは有限の無向単純グラフであると理解されています。ただし、ラベル付けの概念は、グラフのすべての拡張および一般化に適用できます。たとえば、オートマトン理論と形式言語理論では、ラベル付きマルチグラフを考慮するのが便利です。つまり、頂点のペアはいくつかのラベル付きエッジで接続されます。

歴史

ほとんどのグラフのラベル付けは、1967年にAlex Rosaが発表したラベル付けに由来します。ローザは3種類のラベルを特定しました。これを、α、β、およびρラベルと呼びました。 β-ラベルは後にSW Golombによって優雅な名前に変更され、それ以来この名前は人気を博しています。

特殊なケース

優雅なラベル付け

ローザは元の論文で、サイズが1または2（mod 4）に等しいオイラーグラフはすべて優雅ではないことを証明しました。グラフの特定のファミリーが優雅であるかどうかは、広範な研究の下でのグラフ理論の領域です。間違いなく、グラフのラベル付けにおける最大の実証されていない推測は、すべての木が優雅であると仮定するリンゲル・コッツィヒ推測です。これは、すべてのパス、キャタピラ、および他の多くの無限の樹木ファミリーで証明されています。 Kotzig自身は、推測が「病気」であることを証明する努力をしました。

エッジが優雅なラベル付け

p頂点およびqエッジ上の単純なグラフ（ループまたは複数のエッジなし）のエッジグレースフルラベル付けは、{1、…、 q }の異なる整数によるエッジのラベル付けです。 1頂点に-入射の和との頂点をとるモジュロpは 0からpまでのすべての値を割り当て縁。グラフGは、エッジグレースフルラベル付けを許可する場合、エッジグレースフルであると言われます。

エッジグレースフルラベルは、1985年にS. Loによって初めて導入されました。

グラフがエッジグレースフルであるために必要な条件は、 Loの条件です。

q（q + 1）= p /（p−1）2modp。{\ displaystyle q（q + 1）= p /（p-1）2 \ mod p。}

調和のとれたラベル

グラフG上の調和標識が取ることによってGのエッジと番号モジュロkとの全単射を誘導kは Gのエッジの数であり、kは 、モジュロ整数のグループにGの頂点から噴射され2つの頂点x 、 y （mod k ）のラベルの合計となるエッジ（ x 、 y ）のエッジラベル。 調和の取れたグラフとは、調和の取れたラベルが付いたグラフです。奇数サイクルは、Petersenグラフと同様に調和しています。 1つの頂点ラベルを再利用できる場合、ツリーはすべて調和していると推測されます。 7ページのブックグラフK 1,7× K 2は、調和しないグラフの例を示しています。

グラフの色付け

グラフの色付けは、グラフのラベル付けのサブクラスです。 頂点カラーリングは 、隣接する頂点に異なるラベルを割り当てます。 エッジの色付けは 、隣接するエッジに異なるラベルを割り当てます。

ラッキーラベリング

グラフGの 幸運なラベル付けは、 S （ v ）がvの近傍のラベルの合計を表す場合、 SがGの頂点カラーリングであるようなGの頂点への正の整数の割り当てです。 Gのラッキーナンバーは最小のkであり 、 Gには整数{1、…、 k }のラッキーラベルが付けられます。