マセマティカ エテルナ
オープンアクセス

概要

グラフ機能に関する簡単なメモ

ジェシカ、J

グラフ G の実用性は、すべての誘導サブグラフ H が最も多くを占める場所です。機能性は退化との類推によって定義され、一般化されます。つまり、定義の先頭で を置き換えると、G の退化が得られます。誘導サブグラフを最も多く取ると、誘導サブグラフを取っても実用性は増加しないことが保証されます。他の多くのグラフ パラメータと同様に、グラフの実用性の概念は、その値が小さい、つまりグラフのサイズの継続的な自由度によって有限である場合に価値を持ちます。何よりも、[3] で示されているように、実用性が小さいグラフはコンパクトな表現が可能です。その論文では、グラフの実用性の概念を正式に定義していませんが、そこで証明された結果は、有限の実用性のグラフは長さのバイナリ ワードで表すことができることを示唆しています。