被覆 (グラフ理論における) - 版の履歴

2008年11月13日 (木) 06:19にAlbeit-Kunによる

2008-11-13T06:19:29Z

Orsjwiki: "被覆 (グラフ理論における)" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:43:43Z

"被覆 (グラフ理論における)" を保護しました。 [edit=sysop:move=sysop]

2007年7月17日 (火) 05:46に122.17.2.240による

2007-07-17T05:46:38Z

2007年7月13日 (金) 05:53に122.17.2.240による

2007-07-13T05:53:43Z

2007年7月13日 (金) 04:18に211.9.146.171による

2007-07-13T04:18:07Z

2007年7月13日 (金) 04:17に211.9.146.171による

2007-07-13T04:17:38Z

122.17.2.240: 新しいページ: '【ひふく (cover)】 $G = (V, A)$ を無向グラフとする. 頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ ...'

2007-07-12T16:16:27Z

新しいページ: '【ひふく (cover)】 $G = (V, A)$ を無向グラフとする. 頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ ...'

新規ページ

【ひふく (cover)】

$G = (V, A)$ を無向グラフとする. 頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ に含まれるとき, $U$ を $G$ の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

← 古い版		2008年11月13日 (木) 06:19時点における版
2行目:		2行目:

	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.		<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.
		+
		+	[[Category:グラフ･ネットワーク\|ひふく]]

← 古い版		2007年7月17日 (火) 05:46時点における版
1行目:		1行目:
	'''【ひふく (cover)】'''		'''【ひふく (cover)】'''

−	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.	+	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

← 古い版		2007年7月13日 (金) 05:53時点における版
1行目:		1行目:
−	【ひふく (cover)】	+	'''【ひふく (cover)】'''

	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.		<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

← 古い版		2007年7月13日 (金) 04:18時点における版
1行目:		1行目:
	【ひふく (cover)】		【ひふく (cover)】

−	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,<math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.	+	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

← 古い版		2007年7月13日 (金) 04:17時点における版
1行目:		1行目:
	【ひふく (cover)】		【ひふく (cover)】

−	$G = (V, A)$ を無向グラフとする. 頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ に含まれるとき, $U$ を $G$ の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.	+	<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,<math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

← 古い版	2007年7月20日 (金) 01:43時点における版
(相違点なし)