グラフ理論

質問

大学生です．
学部のグラフ理論の授業の事で質問です．
2つの異なるオイラー部分グラフの排他的論理はまたグラフのオイラー部分グラフになることを証明せよ．
が分かりません．分かる方，教えてくださいお願いします．

回答No.8

hrsmmhr

式は点の数ではなくて辺の数を言ってますし
A(x)のxは例えばx=aのとき、aの周りの本数を言ってます
四角形abcdと三角形adeのとき
A(a)+A^B(a)=1+1=2 (A(a)={ab},A^B(a)={ad})
B(a)+A^B(a)=1+1=2 (B(a)={ae},A^B(a)={ad})
排他的論理和AvB(a)-A^B(a)=A(a)+B(a)=1+1=2です

回答No.7

Tacosan

おぉっと.
「偶数(n≧2)」ってどういう意味だろう. 特に n が未定義.

証明そのものは基本的に
「偶数と偶数を足して整数の 2倍を引いたら偶数」
というだけなんだが.

ちなみに #6 の補足にある
「たとえば，頂点が(a,b,c,d)の四角形と(a,d,e)の三角形を考えると，
A(x)＋A^B(x)=4 , B(x)+A^B(x）=3だから
B(x)+A^B(x）が偶数とは限らないんじゃないですか?」
は, あなたが記号の意味を理解できていないだけ.

補足

nは次数のこと．
B(x)はBのみに含まれてる辺の数，A^B(x）はAとBの共通の辺の数だから，
B(x)+A^B(x）=2+1=3
で奇数じゃないの．

自分なりに証明をやってみたけど，
A(x)+B(x)[ここでの，+は排他的論理和]
=A(x)-(A^B)(x)+B(x)-(A^B)(x)[A(x)とB(x)は頂点xでの辺の数]
=A(x)+B(x)-2(A^B)(x)
これより，A(x)，B(x)，2(A^B)(x)は偶数だから，A(x)+B(x)はオイラー部分グラフである．

こんな感じであってる??

回答No.6

hrsmmhr

E(x)はAvB(x)です
最初のその点の次数だからと思って書いていて、部分グラフだからまずいと思って書き換えたつもりでしたが、残ってしまいました。

補足

たとえば，頂点が(a,b,c,d)の四角形と(a,d,e)の三角形を考えると，
A(x)＋A^B(x)=4 , B(x)+A^B(x）=3だから
B(x)+A^B(x）が偶数とは限らないんじゃないですか?
また，
頂点が(a,b,c,d)の四角形と(a,d,e)の三角形を考えた時に，
A^B(x)＝AvB(x)-(2)-(3)
＝AvB(x)-(A(x)＋A^B(x))-(B(x)+A^B(x))
＝AvB(x)-A(x)-B(x)-2(A^B(x))
この計算をすると，
左辺＝1
右辺＝6-3-2-2=-1
より，左辺≠右辺
が成り立たないんですけど…

回答No.5

hrsmmhr

ｎが2以上はｎが１でなければいいのでは？
偶数なので１ではありません
０の次数は排他的論理和には含まれないとするのでは？
もし含めるのならそれは示せません

補足

hrsmmhrさん
ほとんど，理解しました．ありがとうございました．
ですが，E(x)が何かわかりません．
E(x)は何ですか?

回答No.4

hrsmmhr

オイラー部分グラフA,Bで頂点ｘでの辺の本数を
AvB(x)=A(x)＋B(x)＋A^B(x)…(1)　（A(x)はAのみに含まれる辺の数の意味）
A(x)＋A^B(x)：偶数…(2)、B(x)+A^B(x）：偶数…(3)ですので
A^B(x)=((1)=AvB(x))-(2)-(3)なのでA^B(x)とE(x)が共に奇数か偶数
A(x)+B(x)=AvB(x)-A^B(x)：偶数→排他的論理和の辺の数

お礼

ありがとうございました．

今回は，AとBの排他的論理のグラフのすべての頂点の次数がn≧2であることを示したいんですけど…

補足

AvB(x)とA^B(x)はどういう意味ですか?

回答No.3

Tacosan

その定義でいくならほとんど「定義より」で終わり. 図にして次数の関係を考えれば一瞬でわかる.

補足

自分もそう思ったんですけど，問題が証明せよなので，証明をしなくてはいけません．
Tacosanさん，証明が分かるならば，教えてもらえますか?

回答No.2

hrsmmhr

異なる２つのオイラー部分グラフの排他的論理和は、多くの場合非連結になる気がするのですが
それでもオイラー部分グラフになるという命題なのでしょうか？

補足

非連結グラフでも，各頂点の次数が偶数(n≧2)であれば，オイラー部分グラフです．

回答No.1

Tacosan

「オイラー部分グラフ」って何?
グラフの「排他的論理」って何?

補足

オイラー部分グラフは次数が偶数(n≧2)のグラフ
排他的論理は複数のグラフに対し，共通の辺を除き，それ以外の辺を１つのグラフで表す．