グラフ理論用語 英和対訳表

英和対訳表

cf.English日本語ほらあれ
MWgeneral graph一般グラフG=(V, E, φ)
MWvertex頂点
pointalias for vertex
nodeノード,節点alias for vertex
vertex set頂点集合
MWedge
linealias for edge
edge set辺集合
incidence map接続写像, 接合写像
order位数#(V)
sizeサイズ#(E)
join結ぶe は v, u を結ぶ
MWloopループ
linkリンクループでない
MWmultiple edge多重辺
adjacent隣接している
incident接続している
MWsimple graph単純グラフ
graphグラフ
MWempty graph空グラフNp サイズが0
MWcomplete graph完全グラフ, 完備グラフKp
isomorphism同型写像
isomorphic同型
MWdegree次数
Handshaking Lemma握手原理
MWeven vertex偶点次数が偶数
MWodd vertex奇点次数が奇数
even graph偶グラフ偶点のみ
odd graph奇グラフ奇点のみ
isolated vertex孤立点, 孤立頂点
end vertex, end point端点, 端頂点
Pigeonhole Principle鳩の巣原理
MWDirichlet's Box Principleディリクレの部屋割り論法
maximum degree最大次数Δ(G)
minimum degree最小次数δ(G)
MWregular graph正則グラフΔ(G)=δ(G)=r (r-正則)
neighbor
MWneighborhood, neighbor set近傍
subgraph部分グラフ
proper subgraph真部分グラフ
spanning subgraph全域部分グラフ, 生成部分グラフV'=V
MWfactor因子r-factor. 全域部分グラフがr-正則のとき
induced subgraph誘導部分グラフE'=E∩(V' 2)
complementary graph, complement補グラフ~G = (V, ~E), ~E = (V 2)\E
self complementary graph自己補グラフ~G = G
MWRamsey's Theoremラムゼイ定理
quotient graph商グラフG/e
contraction縮約
MWwalk遊歩道, 歩道v0-vn歩道
length長さ歩道に含まれる辺の数
distance距離最短の歩道の長さ
diameter直径グラフの2頂点間の距離の最大
closed walk閉じた歩道v0=vn
open walk開いた歩道v0≠vn
trail小道e1≠e2≠...≠en. ⊂walk
MWpath通路, 道, 路v0≠v1≠...≠vn. ⊂trail
MWcircuit閉路, 回路, サーキットv0=vn, v1≠v2≠...≠vn. ⊂trail
MWcycleサイクルalias for circuit
MWgirth内周グラフ内の最短サイクルの長さ
connected(Gは)連結であるGの任意の2頂点が通路で結ばれる
connected component連結成分Gの連結部分グラフでそれより大きい連結部分グラフに含まれないもの
component成分alias for connected component
MWdegree sequence次数列
MWgraphicグラフ的
MWbipartite graph, bigraph二部グラフVを空でなく元同士結ぶ辺のない2集合に分けれる
MWcomplete bigraph完全二部グラフV'とV''のどの頂点を結ぶ辺もある
König's Theoremケーニッヒの定理
bridgeeを除くと連結成分の個数が増えるときeは橋
bank橋を除いて残る2つの連結部分グラフ
cut point切断点v(およびvに接続する辺)を除くと連結成分が増える
articulation vertex関節点alias for cut point
forestグラフが閉路をもたないとき
tree木, 樹木連結な林
spanning tree全域木
spanning forest全域林
MWlabeled graphラベル付きグラフ
edge-labeled graph辺ラベル付きグラフ
vertex-labeled graph頂点ラベル付きグラフ
weight重み
MWweighted graph重み付きグラフ
weighted tree重み付き木
minimum spanning tree最小全域木, 最適木
Eulerlian circuitオイラー回路すべての辺を1度ずつ含む閉じた小道
Eulerlian graphオイラーグラフオイラー回路をもつグラフ
Eulerlian trailオイラー小道すべての辺を1度ずつ含む開いた小道
semi-Eulerlian graph半オイラーグラフオイラー小道をもつグラフ
MWgeneral directed graph一般有向グラフD=(V, A, ψ)
directed edge有向辺
arcalias for directed edge
arc set弧集合
initial vertex始点
terminal vertex終点
indirected graph無向グラフ
symmetric arc対称弧
multiple arc多重弧
simple directed graph単純有向グラフ
outdegree出次数, 正次数
indegree入次数, 負次数
orientation向きづけ
underlying indirected graph台無向グラフ
underlying graph台グラフalias for underlying indirected graph
directed walk有向遊歩道, 有向歩道
directed trail有向小道
directed path有向通路
directed cycle有向閉路
semi-walk半歩道台グラフにおける歩道
semi-trail半小道
semi-path半通路
semi-cycle半閉路
weakly connected弱連結どの2頂点にも半歩道がある
unilaterally connected片側連結どの2頂点にもどちら向きかの有向歩道がある
strongly connected強連結どの2頂点にも両方の向きに有向歩道がある
strongly connected orientation強連結な向きづけ(をもつ)Gに適当に向きをつければ強連結なDにできる
directed Eulerlian circuit有向オイラー回路
directed Eulerlian graph有向オイラーグラフ
directed Eulerlian trail有向オイラー小道
directed semi-Eulerlian graph有向半オイラーグラフ
MWhypergraph超グラフ, ハイパーグラフ
MWhyperedgeハイパーエッジ
t-uniformt一様
t-simplet単純
MWcliqueクリーク部分グラフで完全グラフになっているもの
MWperfect graph理想グラフ

参考


This document was generated through CMS which extended PukiWiki.