と G ′ {\displaystyle G'} はグラフ同型（あるいは単に同型）であるといい、 G ′ {\displaystyle G'} は G {\displaystyle G} の同型グラフであるという。 例として以下のようなグラフが与えられたとする。 このとき、隣接する頂点に対応する頂点は隣接していることがわかる。...

同型写像（どうけいしゃぞう、（英: isomorphism）あるいは単に同型とは、数学において準同型写像あるいは射であって、逆射を持つものである。 2つの数学的対象が同型 (isomorphic) であるとは、それらの間に同型写像が存在することをいう。自己同型写像は始域と終域が同じ同型...

未満となるグラフを n-クランという。 オイラー路（オイラー閉路・オイラーグラフ） ハミルトン路（ハミルトン閉路・ハミルトングラフ） 木 （根つき木・森） 全域木 シュタイナー木 直径 カット 2部グラフ （n 部グラフ・彩色） 同型グラフ 連結グラフ （連結成分・連結度） 平面グラフ （平面的グラフ） 隣接行列...

の自己同型全体の部分群を拡大のガロア群と呼ぶ。 p-進数の体 Qp は非自明な自己同型を持たない。 グラフ理論では、グラフの自己同型（英語版）(automorphism of a graph)は、頂点の置換で隣接関係を保つ写像のことを言う。 関係性の自己同型については、自己同型を保存する関係（英語版）(relation-preserving...

グラフは頂点推移的であると言われる。グラフの列挙（英語版）やグラフ同型の文脈において、ラベル付けされた頂点とされていない頂点を区別することは重要である。ラベル付けされた頂点は、それを他のラベル付けされた頂点と区別することを可能にするような外的な情報を備えるものである。二つのグラフ...

平面的でないグラフ 平面グラフ（へいめんグラフ、英: plane graph）は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフである。平面グラフと同型なグラフを平面的グラフ (planar graph) という。平面的グラフであっても、描き方によっては平面グラフにならない。 平面的グラフ...

ピーターセングラフとその一般化 パーフェクトグラフ 補グラフ 弦グラフ 大きなグラフ自己同型群 (Graph automorphism) を持つその他のグラフ（頂点推移グラフ、弧推移グラフ、距離推移グラフ） 強正則グラフとその一般化である距離正則グラフ (distance-regular graph)  グラフの2辺が共通の頂点を共有する場合は、2辺が「隣接する...

グラフ理論において、誘導部分グラフ（ゆうどうぶぶんグラフ、英: induced subgraph）とは、部分グラフの一種であり、あるグラフから、一部の頂点を取り出し、その頂点対の辺の有無が元のグラフと一致するグラフである。部分グラフは元のグラフから任意の頂点と任意の辺を選択して取り出したグラフ...

同型である場合をいう。ハイパーグラフが自己同型であるとは、頂点集合がラベルを付け直した頂点集合と準同型であることをいう。ハイパーグラフの自己同型の集合 H (= (X, E)) は、合成について群となり、ハイパーグラフの自己同型群と呼ばれ Aut(H) で表される。ハイパーグラフ...

f(v_{1})=v_{2}\ } であるような自己同型（英語版） f : V ( G ) → V ( G )   {\displaystyle f:V(G)\rightarrow V(G)\ } が存在するグラフ G のことを言う。 言い換えれば、グラフが頂点推移的であるとは、その自己同型...

グラフの全ての準同型（英語版）は自己同型である。図に示しているように、ピーターセングラフは5回対称としても3対称としても描けるが、対称群全体を表すような図を平面に描くことはできない。 ピーターセングラフは高い対称性があるがケイリーグラフではない。ケイリーグラフでない連結頂点推移グラフとしては最小である。...

命題論理と二値ブール代数に同型的な体系 「ベータ」 - 等号付き一階述語論理に同型的な体系 「ガンマ」 - 正規様相論理に（ほぼ）同型的な体系 アルファはベータやガンマに内包される。ベータはガンマには内包されない。 統語論: 空白のページ 字句はページ上の任意の場所に書ける。 任意のグラフを cut または...

数学のグラフ理論の分野における辺推移グラフ（へんすいいグラフ、英: edge-transitive graph）とは、与えられた任意の辺 e1 および e2 に対して、e1 を e2 へと写す自己同型（英語版）が存在するようなグラフ G のことを言う。 言い換えると、グラフ...

グラフは頂点推移的である。これは以下のケイリーグラフの特徴づけに繋がる： Sabidussiの定理：グラフ Γ が群 G のケイリーグラフである必要十分条件はグラフがグラフ自己同型として群 G の単純推移的な作用を持つことである。 ケイリーグラフ Γ = Γ(G, S) から群...

と表せる。n=4 のときはシュリクハンデグラフとパラメータが一致するが、これらはグラフ同型ではない。 ホフマン–シングルトングラフ：srg(50, 7, 0, 1) ジェウィルスグラフ（英語版）（Gewirtz graph）：srg(56, 10, 0, 2) M22グラフ（英語版）：srg(77, 16...

グラフのマトロイド M(G)についての色々な定理を証明した。その一つの定理である、現在ホイットニーの2-同型定理と呼ばれているものの言明は以下である。 GとHが孤立した頂点を持たないグラフであるとすると、 GとHが2-同型である時、その時に限り、M(G)とM(H)はグラフ同型である。...

isospectral）であると呼ばれる。 二つの共スペクトルグラフは互いに同型である必要はない、しかし同型なグラフは常に共スペクトルである。 ほとんどすべての木は共スペクトルである、すなわち、頂点が増えるにつれ、共スペクトルな木があるような木の割合は1に近づいてゆく。 正則グラフの一対は、それらの補グラフが共スペクトルであるときにかぎり、共スペクトルである。...

ホモロジー群は、複体のホモトピー同型性に関しての不変量である。 オイラー標数はホモロジー群の群同型性に関しての不変量であり、したがって複体のホモトピー同型性に関しての不変量である。 結び目不変量は、結び目の同型性に関しての不変量である。 グラフの頂点数は、グラフの同型性に関しての不変量である。...

頂点数が3のスターであるクローはクローフリーグラフ（誘導部分グラフとしてクローを持たないグラフ）の定義で有名である。また、ハスラー・ホイットニー (Hassler Whitney) のグラフ同型定理（一般的に、グラフ同型な線グラフはクローと三角形グラフ K3を除き同型である。）の例外の1つでもある。...

無向グラフの次数列 (degree sequence) とは、そのグラフの頂点の次数を増加しない順序で並べた数列である。上のグラフでは (3, 3, 3, 2, 2, 1, 0) となる。次数列はグラフ不変量であり、同型のグラフは同じ次数列を有する。しかし、一般に次数列だけでグラフ...

0年（平成2年）3月より営業運転を開始した大阪市交通局70系電車である。 導入当初は前後から見るとY字型をしたフェブレー社製シングルアームパンタグラフと同型のものが多かったが、近年さらに簡略化が進み、上枠、下枠とも1本の鋼管で済ませ、前後視ではT字型の形状のものが現れている。新幹線に採用されたタイプ...

グラフ）と同型なグラフになるからである。この定義の双対では、双対を4回取ると元のグラフに戻る。 平面グラフの弱い双対は、双対グラフのサブグラフで、その頂点は主グラフの面に対応する。平面グラフは、その弱い双対が森である場合に限り、外平面グラフになる。任意の平面グラフ...

に属することが証明されていない問題の多くは NP完全であり、その例は「NP完全問題」の項に譲る。それ以外の、 P にも NP完全にも属さない問題の候補としてグラフ同型性判定問題（英語版）が挙げられる。 Pは、決定性チューリングマシンを使って多項式時間で解ける問題のクラスである。定義より明らかに P ⊆ NP {\displaystyle...

グラフ同型な）多面体が存在する。そのようなグラフが与えられれば、凸多角形をより小さな凸多角形に細分化したものを、Tutte embeddingを用いて表現できる。 P. G. テイトは「3次の多面体グラフはハミルトン路を持つ」というテイト予想 (グラフ理論)を1884年に提唱したが、この予想1946年にはW...

v2 であるような自己同型（英語版） f : V(G) → V(G) が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う。 そのようなグラフ...

これらの同型は単純・半単純リー環の同型に対応し、リー群の同型にも対応する。それらは En 族（英語版）に文脈を与えもする。 異なる図形の間の同型に加えて、いくつかの図形は自分自身への同型すなわち「自己同型」も持つ。図形自己同型はリー環の外部自己同型（英語版）に対応する、つまり、外部自己同型群 Out...

グラフは頂点推移グラフとはならないことがHigmanによって証明されている。またMačajとŠiráňによれば、そのようなムーアグラフの自己同型群の位数は高々375である。 ムーアグラフの定義を内周が偶数も許容するように一般化すると、偶数内周のムーアグラフは一般化多角形の縮退したインシデントグラフ...

グラフ（英語版）、デザルググラフ（英語版）、ナウルグラフ（英語版）、コクセターグラフ（英語版）、トゥッテ-コクセターグラフ（英語版）、ディックグラフ（英語版）、フォスターグラフ（英語版）、ビッグス-スミスグラフ（英語版）など、多くの有名なグラフは立方体かつ対称的であった。...

完全2部グラフ（かんぜんにぶグラフ、英: complete bipartite graph）は、グラフ理論において、2部グラフのうち特に第1の集合に属するそれぞれの頂点から第2の集合に属する全ての頂点に辺が伸びているものをいう。bicliqueとも。 完全2部グラフ G := ( V 1 + V 2...

f が順序同型写像（英語版）であるとは、f が順序埋め込みな全単射であることをいう。 f: S → T が順序埋め込みであるとき、S は f によって T に（順序集合として）埋め込まれるという。 また順序同型 f: S → T が存在するとき、S と T は順序同型あるいは単に同型であるという。...

というような置換行列Pが存在する時かつその時に限り同型である。 具体的には、A1およびA2は相似であり、したがって同一の最小多項式、固有多項式、固有値、行列式、跡を有する。したがってこれらは、グラフの同型不変量として機能する。しかしながら、2つのグラフは同じ固有値の組を持つかもしれないが、同型...