スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

完全グラフ

完全グラフの基本的なことについて

Tags : 数学 グラフ理論

[ いくつかの用語の定義 ]

・ループ (loop)
グラフにおいて、端点(有向グラフなら始点と終点)が一致している辺をループといいます。
図の e2 はループです。

・多重辺 (multiple edge)
グラフにおいて、同じ2頂点を共有する辺を多重辺といいます。
図の e4 と e5 は多重辺です。

単純でないグラフの例

・単純グラフ (simple graph)
ループも多重辺ももたないグラフを単純グラフといいます。

・完全グラフ (complete graph)
n個の頂点をもち、任意の2頂点間に辺がある単純グラフを完全グラフといい、Kn と書きます。
たとえば、K4, K6 は次のようになります。
K4, K6
グラフ理論では ( 多くの場合 ) 頂点と辺のつながりだけに興味があるので、グラフはその形が多角形である必要はありません。一応。

これは無向グラフの場合ですが、有向グラフの場合でも同じように定義されます。
つまり、
n個の頂点をもち、任意の2頂点間に有向辺(どちら向きでもいい)がある単純グラフを完全グラフといい、Dn と書くことがあります。


[ 完全グラフの辺の数 ]

完全グラフ Kn, Dn の辺の数は
n(n-1)/2

○説明1

1個の頂点に注目すると、残りのn-1個の頂点への辺があるので、1つの頂点から出ている辺の数はn-1本。
これがn頂点あるので、n倍して、n(n-1)本。
このままだと、同じ辺を2回カウントしているので、2で除して求める辺の数になる。

以降、グラフ G の辺の数を |G| と書くことにします。 ( この記号はあまり一般的ではない )

○説明2
  1. |K1| = 0 ( K1 は1つの頂点のみからなる、いわゆる自明なグラフ )
  2. Kn に頂点を1つ追加して Kn+1 を作ることを考えると、
    この操作によって n 本の辺が追加されるので、漸化式 |Kn+1| = |Kn| + n が成り立つ。
初期条件 1. のもと、2. の漸化式を解くと、|Kn| = n(n-1)/2 が得られる。

○説明3

( 頂点を区別しないで ) n 個の頂点から2個を選ぶ、選び方の総数は nC2 通り。
これがすなわち、|Kn| に等しい。

2010/08/27 : 説明 2, 3 を追記
2012/05/04 : 細部を修正
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。