グラフ理論用語集

無料辞書『ウィクショナリー』で「付録:グラフ理論の用語集」を調べてください。

これはグラフ理論の用語集です。グラフ理論は、線または辺によってペアで接続された ノードまたは頂点のシステムであるグラフの研究です。

角括弧 [ ]

G [ S ]はグラフGの頂点部分集合Sに対する誘導部分グラフである。

プライム記号 '

プライム記号は、グラフ不変量の表記法を変更して、与えられたグラフではなく線グラフに適用するためによく使用されます。たとえば、 α ( G )はグラフの独立数です。α ′( G )はグラフのマッチング数であり、線グラフの独立数に等しくなります。同様に、χ ( G )はグラフの彩度数であり、χ  ′( G )はグラフの彩度インデックスであり、線グラフの彩度数に等しくなります。

吸収する

有向グラフの吸収集合とは、任意の頂点 に対して から の頂点に向かう辺が存在するような頂点の集合です。${\displaystyle A}$${\displaystyle G}$${\displaystyle v\in G\setminus A}$${\displaystyle v}$${\displaystyle A}$

無彩色の

グラフの無彩色数は、完全な色付けにおける最大の色数である。^[1]

非環式

1. グラフが非巡回グラフであるのは、そのグラフにサイクルがない場合です。無向非巡回グラフはフォレストと同じものです。有向サイクルのない有向グラフである非巡回有向グラフは、特にコンピュータサイエンスの分野では、有向非巡回グラフと呼ばれることがよくあります。^[2]

2.無向グラフの非巡回着色は、2つの色クラスごとにフォレストを誘導する適切な着色である。^[3]

隣接行列

グラフの隣接行列は、行と列の両方がグラフの頂点によってインデックス付けされた行列であり、頂点iとjが隣接している場合は行iと列jのセルに1が入り、そうでない場合は0が入る。^[4]

隣接

1. 同じ辺の両端点である2つの頂点間の関係。^[2]

2. 端点を共有する2つの異なる辺の関係。^[5]

α

グラフGの場合、α ( G ) (ギリシャ文字のアルファを使用) は独立数 (独立を参照) であり、α ′( G )はマッチング数 (マッチングを参照) です。

交互

マッチングのあるグラフでは、交互パスとは、エッジがマッチングしたエッジと一致しないエッジの間で交互に現れるパスです。同様に、交互サイクルとは、エッジがマッチングしたエッジと一致しないエッジの間で交互に現れるサイクルです。増加パスとは、飽和していない頂点で始まり、飽和していない頂点で終わる交互パスです。より大きなマッチングは、マッチングと増加パスの対称差として見つけることができます。マッチングが最大になるのは、増加パスがない場合のみです。

アンチチェーン

有向非巡回グラフでは、頂点のサブセットS は互いに比較不可能です。つまり、Sの任意の頂点に対して、 xからyまたはyからxへの有向パスは存在しません。これは、半順序集合の反連鎖の概念にヒントを得ています。${\displaystyle x\leq y}$

アンチエッジ

非エッジ (隣接しない頂点のペア)の同義語。

反三角形

3 つの頂点を持つ独立集合、つまり三角形の補集合。

頂点

1.頂点グラフは、1 つの頂点を削除して平面サブグラフを残すことができるグラフです。削除された頂点は頂点と呼ばれます。k頂点グラフは、 k個の頂点を削除することで平面にできるグラフです。

2.他のすべての頂点に隣接する頂点である普遍頂点の同義語。

樹木状

ルート付き有向ツリーの同義語。ツリーを参照してください。

アーク

エッジを参照してください。

矢印

有向グラフの辺などの、頂点の順序付きペア。矢印( x , y )には、末尾がx、先頭がyで、方向はxからyです。y はxの直接の後続、x はyの直接の前続と呼ばれます。矢印( y , x )は、矢印( x , y )の反転矢印です。

関節点

連結グラフ内の、削除するとグラフが切断される頂点。より一般的には、削除するとコンポーネントの数が増加する頂点。

-ary

k進木は、すべての内部頂点がk 個以下の子を持つ根付き木です。1 進木は単なるパスです。2 進木は二分木とも呼ばれますが、この用語は、各ノードの子が左の子または右の子 (それぞれ最大で 1 つ) として区別される 2 進木を指すのがより適切です。すべての内部頂点がちょうどk 個の子を持つ場合、 k進木は完全であると言われます。

増強する

交互パスの特殊なタイプ。交互を参照してください。

自己同型性

グラフの自己同型性はグラフの対称性であり、グラフからそれ自身への同型性です。

バッグ

ツリー分解における頂点セットの 1 つ。

バランスのとれた

二部グラフまたは多部グラフは、その頂点パーティションの 2 つのサブセットのサイズが互いに等しい場合、バランスが取れています。

帯域幅

グラフGのバンド幅は、 Gの頂点のすべての順序付けにおいて、最長の辺の長さ（2 つの端点間の順序付けのステップ数）の最小値です。また、これは、クリークのサイズを最小化するために選択された、 Gの適切な区間完備化における最大クリークのサイズより 1 小さい値でもあります。

二派閥

完全二部グラフまたは完全二部サブグラフの同義語。「complete」を参照してください。

二重接続

通常は2頂点連結の同義語ですが、2 連結でないK _{2も含まれることがあります。連結を参照してください。2}連結コンポーネントについては、コンポーネントを参照してください。

拘束番号

頂点の適切な部分集合の近傍点の数とその部分集合のサイズの可能な限り最小の比率。^[6]

二分された

二部グラフとは、頂点を 2 つの互いに素な集合に分割できるグラフのことです。一方の集合の頂点は互いに接続されていませんが、もう一方の集合の頂点には接続される可能性があります。言い換えると、二部グラフは奇数サイクルのないグラフです。つまり、2 色で適切に色付けできるグラフです。二部グラフは、G = ( U , V , E )と表記されることが多く、UとV は各色の頂点のサブセットです。ただし、グラフが接続されていない場合は、一意の 2 色付けができない場合があります。

二規則的な

双正則グラフは、頂点二分割の各セットに 1 つずつ、異なる頂点次数が 2 つだけある二部グラフです。

ブロック

1. グラフGのブロックは、孤立した頂点、ブリッジ エッジ、または 2 連結サブグラフのいずれかである最大サブグラフです。ブロックが 2 連結の場合、そのブロック内のすべての頂点のペアは共通のサイクルに属します。グラフのすべてのエッジは、正確に 1 つのブロックに属します。

2. グラフGのブロック グラフは、 Gのブロックを頂点とする別のグラフであり、対応するブロックが結合点を共有する場合、2 つの頂点を接続する辺を持ちます。つまり、 Gのブロックの交差グラフです。任意のグラフのブロック グラフはフォレストです。

3. グラフGのブロックカット（またはブロックカットポイント）グラフは、 1 つの部分集合がGのカット頂点で構成され、もう 1 つの部分集合がGの各ブロックの頂点を持つ 2 部グラフです。 Gが連結されている場合、そのブロックカットポイント グラフは木です。${\displaystyle b_{i}}$${\displaystyle B_{i}}$

4.ブロック グラフ(連結されている場合はクリーク ツリーとも呼ばれ、誤って Husimi ツリーと呼ばれることもあります) は、すべてのブロックが完全グラフであるグラフです。フォレストはブロック グラフです。したがって、特に任意のグラフのブロック グラフはブロック グラフであり、すべてのブロック グラフはグラフのブロック グラフとして構築できます。

ボンド

最小カットセット: 削除するとグラフが切断されるエッジのセット。そのエッジの適切なサブセットは同じプロパティを持ちません。

本

1.ブック、ブックグラフ、または三角形の本は、完全な三部グラフK _{1,1, n} 、つまり共有エッジで結合されたn 個の三角形の集合です。

2. ブックまたは四辺形ブックとも呼ばれる別の種類のグラフは、共有エッジで結合された4 つのサイクルの集合であり、エッジを持つスターの直積です。

3.ブック埋め込みとは、グラフをトポロジカルブックに埋め込むことです。トポロジカルブックとは、共有線に沿って半平面の集合を結合して形成される空間です。通常、埋め込みの頂点は埋め込みの背骨と呼ばれる線上にある必要があり、埋め込みの辺は単一の半平面、つまり本のページの 1 つ内にある必要があります。

境界

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 つの辺があり、頂点を共有する 2 つの三角形によって形成されます。

2. バタフライネットワークは、分散コンピューティングにおけるネットワークアーキテクチャとして使用されるグラフであり、立方体接続サイクルと密接に関連しています。

Ｃ

C _{n は}n頂点のサイクル グラフです。サイクルを参照してください。

カクタス

サボテン グラフ、サボテン ツリー、サボテン、または Husimi ツリーは、各エッジが最大 1 つのサイクルに属する連結グラフです。そのブロックはサイクルまたは単一のエッジです。さらに、各頂点が最大 2 つのブロックに属する場合、クリスマス カクタスと呼ばれます。

ケージ

ケージは、その内周の順序が可能な限り小さい正則グラフです。

正統な

列聖

グラフの正準形式とは、2 つのグラフが同型である場合にのみ、それらの不変量が等しい不変量を持つ不変量です。正準形式は、正準不変量または完全不変量とも呼ばれ、特定のグラフ ファミリ内のグラフに対してのみ定義されることもあります。グラフの正準化は、正準形式を計算するプロセスです。

カード

特定のグラフから 1 つの頂点を削除することによって形成されるグラフ。特に再構成予想のコンテキストで使用されます。グラフのすべてのカードの多重集合であるデッキも参照してください。

彫刻幅

カービング幅は、枝幅に類似したグラフ幅の概念ですが、エッジの階層的クラスタリングの代わりに頂点の階層的クラスタリングを使用します。

毛虫

キャタピラーツリーまたはキャタピラーは、内部ノードがパスを誘導するツリーです。

中心

グラフの中心は、離心率が最小の頂点の集合です。

重心

ツリーの重心とは、vをルートとした場合、他のどの頂点もツリーのサイズの半分よりも大きいサブツリー サイズを持たない頂点vです。

鎖

1. walk（歩く）の同義語。

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内の最大クリークの交差グラフです。完全な二部サブグラフである biclique も参照してください。

クリークツリー

ブロックグラフの同義語。

クリーク幅

グラフGのクリーク幅は、ラベル付き頂点を作成する、2 つのラベル付きグラフの互いに素な和を形成する、指定されたラベルを持つすべての頂点のペアを接続する辺を追加する、または指定されたラベルを持つすべての頂点にラベルを付ける操作によってG を構築するために必要な、異なるラベルの最小数です。クリーク幅が最大2のグラフは、まさにコグラフです。

閉鎖

1. 閉じた近傍とは、中心の頂点を含む近傍のことです。近傍を参照してください。

2. 閉じたウォークとは、同じ頂点で始まり、終わるウォークです。ウォークを参照してください。

3. グラフが推移的に閉じているとは、グラフがそれ自身の推移閉包と等しい場合です。推移を参照してください。

4. グラフ プロパティは、操作の引数にプロパティがある場合に、結果もプロパティを持つ場合、グラフに対する何らかの操作に対して閉じています。たとえば、遺伝的プロパティは誘導サブグラフに対して閉じており、単調プロパティはサブグラフに対して閉じており、マイナー閉じプロパティはマイナーに対して閉じています。

閉鎖

1. 有向グラフの推移閉包については、「推移」を参照してください。

2. 有向グラフの閉包とは、閉包の外側の頂点への出力エッジを持たない頂点の集合です。たとえば、シンクは 1 頂点の閉包です。閉包問題は、最小または最大の重みを持つ閉包を見つける問題です。

共同

この接頭辞には、通常は補グラフに関係するさまざまな意味があります。たとえば、コグラフは補集合を含む操作によって生成されるグラフです。コカラーリングは、各頂点が独立集合 (適切なカラーリングの場合) またはクリーク (補集合のカラーリングの場合) のいずれかを誘導するカラーリングです。

色

着色

1.グラフの色付けとは、グラフの頂点に特定の色のセットの要素をラベル付けすること、または頂点を「色クラス」と呼ばれるサブセットに分割することであり、各サブセットはいずれかの色に関連付けられます。

2. 一部の著者は、"カラーリング" を、各エッジのエンドポイントに異なる色を割り当てる適切なカラーリングの意味で無条件に使用しています。グラフ カラーリングでは、できるだけ少ない色を使用する適切なカラーリングを見つけることが目標です。たとえば、2 部グラフは 2 色のみでカラーリングされるグラフであり、4 色定理では、すべての平面グラフは最大 4 色でカラーリングできるとされています。グラフがk色で(適切に) カラーリングされている場合、そのグラフはk色であると言われ、それが可能な場合はkカラー可能またはk有彩であると言われます。

3. エッジ カラーリング(同じエンドポイントを持つ 2 つのエッジが同じ色を共有しないようにエッジをカラーリングする)、リスト カラーリング(各頂点を使用可能な色のサブセットに制限した適切なカラーリング)、非巡回カラーリング(2 色のサブグラフはすべて非巡回である)、共カラーリング (すべての色クラスが独立したセットまたはクリークを誘導する)、完全カラーリング(2 つの色クラスはすべてエッジを共有する)、および合計カラーリング (エッジと頂点の両方に色を付ける) など、多くのカラーリングのバリエーションが研究されてきました。

4. グラフの色数は 1 に退化を加えた数です。グラフの退化順序に貪欲な色付けアルゴリズムを適用すると、最大でこれだけの色数が使用されるため、このように呼ばれています。

比較可能性

無向グラフは、その頂点が半順序集合の要素であり、半順序で比較可能な 2 つの頂点が隣接している場合、比較可能グラフです。同様に、比較可能グラフは推移的な方向を持つグラフです。他の多くのグラフのクラスは、特殊な半順序の比較可能グラフとして定義できます。

補体

単純グラフGの補グラフは 、Gと同じ頂点集合上にある別のグラフであり、 G内で隣接していない 2 つの頂点ごとに辺を持ちます。${\displaystyle {\bar {G}}}$

完了

1.完全グラフとは、2 つの頂点がすべて隣接しているグラフです。つまり、存在できるすべての辺が存在します。n個の頂点を持つ完全グラフは、多くの場合K _{n と}表記されます。完全 2 部グラフとは、頂点の分割の反対側にある 2 つの頂点がすべて隣接しているグラフです。分割の片側にa 個の頂点があり、反対側にb 個の頂点がある完全 2 部グラフは、多くの場合K _{a、b と}表記されます。同じ用語と表記法は、完全多部グラフにも拡張されています。完全多部グラフとは、頂点が 3 つ以上のサブセットに分割され、異なるサブセット内のすべての頂点のペアが隣接しているグラフです。サブセット内の頂点の数がa、b、c、...の場合、このグラフはK _{a、b、c、...}と表記されます。

2. 与えられたグラフの完成とは、何らかの望ましい特性を持つスーパーグラフのことです。たとえば、弦完成は弦グラフであるスーパーグラフです。

3. 完全一致は完全一致の同義語です。一致を参照してください。

4.完全着色とは、各色のペアが少なくとも 1 つの辺の端点に使用される適切な着色です。最小数の色の着色はすべて完全ですが、より多くの色の完全着色が存在する場合もあります。グラフの無彩色数は、完全着色における色の最大数です。

5. グラフの完全不変量は、非同型グラフに対して異なる値を持つ不変量である標準形式の同義語です。

成分

グラフの連結成分は、最大連結サブグラフです。この用語は、2 連結成分、3 連結成分、強連結成分など、より高い連結順序を持つグラフの頂点の最大サブグラフまたはサブセットにも使用されます。

結露

有向グラフGの凝縮は、 Gの強く連結された各コンポーネントに対して 1 つの頂点と、 G内の少なくとも 1 つの辺の 2 つの端点を含むコンポーネントのペアを接続する辺を持つ、有向非巡回グラフです。

円錐

普遍頂点を含むグラフ。

接続する

繋がる原因。

接続された

接続されたグラフとは、各頂点のペアがパスのエンドポイントを形成するグラフです。接続性のより高度な形式には、有向グラフの強い接続性 (各 2 つの頂点に対して、一方から他方へのパスが両方向に存在します)、k頂点接続グラフ( k個未満の頂点を削除してもグラフを切断できません)、およびk辺接続グラフ( k個未満の辺を削除してもグラフを切断できません) があります。

連結成分

コンポーネントの同義語。

収縮

エッジの縮小は、グラフからエッジを削除し、そのエッジが以前結合していた 2 つの頂点を結合する基本的な操作です。頂点の縮小 (頂点の識別と呼ばれることもあります) も同様ですが、2 つの頂点は必ずしもエッジで接続されるわけではありません。パスの縮小は、パスのエンドポイント間で 1 つのエッジを形成するように縮小するパス内のエッジのセットに対して発生します。エッジの縮小の逆は、頂点の分割です。

会話する

逆グラフは転置グラフの同義語です。転置を参照してください。

コア

1. kコアは、次数がk未満のすべての頂点と、以前の削除後に次数がk未満になるすべての頂点を削除することによって形成される誘導サブグラフです。退化を参照してください。

2.コアとは、 Gからそれ自身へのすべてのグラフ準同型が同型となるようなグラフGです。

3.グラフGのコアは、 GからHへの準同型とその逆が存在するような極小グラフHです。 H は同型を除いて一意です。 これはGの誘導サブグラフとして表すことができ、そのすべての自己準同型が同型であるという意味でコアです。

4. グラフマッチングの理論では、グラフのコアは、すべての最大マッチングの和集合として形成されるダルメージ・メンデルゾーン分解の側面です。

コツリー

1.全域木の補木。

2.コグラフを記述するために使用されるルート付きツリー構造。コグラフの各頂点はツリーの葉であり、ツリーの各内部ノードには 0 または 1 のラベルが付けられ、2 つのコグラフ頂点は、ツリー内の最下位の共通祖先に 1 のラベルが付けられている場合にのみ隣接します。

カバー

頂点カバーは、グラフ内のすべての辺に接する頂点の集合です。辺カバーは、グラフ内のすべての頂点に接する辺の集合です。グラフのサブグラフの集合は、その和集合(頂点ごとおよび辺ごと) がグラフと等しい場合、そのグラフをカバーします。

致命的

特定のプロパティの臨界グラフとは、そのプロパティを持つグラフですが、1 つの頂点を削除することによって形成されるすべてのサブグラフにはそのプロパティがありません。たとえば、因子臨界グラフとは、すべての頂点削除に対して完全マッチング (1 因子) を持つグラフですが、(頂点の数が奇数であるため) それ自体には完全マッチングがありません。プロパティを持たないが、1 頂点削除ごとにそのプロパティを持つグラフに使用されるhypo-と比較してください。

キューブ

キュービック

1.  立方体グラフ、立方体の頂点と辺の 8 つの頂点のグラフ。

2.  ハイパーキューブグラフ、キューブグラフの高次元一般化。

3.  折り畳まれた立方体グラフ。対応する反対の頂点を追加してハイパーキューブから形成されます。

4.  半立方体グラフ、超立方体グラフの半分の正方形。

5.  部分立方体、超立方体の距離保存サブグラフ。

6. グラフGの 3 乗はグラフ冪 G ³です。

7.  立方体グラフ。3正則グラフの別名で、各頂点に 3 つの接続辺があるグラフです。

8.  立方体接続サイクル。超立方体の各頂点をサイクルに置き換えることによって形成される立方体グラフ。

カット

カットセット

カットとは、グラフの頂点を 2 つのサブセットに分割すること、または、そのセットが空でない場合は、そのようなパーティションにまたがるエッジのセット (カットセットとも呼ばれます) です。エッジがパーティションにまたがるとは、両方のサブセットにエンドポイントがある場合です。したがって、接続されたグラフからカットセットを削除すると、グラフは切断されます。

カットポイント

アーティキュレーションポイントを参照してください。

スペースをカット

グラフのカット空間は、グラフのカットセットを要素とし、セットの対称差をベクトル加算演算とするGF(2)ベクトル空間です。

サイクル

1.サイクルは、グラフの一種かウォークの一種です。ウォークとしては、閉じたウォーク (ツアーとも呼ばれる) か、より一般的には、頂点とエッジが繰り返されない閉じたウォーク (単純サイクルとも呼ばれる) のいずれかになります。後者の場合、通常はグラフと見なされます。つまり、最初の頂点と方向の選択は通常重要ではないと見なされます。つまり、ウォークの循環的な順列と反転は同じサイクルを生成します。重要な特殊なサイクルには、ハミルトンサイクル、誘導サイクル、周辺サイクル、およびグラフの内周を定義する最短サイクルがあります。 kサイクルは長さkのサイクルです。たとえば、2サイクルは二角形であり、3サイクルは三角形です。サイクルグラフは、それ自体が単純サイクルであるグラフです。n個の頂点を持つサイクルグラフは、通常C _nと表記されます。

2.サイクル空間は、グラフ内の単純なサイクルによって生成されるベクトル空間であり、多くの場合 2 元の体上ですが、他の体上でも生成されます。

ダグ

有向非巡回グラフの略語。有向サイクルのない有向グラフ。

デッキ

単一のグラフ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]

ディパス

有向パスを参照してください。

直接の前身

指定された頂点を先頭とする有向辺の末尾。

直接の後継者

指定された頂点を末尾とする有向辺の先頭。

監督された

有向グラフとは、ある頂点から別の頂点へ向かう辺が明確な方向を持っているグラフのことである。 ^[2]混合グラフでは、有向辺は明確な方向を持っている。有向辺は弧や矢印とも呼ばれる。

有向弧

矢印を参照してください。

有向エッジ

矢印を参照してください。

有向線

矢印を参照してください。

有向パス

すべてのエッジが同じ方向を持つパス。有向パスが頂点xから頂点yにつながる場合、xはyの前身であり、y はxの後身であり 、y はxから到達可能であると言われます。

方向

1.グラフ内の 2 つの隣接する頂点間の非対称関係。矢印として表されます。

2. 有向パス上の 2 つの頂点間の非対称関係。

切断する

切断の原因となります。

切断された

接続されていません。

ばらばらの

1. 2 つのサブグラフは、エッジを共有しない場合はエッジが分離しており、頂点を共有しない場合は頂点が分離しています。

2. 2 つ以上のグラフの非結合和は、頂点と辺の集合が対応する集合の非結合和であるグラフです。

解離数

グラフG内の頂点のサブセットが最大次数1のサブグラフを誘導する場合、そのサブセットは分離と呼ばれます。

距離

グラフ内の任意の 2 つの頂点間の距離は、その 2 つの頂点を端点とする最短経路の長さです。

ドマティック

グラフの支配分割は、頂点を支配集合に分割することです。グラフの支配数は、そのような分割における支配集合の最大数です。

支配的な

支配集合は、グラフ内のすべての頂点を含むか、またはすべての頂点に隣接する頂点の集合です。グラフ内のすべての辺に接する頂点集合である頂点カバーと混同しないでください。支配集合の重要な特殊なタイプには、独立支配集合 (独立集合でもある支配集合) と連結支配集合 (連結されたサブグラフを誘導する支配集合) があります。単一頂点の支配集合は、ユニバーサル頂点と呼ばれることもあります。グラフの支配数は、最小の支配集合の頂点の数です。

デュアル

平面グラフGの双対グラフは、 Gの各面ごとに頂点を持つグラフです。

え

E ( G ) はGのエッジ セットです。エッジ セットを参照してください。

耳

グラフの耳とは、端点が一致する可能性があるが、それ以外では頂点や辺の繰り返しがないパスです。

耳の分解

耳分解とは、グラフの辺を一連の耳に分割することです。各耳の端点 (最初のものの後) は前の耳に属し、各内部点は前のどの耳にも属しません。開いた耳は単純なパス (重複する頂点のない耳) であり、開いた耳分解は最初の耳の後の各耳が開いている耳分解です。グラフが 2 連結である場合に限り、グラフは開いた耳分解を持ちます。辺の数が奇数である場合、耳は奇数であり、奇数耳分解は各耳が奇数である耳分解です。グラフが因数臨界である場合に限り、グラフは奇数耳分解を持ちます。

偏心

頂点の離心率は、その頂点から他の頂点までの最長距離です。

角

辺は（頂点とともに）グラフを構成する 2 つの基本単位の 1 つです。各辺には 2 つ（ハイパーグラフの場合はそれ以上）の頂点が接続されており、端点と呼ばれます。辺は有向または無向です。無向辺は線とも呼ばれ、有向辺は弧または矢印とも呼ばれます。無向単純グラフでは、辺はその頂点の集合として表され、有向単純グラフでは頂点の順序付きペアとして表されます。頂点xとy を接続する辺は、xyと表記されることもあります。

エッジカット

削除するとグラフが切断されるエッジのセット。1 つのエッジのカットは、ブリッジ、地峡、またはカット エッジと呼ばれます。

エッジセット

与えられたグラフGの辺の集合。E ( G )と表記されることもある。

エッジのないグラフ

エッジのないグラフ、または特定の頂点セット上の完全に切断されたグラフは、エッジのないグラフです。空のグラフと呼ばれることもありますが、この用語は頂点のないグラフを指す場合もあります。

埋め込み

グラフ埋め込みは、各頂点が点として表現され、各辺が曲線として表現され、辺の端点が曲線の端点となり、頂点または辺の間に他の交差がない位相空間のサブセットとしてのグラフの位相表現です。平面グラフは、ユークリッド平面への埋め込みを持つグラフであり、トーラスへの埋め込みを持つグラフです。グラフの種数は、グラフを埋め込むことができる 2 次元多様体の最小の種数です。

空のグラフ

1.空でない頂点の集合上のエッジのないグラフ。

2.ゼロ次グラフ、頂点も辺もないグラフ。

終わり

無限グラフの端は、光線の同値類です。2 つの光線は、その両方の光線から無限に多くの頂点を含む 3 番目の光線がある場合に同値になります。

終点

特定のエッジによって結合された 2 つの頂点の 1 つ、またはウォーク、トレイル、またはパスの最初または最後の頂点の 1 つ。特定の有向エッジの最初のエンドポイントは末尾と呼ばれ、 2 番目のエンドポイントは先頭と呼ばれます。

列挙

グラフ列挙は、グラフの特定のクラス内のグラフを、その順序の関数として数える問題です。より一般的には、列挙問題は、特定のクラスの組み合わせオブジェクト (クリーク、独立集合、色付け、スパニング ツリーなど) を数える問題、またはそのようなオブジェクトをすべてアルゴリズム的にリストする問題のいずれかを指します。

オイラー

オイラーパスは、グラフのすべてのエッジを 1 回だけ使用するウォークです。オイラー回路 (オイラーサイクルまたはオイラーツアーとも呼ばれます) は、すべてのエッジを 1 回だけ使用する閉じたウォークです。オイラーグラフは、オイラー回路を持つグラフです。無向グラフの場合、これはグラフが接続されており、すべての頂点の次数が偶数であることを意味します。有向グラフの場合、これはグラフが強く接続されており、すべての頂点の入次数が出次数と等しいことを意味します。場合によっては、接続要件が緩められ、次数要件のみを満たすグラフがオイラーと呼ばれます。

平

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の関数が多項式である場合、多項式展開を持ちます。

顔

平面グラフまたはグラフ埋め込みにおいて、グラフから分離している埋め込みの平面または表面のサブセットの接続コンポーネント。平面内の埋め込みの場合、1 つの面を除くすべての面が境界で区切られます。無限に広がる例外的な 1 つの面は外面と呼ばれます。

要素

グラフの因子は、スパニング サブグラフです。つまり、グラフのすべての頂点を含むサブグラフです。この用語は主に、正規サブグラフのコンテキストで使用されます。k因子は、 k正規の因子です。特に、1因子は完全マッチングと同じものです。因子臨界グラフとは、任意の 1 つの頂点を削除すると、 1因子を持つグラフが生成されるグラフです。

因数分解

グラフ因数分解は、グラフの辺を因数に分割することです。k因数分解は、 k因数に分割することです。たとえば、1因数分解は、各頂点が各色の辺に接するという追加の特性を持つ辺の色付けです。

家族

クラスの同義語。

有限

グラフが有限であるのは、頂点と辺の数が有限の数である場合です。多くの情報源では、明示的に言及することなく、すべてのグラフが有限であると想定しています。各頂点に有限の数の辺がある場合、グラフは局所的に有限です。無限グラフは有限ではないグラフです。つまり、頂点、辺、またはその両方が無限にあります。

最初の注文

グラフの1 階論理は、変数がグラフの頂点を表し、2 つの頂点が隣接しているかどうかをテストするバイナリ述語が存在する論理形式です。変数が頂点またはエッジのセットを表すこともできる 2 階論理とは区別されます。

-フラップ

頂点の集合Xについて、Xフラップは、 X を削除することによって形成される誘導サブグラフの接続コンポーネントです。フラップという用語は、小さな頂点の集合をフラップにマップする関数であるヘイブンのコンテキストでよく使用されます。サイクルのブリッジも参照してください。これは、サイクルの頂点のフラップまたはサイクルの弦のいずれかです。

禁断

禁制グラフの特徴付けは、サブグラフ、誘導サブグラフ、またはマイナーとして他の特定のグラフを持たないグラフとしてグラフの族を特徴付けることです。Hがサブグラフ、誘導サブグラフ、またはマイナーとして出現しないグラフの 1 つである場合、H は禁制であると言われます。

強制グラフ

強制グラフとは、グラフシーケンスG(n)のグラフにおけるHのサブグラフ密度を評価することで、そのシーケンスが準ランダムであるかどうかをテストするのに十分なグラフHです。

森

フォレストは、サイクルのない無向グラフ (根のない木の非結合和)、または根のある木の非結合和として形成される有向グラフです。

フルクト

1.  ロバート・フルクト

2.フルヒトグラフ。非自明な対称性を持たない 2 つの最小の立方グラフのうちの 1 つです。

3.  すべての有限群は有限グラフの対称群であるというフルクトの定理。

満杯

誘発の同義語。

関数グラフ

関数グラフは、すべての頂点の出力次数が 1 である有向グラフです。同様に、関数グラフは最大有向擬似フォレストです。

グ

グラフを表すためによく使用される変数。

属

グラフの種数は、グラフを埋め込むことができる表面の最小の種数です。埋め込みを参照してください。

測地線

名詞として、測地線は最短経路の同義語です。形容詞として使用される場合、最短経路または最短経路距離に関連することを意味します。

巨人

ランダム グラフの理論では、巨大コンポーネントはグラフの頂点の一定の割合を含む連結コンポーネントです。ランダム グラフの標準モデルでは、通常、巨大コンポーネントは最大で 1 つ存在します。

胴回り

グラフの周囲長は、その最短サイクルの長さです。

グラフ

グラフ理論の基本的な研究対象であり、エッジによってペアで接続された頂点のシステム。エッジに方向があるかどうかによって、有向グラフまたは無向グラフに細分されることが多い。混合グラフには、両方のタイプのエッジが含まれます。

よく深い

貪欲アルゴリズムによって生成されます。たとえば、グラフの貪欲な色付けは、頂点をある順序で検討し、各頂点に最初に利用可能な色を割り当てることによって生成される色付けです。

グロッチュ

1.  ヘルベルト・グロッチュ

2.グロッチュグラフ、任意の適切な色付けで 4 色を必要とする最小の三角形のないグラフ。

3.  三角形のない平面グラフは常に最大 3 色で着色できるというGrotzsch の定理。

グランディ数

1.グラフのグランディ数とは、頂点の順序を不適切に選択した貪欲な色付けによって生成される色の最大数です。

H

特に別のグラフがすでにGで表されている場合に、グラフを表すためによく使用される変数。

Hカラーリング

グラフG ( Hもグラフ)のH色付けは、 HからGへの準同型です。

Hフリー

グラフがHフリーであるとは、 Hと同型の誘導サブグラフを持たない場合、つまりH が禁制の誘導サブグラフである場合です。Hフリーグラフは、 Hフリーであるすべてのグラフ（または、多くの場合、すべての有限グラフ）の族です。^[10]たとえば、三角形フリーグラフは、三角形グラフをサブグラフとして持たないグラフです。 Hフリーであるという特性は常に遺伝的です。グラフがHと同型のマイナーを持たない場合、グラフは H マイナーフリーです。

ハドヴィガー

1.  ヒューゴ・ハドヴィガー

2.グラフのハドヴィガー数は、グラフの最大完全マイナーの位数です。これは、収縮クリーク数または準同型次数とも呼ばれます。

3.ハドヴィガー予想は、ハドヴィガー数が彩色数より小さくなることはないという予想です。

ハミルトニアン

ハミルトン パスまたはハミルトン サイクルは、単純な全域パスまたは単純な全域サイクルです。グラフ内のすべての頂点を正確に 1 回カバーします。グラフにハミルトン サイクルが含まれている場合、グラフはハミルトンであり、ハミルトン パスが含まれている場合、グラフは追跡可能です。

避難所

kヘイブンは、 k 個未満の頂点を持つすべての集合Xをそのフラップの 1 つにマッピングする関数であり、多くの場合、追加の一貫性条件を満たします。ヘイブンの順序は数kです。ヘイブンは、有限グラフのツリー幅や、無限グラフの端とハドヴィガー数を特徴付けるために使用できます。

身長

1.ルート付きツリーのノードの高さは、そのノードから始まり、リーフで終わる、ルートから遠ざかる（つまり、ノードの深さは厳密に増加する）最長パスのエッジの数です。

2.根付き木の高さは、その根の高さです。つまり、木の高さは、根から始まり葉で終わる、根から離れる最長のパスの辺の数です。

3.有向非巡回グラフの高さは、このグラフ内の有向パスの最大長です。

遺伝性の

グラフの遺伝的性質は、誘導されたサブグラフに対して閉じている性質です。つまり、Gが遺伝的性質を持つ場合、Gのすべての誘導されたサブグラフも遺伝的性質を持つ必要があります。monotone (すべてのサブグラフに対して閉じている) またはminor-closed (マイナーに対して閉じている)を比較してください。

六角形

ちょうど 6 つの辺と 6 つの頂点で構成される単純なサイクル。

穴

ホールとは、長さが 4 以上の誘導サイクルです。奇数ホールとは、長さが奇数のホールです。反ホールとは、補グラフがサイクルである、位数 4 の誘導サブグラフです。つまり、補グラフ内のホールです。この用語は主に、完全グラフのコンテキストで使用されます。完全グラフは、強い完全グラフ定理によって、奇数ホールや奇数反ホールのないグラフとして特徴付けられます。ホールのないグラフは、弦グラフと同じです。

準同型性

2 つのグラフが準同型的に同等であるとは、各グラフから他のグラフへの準同型が 1 つずつ存在する場合です。

準同型

1.グラフ準同型とは、あるグラフの頂点集合から別のグラフの頂点集合へのマッピングであり、隣接する頂点を隣接する頂点にマッピングします。このタイプのグラフ間のマッピングは、グラフ理論に対するカテゴリ理論的アプローチで最も一般的に使用されます。適切なグラフの色付けは、完全グラフへの準同型として同等に記述できます。

2. グラフの準同型次数は、最大クリークマイナーの順序であるハドヴィガー数と同義です。

ハイパーアーク

ソースとターゲットのセットを持つ有向ハイパーエッジ。

ハイパーエッジ

グラフのエッジには正確に 2 つのエンドポイントが必要であるという要件とは対照的に、ハイパーグラフ内のエッジには任意の数のエンドポイントがあります。

ハイパーキューブ

ハイパーキューブ グラフは、幾何学的ハイパーキューブの頂点と辺から形成されるグラフです。

ハイパーグラフ

ハイパーグラフは、各エッジ (このコンテキストではハイパーエッジと呼ばれます) が 2 つ以上のエンドポイントを持つことができるグラフの一般化です。

低

この接頭辞は、グラフの特性と組み合わされて、特性を持たないグラフであるが、頂点を一つ削除することで形成されるすべてのサブグラフが特性を持つグラフを示します。たとえば、ハイポハミルトングラフはハミルトン閉路を持たないグラフですが、頂点を一つ削除するとハミルトンサブグラフが生成されます。特性を持つグラフですが、頂点を一つ削除するとハミルトンサブグラフが生成されないグラフに使用される臨界グラフと比較してください。^[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 )の反転した矢印です。

孤立した

グラフの孤立頂点とは次数が0の頂点、つまり接続辺を持たない頂点のことである。^[2]

同形の

2 つのグラフの間に同型性がある場合、それらのグラフは同型です。同型性を参照してください。

同型性

グラフ同型性は、あるグラフの頂点と辺が別のグラフの頂点と辺と 1 対 1 で対応関係を保つことです。このように関連する 2 つのグラフは同型であると言われます。

等周

拡張を参照してください。

地峡

削除するとグラフが切断されるエッジという意味で、ブリッジの同義語です。

参加する

2 つのグラフの結合は、一方のグラフの各頂点からもう一方のグラフの各頂点に辺を追加することによって、それらの互いに素な和集合から形成されます。つまり、これは補集合の互いに素な和集合の補集合です。

け

完全グラフ、完全二部グラフ、完全多部グラフの表記については、「complete」を参照してください。

κ

κ ( G ) (ギリシャ文字のカッパを使用) は、 Gの頂点の接続性、またはGのクリーク数を表します。

カーネル

有向グラフのカーネルは、安定かつ吸収性のある頂点の集合です。

結び目

有向グラフの避けられない部分。結び目 (数学)および結び目理論を参照してください。

ら

L ( G ) はGの折れ線グラフです。線を参照してください。

ラベル

1. グラフの頂点または辺に関連付けられた情報。ラベル付きグラフとは、頂点または辺にラベルがあるグラフのことです。頂点ラベルまたは辺ラベルという用語は、グラフのどのオブジェクトにラベルがあるかを指定するために使用されます。グラフのラベル付けは、特定の制約に従ってグラフにラベルを割り当てるさまざまな問題を指します。ラベルを色として解釈するグラフの色付けも参照してください。

2.グラフの列挙の文脈では、グラフの頂点がすべて互いに区別できる場合、その頂点はラベル付けされていると言われます。たとえば、頂点と 1 からグラフの順序までの整数との 1 対 1 の対応を固定することで、これを真にすることができます。頂点にラベルが付けられている場合、互いに同型のグラフ (ただし、頂点の順序は異なる) は、別のオブジェクトとしてカウントされます。対照的に、頂点にラベルが付けられていない場合、互いに同型のグラフは別々にカウントされません。

葉

1. リーフ頂点またはペンダント頂点（特にツリー内）は、次数が 1 の頂点です。リーフ エッジまたはペンダント エッジは、リーフ頂点をその単一の隣接頂点に接続するエッジです。

2.木の葉の累乗は、頂点が木の葉であり、辺が木内の距離が最大で指定されたしきい値である葉を接続するグラフです。

長さ

重み付けされていないグラフでは、サイクル、パス、またはウォークの長さは、使用されるエッジの数です。重み付けされたグラフでは、長さは、使用されるエッジの重みの合計になる場合があります。長さは、グラフ内の 2 つの頂点間の最短パス、内周(最短サイクル長)、および最長パスを定義するために使用されます。

レベル

1. これはノードの深さに1を加えたものですが、一部の^{[12]ではこれを}深さと同義であると定義しています。ルート付きツリーのノードのレベルは、ルートからノードまでのパスにあるノードの数です。たとえば、ルートはレベル1で、隣接するノードのいずれかがレベル2になります。

2. 同じレベルまたは深さを持つすべてのノードの集合。^[12]

ライン

無向辺の同義語。グラフGの線グラフ L ( G )は、 Gの各辺に頂点があり、 G内の端点を共有する辺のペアごとに辺があるグラフです。

リンケージ

退化の同義語。

リスト

1. 隣接リストは、グラフ アルゴリズムで使用されるグラフのコンピュータ表現です。

2.  リストカラーリングは、各頂点に使用可能な色のリストがあるグラフカラーリングのバリエーションです。

地元

グラフのローカル プロパティは、グラフ内の頂点の近傍によってのみ決定されるプロパティです。たとえば、グラフのすべての近傍が有限である場合、そのグラフはローカル有限です。

ループ

ループまたは自己ループは、両方の端点が同じ頂点である辺です。これは長さ1のサイクルを形成します。これらは単純なグラフでは許可されません。

倍率

頂点拡張の同義語。

マッチング

マッチングとは、どの 2 つの辺も頂点を共有しない辺の集合です。頂点は、マッチング内の辺の端点の 1 つである場合に、マッチングまたは飽和状態になります。完全マッチングまたは完全マッチングは、すべての頂点が一致するマッチングです。これは 1 因子とも呼ばれ、順序が偶数の場合にのみ存在できます。奇数順序のグラフにおけるほぼ完全なマッチングは、1 つの頂点を除くすべての頂点が飽和状態になるマッチングです。最大マッチングは、可能な限り多くの辺を使用するマッチングです。グラフGのマッチング数α ′( G )は、最大マッチング内の辺の数です。最大マッチングは、これ以上の辺を追加できないマッチングです。

最大限

1. グラフGのサブグラフが特定の特性に対して最大であるとは、その特性を持ち、かつGのサブグラフでもあるそのサブグラフの他のスーパーグラフが同じ特性を持たない場合です。つまり、その特性を持つサブグラフの最大要素です。たとえば、最大クリークは、より大きな完全サブグラフに拡張できない完全サブグラフです。「最大」という言葉は「最大」と区別する必要があります。最大サブグラフは常に最大ですが、その逆は必ずしも当てはまりません。

2. 与えられた特性を持つ単純なグラフは、グラフの単純さと特性の両方を維持しながら、それ以上の辺を追加することができない場合（頂点集合は変更されないまま）、その特性に対して最大です。したがって、たとえば、最大平面グラフは、それ以上の辺を追加すると非平面グラフになるような平面グラフです。

最大

与えられたグラフGのサブグラフは、特定のプロパティを持つすべてのサブグラフの中で最大のサブグラフ (順序またはサイズで) である場合に、特定のプロパティに対して最大です。たとえば、最大クリークは、与えられたグラフ内の最大のクリークのいずれかです。

中央値

1. 頂点の三つ組の中央値。特に中央値グラフとモジュラー グラフにおいて、すべての頂点のペア間の最短経路に属する頂点。

2.中央値グラフは、3 つの頂点ごとに一意の中央値を持つグラフです。

メイニエル

1. アンリ・メイニエル、フランスのグラフ理論家。

2.メイニエル グラフは、長さ 5 以上の奇数サイクルごとに少なくとも 2 つの弦があるグラフです。

最小限

与えられたグラフのサブグラフが特定のプロパティに対して最小であるとは、そのサブグラフがそのプロパティを持っているが、そのサブグラフのどの真サブグラフも同じプロパティを持っていないことを意味します。つまり、そのサブグラフはそのプロパティを持つサブグラフの最小要素です。

最小カット

カットセットの合計重量が最小のカット。指定された頂点のペアを分離するカットに限定される場合もあります。最大フロー最小カット定理によって特徴付けられます。

マイナー

グラフHが別のグラフGのマイナーであるとは、 Gから辺または頂点を削除し、Gの辺を縮約することによってHが得られる場合です。 H の頂点を形成するために縮約された G のサブグラフがすべて小さな直径を持つような方法でマイナーとして形成できる場合、それは浅いマイナーです。 GがHのサブ分割であるサブグラフを持つ場合、HはGの位相マイナーです。グラフがH をマイナーとして持たない場合、それはHマイナーフリーです。グラフの族は、マイナーに関して閉じている場合、マイナー閉じています。ロバートソン-シーモア定理は、マイナー閉じた族を、有限の禁制マイナー集合を持つものとして特徴付けます。

混合

混合グラフは、有向エッジと無向エッジの両方を含むことができるグラフです。

モジュラー

1.  モジュラー グラフ。頂点の 3 つ組ごとに、その 3 つの組のすべてのペア間の最短経路に属する中央頂点が少なくとも 1 つあるグラフ。

2.  モジュラー分解。グラフをサブグラフに分解し、そのサブグラフ内のすべての頂点がグラフの残りの部分に同じように接続します。

3.  グラフ クラスタリングにおけるモジュール性、つまり、クラスタ間エッジの数とその期待値の差。

単調

グラフの単調性は、サブグラフに対して閉じている性質です。つまり、G が単調性を持つ場合、Gのすべてのサブグラフも単調性を持つ必要があります。遺伝的（誘導サブグラフに対して閉じている）またはマイナー閉じている（マイナーに対して閉じている）と比較してください。

ムーアグラフ

ムーアグラフは、ムーア境界が正確に満たされる正則グラフです。ムーア境界は、グラフの次数、直径、順序に関連する不等式であり、エドワード F. ムーアによって証明されました。すべてのムーア グラフはケージです。

マルチグラフ

マルチグラフは、複数の隣接性 (多くの場合、自己ループ) を許容するグラフであり、単純である必要のないグラフです。

複数の隣接

多重隣接または多重エッジとは、すべて同じエンドポイント (有向グラフの場合は同じ方向) を持つ複数のエッジのセットです。複数のエッジを持つグラフは、マルチグラフと呼ばれることがよくあります。

多重性

エッジの多重度は、多重隣接におけるエッジの数です。グラフの多重度は、そのエッジの最大多重度です。

いいえ

1. オープンな近隣地域とクローズドな近隣地域の表記については、近隣地域を参照してください。

2. 小文字のn は、特定のグラフの頂点の数を表すためによく使用されます (特にコンピューター サイエンスの分野)。

近所の人

近所の人

特定の頂点に隣接する頂点。

近所

近所

頂点vの開近傍（または近傍）は、 vに隣接するすべての頂点によって誘導されるサブグラフです。閉近傍も同様に定義されますが、v自体も含まれます。Gにおけるvの開近傍はN G ( _v )またはN ( v )と表記され、閉近傍はN G [ v ]またはN [ v ]と表記されます。近傍の開_状態または閉状態が指定されていない場合は、開いているものとみなされます。

ネットワーク

属性 (名前など) がノードやエッジに関連付けられているグラフ。

ノード

頂点の同義語。

非エッジ

非エッジまたは反エッジは、隣接していない頂点のペア、つまり補グラフのエッジです。

ヌルグラフ

空のグラフを参照してください。

奇数

1. 奇サイクルとは、長さが奇数のサイクルのことです。非二部グラフの奇内周は、その最短の奇サイクルの長さです。奇ホールは、奇サイクルの特殊なケースで、誘導され、4 つ以上の頂点を持つものです。

2. 奇頂点とは、次数が奇数である頂点のことです。握手補題により、すべての有限無向グラフには偶数個の奇頂点があります。

3. 奇数耳は、奇数個の辺を持つ単純パスまたは単純サイクルであり、因数臨界グラフの奇数耳分解で使用されます。「耳」を参照してください。

4. 奇弦とは、偶数サイクル内で奇数距離だけ離れた 2 つの頂点を結ぶ辺です。奇弦は、強い弦グラフを定義するために使用されます。

5.奇グラフはクネザーグラフの特殊なケースであり、( 2n − 1)要素集合の( n −1)要素部分集合ごとに1つの頂点を持ち、対応する集合が互いに素である場合に2つの部分集合を接続する辺を持つ。

開ける

1. 近所を見る。

2. 歩くを参照してください。

注文

1. グラフGの位数は、その頂点の数| V ( G )|です。この量には変数nがよく使用されます。辺の数であるサイズも参照してください。

2.グラフの論理の一種。1 次および 2 次を参照。

3. グラフの順序とは、グラフの頂点を順番に配置することです。特に、位相順序(すべての辺が順序内の前の頂点から後の頂点に向かう有向非巡回グラフの順序) や退化順序 (各頂点の誘導サブグラフとそれ以降のすべての頂点の次数が最小となる順序) のコンテキストで使用されます。

4. ヘイブンまたはブラムブルの順序については、ヘイブンとブラムブルを参照してください。

オリエンテーション

指向性のある

1.無向グラフの方向付けとは、その辺に方向を割り当てて、有向グラフにすることです。有向グラフとは、方向が割り当てられたグラフです。たとえば、ポリツリーは有向ツリーです。有向ツリー (樹状) とは異なり、その辺の方向の一貫性は要求されません。その他の特殊な方向付けには、トーナメント(完全グラフの方向付け)、強い方向付け(強く接続されている方向付け)、非巡回方向 (非巡回である方向付け)、オイラー方向 (オイラーである方向付け)、推移的方向(推移的に閉じている方向付け) などがあります。

2. 有向グラフ。一部の著者は有向グラフの同義語として使用しています。

アウトディグリー

程度を参照してください。

外側の

顔を見てください。

外平面

外平面グラフは、すべての頂点がグラフの外面上にあるように平面に（交差せずに）埋め込むことができるグラフです。

親

ルート付きツリーでは、頂点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平面グラフは、1 辺あたり最大kの交差で平面に描画できるグラフです。

ポリツリー

ポリツリーは有向ツリーです。つまり、基礎となる無向グラフがツリーである有向非巡回グラフです。

力

1.グラフGのグラフ パワー G ^kは、同じ頂点集合上の別のグラフです。2 つの頂点がG ^k内で隣接しているとは、それらの頂点がG内で最大でk の距離にある場合です。リーフ パワーは、ツリーのパワーからツリーのリーフによって誘導されるサブグラフを取得して派生した、密接に関連した概念です。

2.  パワーグラフ分析は、ネットワーク内のクリーク、バイクリーク、スターを識別して複雑なネットワークを分析する方法です。

3.  スケールフリーネットワークの次数分布におけるべき乗法則は、与えられた次数の頂点の数が次数のべき乗に比例する現象です。

前任者

有向パス内で特定の頂点の前に来る頂点。

ちゃんとした

1. 真部分グラフとは、グラフ全体に対して少なくとも 1 つの頂点または辺を削除した部分グラフです。有限グラフの場合、真部分グラフはグラフ全体と同型になることはありませんが、無限グラフの場合は同型になることがあります。

2. 適切な色付けとは、グラフの頂点に色を割り当てること（色付け）であり、各辺の端点に異なる色を割り当てます。色を参照してください。

3.真区間グラフまたは真円弧グラフは、区間または円弧の集合の交差グラフであり、区間または円弧が別の区間または円弧を含まないグラフです。真区間グラフは、単位区間グラフ (常に単位区間で表すことができるため) または無差別グラフとも呼ばれます。

財産

グラフプロパティとは、一部のグラフでは真で、他のグラフでは偽となる可能性のあるもので、ラベルなどの付随情報ではなくグラフ構造のみに依存します。グラフ プロパティは、グラフのクラス (特定のプロパティを持つグラフ) の観点から同等に説明できます。より一般的には、グラフ プロパティは、グラフのサイズ、順序、次数シーケンスなどの付随情報とは独立したグラフの関数である場合もあります。このより一般的なプロパティの定義は、グラフの不変量とも呼ばれます。

疑似森林

疑似フォレストは、接続された各コンポーネントが最大 1 つのサイクルを持つ無向グラフ、または各頂点が最大 1 つの出力エッジを持つ有向グラフです。

擬似文字

擬似グラフは、自己ループを許可するグラフまたはマルチグラフです。

準線グラフ

準直線グラフまたは局所共二部グラフは、各頂点の開近傍を 2 つのクリークに分割できるグラフです。これらのグラフは常にクローフリーであり、特殊なケースとして直線グラフが含まれます。これらはクローフリー グラフの構造理論で使用されます。

準ランダムグラフシーケンス

準ランダム グラフ シーケンスは、エルデシュ-レーニ ランダム グラフ モデルに従って生成されたランダム グラフシーケンスといくつかの特性を共有するグラフ シーケンスです。

矢筒

矢筒は、圏論で使用される有向多重グラフです。矢筒の辺は矢印と呼ばれます。

半径

グラフの半径は、任意の頂点の最小離心率です。

ラマヌジャン

ラマヌジャングラフは、スペクトル展開が可能な限り大きいグラフです。つまり、隣接行列の 2 番目に大きい固有値が最大 であるようなd正則グラフです。${\displaystyle 2{\sqrt {d-1}}}$

レイ

無限グラフ内の光線は、正確に 1 つの終点を持つ無限の単純なパスです。グラフの端点は光線の同値類です。

到達可能性

グラフ内のある頂点から別の頂点へ移動する機能。

到達可能

肯定的な到達可能性を持ちます。頂点yは、頂点xから到達可能であるとされるのは、 xからyへのパスが存在する場合です。

認識できる

再構築予想の文脈では、グラフのデッキからその真偽を判断できる場合、グラフ プロパティは認識可能です。多くのグラフ プロパティは認識可能であることが知られています。再構築予想が真である場合、すべてのグラフ プロパティは認識可能です。

再建

再構築予想は、各無向グラフG は、そのデッキ、つまり Gからあらゆる方法で 1 つの頂点を削除することによって形成されるグラフの多重集合によって一意に決定されるというものです。この文脈では、再構築とは、デッキからグラフを形成することです。

矩形

ちょうど 4 つの辺と 4 つの頂点で構成される単純なサイクル。

通常

グラフのすべての頂点の次数がdである場合、そのグラフはd正則です。正則グラフとは、あるdに対してd正則であるグラフです。

定期トーナメント

通常のトーナメントは、すべての頂点の入次数が出次数と等しいトーナメントです。

逆行する

「転置」を参照してください。

根

1. グラフ、特に有向木および根付きグラフ内の指定された頂点。

2.グラフのべき乗の逆演算:グラフGのk乗根は、同じ頂点集合上の別のグラフであり、2 つの頂点がG内で隣接しているのは、それらの頂点間の距離が根で最大でkである場合のみです。

飽和した

マッチングを参照してください。

検索番号

ノード検索数はパス幅と同義です。

2番目の注文

グラフの2 階論理は、変数が頂点、辺、頂点の集合、および (場合によっては) 辺の集合を表す論理形式です。この論理には、頂点と辺が接続されているかどうか、および頂点または辺が集合に属しているかどうかをテストするための述語が含まれます。変数が頂点のみを表す 1 階論理とは区別されます。

自己ループ

loop の同義語。

分離頂点

アーティキュレーションポイントを参照してください。

分離番号

頂点分離数はパス幅と同義です。

兄弟

ルート付きツリーでは、頂点vの兄弟とは、 vと同じ親頂点を持つ頂点のことです 。

単純

1.単純グラフとは、ループや多重隣接のないグラフです。つまり、各エッジは 2 つの異なるエンドポイントを接続し、2 つのエッジが同じエンドポイントを持つことはありません。単純エッジとは、多重隣接の一部ではないエッジです。多くの場合、特に指定がない限り、グラフは単純であると見なされます。

2. 単純パスまたは単純サイクルとは、重複する頂点がなく、したがって重複するエッジがないパスまたはサイクルです。

シンク

シンクは、有向グラフでは、出力エッジを持たない頂点です (出力次数は 0 です)。

サイズ

グラフGの大きさはその辺の数| E ( G )|である。^[13]この量を表すために変数mがよく使われる。頂点の数orderも参照。

スモールワールドネットワーク

スモールワールドネットワークとは、ほとんどのノードが互いに隣接していないが、ほとんどのノードは他のすべてのノードから少数のホップまたはステップで到達できるグラフです。具体的には、スモールワールドネットワークは、ランダムに選択された2つのノード間の典型的な距離L （必要なステップ数）が、ネットワーク内のノード数Nの対数に比例して増加するグラフとして定義されます^[14]

皮肉

スナークは、彩度指数が 4 である、単純で連結されたブリッジのない 3 次グラフです。

ソース

有向グラフのソースとは、入ってくるエッジがない頂点（入次数が 0）のことです。

空間

代数的グラフ理論では、2 値体上の複数のベクトル空間がグラフに関連付けられることがあります。各ベクトル空間には、ベクトルに対する辺または頂点の集合と、ベクトル和演算としての集合の対称差があります。辺空間はすべての辺の集合の空間であり、頂点空間はすべての頂点の集合の空間です。カット空間は、グラフのカットセットを要素とする辺空間の部分空間です。サイクル空間は、オイラー全域サブグラフを要素としています。

スパナ

スパナとは、最短経路の距離が密グラフまたはその他のメトリック空間内の最短経路の距離に近似する (通常は疎な) グラフです。そのバリエーションには、頂点が幾何空間内の点である幾何学的スパナ、距離がグラフの距離に近似するグラフの全域木である木スパナ、距離が元のグラフの距離に近似する密グラフの疎なサブグラフである グラフスパナ などがあります。貪欲スパナは貪欲アルゴリズムによって構築されるグラフスパナで、通常は最短から最長までのすべてのエッジを考慮し、距離の近似値を維持するために必要なエッジのみを保持します。

跨る

部分グラフが全域グラフであるとは、その部分グラフが与えられたグラフの頂点をすべて含んでいる場合です。重要な例としては、全域木、つまり部分グラフが木である場合や、完全マッチング、つまり部分グラフがマッチングである場合などがあります。全域部分グラフは、特に正則な場合 (ただし、正則だけではない) は因子と呼ばれることもあります。

まばらな

スパース グラフとは、頂点の数に比べて辺の数が少ないグラフです。定義によっては、同じ特性が、特定のグラフのすべてのサブグラフにも当てはまる場合もあります。

スペクトル

スペクトラム

グラフのスペクトルは、その隣接行列の固有値の集合です。スペクトル グラフ理論は、スペクトルを使用してグラフを分析するグラフ理論の分野です。スペクトル展開も参照してください。

スプリット

1.分割グラフは、頂点をクリークと独立集合に分割できるグラフです。関連するグラフのクラスである二重分割グラフは、強い完全グラフ定理の証明に使用されます。

2.任意のグラフの分割とは、その頂点を 2 つの空でない部分集合に分割することであり、この切断にまたがる辺は完全な二部グラフを形成します。グラフの分割は、分割分解と呼ばれるツリー構造で表すことができます。分割は、他の分割と交差しない場合は強い分割と呼ばれます。分割は、両側に 1 つ以上の頂点がある場合には非自明と呼ばれます。非自明な分割がない場合には、グラフは素数と呼ばれます。

3.  頂点分割(頂点切断とも呼ばれる) は、頂点を 2 つに分割する基本的なグラフ操作です。分割された 2 つの新しい頂点は、元の頂点が隣接していた頂点に隣接します。頂点分割の逆は頂点収縮です。

四角

1. グラフGの平方はグラフの累乗 G ²です。逆の場合、GはG ²の平方根です。二部グラフの半平方は、二部グラフの片側によって誘導されるその平方の部分グラフです。

2.スクエアグラフは、すべての境界面が 4 サイクルであり、次数 ≤ 3 のすべての頂点が外面に属するように描画できる平面グラフです。

3. 正方格子グラフは、単位長さの辺で接続された整数座標を持つ平面上の点から定義される格子グラフです。

安定した

安定集合は独立集合の同義語です。

星

スターは内部に 1 つの頂点を持つ木です。つまり、 n ≥ 2である完全な二部グラフK _{1, n}です。3 つの葉を持つスターの特殊なケースはクローと呼ばれます。

強さ

グラフの強さは、すべての可能な削除における、グラフから削除されたエッジの数と作成されたコンポーネントの数の最小比率です。これは、頂点の削除に基づく強靭性に類似しています。

強い

1.有向グラフの強い接続性と強く接続されたコンポーネントについては、「接続」と「コンポーネント」を参照してください。強い方向とは、強く接続された方向のことです。方向を参照してください。

2.強いパーフェクトグラフ定理については、perfect を参照してください。

3.強正則グラフとは、隣接する 2 つの頂点が同じ数の共有隣接頂点を持ち、隣接しない 2 つの頂点が同じ数の共有隣接頂点を持つ正則グラフです。

4.強い弦グラフとは、長さが 6 以上のすべての偶数サイクルに奇数の弦がある弦グラフです。

5. 強く完全なグラフとは、すべての誘導サブグラフにすべての最大クリークを満たす独立集合があるグラフです。メイニエル グラフは、すべての頂点がこのような独立集合に属するため、「非常に強く完全なグラフ」とも呼ばれます。

亜森林

フォレストのサブグラフ。

サブグラフ

グラフGのサブグラフは、 Gの頂点と辺のサブセットから形成される別のグラフです。頂点サブセットには、辺サブセットのすべての端点が含まれている必要がありますが、追加の頂点が含まれている場合もあります。スパニング サブグラフは、グラフのすべての頂点を含むグラフです。誘導サブグラフは、端点が頂点サブセットに属するすべての辺を含むグラフです。

サブツリー

サブツリーは、ツリーの接続されたサブグラフです。ルート付きツリーの場合、サブツリーは、選択された頂点から到達可能なすべての頂点と辺によって形成される、特別なタイプの接続されたサブグラフとして定義されることがあります。

後継

有向パス内で特定の頂点の後に来る頂点。

超濃縮装置

スーパーコンセントレータは、頂点IとO の指定された等しいサイズの 2 つのサブセットを持つグラフであり、 IとT Oの等しいサイズの 2 つのサブセットSごとに、Sのすべての頂点をTの頂点に接続する互いに素なパスのファミリが存在します。一部のソースでは、スーパーコンセントレータが有向非巡回グラフであり、Iがソース、Oがシンクであることがさらに要求されます。

スーパーグラフ

与えられたグラフに頂点、辺、またはその両方を追加することによって形成されるグラフ。H がGのサブグラフである場合、GはHのスーパーグラフです。

シータ

1. シータグラフは、同じ2つの異なる端点を持つ3つの内部的に互いに素な（単純な）パスの和集合である。^[15]

2.ユークリッド平面上の点の集合のシータグラフは、各点を囲む円錐のシステムを構築し、円錐の中心線への投影が最小となる点に、円錐ごとに 1 つの辺を追加することによって構築されます。

3.グラフのロヴァース数またはロヴァース シータ関数は、半正定値計画法によって多項式時間で計算できるクリーク数と彩色数に関連するグラフ不変量です。

トムセングラフ

トムセングラフは、完全な二部グラフ の名前です。${\displaystyle K_{3,3}}$

位相的な

1.トポロジカル グラフは、グラフの頂点と辺を平面上の点と曲線で表現したものです (交差を避ける必要はありません)。

2.  位相グラフ理論はグラフ埋め込みの研究です。

3.  トポロジカル ソートは、有向非巡回グラフを位相的順序、つまり各辺がシーケンス内の前の頂点から後の頂点に向かうような頂点シーケンスに配置するアルゴリズムの問​​題です。

完全に切断された

エッジレスの同義語。

ツアー

閉じたトレイル。同じ頂点で始まり、終わり、重複するエッジがないウォークです。オイラー ツアーは、すべてのグラフ エッジを使用するツアーです。オイラーを参照してください。

トーナメント

トーナメントは完全グラフの方向です。つまり、2 つの頂点が 1 つの有向辺 (2 つの頂点間の 2 つの方向のうちの 1 つの方向にのみ進む) で接続される有向グラフです。

追跡可能

追跡可能なグラフは、ハミルトン経路を含むグラフです。

トレイル

エッジが繰り返されない散歩。

推移的

Having to do with the transitive property. The transitive closure of a given directed graph is a graph on the same vertex set that has an edge from one vertex to another whenever the original graph has a path connecting the same two vertices. A transitive reduction of a graph is a minimal graph having the same transitive closure; directed acyclic graphs have a unique transitive reduction. A transitive orientation is an orientation of a graph that is its own transitive closure; it exists only for comparability graphs.

transpose

The transpose graph of a given directed graph is a graph on the same vertices, with each edge reversed in direction. It may also be called the converse or reverse of the graph.

tree

1.  A tree is an undirected graph that is both connected and acyclic, or a directed graph in which there exists a unique walk from one vertex (the root of the tree) to all remaining vertices.

2.  A k-tree is a graph formed by gluing (k + 1)-cliques together on shared k-cliques. A tree in the ordinary sense is a 1-tree according to this definition.

tree decomposition

A tree decomposition of a graph G is a tree whose nodes are labeled with sets of vertices of G; these sets are called bags. For each vertex v, the bags that contain v must induce a subtree of the tree, and for each edge uv there must exist a bag that contains both u and v. The width of a tree decomposition is one less than the maximum number of vertices in any of its bags; the treewidth of G is the minimum width of any tree decomposition of G.

treewidth

The treewidth of a graph G is the minimum width of a tree decomposition of G. It can also be defined in terms of the clique number of a chordal completion of G, the order of a haven of G, or the order of a bramble of G.

triangle

A cycle of length three in a graph. A triangle-free graph is an undirected graph that does not have any triangle subgraphs.

trivial

A trivial graph is a graph with 0 or 1 vertices.^[16] A graph with 0 vertices is also called null graph.

Turán

1.  Pál Turán

2.  A Turán graph is a balanced complete multipartite graph.

3.  Turán's theorem states that Turán graphs have the maximum number of edges among all clique-free graphs of a given order.

4.  Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph.

twin

Two vertices u,v are true twins if they have the same closed neighborhood: N_G[u] = N_G[v] (this implies u and v are neighbors), and they are false twins if they have the same open neighborhood: N_G(u) = N_G(v)) (this implies u and v are not neighbors).

unary vertex

In a rooted tree, a unary vertex is a vertex which has exactly one child vertex.

undirected

An undirected graph is a graph in which the two endpoints of each edge are not distinguished from each other. See also directed and mixed. In a mixed graph, an undirected edge is again one in which the endpoints are not distinguished from each other.

uniform

A hypergraph is k-uniform when all its edges have k endpoints, and uniform when it is k-uniform for some k. For instance, ordinary graphs are the same as 2-uniform hypergraphs.

universal

1.  A universal graph is a graph that contains as subgraphs all graphs in a given family of graphs, or all graphs of a given size or order within a given family of graphs.

2.  A universal vertex (also called an apex or dominating vertex) is a vertex that is adjacent to every other vertex in the graph. For instance, wheel graphs and connected threshold graphs always have a universal vertex.

3.  In the logic of graphs, a vertex that is universally quantified in a formula may be called a universal vertex for that formula.

unweighted graph

A graph whose vertices and edges have not been assigned weights; the opposite of a weighted graph.

utility graph

The utility graph is a name for the complete bipartite graph ${\displaystyle K_{3,3}}$.

V

See vertex set.

valency

Synonym for degree.

vertex

A vertex (plural vertices) is (together with edges) one of the two basic units out of which graphs are constructed. Vertices of graphs are often considered to be atomic objects, with no internal structure.

vertex cut

separating set

A set of vertices whose removal disconnects the graph. A one-vertex cut is called an articulation point or cut vertex.

vertex set

The set of vertices of a given graph G, sometimes denoted by V(G).

vertices

See vertex.

Vizing

1.  Vadim G. Vizing

2.  Vizing's theorem that the chromatic index is at most one more than the maximum degree.

3.  Vizing's conjecture on the domination number of Cartesian products of graphs.

volume

The sum of the degrees of a set of vertices.

W

The letter W is used in notation for wheel graphs and windmill graphs. The notation is not standardized.

Wagner

1.  Klaus Wagner

2.  The Wagner graph, an eight-vertex Möbius ladder.

3.  Wagner's theorem characterizing planar graphs by their forbidden minors.

4.  Wagner's theorem characterizing the K₅-minor-free graphs.

walk

A walk is a finite or infinite sequence of edges which joins a sequence of vertices. Walks are also sometimes called chains.^[17] A walk is open if its first and last vertices are distinct, and closed if they are repeated.

weakly connected

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.

weight

A numerical value, assigned as a label to a vertex or edge of a graph. The weight of a subgraph is the sum of the weights of the vertices or edges within that subgraph.

weighted graph

A graph whose vertices or edges have been assigned weights. A vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges.

well-colored

A well-colored graph is a graph all of whose greedy colorings use the same number of colors.

well-covered

A well-covered graph is a graph all of whose maximal independent sets are the same size.

wheel

A wheel graph is a graph formed by adding a universal vertex to a simple cycle.

width

1.  A synonym for degeneracy.

2.  For other graph invariants known as width, see bandwidth, branchwidth, clique-width, pathwidth, and treewidth.

3.  The width of a tree decomposition or path decomposition is one less than the maximum size of one of its bags, and may be used to define treewidth and pathwidth.

4.  The width of a directed acyclic graph is the maximum cardinality of an antichain.

windmill

A windmill graph is the union of a collection of cliques, all of the same order as each other, with one shared vertex belonging to all the cliques and all other vertices and edges distinct.

• List of graph theory topics
• Gallery of named graphs
• Graph algorithms
• Glossary of areas of mathematics