樹木性

無向グラフの樹状性は、その辺を分割できるフォレストの最小数です。同様に、グラフのすべての辺をカバーするために必要な全域フォレストの最小数でもあります。ナッシュ・ウィリアムズの定理は、グラフがk樹状である場合の必要十分条件を提供します。

この図は完全な二部グラフ K _4,4を示しており、色はその辺が 3 つのフォレストに分割されていることを示しています。K _{4,4 は}、8 つの頂点にあるフォレストの辺が最大で 7 つであるのに対し、グラフ全体の辺は 16 個で、単一のフォレストの辺数の 2 倍以上であるため、それより少ないフォレストに分割することはできません。したがって、K _4,4の樹木度は3 です。

グラフの樹状性は、グラフの密度の尺度です。多くのエッジを持つグラフは樹状性が高く、樹状性が高いグラフには密なサブグラフが必ず存在します。

より詳しく言うと、n 頂点の森は最大で n-1 本の辺を持つので、n 頂点と m 本の辺を持つグラフの樹状度は少なくとも である。さらに、どのグラフの部分グラフもグラフ自体よりも大きな樹状度を持つことはできない。つまり、グラフの樹状度は少なくともその部分グラフの最大樹状度でなければならない。ナッシュ・ウィリアムズは、これら 2 つの事実を組み合わせて樹状度を特徴付けることができることを証明した。与えられたグラフの任意の部分グラフ S の頂点と辺の数をそれぞれ n _Sと m _Sとすると、グラフの樹状度は次のようになる。${\displaystyle \lceil m/(n-1)\rceil }$${\displaystyle \max_{S}\{\lceil m_{S}/(n_{S}-1)\rceil \}.}$

頂点を持つ任意の平面グラフには最大で個の辺があり、ナッシュ・ウィリアムズの公式から、平面グラフの樹状性は最大で 3 個であることがわかります。シュナイダーは、平面グラフをシュナイダー ウッドと呼ばれる 3 つの森に特別に分解して、任意の平面グラフを小さな領域のグリッドに直線で埋め込む方法を見つけました。 ${\displaystyle n}$${\displaystyle 3n-6}$

グラフの樹状性は、より一般的なマトロイド分割問題^[1]の特殊なケースとして表現できます。この問題では、マトロイドの要素の集合を少数の独立集合の和集合として表現します。その結果、樹状性は多項式時間アルゴリズム (Gabow & Westermann 1992) によって計算できます。現在の最良正確なアルゴリズムは、時間で樹状性を計算します。ここで、はグラフの辺の数です。 ${\displaystyle O(m{\sqrt {m}})}$${\displaystyle m}$

グラフの樹状性の近似値はより高速に計算できます。線形時間の2近似アルゴリズム^{[2] [3]}と、加法誤差が2の近似線形時間アルゴリズム^{[4]があります。}

グラフの無樹状性は、グラフのエッジを分割できる、エッジが互いに素な非循環サブグラフの最大数です。

グラフのスター樹状性は、各ツリーがスター(最大で 1 つの非リーフ ノードを持つツリー) であり、グラフのエッジを分割できる最小のフォレストのサイズです。ツリー自体がスターでない場合は、エッジをツリーのルートから奇数と偶数の距離にある 2 つのサブセットに分割するとわかるように、そのスター樹状性は 2 です。したがって、どのグラフのスター樹状性も、少なくとも樹状性と同じで、最大で樹状性の 2 倍になります。

グラフの線形樹状性は、グラフのエッジを分割できる線形フォレスト(パスの集合)の最小数です。グラフの線形樹状性は、最大次数と傾き数に密接に関連しています。

グラフの擬似樹木性は、その辺を分割できる擬似森林の最小数です。同様に、グラフの任意のサブグラフにおける辺と頂点の最大比率を整数に切り上げた値です。樹木性と同様に、擬似樹木性はマトロイド構造を持ち、効率的に計算できます (Gabow & Westermann 1992)。

グラフのサブグラフ密度は、最も密度の高いサブグラフの密度です。

グラフの厚さは、その辺を分割できる平面サブグラフの最小数です。平面グラフの樹状度は 3 なので、グラフの厚さは少なくとも樹状度の 3 分の 1 に等しく、最大でも樹状度に等しくなります。

グラフの退化とは、グラフのすべての誘導されたサブグラフにおける、サブグラフの頂点の最小次数の最大値です。樹木性を持つグラフの退化は、少なくとも に等しく、最大で に等しくなります。グラフの彩色数は、Szekeres-Wilf 数 (Szekeres & Wilf 1968) としても知られ、常に退化に 1 を加えた値に等しくなります (Jensen & Toft 1995、p. 77f.)。 ${\displaystyle a}$${\displaystyle a}$${\displaystyle 2a-1}$

グラフの強さは小数値であり、その整数部分はグラフに描画できる分離全域木の最大数を示します。これは、樹木性によって生じる被覆問題と双対となるパッキング問題です。この 2 つのパラメータは、Tutte と Nash-Williams によって一緒に研究されてきました。

分数樹状性は、グラフに対して次のように定義される樹状性の改良版です。言い換えると、グラフの樹状性は分数樹状性の上限です。 ${\displaystyle G}$${\displaystyle \max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.}$

(a,b)-分解可能性は樹木性を一般化します。グラフの辺を集合に分割でき、各集合がフォレストを誘導し、最大次数のグラフを誘導するものを除いて、その場合、グラフは -分解可能です。樹木性を持つグラフは-分解可能です。 ${\displaystyle (a,b)}$${\displaystyle a+1}$${\displaystyle b}$${\displaystyle a}$${\displaystyle (a,0)}$

ツリー数とは、グラフのエッジをカバーするツリーの最小数です。

樹木性はゴールドバーグ・シーモア予想に現れます。