シンボル 角括弧 [ ] G [ S ]S に対するグラフGの 誘導部分グラフ プライム記号 ' プライム記号は、グラフ不変量の表記法を、与えられたグラフではなく 線グラフ に適用できるように変更するためによく使用されます。たとえば、α G )′ G )χ G )′ G )
B バッグ 木分解 バランスの取れた 二部グラフまたは多部グラフは、頂点分割の各2つの部分集合のサイズが互いに1以内である場合にバランスが取れていると言えます。 ボール ボール（近傍ボールまたは距離ボールとも呼ばれる）とは、ある頂点から距離がr以下のすべての頂点の集合である。より厳密には、与えられた頂点vと半径rに対して、ボールB(v,r)は、vへの最短経路距離がr以下のすべての頂点から構成される。 帯域幅 グラフG の帯域幅は、 G の頂点のすべての順序付けにおいて、最長辺の長さ（その2つの端点間の順序付けにおけるステップ数）の最小値である。また、クリークのサイズを最小化するように選択されたG の適切な区間完備化における最大クリークのサイズより1小さい値でもある。 バイクリック 完全二部グラフ または完全二部部分グラフの同義語。完全を 双連結 通常は2 頂点連結K2 を含む場合もあります。 連結 については「connected」、双連結成分 については「component」を バインディングナンバー 頂点の真部分集合の近傍の数と部分集合のサイズの最小比率。[ 6 ] 二部構成 二部グラフ とは、頂点を互いに素な2つの集合に分割できるグラフのことです。ただし、一方の集合の頂点同士は接続されていませんが、もう一方の集合の頂点とは接続されている可能性があります。言い換えれば、二部グラフは奇数サイクルを持たないグラフです。つまり、2色で適切に彩色できるグラフです。二部グラフは、G = ( U , V , E )U とV は それぞれの色の頂点のサブセットです。ただし、グラフが連結でない限り、一意の2彩色を持つとは限りません。 双規則 双正則グラフ とは、頂点の二分割の各集合に対応する2つの異なる頂点次数のみを持つ二部グラフのことである。 ブロック 1.グラフG のブロックとは、孤立頂点、ブリッジエッジ、または2連結部分グラフのいずれかである極大部分グラフのことである。ブロックが2連結である場合、そのブロック内のすべての頂点のペアは共通のサイクルに属する。グラフのすべてのエッジは、ちょうど1つのブロックに属する。 2.グラフGのブロック グラフは、頂点が G のブロックであり、対応するブロックが共通の連結点を持つ場合に 2 つの頂点を結ぶ辺を持つ別のグラフです。つまり、 G のブロックの交差グラフです。任意のグラフのブロック グラフは森 3.グラフG のブロックカット (またはブロックカットポイント) グラフは、一方の部集合がG のカット頂点からなり、もう一方の部集合が頂点を持つ二部グラフです。 b 私 {\displaystyle b_{i}} B 私 {\displaystyle B_{i}} G の。G が連結である場合、そのブロックカットポイントグラフは木になります。 4.ブロックグラフ （連結されている場合はクリークツリーとも呼ばれ、誤ってフシミツリーと呼ばれることもある）とは、すべてのブロックが完全グラフであるグラフのことである。フォレスト ボンド 最小カットセット：それを取り除くとグラフが分断されるエッジの集合で あり 本 1.ブック、ブックグラフ、または三角形ブックは、完全な三部グラフK 1,1, n で あり、共通のエッジで結合されたn 個の三角形の集合です。 2.もう一つのグラフの種類は、ブックまたは四角形ブックとも呼ばれ、共通のエッジで結合された4 つの サイクルの集合です。これは、星とエッジのデカルト積です。 3.ブック埋め込み とは、グラフをトポロジカルブック（共有線に沿って複数の半平面を結合して形成される空間）に埋め込むことです。通常、埋め込みの頂点は埋め込みの背骨と呼ばれる線上に存在し、埋め込みの辺は単一の半平面（本のページの一つ）内に存在する必要があります。 境界 1.グラフ埋め込み において、境界ウォークとは、面 イバラ ブランブルと は、互いに接する連結部分グラフの集合であり、2つの部分グラフが接するのは、それらが頂点を共有するか、またはそれぞれが辺の端点を1つずつ含む場合である。ブランブルの次数とは、すべての部分グラフと空でない共通部分を持つ頂点集合の最小サイズである。グラフの木幅とは、そのグラフに含まれるいずれかのブランブルの最大次数である。 支店 次数が2の頂点のパスで、次数が2と等しくない頂点で終わる。[ 7 ] 分岐分解 G の分岐分解は、 G のエッジの階層的クラスタリングであり、 G のエッジでラベル付けされた葉を持つ根なし二分木で表されます。分岐分解の幅は、この二分木のエッジeに関して、 e で隔てられた 2 つのサブツリー内のG のエッジによって決定されるサブグラフ間で共有される頂点の数の最大値です。G の分岐幅は、G の任意の分岐分解の最小幅です。枝幅 分岐分解を 橋 1.橋、地峡、または切断辺とは、 それを取り除くとグラフが分断される辺のことです。橋のないグラフとは、橋を持たないグラフのことです。言い換えれば、2辺で連結されたグラフのことです。 2.部分グラフH のブリッジとは、グラフの残りの部分からH によって分離された極大連結部分グラフのことです。つまり、Hと辺素であり、かつ、2 つの頂点と辺がそれぞれ H と内部的に素なパスに属する極大部分グラフのことです。H は 頂点の集合でも構いません。弦とは、1 つの辺を持つブリッジのことです。平面性判定 において、H はサイクルであり、周辺サイクル とは、ブリッジが最大で 1 つしかないサイクルのことです。周辺サイクルは、そのグラフの任意の平面埋め込みにおいて面境界でなければなりません。 3.サイクルのブリッジとは、サイクルの2つの頂点を結ぶ経路のうち、同じ2つの頂点を結ぶ他の経路よりも短い経路を指す場合もあります。ブリッジグラフ とは、4つ以上の頂点からなるすべてのサイクルにブリッジが存在するグラフのことです。 橋のない 橋のない グラフまたは地峡のないグラフとは、橋となる辺（つまり、地峡）を持たないグラフのことです。つまり、各連結成分は2辺で連結されたグラフ です。蝶 1.バタフライグラフは 5つの頂点と6つの辺を持ち、1つの頂点を共有する2つの三角形によって形成されます。 2.バタフライネットワークは、分散コンピューティングにおけるネットワークアーキテクチャとして使用されるグラフであり、キューブ接続サイクル と密接に関連しています。
C C C n はn 頂点サイクルグラフ です。サイクル カクタス サボテングラフ 、サボテンツリー、サボテン、またはフシミツリーとは、各辺が最大で1つのサイクルに属する連結グラフのことです。そのブロックはサイクルまたは単一の辺です。さらに、各頂点が最大で2つのブロックに属する場合、それはクリスマスサボテンと呼ばれます。 ケージ ケージと は、周長の次数が最小となる正則グラフのことである。 正統派 列聖 グラフの標準形とは、2つのグラフが同型である場合に限り、それらの不変量が等しいという不変量のことです。標準形は、標準不変量または完全不変量とも呼ばれ、特定のグラフ族内のグラフに対してのみ定義される場合もあります。グラフの 標準化 とは、標準形を計算するプロセスです。 カード 与えられたグラフから頂点を1つ削除して形成されるグラフ。特に再構成予想 の文脈で用いられる。グラフのすべてのカードの多重集合である「デッキ」も参照のこと。 彫刻の幅 カービング幅は、枝幅に類似したグラフ幅の概念であるが、エッジの階層的クラスタリングではなく、頂点の階層的クラスタリングを使用する。 毛虫 キャタピラツリー またはキャタピラとは、内部ノードがパスを誘導するツリーのことです。 中心 グラフの中心とは、離心率が最小となる頂点の集合のことで ある 重心 木の重心とは、v を根とした場合、他のどの頂点も部分木のサイズが木のサイズの半分を超えることがないような頂点vの こと である。 鎖 1.歩く 2.グラフに代数トポロジー の方法を適用する場合、チェーン複合体 の要素、すなわち頂点の集合または辺の集合。 チーガー定数 展開図を チェリー チェリーは3つの頂点を持つ経路である。[ 8 ] χ χ G )G の彩色数であり、 χ G )彩色 着色を 子供 根付き木において、頂点v の子とは、根から離れる方向に向かう辺に沿ったv の隣接頂点のことである。 コード 和音 1.サイクルの弦とは、両端がサイクルに属するものの、サイクルに属さない辺のことである。 2.弦グラフ とは、4つ以上の頂点からなるすべてのサイクルに弦が存在するグラフであり、誘導されるサイクルは三角形のみである。 3.強弦グラフ とは、長さが6以上のすべてのサイクルに奇数弦が含まれる弦グラフのことである。 4.弦状二部グラフは 弦状ではありません（森でない限り）。これは、6 つ以上の頂点のすべてのサイクルに弦がある二部グラフであり、誘導されるサイクルは 4 サイクルのみです。 5.円の弦 とは、円上の2点を結ぶ線分のことです。弦の集合の交点グラフは 円グラフ と呼ばれます。 色彩 色付けに関する。色を 彩色数 χ G )は、 G の適切な彩色に必要な最小色の数である。χ ′ G )はG の彩色指数 であり、 G の適切な辺彩色 に必要な最小色の数である。 選択可能 選択可能性 グラフがk 選択可能であるとは、各頂点にk個の利用可能な色のリストが存在する場合に、そのグラフが リスト彩色を 持つことを意味する。グラフの選択可能性とは、そのグラフがk 選択可能となる最小のk の値である。 丸 円グラフと は、円を構成する弦の交点グラフ のことである。 回路 回路とは、閉じた経路、またはサイクル空間 の要素（オイラー全域部分グラフ）を指す場合がある。グラフの回路ランクは、そのサイクル空間の次元である。 周 グラフの円周とは、そのグラフにおける最長の単純サイクルの長さのことである。グラフがハミルトングラフであるのは、その円周がグラフの次数と等しい場合に限る。 クラス 1.グラフのクラスまたはグラフの族とは、 （通常は無限の）グラフの集合であり、多くの場合、特定の性質を持つグラフとして定義されます。「集合」ではなく「クラス」という言葉が使われるのは、特別な制約（例えば、特定の集合から頂点を抽出するように制限したり、辺を2つの頂点の集合として定義したりするなど）を設けない限り、グラフのクラスは集合論を用いて形式化した場合、通常は集合にならないためです。 2.色付きグラフの色クラスとは、特定の色を持つ頂点または辺の集合のことです。 3.ヴィジングの定理 の文脈では、単純グラフの辺彩色において、グラフの彩色指数が最大次数に等しい場合、そのグラフはクラス1に属し、彩色指数が次数に1を加えた値に等しい場合、クラス2に属するとされます。ヴィジングの定理によれば、すべての単純グラフはクラス1かクラス2のいずれかに属します。 爪 クローと は、内部頂点が1つと葉が3つある木、あるいは同等に完全二部グラフK 1,3の クローフリーグラフ とは、クローとなる誘導部分グラフを持たないグラフのことである。 仲間 クリークと は、互いに隣接する頂点の集合（またはその集合によって誘導される完全部分グラフ）のことです。クリークは、より大きな集合（または部分グラフ）の一部ではない、互いに隣接する頂点の最大集合（または最大完全部分グラフ）として定義されることもあります。k-クリークとは、次数が k のクリークのことです。グラフGの クリーク数 ω G )Gの クリークグラフは、 G 内の最大クリークの交差グラフ です。完全二部グラフである二部 クリックツリー ブロックグラフ クリーク幅 グラフG のクリーク幅 は、ラベル付き頂点を作成する操作、2 つのラベル付きグラフの非交和を形成する操作、指定されたラベルを持つすべての頂点のペアを接続するエッジを追加する操作、または指定されたラベルを持つすべての頂点を再ラベル付けする操作によってG を構築するために必要な、異なるラベルの最小数です。クリーク幅が最大 2 の グラフは、まさにコグラフ です。 閉店 1.閉じた近傍とは、中心の頂点を含む近傍のことです。近傍を 2.閉じたウォークとは、同じ頂点から始まり同じ頂点で終わるウォークのことです。ウォークを 3.グラフは、自身の推移閉包と等しい場合、推移的に閉じていると言います。推移性を 4.グラフの性質は、グラフに対する何らかの操作の下で閉じていると言います。それは、その操作の引数がその性質を持つ場合、結果もその性質を持つ場合です。例えば、遺伝的性質は誘導部分グラフの下で閉じており、単調性は部分グラフの下で閉じており、マイナー閉性はマイナーの下で閉じています。 閉鎖 1.有向グラフの推移閉包については、推移を 2.有向グラフの閉包とは、閉包外の頂点への出力辺を持たない頂点の集合のことです。例えば、シンクは1つの頂点からなる閉包です。閉包問題 とは、最小または最大の重みを持つ閉包を見つける問題です。 共同 この接頭辞は、補グラフ に関連するさまざまな意味を持ちます。たとえば、コグラフ は補グラフを含む操作によって生成されるグラフです。コカラーリング は、各頂点が独立集合（適切な彩色の場合）またはクリーク（補グラフの彩色の場合）のいずれかを誘導する彩色です。色 着色 1.グラフ彩色 とは、与えられた色のセットから要素を選んでグラフの頂点にラベルを付けること、あるいは同等に、頂点を「色クラス」と呼ばれる部分集合に分割し、それぞれの部分集合にいずれかの色を割り当てることです。 2.一部の著者は、特に条件を付けずに「彩色」という言葉を、各辺の端点に異なる色を割り当てる適切な彩色という意味で使用しています。グラフ彩色では、できるだけ少ない色数で適切な彩色を見つけることが目標です。例えば、二部グラフ は2色のみで彩色できるグラフであり、四色定理は、すべての 平面グラフは 最大4色で彩色できると述べています。グラフがk 色で（適切に）彩色されている場合、そのグラフはk 彩色されていると言われ、それが可能な場合はk 彩色可能またはk彩色可能と呼ばれます。 3.エッジ彩色 （同じ終点を持つ2つのエッジが同じ色を共有しないようにエッジを彩色する）、リスト彩色 （各頂点が使用可能な色のサブセットに制限された適切な彩色）、非巡回彩色 （2色で彩色された部分グラフはすべて非巡回）、共彩色（すべての色クラスが独立集合またはクリークを誘導する）、完全彩色 （2つの色クラスはすべてエッジを共有する）、および全彩色 （エッジと頂点の両方が彩色される）など、多くの彩色方法が研究されてきました。 4.グラフの彩色数は、縮退度を 1に足した数です。これは、グラフの縮退度順序に貪欲彩色アルゴリズムを適用した場合、最大でこの数の色しか使用されないことに由来します。 通勤グラフ 群 またはより一般的には半群 の可換グラフ とは、頂点が群/半群の要素であり、可換な要素の任意のペア間にエッジが存在する 無向グラフである（つまり、 xy = yx x y 比較可能性 無向グラフは、その頂点が半順序集合 の要素であり、かつ、半順序において比較可能な2つの頂点が隣接している場合に、比較可能性グラフ と呼ばれる。言い換えれば、比較可能性グラフとは、推移的な向きを持つグラフのことである。その他多くのグラフのクラスも、特殊なタイプの半順序の比較可能性グラフとして定義できる。 補体 補グラフ G ¯ {\displaystyle {\bar {G}}} Gの は、 G と同じ頂点集合を持つ別のグラフであり、 G で隣接していない 2 つの頂点ごとに辺があります。 完了 1.完全グラフ とは、すべての2つの頂点が隣接しているグラフのことです。つまり、存在しうるすべての辺が存在します。n個の頂点を持つ完全グラフは、しばしば K nと表記されます。 完全 部グラフ とは、頂点の分割の反対側にあるすべての2つの頂点が隣接しているグラフのことです。分割の一方の側にa個の 頂点、もう一方の側にb個の頂点を持つ完全二部グラフは、しばしば K a , b 完全多部グラフ にも拡張されています。完全多部グラフとは、頂点が2つ以上の部分集合に分割され、異なる部分集合のすべての頂点のペアが隣接しているグラフのことです。部分集合の頂点の数がa 、 b 、 c 、...である場合、このグラフは K a , b , c , ... 2.与えられたグラフの完全化とは、何らかの望ましい性質を持つスーパーグラフのことである。例えば、弦グラフの完全化 とは、弦グラフであるスーパーグラフのことである。 3.完全一致は完全一致 の同義語です。一致を 4.完全彩色 とは、各色のペアが少なくとも1つの辺の端点に使用される適切な彩色のことです。最小色の彩色はすべて完全彩色ですが、より多くの色を使用する完全彩色も存在する場合があります。グラフの無彩色数は、完全彩色における最大色の数です。 5.グラフの完全不変量は、非同型グラフに対して異なる値をとる不変量である標準形と同義である。 成分 グラフの連結成分とは、最大連結部分グラフのことです。この用語は、 二重連結成分 、三重連結成分、 強連結成分 など、より高い次数の接続性を持つグラフの頂点の最大部分グラフまたは部分集合にも使用されます。 結露 有向グラフG の縮約は、 G の各強連結成分に対応する頂点を 1 つ持ち、 G 内の少なくとも 1 つのエッジの 2 つの端点を含む成分のペアを接続するエッジを持つ有向非巡回グラフである。 円錐 普遍頂点 を含むグラフ。接続する 接続 接続済み 連結グラフ とは、頂点のペアごとにパスの端点が存在するグラフのことです。より高度な連結性としては、有向グラフにおける強連結性（任意の2つの頂点間で、一方から他方へのパスが双方向に存在する）、k 頂点連結グラフ（ k 個未満の頂点を削除してもグラフが分断されない）、およびk 辺連結グラフ（ k 個未満の辺を削除してもグラフが分断されない）などがあります。接続されたコンポーネント コンポーネント 収縮 辺の縮約 は、グラフから辺を削除し、その辺が以前接続していた2つの頂点を結合する基本的な操作です。頂点の縮約（頂点識別とも呼ばれる）はこれに似ていますが、2つの頂点は必ずしも辺で接続されているとは限りません。パスの縮約は、パスの端点間に1つの辺を形成するように縮約するパス内の辺の集合に対して行われます。辺の縮約の逆操作は頂点の分割です。コンバース 逆グラフは転置グラフの同義語です。転置を コア 1. k-コアとは、次数が k 未満のすべての頂点と、以前の削除後に次数がk 未満になったすべての頂点を削除することによって形成される誘導部分グラフです。 縮退を 2.コアと は、グラフGからG 自身へのすべてのグラフ準同型写像 が同型写像となるようなグラフG のことである。 3.グラフG のコアとは、 G から Hへの準同型写像と G からH への準同型写像が存在するような最小グラフH のことである。Hは同型写像を除いて一意である。H は G の誘導部分グラフとして表現でき、自己準同型写像がすべて同型写像であるという意味でコアである。 4.グラフマッチングの理論では、グラフのコアは、すべての最大マッチングの和集合として形成される、そのダルマージ・メンデルゾーン分解の一側面である。 コツリー 1.スパニングツリー の補集合。 2.コグラフ を記述するために使用される根付き木構造。各コグラフ頂点は木の葉であり、木の各内部ノードには0または1のラベルが付けられ、2つのコグラフ頂点は、木の中でそれらの最小共通祖先に1のラベルが付けられている場合に限り隣接している。 カバー 頂点被覆と は、グラフ内のすべての辺に接続する頂点の集合のことです。辺被覆 とは、グラフ内のすべての頂点に接続する辺の集合のことです。グラフの部分グラフの集合が、頂点ごとおよび辺ごとにその集合 を合わせたものが元のグラフと等しい場合、その部分グラフの集合はそのグラフを被覆していると言います。 致命的 ある性質に対する臨界グラフとは、その性質を持つグラフでありながら、1つの頂点を削除して形成されるすべての部分グラフがその性質を持たないグラフのことである。例えば、因子臨界グラフ とは、すべての頂点削除に対して完全マッチング（1因子）を持つが、（頂点数が奇数であるため）それ自体は完全マッチングを持たないグラフのことである。性質を持たないが、すべての1頂点削除によってその性質を持つグラフに対して用いられるhypo-と比較されたい。 キューブ キュービック 1.立方体グラフ ：立方体の頂点と辺からなる8つの頂点を持つグラフ。 2.ハイパーキューブグラフ ：キューブグラフの高次元への一般化。 3.折り畳まれた立方体グラフ 。ハイパーキューブから、対応する接続された反対側の頂点を追加することによって形成されます。 4.半立方体グラフ 、ハイパーキューブグラフの半分の正方形。 5.部分立方体 、ハイパーキューブの距離保存部分グラフ。 6.グラフG の立方体はグラフのべき乗 G 3 7.立方グラフ。3 正則 グラフの別名で、各頂点に3つの接続辺があるグラフ。 8.キューブ連結サイクル ：ハイパーキューブの各頂点をサイクルに置き換えることによって形成される立方体グラフ。 カット カットセット カットと は、グラフの頂点を2つの部分集合に分割すること、または、その分割をまたぐ辺の集合（カット集合とも呼ばれる）のことである。ただし、その集合が空でない場合に限る。辺は、両端点が両方の部分集合に含まれる場合に、その分割をまたぐと言われる。したがって、連結グラフからカット集合を取り除くと、グラフは分断される。 カットポイント 関節点 スペースを切り取る グラフのカット空間 は、グラフのカットセットsを要素とし、セットの 差をベクトル加算演算とする GF(2) ベクトル空間である。 サイクル 1.サイクルは 、グラフの一種またはウォーク ツアー 巡回順列と反転は同じサイクルを生成する。重要な特殊なタイプのサイクルには、 ハミルトンサイクル 、誘導サイクル 、周辺サイクル 、およびグラフの周長を 定義する最短サイクルがある。kサイクルは長さ k のサイクルである。たとえば、2 サイクルは二角形 であり、3 サイクルは三角形である。サイクルグラフ は、それ自体が単純サイクルであるグラフである。n 個の頂点を持つサイクルグラフは、一般的に C n 2.サイクル空間 は、グラフ内の単純サイクルによって生成されるベクトル空間 であり、多くの場合2要素の体上に存在するが、他の体上にも存在する。
D DAG 有向非巡回グラフ の略語。有向サイクルを持たない有向グラフのこと。デッキ 単一のグラフG から単一の頂点をあらゆる方法で削除することによって形成されるグラフの多重集合。特に再構成予想 の文脈で用いられる。同様に、単一のエッジをあらゆる方法で削除することによってエッジデッキが形成される。デッキ内のグラフはカード とも呼ばれる。クリティカル ハイポ 分解 ツリー分解 パス分解 ブランチ分解 退化する 退廃 k 退化グラフとは、誘導部分グラフの最小次数が高々k である無向グラフのことです。グラフの退化度 とは、そのグラフがk退化となる最小の k のことです。退化順序とは、各頂点が、その頂点とそれ以降のすべての頂点の誘導部分グラフにおいて最小次数を持つような頂点の順序のことです。k 退化グラフの退化順序では、 各頂点は高々k 個の後続の隣接点を持ちます。退化度は、 k コア数、幅、連結度とも呼ばれ、退化度に 1 を加えた値は彩色数または Szekeres–Wilf 数とも呼ばれます。k退化グラフは、k 誘導 グラフとも呼ばれます。程度 1.グラフの頂点の次数は、その頂点に接続する辺の数です。[ 2 ] グラフ G の 次数(または最大次数) は、その頂点の次数の最大値であり、しばしばΔ ( G ) と表記されます。G の最小次数は、 その頂点の次数の最小値であり、しばしばδ ( G ) と表記されます。次数は、価数 と呼ばれることもあります。Gのv の次数は、 d G ( v ) 、d ( G ) 、またはdeg( v ) と表記されることがあります。総次数は、すべての頂点の次数の合計であり、握手補題 により偶数になります。次数列 は、すべての頂点の次数を大きい順から小さい順に並べたものです。有向グラフでは、入次数 (入ってくる辺の数) と出次数 (出ていく辺の数) を区別することができます。[ 2 ] 2.グラフの準同型度は、最大のクリークマイナーの位数であるハドウィガー数と同義です。 Δ 、δ Δ ( G ) (ギリシャ文字デルタを使用) はG の頂点の最大次数であり、 δ G )次数を 密度 n 個のノードを持つグラフにおいて、密度とは、そのグラフのエッジ数と、 n 個のノードを持つ完全グラフのエッジ数の比のことです。密なグラフ を参照してください。深さ 根付き木におけるノードの深さは、根からそのノードまでのパスにあるエッジの数です。たとえば、根の深さは 0 であり、その隣接ノードの深さは 1 です。これは、ノードのレベルから 1 を引いた値です。ただし、一部の著者は、深さを ノードのレベル と同義語として使用する場合があることに注意してください。 [ 9 ] 直径 連結グラフの直径は、最短経路の最大長です。つまり 、 グラフ内の頂点ペア間の距離の最大値です。グラフのエッジに重みが付けられている場合、重み付き直径は経路に沿ったエッジの重みの合計によって経路長を測定し、重みなし直径はエッジの数によって経路長を測定します。非連結グラフの場合、定義は様々です。直径は無限大と定義される場合もあれば、連結成分の最大直径と定義される場合、あるいは定義されない場合もあります。 ダイヤモンド ひし形グラフ は、4つの頂点と5つの辺を持つ無向グラフである。 切断された 強く 結びついている 断絶している ディゴン 二角形と は、有向グラフまたは多重グラフにおける長さ 2 の単純サイクルです。二角形は、同じ辺を 2 回繰り返す必要があるため、単純無向グラフの定義に反するため、単純無向グラフには出現しませ ん 。 二重音字 有向グラフ の同義語。[ 2 ] ダイパス 有向パス 直接の前任者 与えられた頂点を始点とする有向辺の終点。 直接の後継者 与えられた頂点を始点とする有向辺の始点。 監督 有向グラフとは、辺が1つの頂点から別の頂点へと明確な方向を持つグラフのことです。[ 2 ]混合 グラフ では、有向辺はやはり明確な方向を持ちます。有向辺は弧や矢印とも呼ばれます。 方向付けられた弧 矢印 方向付けられたエッジ 矢印 有向線 矢印 有向パス すべての辺 が 同じ方向 、 x は の 頂点 で 、 x の 頂点 yは x 到達可能 方向 1.グラフ 隣接する 頂点 な関係を 矢印 2.有向パス上 切断 接続 切断されました 接続され 互いに分離している 1. 2つの部分グラフは、辺を共有しない場合は辺が互いに素であり、頂点を共有しない場合は頂点が互いに素である。 2. 2つ以上のグラフの非交和とは、頂点集合と辺集合が対応する集合の非交和となるグラフのことである。 解離数 グラフG の頂点の部分集合が、最大次数が1の 部分グラフ を誘導する場合、その部分集合は解離 と呼ばれる。 距離 グラフ内の任意の2つの頂点間の距離は 、その2つの頂点を端点とする最短経路の長さである。 ドマティック グラフのドマティック分割とは、頂点を支配集合に分割することである。グラフのドマティック数とは、そのような分割における支配集合の最大数である。 圧倒的に 支配集合 とは、グラフ内のすべての頂点を含むか、またはそれらに隣接する頂点の集合のことです。グラフ内のすべての辺に接続する頂点の集合である頂点被覆とは混同しないように注意が必要です。重要な特殊な支配集合の種類としては、独立支配集合（独立集合でもある支配集合）と連結支配集合（連結部分グラフを誘導する支配集合）があります。単一頂点の支配集合は、普遍頂点とも呼ばれます。グラフの支配数とは、最小の支配集合に含まれる頂点の数です。 デュアル 平面グラフG の双対グラフとは、 G の各面に対応する頂点を持つグラフのことである。
E E E ( G )はG のエッジ集合です。エッジ集合を 耳 グラフの耳とは、端点が一致する場合もあるが、それ以外に頂点や辺の重複がないパスのことである。 耳の分解 耳分解 とは、グラフのエッジを耳の列に分割したもので、各耳の端点（最初の耳を除く）は前の耳に属し、各耳の内部点は前の耳には属しません。開いた耳とは、単純なパス（重複する頂点のない耳）のことで、開いた耳分解とは、最初の耳以降の各耳が開いている耳分解のことです。グラフが開いた耳分解を持つのは、それが双連結である場合に限ります。耳は、エッジの数が奇数である場合に奇数と呼ばれ、奇数耳分解とは、各耳が奇数である耳分解のことです。グラフが奇数耳分解を持つのは、それが因子臨界である場合に限ります。 偏心 頂点の離心率とは、その頂点から他のどの頂点までの距離が最も遠い値である。 角 エッジは（頂点とともに）グラフを構成する2つの基本単位の1つです。各エッジには、そのエッジが接続されている2つ（ハイパーグラフの場合はそれ以上）の頂点があり、これらは端点と呼ばれます。エッジは有向または無向です。無向エッジは線とも呼ばれ、有向エッジは弧または矢印とも呼ばれます。無向単純グラフでは、エッジはその頂点の集合として表され、有向単純グラフでは、エッジはその頂点の順序付きペアとして表されます。頂点 x とy を結ぶエッジは、xyと 表記されることがあります。 エッジカット グラフを 分断する の ブリッジ 峡谷 切断エッジ エッジセット 与えられたグラフG のエッジの集合。E ( G ) と表記されることもある エッジのないグラフ 与えられた頂点集合上の辺のないグラフ 、または完全に連結していないグラフとは、辺を一切持たないグラフのことである。これは空グラフと呼ばれることもあるが、この用語は頂点を持たないグラフを指す場合もある。埋め込み グラフ埋め込みと は、グラフを位相空間の部分集合として表現した位相表現であり、各頂点は点として、各辺は曲線として表され、辺の端点は曲線の端点として表され、頂点間または辺間に他の交点はありません。平面グラフ とは、このような埋め込みがユークリッド平面上に存在するグラフであり、トーラスグラフ とは、このような埋め込みがトーラス上に存在するグラフです。グラフの種数とは 、グラフを埋め込むことができる2次元多様体の最小種数です。 空のグラフ 1.空でない頂点集合上の辺のないグラフ 。 2.次数ゼロのグラフ 。頂点も辺もないグラフ。 終わり 無限グラフの端点は 、光線の同値類であり、2つの光線が同値であるとは、両方の光線から無限個の頂点を含む第3の光線が存在する場合をいう。 終点 与えられた辺で結ばれた2つの頂点のうちの1つ、またはウォーク、トレイル、パスの最初または最後の頂点のいずれか。与えられた有向辺の最初の端点はテール、 2番目の端点はヘッド と呼ばれます。 列挙 グラフ列挙と は、与えられたグラフのクラスに属するグラフを、その次数に応じて数える問題である。より一般的には、列挙問題とは、特定の組み合わせオブジェクト（クリーク、独立集合、彩色、全域木など）の数を数える問題、あるいはそのようなオブジェクトをアルゴリズム的に列挙する問題を指す。オイラー オイラーパスと は、グラフのすべての辺をちょうど一度ずつ通る経路のことです。オイラー閉路（オイラーサイクルまたはオイラーツアーとも呼ばれる）とは、すべての辺をちょうど一度ずつ通る閉じた経路のことです。オイラーグラフとは、オイラー閉路を持つグラフのことです。無向グラフの場合、これはグラフが連結であり、すべての頂点の次数が偶数であることを意味します。有向グラフの場合、これはグラフが強連結であり、すべての頂点の入次数と出次数が等しいことを意味します。場合によっては、連結性の要件が緩和され、次数要件のみを満たすグラフがオイラーグラフと呼ばれることもあります。 平 2で割り切れること。例えば、偶数サイクルとは、長さが偶数のサイクルのことである。 エキスパンダー エクスパンダーグラフ とは、辺の拡張、頂点の拡張、またはスペクトル拡張がゼロから離れた範囲に収まるグラフのことである。 拡大 1.グラフG の辺拡張、等周数、またはCheeger 定数は、 G の頂点の最大半分からなる部分集合Sにおいて、 S から出る辺の数とS 内の頂点の数の比の最小値である。 2.グラフGの頂点拡張、頂点等周数、または拡大とは、 G の頂点の最大半分からなる部分集合Sについて、 S の外側にあるが隣接する頂点の数とS 内の頂点の数の最小比のことである。 3.グラフGの一意な隣接点拡張とは、 G の頂点の最大半分のサブセットについて、 S の外側にあるが S 内 の一意な頂点に隣接する頂点の数とS 内の頂点の数の最小比のことである。 4. d 正則グラフG のスペクトル展開は、その隣接行列の最大固有値d と2番目に大きい固有値との間のスペクトルギャップ である。 5.グラフの族は、そのすべてのr 浅いマイナーのエッジと頂点の比がrの関数によって制限されている場合、 有界拡張を持ち、 r の関数が多項式である場合、多項式拡張を持つ。
F 顔 平面グラフ またはグラフ埋め込み において、グラフとは互いに素な、埋め込みの平面または表面の部分集合の連結成分。平面への埋め込みの場合、1つの面を除いてすべての面が有界であり、無限に広がる例外的な面は外側（または無限）面と呼ばれる。要素 グラフの因子とは、全域部分グラフ、つまりグラフのすべての頂点を含む部分グラフのことです。この用語は主に正則部分グラフの文脈で使用されます。k因子とは、 k 正則な因子のことです。特に、1 因子は完全マッチングと同じです。因子臨界グラフとは、任意の1つの頂点を削除すると 1 因子を持つグラフになるグラフのことです。 因数分解 グラフの因数分解 とは、グラフのエッジを因子に分割することであり、k-因数分解とは、 k 個の因子に分割することです。例えば、1- 因数分解とは、各頂点が各色のエッジに接しているという性質を持つエッジ彩色です。 家族 クラス 有限 グラフは、頂点の数と辺の数の両方が有限である場合に有限グラフと呼ばれます。多くの資料では、明示的に述べずにすべてのグラフが有限であると仮定しています。グラフは、各頂点に接続する辺の数が有限である場合に局所的に有限です。無限グラフとは、有限ではないグラフ、つまり頂点の数、辺の数、またはその両方が無限であるグラフのことです。 第一の注文 グラフの一階述語論理 とは、変数がグラフの頂点を表し、2つの頂点が隣接しているかどうかを判定する二項述語が存在する論理形式である。これは、変数が頂点の集合や辺の集合も表すことができる二階述語論理とは区別される。 -フラップ 頂点集合X に対して、Xフラップとは、 X を 削除して形成される誘導部分グラフの連結成分のことです。フラップという用語は、小さな頂点集合をそのフラップにマッピングする関数であるヘイブン の文脈でよく使用されます。サイクルのブリッジ 禁断 禁止グラフ特性 とは、あるグラフ族を、特定の他のグラフを部分グラフ、誘導部分グラフ、またはマイナーとして持たないグラフとして特徴付けるものです。H が部分グラフ、 誘導部分グラフ、またはマイナーとして出現しないグラフの 1 つである場合、H は禁止グラフであると言われます。 強制グラフ 強制グラフとは、グラフ列 G(n) のグラフにおけるH の部分グラフ密度を評価することで、その列が準ランダムで H のことである。 森 フォレストと は、サイクルを持たない無向グラフ（根なし木の非交和）または根付き木の非交和として形成される有向グラフのことである。 フリーエッジ 一致する エッジ ではない。自由頂点 1.マッチングされた エッジ 上 にない頂点 2.一致していない頂点。 フルーツ 1.ロバート・フルヒト 2.フルヒトグラフ 。非自明な対称性を持たない2つの最小の3次グラフのうちの1つ。 3.フルヒトの定理 ：すべての有限群は有限グラフの対称群である。 満杯 誘発された 関数グラフ 関数グラフ とは、すべての頂点の出次数が1である有向グラフのことである。言い換えれば、関数グラフは最大有向擬似森林である。
H H グラフを表すためによく使われる変数で、特に別のグラフがすでにG で表されている場合に使用されます。 H 着色グラフG ( H もグラフである)のH 彩色とは、 Hから G への準同型写像のことである。 H フリーグラフがHフリーであるとは、 H と同型な誘導部分グラフを持たない場合、つまりH が禁止誘導部分グラフである場合をいう。Hフリーグラフとは、 H フリーであるすべてのグラフ (または多くの場合、すべての有限グラフ) の族である。[ 10 ] 三角形フリーグラフとは、 三角形グラフを 部分グラフとして持たないグラフのことである。Hフリー であるという性質は常に遺伝的である。グラフがH と同型なマイナーを持たない場合、H マイナーフリーである。 ハドウィガー 1.ヒューゴ・ハドウィガー 2.グラフのハドウィガー数は 、グラフの最大の完全マイナーの位数です。これは、縮約クリーク数または準同型次数とも呼ばれます。 3.ハドウィガー予想 とは、ハドウィガー数が彩色数より小さくなることはないという予想である。 ハミルトニアン ハミルトン路 またはハミルトン閉路とは、単純全域路または単純全域閉路のことで、グラフ内のすべての頂点をちょうど一度ずつ通過するものです。グラフは、ハミルトン閉路を含む場合、ハミルトングラフであり、ハミルトン路を含む場合、トレース可能グラフです。 避難所 k-ヘイブンと は、k個 未満の頂点を持つ任意の集合 X をそのフラップのいずれかにマッピングする関数であり、多くの場合、追加の整合性条件を満たします。ヘイブンの次数はk です。ヘイブンは、有限グラフの木幅や、無限グラフの端点およびハドウィガー数を特徴付けるために使用できます。 身長 1.根付き木のノードの高さ は、根から離れる方向（つまり、ノードの深さが厳密に増加する）に、そのノードから葉まで伸びる最長パスの辺の数です。 2.根付き木の高さ は、その根の高さです。つまり、木の高さ は、根から葉まで伸びる最長の経路における辺の数です。 3.有向非巡回グラフ の高さは 、このグラフにおける有向パスの最大長です。 遺伝性 グラフの遺伝的性質 とは、誘導部分グラフの下で閉じている性質のことです。つまり、グラフG が遺伝的性質を持つ場合、G のすべての誘導部分グラフも遺伝的性質を持つ必要があります。単調性 マイナー閉性 （マイナーの下で閉じている）と比較してください。 六角形 辺がちょうど6本、頂点がちょうど6個からなる単純なサイクル。 穴 穴とは、長さが４以上の誘導サイクルのことです。奇数穴とは、長さが奇数の穴のことです。反穴とは、補グラフがサイクルであるような、次数が４の誘導部分グラフのことです。言い換えれば、補グラフにおける穴のことです。この用語は主に完全グラフの文脈で使用されます。完全グラフは、強完全グラフ定理 によって、奇数穴や奇数反穴を持たないグラフとして特徴付けられます。穴のないグラフは、弦グラフ と同じです。 準同型同値 2つのグラフは、それぞれのグラフから他方のグラフへの2つの準同型写像が存在する場合に、準同型であるという。 準同型 1.グラフ準同型 写像とは、あるグラフの頂点集合から別のグラフの頂点集合への写像であり、隣接する頂点同士を写像するものです。この種のグラフ間の写像は、グラフ理論の圏論的アプローチにおいて最も一般的に用いられています。適切なグラフ彩色も、完全グラフへの準同型写像として同様に記述できます。 2.グラフの準同型度は、最大のクリークマイナーの位数であるハドウィガー数と同義です。 ハイパーアーク ソースとターゲットの集合を持つ有向ハイパーエッジ。 ハイパーエッジ ハイパーグラフ は ハイパーキューブ ハイパーキューブグラフとは、幾何学的 ハイパーキューブ の頂点と辺から構成されるグラフのことである。 ハイパーグラフ ハイパーグラフ とは、グラフを一般化したもので、各辺（この文脈ではハイパーエッジと呼ばれる）が2つ以上の端点を持つことができるという特徴を持つ。 低 この接頭辞は、グラフの特性と組み合わせることで、その特性を持たないが、1 つの頂点を削除して形成されるすべての部分グラフがその特性を持つグラフを示します。たとえば、低ハミルトングラフ は、ハミルトン閉路を持たないが、すべての 1 つの頂点の削除によってハミルトン部分グラフが生成されるグラフです。特性を持つが、すべての 1 つの頂点の削除によって特性を持たないグラフに使用されるcritical と比較してください。 [ 11 ]
私 入次数 有向グラフにおける入力エッジの数。次数 入射 グラフにおける接続とは、頂点が辺の端点となるような頂点と辺のペアのことである。 発生率マトリックス グラフの接続行列 とは、行がグラフの頂点によってインデックス付けされ、列が辺によってインデックス付けされた行列であり、頂点i と辺jが接続している場合は行 i と列j のセルに 1 が、そうでない場合は 0 が入ります。 事件 （形容詞）辺とその端点の間の関係。[ 2 ] 比較不可能性 非比較グラフは比較グラフ の補グラフです。比較性を 独立した 1.独立集合 とは、辺のない部分グラフを誘導する頂点の集合です。安定集合またはコクリークとも呼ばれます。独立数 α ( G )は、 最大独立集合 のサイズです。 2.グラフのグラフィックマトロイド では、対応する部分グラフが木または森である場合、辺のサブセットは独立である。二重円マトロイドでは、対応する部分グラフが 擬似森で ある場合、辺のサブセットは独立である。 無関心 無差別グラフは 、適切な区間グラフまたは単位区間グラフの別名です。適切な 誘発された グラフの誘導部分グラフ または完全部分グラフとは、頂点のサブセットと、そのサブセットに両端点を持つすべての辺から構成される部分グラフのことです。特殊なケースとして、誘導パス と誘導サイクル があり、これらは誘導部分グラフがパスまたはサイクルであるものです。 帰納的 退廃的 無限 無限グラフとは、有限ではないグラフのことです。有限グラフ 内部 パスまたはツリーの頂点は、葉でない場合、つまり次数が1より大きい場合、内部頂点と呼ばれます。2つのパスは、最初と最後の頂点を除いて共通の頂点を持たない場合、内部的に互いに素である（独立して いると言う人もいます）。 交差点 1. 2つのグラフの共通部分は、それらの最大の共通部分グラフであり、両方のグラフに属する頂点と辺によって形成されるグラフです。 2.交差グラフ とは、頂点が集合または幾何学的オブジェクトに対応し、対応する 2 つの集合またはオブジェクトが空でない共通部分を持つ場合にのみ、2 つの頂点間にエッジが存在するグラフです。いくつかのグラフのクラスは、特定の種類のオブジェクトの交差グラフとして定義できます。たとえば、弦グラフ ( 木のサブツリーの交差グラフ)、円グラフ (円の弦の交差グラフ)、区間グラフ (直線の区間の交差グラフ)、線グラフ (グラフのエッジの交差グラフ)、クリークグラフ (グラフの最大クリークの交差グラフ) などです。すべてのグラフは、ある集合族の交差グラフであり、この集合族はグラフの交差表現と呼ばれます。グラフGの 交差数は、 G の任意の交差表現における要素の総数の最小値です。 間隔 1.区間グラフは、 直線の区間 の交点グラフ です。 2.グラフにおける区間[ u , v ]は、 uから v へのすべての最短経路の和集合です。 3.インターバル厚さはパス幅 不変 財産 逆矢印 別の矢印 方向 （y 、x ） は矢印（x 、y ） の反転矢印です。孤立した グラフの孤立頂点とは、次数がゼロの頂点、つまり接続する辺を持たない頂点のことである。[ 2 ] 同型 2つのグラフは、それらの間に同型写像が存在する場合に同型であると言います。同型写像を 同型性 グラフ同型性 とは、あるグラフの頂点と辺が、別のグラフの頂点と辺と一対一に対応する関係性を保持する写像のことである。このように関連付けられた2つのグラフは同型であると言われる。 等周 展開図を 地峡 グラフから切り離される辺という意味での「橋」
J 参加する 2つのグラフの結合は、それらの非交和から、一方のグラフの各頂点から他方のグラフの各頂点へ辺を追加することによって形成されます。言い換えれ ば
L L L ( G )はG の線グラフ です。線グラフ ラベル 1.グラフの頂点または辺に関連付けられた情報。ラベル付きグラフとは、頂点または辺にラベルが付与されたグラフのことです。グラフのどのオブジェクトにラベルが付与されているかを指定するために、「頂点ラベル付き」 または「辺ラベル付き」という用語が使用されることがあります。 グラフのラベル付けと は、特定の制約の下でグラフにラベルを割り当てる、いくつかの異なる問題を指します。ラベルを色として解釈するグラフ彩色も参照してください。 2.グラフ列挙 の文脈では、グラフの頂点が互いに区別可能な場合、それらの頂点はラベル付けされていると言われます。例えば、頂点とグラフの次数までの整数との間に1対1の対応関係を固定することで、これを実現できます。頂点にラベルが付けられている場合、互いに同型であるグラフ（ただし頂点の順序が異なる）は別々のオブジェクトとしてカウントされます。一方、頂点にラベルが付けられていない場合、互いに同型であるグラフは別々にカウントされません。 葉 1.葉頂点または垂下頂点（特に木構造において）とは、次数が1で ある頂点のことである。葉辺または垂下辺とは、葉頂点をその唯一の隣接頂点に接続する辺のことである。 2.木の葉パワー とは、頂点が木の葉であり、辺が木の中での距離が与えられた閾値以下である葉同士を結んでいるグラフのことである。 長さ 重み付けされていないグラフでは、サイクル、パス、またはウォークの長さは、それが使用するエッジの数です。重み付けされたグラフでは、代わりに、使用するエッジの重みの合計になる場合があります。長さは、グラフ内の2つの頂点間の最短パス 、周長 （最短サイクル長）、および最長パスを定義するために使用されます。 レベル 1.これはノードの深さプラス 1 ですが、一部の [ 12 ] はこれを深さ の同義語として定義しています。根付きツリーにおけるノードのレベルは、根からノードまでのパスにあるノードの数です。たとえば、根のレベルは 1 であり、その隣接ノードのいずれかのレベルは 2 です。 2.同じレベルまたは深さを持つすべてのノードの集合。[ 12 ] ライン 無向辺の同義語。グラフGの 線グラフ L ( G )は、 G の各辺に対応する頂点と、 G で端点を共有する各辺のペアに対応する辺を持つグラフです。 リンケージ 退廃 リスト 1.隣接リスト は、グラフアルゴリズムで使用するためのグラフのコンピュータ表現です。 2.リスト彩色 とは、各頂点に使用可能な色のリストがあるグラフ彩色の一種です。 地元 グラフの局所的性質とは、グラフ内の頂点の近傍 のみによって決定される性質のことである。例えば、グラフのすべての近傍が有限である場合、そのグラフは局所的に有限である。 ループ ループまたは自己ループとは、両端の頂点が同じ頂点である辺のことです。これは長さ1のサイクルを形成します。単純グラフでは 、 このようなループは許容されません。
M 倍率 頂点拡張 マッチング マッチングと は、どの2つの辺もどの頂点も共有しない辺の集合です。頂点は、マッチング内の辺の端点のいずれかである場合、マッチングされている、または飽和していると言います。完全マッチング または完全一致とは、すべての頂点が一致するマッチングのことです。これは1因子とも呼ばれ、次数が偶数の場合にのみ存在します。次数が奇数のグラフにおけるほぼ完全マッチングとは、1つの頂点を除くすべての頂点が飽和しているマッチングのことです。最大マッチング とは、可能な限り多くの辺を使用するマッチングのことです。グラフG のマッチング数α G )最大マッチング とは、これ以上辺を追加できないマッチングのことです。 最大 1.与えられたグラフG の部分グラフが特定の性質に関して極大であるとは、その部分グラフがその性質を持ち、かつ、その部分グラフのスーパーグラフで、かつG の部分グラフでもある他のスーパーグラフが同じ性質を持たない場合をいう。つまり、その部分グラフは、その性質を持つ部分グラフの中で極大な要素 である。例えば、極大クリーク とは、より大きな完全部分グラフに拡張できない完全部分グラフのことである。「極大」という言葉は「最大」と区別する必要がある。極大部分グラフは常に極大であるが、その逆は必ずしも成り立たない。 2.ある性質を持つ単純グラフは、頂点集合を変えずにそれ以上辺を追加してもグラフの単純性と性質の両方が維持されない場合、その性質に関して極大であると言います。例えば、極大平面グラフ とは、それ以上辺を追加すると非平面グラフになってしまうような平面グラフのことです。 最大 与えられたグラフG の部分グラフは、特定の性質に関して最大であるとは、その性質を持つすべての部分グラフの中で、その部分グラフが（順序またはサイズで）最大である場合をいう。例えば、最大クリーク とは、与えられたグラフにおける最大のクリークのいずれかを指す。 中央値 1.頂点の3つ組の中央値、すべての頂点のペア間の最短経路に属する頂点、特に中央値グラフとモジュラーグラフ において。 2.メディアングラフ とは、3つの頂点ごとに一意のメディアン値を持つグラフのことです。 メイニエル 1.アンリ・メイニエル、フランスのグラフ理論家。 2.メイニエルグラフ とは、長さが5以上のすべての奇数サイクルに少なくとも2つの弦が存在するグラフのことである。 ミニマル 与えられたグラフの部分グラフが特定の性質に関して最小であるとは、その部分グラフがその性質を持ち、かつその部分グラフの真部分グラフには同じ性質を持つものが存在しない場合をいう。つまり、その部分グラフは、その性質を持つ部分グラフの中で最小の要素 である。 最低カット カットセット 。 最大フロー最小カット定理 によって特徴付けられる。マイナー グラフH が別のグラフGの マイナー であるとは、G から辺または頂点を削除し、 G の辺を縮約することによってH が得られる場合をいう。H が浅いマイナーであるとは、 H の頂点を形成するために縮約されたG の部分グラフの直径がすべて小さいような方法でマイナーとして形成できる場合をいう。Hが G の位相的マイナー であるとは、G が H の細分 である部分グラフを持つ場合をいう。グラフがH を マイナーとして持たない場合をH マイナーフリーとする。グラフの族がマイナーに関して閉じている場合をマイナー閉じであるとは、マイナーに関して閉じている族をいう。ロバートソン・シーモアの定理は、 マイナー閉じた族が有限個の禁止 混合 混合グラフ とは、有向辺と無向辺の両方を含む可能性のあるグラフのことである。モジュラー 1.モジュラーグラフ とは、各頂点の3つ組が、その3つ組のすべてのペア間の最短経路に属する少なくとも1つの中央頂点を持つグラフのことです。 2.モジュラー分解とは 、グラフを部分グラフに分解し、その部分グラフ内のすべての頂点が、同じ方法でグラフの残りの部分に接続することである。 3.グラフクラスタリングのモジュール性 、つまりクラスタ間エッジの数と期待値との差。 単調 グラフの単調性とは、部分グラフに関して閉じている性質のことです。つまり、グラフG が単調性を持つ場合、G のすべての部分グラフも単調性を持つ必要があります。遺伝的 マイナー閉性 （マイナーに関して閉じている）と比較してください。 ムーアグラフ ムーアグラフ とは、ムーア限界が厳密に満たされる正則グラフのことである。ムーア限界とは、グラフの次数、直径、および順序を関連付ける不等式であり、エドワード・F・ムーア によって証明された。すべてのムーアグラフは檻である。 マルチグラフ 多重グラフ とは、複数の隣接関係（そして多くの場合、自己ループ）を許容するグラフであり、単純である必要のないグラフである。多重隣接 多重隣接または多重エッジとは、すべて同じ端点（有向グラフの場合は同じ方向）を持つ複数のエッジの集合のことです。複数のエッジを持つグラフは、しばしば多重グラフと呼ばれます。 多重度 辺の多重度とは、多重隣接関係にある辺の数のことである。グラフの多重度とは、そのグラフに含まれる任意の辺の最大多重度のことである。
N N 1.オープンネイバーフッドとクローズドネイバーフッドの表記については、ネイバーフッド 2.小文字のn は、（特にコンピュータサイエンスにおいて）与えられたグラフの頂点の数を表すためによく使用されます。 近所の人 近所の人 特定の頂点に隣接する頂点。 近所 近所 頂点v の開近傍（または近傍）とは、 v に隣接するすべての頂点によって誘導される部分グラフのことです。閉近傍も同様に定義されますが、v 自体も含まれます。グラフG におけるvの開近傍は N G ( v ) またはN ( v ) と表記され、閉近傍はN G [ v ] またはN [ v ] と表記されます。近傍の開性または閉性が指定されていない場合は、開近傍であるとみなされます。 ネットワーク ノードやエッジに属性（例えば名前）が関連付けられたグラフ。 ノード 頂点 非エッジ 非辺または反辺とは、隣接していない頂点のペアのことであり、補グラフの辺にあたる。 ヌルグラフ 空のグラフ
O 奇数 1.奇数サイクルとは、長さが奇数のサイクルのことです。非二部グラフの奇数周長は 、そのグラフの最短奇数サイクルの長さです。奇数穴とは、奇数サイクルの特殊なケースで、誘導型であり、かつ4つ以上の頂点を持つものです。 2.奇数頂点とは、次数が奇数である頂点のことである。握手補題 によれば、すべての有限無向グラフは偶数個の奇数頂点を持つ。 3.奇数耳とは、奇数個のエッジを持つ単純なパスまたは単純なサイクルであり、因子臨界グラフの奇数耳分解で使用されます。耳を 4.奇数弦とは、偶数サイクルにおいて奇数の距離にある2つの頂点を結ぶ辺のことです。奇数弦は、強弦グラフ を定義するために使用されます。 5.奇数グラフは クネーザーグラフ の特殊なケースであり、(2 n − 1 ) 個の要素からなる集合の各( n − 1) 個の要素からなる部分集合に対して 1 つの頂点を持ち、対応する集合が互いに素である場合に 2 つの部分集合を結ぶ辺を持ちます。 開ける 1.近隣地域 2.ウォーク 注文 1.グラフG の次数は、その頂点の数、| V ( G )| で表されます。この値を表すのに変数n がよく用いられます。辺の数であるsizeも参照してください。 2.グラフの論理 の一種。一階述語論理 二階述語論理 3.グラフの順序または順序付けとは、その頂点をシーケンスに並べたものであり、特にトポロジカル順序付け （すべての辺が順序内の前の頂点から後の頂点に向かう有向非巡回グラフの順序）および縮退順序付け （各頂点が、その頂点とそれ以降のすべての頂点の誘導部分グラフにおいて最小次数を持つ順序）の文脈で用いられます。 4.避難所またはイバラの順序については、避難所 イバラを 方向 指向性 1.無向グラフの向き付けと は、その辺に方向を割り当てて有向グラフにすることである。向き付けされたグラフとは、向きが割り当てられたグラフのことである。例えば、多木 は向き付けされた木である。有向木（樹状構造）とは異なり、辺の方向の一貫性は要求されない。その他の特殊な向き付けには、トーナメント（ 完全グラフの向き付け） 、強 連結の向き付け、非巡回向き付け 、オイラー向き付け 、推移的閉の向き付けなどがある。 2.有向グラフ。一部の著者は、有向グラフ の同義語として使用しています。 出次数 学位 外側 顔を 外平面 外平面グラフ とは、平面に埋め込むことができる（交差のない）グラフであり、すべての頂点がグラフの外側の面上に位置する。
P 親 根付き木において、頂点v の親とは、根に向かう方向の辺に沿ってv に隣接する頂点のことである。 パス パスは 、その発生源に応じて、ウォークまたは頂点の重複がなく、結果として辺も重複しないウォーク（単純パスとも呼ばれる）のいずれかになります。重要な特殊ケースとしては、誘導パス と最短パス があります。 経路分解 グラフG のパス分解 とは、基となる木がパスである木分解のことです。その幅は、木分解と同様に、最大のバッグのサイズより 1 小さい値として定義されます。G の任意のパス分解の最小幅は、G の パス幅です。 パス幅 グラフG のパス幅は、 G のパス分解の最小幅です。また、 G の区間完成のクリーク数で定義することもできます。パス幅は常にG の帯域幅と木幅の間にあります。パス幅は、区間厚さ、頂点分離数、またはノード探索数とも呼ばれます。 ペンダント 葉を 完璧 1.完全グラフ とは、誘導部分グラフの彩色数がクリーク数と等しいグラフのことである。完全グラフ定理 と強完全グラフ定理は、 完全グラフに関する2つの定理であり、前者はその補グラフも完全グラフであることを証明し、後者はそれらが奇数ホールや反ホールを持たないグラフであることを証明している。 2.完全順序付け可能グラフ とは、頂点をある順序で並べることができ、その順序を用いた貪欲彩色アルゴリズムによって、誘導されるすべての部分グラフが最適に彩色されるようなグラフのことである。完全順序付け可能グラフは、完全グラフのサブクラスである。 3.完全マッチング とは、すべての頂点を飽和させるマッチングのことです。マッチングを 4.完全1因子分解 とは、グラフのエッジを完全マッチングに分割し、各2つのマッチングがハミルトン閉路を形成することである。 周辺 1.周辺サイクル または非分離サイクルとは、ブリッジが最大で1つしかないサイクルのことです。 2.周辺頂点とは、離心率 ピーターセン 1.ユリウス・ペテルセン （1839年 - 1910年）、デンマークのグラフ理論家。 2.ピーターセングラフ 。10個の頂点と15個の辺を持つグラフで、反例としてよく用いられる。 3.橋のないすべての3次グラフには完全マッチングが存在するというピーターセンの定理。 平面 平面グラフとは、ユークリッド平面に 埋め込まれた グラフのことです。平面グラフとは、特定の埋め込みが既に決定されている平面グラフのことです。k-平面グラフとは、各辺の交点が最大で k個 である平面上に描画できるグラフのことです。 ポリツリー ポリツリーと は、有向木の一種であり、言い換えれば、基となる無向グラフが木構造である有向非巡回グラフのことである。 力 1.グラフG のグラフ冪 G k G において距離が最大でk である場合に、G k 葉冪は これと密接に関連する概念で、木の冪から、木の葉によって誘導される部分グラフを取ることによって得られます。 2.パワーグラフ分析は 、ネットワーク内のクリーク、バイクリーク、スターを識別することによって複雑なネットワークを分析する方法です。 3.スケールフリーネットワーク の次数分布 におけるべき乗法則 とは、ある次数を持つ頂点の数が、その次数のべき乗に比例するという現象である。 前任者 有向パスにおいて 、 プライム 1.素数グラフ は代数群 から定義され、群の位数を割り切る各素数 に対応する頂点を持つ。 2.モジュラー分解 の理論では、素グラフとは非自明なモジュールを持たないグラフのことである。 3.分割 理論において、分割集合が完全二部グラフであるような分割とは、分割を持たないグラフのことである。分割による最大分解の商グラフはすべて、素グラフ、スターグラフ、または完全グラフである。 4.グラフの直積 における素グラフとは、それ自体が積ではない連結グラフのことである。すべての連結グラフは、素グラフの直積に一意的に分解できる。 ちゃんとした 1.真部分グラフとは、全体グラフに対して少なくとも1つの頂点または辺を削除した部分グラフのことです。有限グラフの場合、真部分グラフは全体グラフと同型になることはありませんが、無限グラフの場合は同型になることがあります。 2.適切な彩色とは、グラフの頂点に色を割り当てること（彩色）であり、各辺の端点に異なる色を割り当てます。色を 3.適切な区間グラフ または適切な円弧グラフとは、区間または円弧（それぞれ）の集合の交差グラフであり、どの区間または円弧も他の区間または円弧を含まないものです。適切な区間グラフは、単位区間グラフ（常に単位区間で表現できるため）または無差別グラフとも呼ばれます。 財産 グラフ特性 とは、あるグラフでは真となり、別のグラフでは偽となるような性質であり、ラベルなどの付随情報ではなく、グラフ構造のみに依存します。グラフ特性は、グラフのクラス（特定の特性を持つグラフ）という観点からも表現できます。より一般的には、グラフ特性は、グラフのサイズ、次数、次数列などの付随情報に依存しないグラフの関数である場合もあります。このような特性のより一般的な定義は、グラフの不変量とも呼ばれます。 擬似森林 擬似森林 とは、各連結成分が最大で1つのサイクルを持つ無向グラフ、または各頂点が最大で1つの出辺を持つ有向グラフのことである。擬似グラフ 擬似グラフとは、自己ループを許容するグラフまたは多重グラフのことである。
R 半径 グラフの半径とは、任意の頂点の最小離心率の ラマヌジャン ラマヌジャングラフ とは、スペクトル展開が最大となるグラフのことである。つまり、隣接行列の2番目に大きい固有値が最大でd であるような正則グラフである。 2 d − 1 {\displaystyle 2{\sqrt {d-1}}} レイ 無限グラフにおける光線とは、端点がちょうど1つだけ存在する無限の単純経路のことである。グラフの端点は、光線の同値類である。 到達可能性 グラフ内の1つの 頂点 到達可能 到達可能性が 頂点 yは、 x y 経路 x 認識できる 再構成予想 の文脈において、グラフの性質は、その真偽がグラフのデッキから判断できる場合に認識可能である。多くのグラフの性質は認識可能であることが知られている。再構成予想が真であれば、すべてのグラフの性質は認識可能である。再建 再構成予想 とは、無向グラフGは、その デッキ（ G から1つの頂点をあらゆる可能な方法で取り除くことによって形成されるグラフの多重集合）によって一意に決定されるというものである。この文脈において、再構成とは、そのデッキからグラフを形成することである。 矩形 ちょうど4つの辺と4つの頂点からなる単純なサイクル。 通常 グラフは、すべての頂点の次数がdであるとき、 d- 正則である。正則グラフ とは、あるdに対して d- 正則であるグラフのことである。 レギュラートーナメント 正規トーナメントとは、すべての頂点において入次数と出次数が等しいトーナメントのことである。 逆行する 転置を 根 1.グラフ、特に有向木や根付きグラフ における指定された頂点。 2.グラフのべき乗 の逆演算：グラフGの k 乗根とは、同じ頂点集合上の別のグラフであり、2 つの頂点がG 内で隣接しているのは、根においてそれらの距離がk 以下である場合に限る。
S 飽和 一致する項目 検索番号 ノード検索番号はパス幅 2次 グラフの 二階述語論理は、変数が頂点、辺、頂点の集合、そして（場合によっては）辺の集合を表すことができる論理形式です。この論理には、頂点と辺が隣接しているかどうか、また頂点または辺が集合に属しているかどうかを判定する述語が含まれます。変数が頂点のみを表すことができる一階述語論理とは区別されます。自己ループ ループ 分離頂点 関節点 分離番号 頂点分離数はパス幅 兄弟 根付き木において、頂点vの兄弟とは、 v と同じ親頂点を持つ頂点のことである 。 単体頂点 単体頂点とは、その閉近 傍が クリーク 単純 1.単純グラフ とは、ループがなく、多重隣接関係もないグラフのことです。つまり、各辺は2つの異なる端点を結び、どの2つの辺も同じ端点を持ちません。単純辺とは、多重隣接関係に含まれない辺のことです。多くの場合、特に指定がない限り、グラフは単純グラフであるとみなされます。 2.単純パスまたは単純サイクルとは、重複する頂点がなく、したがって重複する辺もないパスまたはサイクルのことです。 シンク 有向グラフにおけるシンクとは、出ていく辺を持たない頂点（出次数が0の頂点）のことである。 サイズ グラフG のサイズは、そのエッジの数、| E ( G )| です。[ 13 ] m がよく使用されます。頂点の数であるorderも参照してください。 スモールワールドネットワーク スモールワールドネットワーク とは、ほとんどのノードが互いに隣接していないが、ほとんどのノードは他のすべてのノードから少数のホップまたはステップで到達できるグラフである。具体的には、スモールワールドネットワークは、ランダムに選択された2つのノード間の典型的な距離L （必要なステップ数）が、ネットワーク内のノード数N の対数に比例して増加するグラフとして定義される[ 14 ]。 皮肉 スナークと は、彩色指数が4である、単純で連結された、橋のない3次グラフのことである。 ソース 有向グラフにおける始点とは、入ってくる辺を持たない頂点（入次数が0の頂点）のことである。 空間 代数的グラフ理論 では、グラフには二元体 上の複数のベクトル空間 が関連付けられる。それぞれのベクトル空間は、辺または頂点の集合をベクトルとして持ち、集合の対称差をベクトル和演算とする。 辺空間 はすべての辺の集合からなる空間であり、頂点空間は すべての頂点の集合からなる空間である。カット空間 は辺空間の部分空間であり、その要素としてグラフのカット集合を持つ。サイクル空間は 、オイラー全域部分グラフを要素として持つ。スパナ スパナーとは、最短経路距離が密なグラフやその他の距離空間における最短経路距離に近似する（通常は疎な）グラフのことです。バリエーションとしては、幾何学的スパナー（ 頂点が幾何学的空間内の点であるグラフ） 、ツリースパナー （距離がグラフの距離に近似するグラフの全域木）、グラフスパナー（距離が元のグラフの距離に近似する密なグラフの疎な部分グラフ）などがあります。グリーディスパナーとは、グリーディアルゴリズムによって構築されたグラフスパナーのことで、一般的には最短から最長まで全ての辺を考慮し、距離近似を維持するために必要な辺のみを残します。 にまたがる 部分グラフは、与えられたグラフのすべての頂点を含む場合に全域グラフと呼ばれます。重要な例としては、全域木 （全域部分グラフが木であるもの）と完全マッチング（全域部分グラフがマッチングであるもの）が挙げられます。全域部分グラフは、特に（ただしこれに限らないが）正則な場合に、 因子 とも呼ばれます。 疎 疎グラフ とは、頂点の数に対して辺の数が少ないグラフのことである。定義によっては、この性質は与えられたグラフのすべての部分グラフにも当てはまるべきである。スペクトル スペクトラム グラフのスペクトルとは、その隣接行列の固有値の集合のことである。 スペクトルグラフ理論は、 スペクトルを用いてグラフを分析するグラフ理論の一分野である。スペクトル展開 スプリット 1.分割グラフ とは、頂点をクリークと独立集合に分割できるグラフのことである。関連するグラフのクラスである二重分割グラフは、強力完全グラフ定理の証明に用いられる。 2.任意のグラフの分割とは、頂点を2つの空でない部分集合に分割し、その分割によってできた辺が完全な二部グラフを形成するような分割のことです。グラフの分割は、分割分解と呼ばれる木構造で表すことができます。分割 が 他の分割と交差しない場合、その分割は強い分割と呼ばれます。分割の両側に複数の頂点がある場合、その分割は非自明な分割と呼ばれます。非自明な分割を持たないグラフは、素グラフと呼ばれます。 3.頂点分割 （頂点切断とも呼ばれる）は、グラフの基本操作の一つで、頂点を二つに分割し、分割後の二つの頂点は元の頂点が隣接していた頂点に隣接します。頂点分割の逆操作は頂点縮小です。 四角 1.グラフGの二乗は グラフのべき乗 G 2 Gは G 2 半二乗は 、二部グラフの一方の辺によって誘導される部分グラフである。 2.正方形グラフ とは、すべての境界面が4サイクルであり、次数が3以下のすべての頂点が外側の面に属するように描画できる平面グラフのことです。 3.正方形グリッドグラフは、平面上の整数座標を持つ点を単位長さの辺で結んで定義される格子グラフです。 安定した 安定集合は独立集合 星 スターと は、内部頂点が1つある木構造のことです。言い換えれば、n ≥ 2 となる完全二部グラフK 1, n 強さ グラフの強さは 、考えられるすべての削除操作において、グラフから削除されたエッジの数と作成されたコンポーネントの数の比率が最小となる値であり、頂点の削除に基づくタフネスに類似している。強い 1.有向グラフの強い連結性と強い連結成分については、 連結 成分を 強い方向付けと は、強い連結性を持つ方向付けのことです。方向付けを 2.強力な完全グラフ定理 については、完全グラフ 3.強正則グラフ とは、隣接する2つの頂点が同じ数の共有隣接頂点を持ち、隣接していない2つの頂点も同じ数の共有隣接頂点を持つ正則グラフのことである。 4.強弦グラフ とは、長さが6以上の偶数サイクルすべてに奇数弦が存在する弦グラフのことである。 5.強完全グラフとは、誘導部分グラフのすべてにおいて、すべての極大クリークと交わる独立集合が存在するグラフのことである。メイニエルグラフ は、すべての頂点がそのような独立集合に属するため、「非常に強完全グラフ」とも呼ばれる。 亜森林 森 サブグラフ グラフGの部分グラフとは、 G の頂点と辺の部分集合から構成される別のグラフのことである。頂点の部分集合は辺の部分集合のすべての端点を含まなければならないが、追加の頂点を含む場合もある。全域部分グラフ 誘導部分グラフと サブツリー 部分木とは、木の連結部分グラフのことです。根付き木の場合、部分木は、選択された頂点から到達可能なすべての頂点と辺で構成される、特別なタイプの連結部分グラフとして定義されることがあります。 後継 有向パスにおいて 、 超濃縮器 スーパーコンセントレータとは、指定された2つの等しいサイズの頂点部分集合I とOを持つグラフであり、 I の任意の2つの等しいサイズの部分集合S とO の任意の2つの部分集合Tに対して、 Sのすべての頂点を T の頂点に接続する互いに素なパスの族が存在する。一部のソースでは、スーパーコンセントレータが有向非巡回グラフであり、I がソース、O がシンクであることをさらに要求している。 スーパーグラフ 与えられたグラフに頂点、辺、またはその両方を追加して形成されるグラフ。HがGの部分グラフである場合、 G はHの スーパー グラフである。
T シータ 1.シータグラフは、同じ2つの異なる終点頂点を持つ、内部的に互いに素な（単純な）パスの3つの和集合である。[ 15 ] 2.ユークリッド平面上の点の集合のシータグラフ は、各点を囲む円錐のシステムを構築し、円錐の中心線への投影が最小となる点に各円錐に1つの辺を追加することによって構築されます。 3.グラフのロヴァーシュ数またはロヴァーシュ・シータ関数は、クリーク数および彩色数に関連するグラフ不変量であり、半正定値計画法によって多項式時間で計算できます。 トムセングラフ トムセングラフは、 完全二部グラフ の別名である。K 3 、 3 {\displaystyle K_{3,3}} 位相的 1.位相グラフ とは、平面上の点と曲線によってグラフの頂点と辺を表現したものであり（必ずしも交差を避ける必要はない）、 2.位相グラフ理論 は、グラフ埋め込みの研究である。 3.トポロジカルソートと は、有向非巡回グラフをトポロジカル順序、つまり各辺がシーケンス内の前の頂点から後の頂点へ向かうような頂点のシーケンスに並べるアルゴリズムの問題である。 完全に断絶している エッジのない ツアー 閉じた経路とは、同じ頂点から始まり同じ頂点で終わり、重複する辺がない経路のことです。オイラー経路は、グラフのすべての辺を使用する経路です。 オイラー経路 トーナメント トーナメントと は、完全グラフの向き付けの一種です。つまり、2つの頂点が、ちょうど1つの有向辺（2つの頂点間の2つの方向のうち、いずれか一方にのみ通る辺）で結ばれている有向グラフのことです。 追跡可能 トレース可能なグラフ とは、ハミルトン経路を含むグラフのことである。トレイル 同じ 他動詞 推移性 に関係する。与えられた有向グラフの推移閉包 とは、元のグラフに同じ 2 つの頂点を結ぶパスが存在する場合に、ある頂点から別の頂点への辺を持つ、同じ頂点集合上のグラフのことである。グラフの推移的縮小とは、同じ推移閉包を持つ最小グラフのことである。有向非巡回グラフは、一意の推移的縮小を持つ。 推移的方向付けと は、グラフ自身の推移閉包であるグラフの方向付けのことである。これは比較グラフ にのみ存在する。転置 与えられた有向グラフの転置グラフ とは、同じ頂点を持つグラフで、各辺の方向が反転しているものです。これは、元のグラフの逆グラフ、あるいは反転グラフとも呼ばれます。 木 1.木と は、連結かつ非巡回的な無向グラフ、または1つの頂点（木の根）から残りのすべての頂点への一意の経路が存在する有向グラフのことです。 2. k-木は、 ( k +1)個のk-クリークを共通の k- クリークで貼り合わせて形成されるグラフです。この定義によれば、 1- 木です。 ツリー分解 グラフG の木分解とは、ノードに G の頂点の集合（バッグ）がラベル付けされた木のことです。各頂点vに対して、 v を含むバッグは必ず木のサブツリーを誘導し、各辺uvに対して、 u とv の 両方を含むバッグが必ず存在します。木分解の幅は、そのバッグに含まれる頂点の最大数より 1 少ない数です。G の木幅は、G の 任意の木分解の最小幅です。 木の幅 グラフGの 木幅 は、 G の木分解の最小幅です。また、 G の弦完成のクリーク数、 G の避難所 の次数、またはG の茨 の次数によって定義することもできます。 三角形 グラフにおける長さ3のサイクル。三角形を 含まないグラフとは、三角形部分グラフを持たない無向グラフのことである。 些細な 自明なグラフとは、頂点が0個または1個のグラフのことである。[ 16 ] ヌルグラフ とも呼ばれる。 トゥラン 1.パル・トゥラン 2.トゥラングラフ は、バランスのとれた完全多部グラフである。 3.トゥランの定理は 、トゥラングラフは、与えられた次数を持つすべてのクリークフリーグラフの中で、最大のエッジ数を持つと述べています。 4.トゥランのレンガ工場問題は、 完全二部グラフの図における交差の最小数を求める問題である。 ツイン 2 つの頂点u、v は 、同じ閉近傍 N G u ] = N G v ]u とv が隣接していることを意味します)。また、同じ開近傍N G u ) = N G v )u とv が隣接していないことを意味します)。
U 単項頂点 根付き木において、単項頂点とは、子頂点をちょうど1つだけ持つ頂点のことである。 方向性なし 無向グラフ とは、各辺の両端が区別されていないグラフのことです。有向グラフ と混合グラフ も参照してください。混合グラフ では、無向辺はやはり両端が区別されていない辺です。 制服 ハイパー グラフは、すべての辺がk 個の 端点を持つ場合、k-一様であると言われ、あるkに対して k- 一様である場合、一様であると言われます。例えば、通常のグラフは2- 一様ハイパーグラフと同じです。普遍的 1.普遍グラフ とは、与えられたグラフ族のすべてのグラフ、または与えられたグラフ族内の特定のサイズまたは次数のすべてのグラフを部分グラフとして含むグラフのことである。 2.普遍頂点 （頂点または支配頂点とも呼ばれる）とは、グラフ内の他のすべての頂点に隣接する頂点のことです。例えば、ホイールグラフ や連結閾値グラフに は必ず普遍頂点が存在します。 3.グラフの論理 では、式の中で全称量化されて いる頂点は、その式の全称頂点と呼ばれることがあります。 重み付けされていないグラフ 頂点と辺 に 重み が 重み付きグラフ ユーティリティグラフ 効用グラフは 完全二部グラフ の別名である。K 3 、 3 {\displaystyle K_{3,3}}
V V 頂点セット を参照してください。価 程度 頂点 頂点（複数形： 頂点群）は、（辺とともに）グラフを構成する2つの基本単位の1つです。グラフの頂点は、内部構造を持たない原子的なオブジェクトとみなされることが多いです。 頂点カット 分離セット グラフを 分断する の 関節点 切断頂点 頂点セット 与えられたグラフG の頂点の集合。V ( G ) と表記されることもある 頂点 頂点を 参照してください。ビジング 1.ヴァディム・G・ヴィジン 2.ヴィジングの定理 ：彩色指数は最大次数より最大で1つ大きい値である。 3.グラフのデカルト積の支配数に関するヴィジングの予想。 音量 頂点集合の次数の合計。
W W 文字Wは、 ホイールグラフ やウィンドミルグラフ の表記に使用されます。この表記法は標準化されていません。 ワーグナー 1.クラウス・ワグナー 2.ワグナーグラフ 、8つの頂点を持つメビウスの梯子。 3.平面グラフを禁止マイナーによって特徴付けるワグナーの定理。 4. K 5 歩く ウォークとは、 頂点 の列を結ぶ有限または無限のエッジ の列のこと です。ウォークはチェーンと 呼ばれることもあります。[ 17 ] 開いて おり、それらが繰り返される場合は閉じています。 弱く結合している 有向グラフは、そのすべての有向辺を無向辺に置き換えたときに連結（無向）グラフが生成されるとき、弱連結であると呼ばれる。 重さ グラフの頂点または辺にラベルとして割り当てられる数値。部分グラフの重みは、その部分グラフ内の頂点または辺の重みの合計です。 重み付きグラフ 頂点 辺に 重みが割り当てられたグラフ 。 色鮮やか 適切に彩色されたグラフ とは、貪欲法による彩色 において、使用する色の数がすべて同じであるグラフのことである。十分に覆われている 十分に被覆されたグラフ とは、その最大独立集合がすべて同じサイズであるグラフのことである。車輪 ホイールグラフ とは、単純サイクルに普遍頂点を 追加することによって形成されるグラフのことである。 幅 1.退廃 2.幅として知られるその他のグラフ不変量については、bandwidth branchwidth clique-width pathwidth treewidth を 3.ツリー分解またはパス分解の幅は、そのバッグの最大サイズより1小さく、ツリー幅とパス幅を定義するために使用できます。 4.有向非巡回グラフ の幅は、反鎖の最大濃度である。 風車 風車グラフ とは、互いに同じ次数を持つ複数のクリークの集合の和集合であり、すべてのクリークに共通する頂点が1つあり、その他の頂点と辺はすべて異なる。
参考文献 ↑ Farber, M.; Hahn, G.; Hell, P. ; Miller, DJ (1986), "グラフの無彩色数について", Journal of Combinatorial Theory, Series B , 40 (1): 21– 39, doi : 10.1016/0095-8956(86)90062-6 1 2 3 4 5 6 7 8 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "B.4 Graphs", Introduction to Algorithms (2 ed.), MIT Press and McGraw-Hill, pp. 1080– 1084 ↑ Grünbaum, B. (1973), "平面グラフの非巡回彩色", Israel Journal of Mathematics , 14 (4): 390–408 , doi : 10.1007/BF02764716 ↑ コーメンら。 (2001) 、p. 529.↑ Diestel, Reinhard (2017), "1.1 グラフ", グラフ理論 、Graduate Texts in Mathematics、第173巻 （第5 版）、ベルリン、ニューヨーク：Springer-Verlag、p. 3、 doi ： 10.1007/978-3-662-53622-3 、 ISBN 978-3-662-53621-6 ↑ Woodall, DR (1973), "グラフの束縛数とそのアンダーソン数", J. Combin. Theory Ser. B , 15 (3): 225– 255, doi : 10.1016/0095-8956(73)90038-5 ↑ van der Holst, Hein (2009年3月)、 「グラフのリンクレス埋め込みを見つけるための多項式時間アルゴリズム」 、 Journal of Combinatorial Theory, Series B 、 99 (2)、Elsevier BV: 512–530 、 doi : 10.1016/j.jctb.2008.10.002 ↑ Sudakov, Benny; Volec, Jan (2017), "Properly colored and rainbow copy of graphs with few cherries", Journal of Combinatorial Theory, Series B , 122 (1): 391– 416, arXiv : 1504.06176 , doi : 10.1016/j.jctb.2016.07.001 ↑ 深さ 、 NIST ↑ Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999)、「第 7 章: 禁止部分グラフ」、 Graph Classes: A Survey 、SIAM Monographs on Discrete Mathematics and Applications、pp. 105–121 、 ISBN 978-0-89871-432-6 ↑ ミッチェム、ジョン (1969)、「グラフの準性質」、 グラフ理論の多面性（会議議事録、ウェスタンミシガン大学、カラマズー、ミシガン州、1968年） 、数学講義ノート、第 110巻、シュプリンガー、pp. 223–230 、 doi : 10.1007/BFb0060121 、 ISBN 978-3-540-04629-5 MR 0253932 1 2 レベル 、 NIST ↑ ハリス、ジョン M. (2000)、 『組合せ論とグラフ理論』 、ニューヨーク：シュプリンガー・フェルラーク、 5 ページ、 ISBN 978-0-387-98736-1 ↑ Watts, Duncan J.; Strogatz, Steven H. (1998年6月)、「スモールワールドネットワークの集団ダイナミクス」、 Nature 、 393 (6684): 440–442 、 Bibcode : 1998Natur.393..440W 、 doi : 10.1038/30918 、 PMID 9623998 、 S2CID 4429113 ↑ Bondy, JA (1972), "ギリシャ文字の「グラフ理論」", Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of JWT Youngs) , Lecture Notes in Mathematics, vol. 303, Springer, pp. 43– 54, doi : 10.1007/BFb0067356 , ISBN 978-3-540-06096-3 MR 0335362 ↑ Diestel, Reinhard (2017), Graph Theory , Graduate Texts in Mathematics, vol. 173, Berlin, Heidelberg: Springer Berlin Heidelberg, p. 2, doi : 10.1007/978-3-662-53622-3 , ISBN 978-3-662-53621-6 ↑ 「連鎖グラフ理論」 、 britannica.com 、 2018年 3月25日 取得 
