無方向グラフ、有方向グラフについて教えてください

1)無方向グラフの接続関数の定義域と終集合を説明せよ。ただし無方向グラフをG(V,E,ψ)とする。
定義域:
終集合:

2)有方向グラフの接続関数の定義域と終集合を説明せよ。ただし有方向グラフをD(V,A,ψ)とする。
定義域:
終集合:

それぞれの定義域と終集合を教えてくだい。
よろしくお願いします。

No.1 ベストアンサー 回答者： alice_44 回答日時： 2012/01/14 19:26

それの答えは、貴方が「接続関数」という言葉にであった

文献または講義ノートに出ていたハズです。
あまり、人に訊ねるようなこととも思えませんが…

接続関数とは、個々のグラフの形状を
辺からその端点への写像として表現したものです。
例えば、D において ψ(a1) = (v1,v2) といえば、
有向辺 a1 は、頂点 v1 から v2 への辺だという具合にです。

ですから、有向グラフの接続関数は、辺集合から
(頂点集合から２元とる全ての順列の集合)への写像。
無向グラフの接続関数は、辺集合から
(頂点集合から２元とる全ての組合せの集合)への写像です。

(頂点集合から２元とる全ての順列の集合)は、
集合の直積を使って V×V とも書けますね。
組合せのほうは、適当な記号に思い当たりませんが。

また、余談ですが、写像の「終集合」というのは、
それ自体がたいへん難点の多い概念です。
ここは、あまり深入りせず、
「接続関数」の定義を確認して終わるのが、得策かと思います。

この回答へのお礼

回答ありがとうございます。
定義を確認して理解を深めたいと思います。

お礼日時：2012/01/15 16:09