検索結果

'''完全2部グラフ'''（かんぜんにぶグラフ、[[英語|英]]: complete bipartite graph）は、[[グラフ理論]]において、[[2部グラフ]]のうち特に第1の集合に属するそれぞれの頂点から第2の集合に属する全ての頂点に辺が伸びているものをいう。'''bicliq * 任意の ''k'' について、<math>K_{1,k}</math> を[[スター (グラフ理論)|スター]]と呼ぶ。[[木 (数学)|木]]でもある完全2部グラフは、全てスターである。 …

'''空グラフ'''（[[英語|英]]: '''null graph'''）は、[[数学]]の[[グラフ理論]]において、[[位数]][[0]]の[[グラフ理論|グラフ]]、または辺のないグラフ ('''edgeless graph''') を意味する（後者は '''empty graph''' とも呼ぶ）。 …y \isin V : \exists path(x,y)</math>）があり、[[閉路グラフ|閉路]]がなく、[[木 (数学)|木]]であり、[[木 (数学)|森]]であり、[[有向グラフ]]または[[無向グラフ]]（あるいは両方）であり、[[完全グラフ]]であり、辺のないグラフ (empty gr …

…極大木'''（きょくだいき）、'''スパニング木'''、'''スパニングツリー'''とは、全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（[[連結グラフ|連結]]で[[閉路]]を持たないグラフ）であるものをいう。全域木は[[連結グラフ]]に必ず存在し、連結でないグラフには存在しない。 * [[グラフ理論]] …

[[数学]]の[[グラフ理論]]の分野における'''頂点推移グラフ'''（ちょうてんすいいグラフ、{{Lang-en-short|vertex-transitive graph}} が存在する[[グラフ理論|グラフ]] ''G'' のことを言う。 …

…つもんだい、{{Lang-en-short|Guan's route problem, Chinese postman problem}}）とは、[[グラフ理論]]における問題の一つであり、以下のように定義される<ref name="EncyclopediaOR">{{Citation|author=Saul # グラフ中に存在する、次数が奇数であるすべての頂点を集める。なおその頂点数は「[[次数 (グラフ理論)#握手補題|握手補題]]」により必ず偶数個になる。 …

'''車輪グラフ'''（しゃりんグラフ、[[英語|英]]: Wheel graph）とは、[[グラフ理論]]のグラフの1つであり、[[閉路グラフ]]と、そのすべての頂点に接続するユニバーサル頂点（支配頂点）と呼ばれる頂点からなるグラフである。''n''… ** 車輪グラフは[[ハリングラフ]]（[[木_(数学)|木]]（グラフ）の葉を閉路でつないだ平面グラフ）である。 …

[[Category:グラフ理論]] …

…s formula}}）は、[[グラフ理論]]における公式のひとつ。正整数 ''n'' に対し、''n'' 個のラベル付き頂点を持つ[[木 (数学)|木]]の個数は ''n''^''n''-2 であるというもの。[[アーサー・ケイリー|ケイリー]]は19世紀のイギリスの数学者。 [[Category:グラフ理論]] …

[[グラフ理論]]における'''次数'''（じすう、{{lang-en-short|degree, valency}}）は、グラフの頂点に接合する辺の数を意味し、ルー …ペンダント辺である。これはグラフ理論の中でも特に[[木 (数学)|木]]の研究でよく使われ、特に[[データ構造]]としての[[木構造 (データ構造)|木]]に対してよく使われる。 …

[[組み合わせ数学]]において、ラベル付きの[[木 (数学)|木]]に対する'''プリューファー列'''（{{lang-en-short|Prüfer sequence}}) あるいは'''プリューファーコード''' [[Category:グラフ理論]] …

[[グラフ理論]]において、'''木分解'''とは[[グラフ理論|グラフ]]から[[木 (数学)|木]]へのマッピングであり、{{仮リンク| 木幅|en|treewidth}}を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。 …元のグラフ''G''において2つの頂点が隣接するのは対応する部分木が共通部分を持つときに限る。それゆえ、''G''は部分木達の[[交差グラフ]]の[[グラフ理論#部分グラフと拡大グラフ|部分グラフ]]をなす。交差グラフそのものは[[弦グラフ]]である。 …

[[グラフ理論]]において'''ムーアグラフ'''とは、[[次数 (グラフ理論)|次数]]''d''、[[直径]]''k''の[[正則グラフ]]で、頂点数が以下の上限に一致するものである。 [[直径]]''k''、[[内周 (グラフ理論)|内周]]2''k''+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2''k''+1のときに長さ''g''のサイク …

'''クラスカル法'''（{{lang-en-short|Kruskal's algorithm}}）は、[[グラフ理論]]において重み付き[[連結グラフ]]の最小[[全域木]]を求める[[最適化問題]]の[[アルゴリズム]]である。 …en|Reverse-delete algorithm}}、[[ブルーフカ法]]などがある。最小全域木とは、グラフの全ての頂点を含む[[木 (数学)|木]]で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」（それぞれの連結部分の最小全域木の集合）を求められる。 …

…1</sub>}} としてオイラー標数は <math>\chi(K) = v - e</math> と書ける。もしグラフ {{mvar|K}} が[[木 (数学)|閉路をもたない]]ならば <math>\chi(K) = 1</math> である。また {{mvar|K}} が[[多面体]]である場合、 …

[[グラフ理論]]において、グラフ ''G''(''V'', ''E'') の頂点 ''V'' の 2 分割 (''S'', ''T'') を'''カット'''（{{ [[Category:グラフ理論]] …

…フの最小[[全域木]]を求める[[最適化問題]]のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される[[木 (数学)|木]]）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは[[1930年]]に数学者 Vojtěch Jarník が発見し …グラフなので、全ての頂点に常に道が存在する。プリム法の出力 ''Y'' に追加される辺と頂点はつねに接合しているため、''Y'' は[[木 (数学)|木]]である。''Y₁'' が P の最小全域木であるとする。''Y₁''=''Y'' なら、''Y'' は最 …

*[[グラフ理論]] …

[[グラフ理論]]における'''ケーニヒの補題'''は[[デネス・ケーニヒ]]<ref>Note that, although Kőnig's name is pro このとき、''G''は無限長の[[道 (グラフ理論)|単純道]]（同じ点を2度通らない道）を持つ。 …

[[Category:グラフ理論]] …

'''幅優先探索'''（はばゆうせんたんさく、{{lang-en-short|breadth first search}}）は[[グラフ理論]]([[:en:graph theory|Graph theory]])において[[木構造 (データ構造)|木構造]]([[:en:tree stru …