正則グラフ（せいそくグラフ、英: regular graph）は、グラフ理論において、各頂点の隣接する頂点数が全て同じであるようなグラフである。すなわち、全ての頂点の次数が等しい。頂点の次数が k の正則グラフを 「k-正則グラフ」または「次数 k の正則グラフ」と呼ぶ。 次数2までの正則グラフ...

から出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数をもつグラフを正則グラフと呼ぶ。任意の頂点 v について、d(v) = k が成り立つとき、k-正則という。k-正則なグラフのことを k-正則グラフという。グラフ G が持つ頂点の次数の最小値を δ(G)、最大値を Δ(G) で表す。また、次数...

正則の距離正則グラフ（英語版）の一つである。 ピーターセングラフの自己同型群（英語版）は対称群 S 5 {\displaystyle S_{5}} である。ピーターセングラフ上の S 5 {\displaystyle S_{5}} の振る舞いは、クネーザーグラフ...

グラフ理論において強正則グラフ（きょうせいそくグラフ、英: strongly regular graph）は次のように定義される。頂点数 v、次数 k の正則グラフ G = (V, E) が強正則であるとは、整数 λ と μ が存在して、 任意の隣接する2頂点は、ちょうど λ 個の近傍を共有する。 任意の隣接しない2頂点は、ちょうど...

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

ホフマン–シングルトングラフとは、50個の頂点と175個の辺からなる7-正則グラフである。これは(50,7,0,1)-強正則グラフであり一意である。このグラフはアラン・ホフマンとロバート・シングルトンによって、ムーアグラフの分類の過程で構成された。またホフマン–シングルトングラフは知られているムーアグラフの中でもっとも頂点数が多いグラフである。...

孤立頂点を含まない対称グラフは、頂点推移的である。また、頂点推移グラフは正則である。しかし、すべての頂点推移グラフが対称であるとは限らない（例えば、切頂四面体の辺から成るグラフ）。また、すべての正則グラフが頂点推移的であるとは限らない（例えば、フルフトグラフ（英語版））。 対称グラフ（例えば、ピーターセングラフ...

と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数...

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

expression は正則表現とも呼ばれるが、正規表現と呼ぶのが一般的である。 正則作用: regular action。グラフが閉集合となるような連続作用。 正則性の公理: Axiom of regularity。公理的集合論の ZF 公理系における公理の一つ。 正則グラフ: グラフ理論において全ての頂点の隣接点の数が同じグラフ。...

グラフ理論においてムーアグラフとは、次数d、直径kの正則グラフで、頂点数が以下の上限に一致するものである。 1 + d ∑ i = 0 k − 1 ( d − 1 ) i . {\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}.} 直径k、内周2k+1のグラフ...