Graph Theory
Graph Theory
グラフの用語をまとめます。順次更新。
Graph Theory
Connected Graph
- 任意の二頂点間にパスが存在するようなグラフを連結グラフという(プログラミングコンテストチャレンジブック 第2版より)
- 日本語で「連結である」とはグラフに対して用いるようだ。間にパスが存在する二頂点間の関係は「到達可能である」という表現を用いるらしい(アルゴリズムC 第3巻を参考)
- 英語では双方共に「Connected」という(Connectivity (graph theory) - Wikipedia, the free encyclopediaより)
A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph.
Connected Graph -- from Wolfram MathWorld
連結グラフ（れんけつグラフ, connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。
連結グラフ - Wikipedia
Disconnected Graph
- 連結グラフではないグラフ
- 日本語での表記はそのまま、「連結ではないグラフ」であるようだ(プログラミングコンテストチャレンジブック 第2版より)
A graph is said to be disconnected if it is not connected, i.e., if there exist two nodes in such that no path in has those nodes as endpoints.
Disconnected Graph -- from Wolfram MathWorld
Complete Graph
- 任意の二頂点間に枝があるグラフ(グラフ理論 - Wikipediaより)
A complete graph is a graph in which each pair of graph vertices is connected by an edge.
Complete Graph -- from Wolfram MathWorld
完全グラフとクリーク
任意の 2 頂点間に枝があるグラフのことを完全グラフ（完備グラフ）[英 complete graph]という。 n頂点の完全グラフは、Knで表す。
グラフ理論 - Wikipedia
Matching
- マッチング
- 辺集合M ⊆ Eで、お互いに頂点を共有しない(プログラミングコンテストチャレンジブック 第2版より)
- 最大マッチング
- 極大マッチング
グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。
マッチング (グラフ理論) - Wikipedia
a. 孤立点のないグラフに対し、|最大マッチング|+|最小辺カバー|=|V|
プログラミングコンテストチャレンジブック 第2版
c. (孤立点のないグラフに対し、)|最大マッチング|=|最小点カバー|
プログラミングコンテストチャレンジブック 第2版
Independent Set
- 安定集合
- 点集合S ⊆ Vで、Sのどの2点もGにおいて隣接していない(プログラミングコンテストチャレンジブック 第2版より)
- 最大安定集合
- 安定集合
グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。
独立集合 - Wikipedia
b. (孤立点のないグラフに対し、)|最大安定集合| + |最小点カバー| = |V|
プログラミングコンテストチャレンジブック 第2版
Vertex Cover
- 点カバー
- 点集合S ⊆ Vで、Gのどの辺も少なくとも1つのSに含まれる頂点に接続している(プログラミングコンテストチャレンジブック 第2版より)
- 日本語では頂点被覆ともいう(頂点被覆 - Wikipediaより)
- 最小点カバー
- 点カバー
グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。
頂点被覆 - Wikipedia
c. (孤立点のないグラフに対し、)|最大マッチング|=|最小点カバー|
プログラミングコンテストチャレンジブック 第2版
