グラフ理論についての質問です。よろしくお願いします。
「グラフGが正則でdiam(G)=3ならば、diam(~G)=2である」(~GはGの補グラフです)
を証明したいです。
前の設問に「diam(G)≧3ならばdiam(~G)≦3」というのがあるので(これは証明できました)、diam(~G)=1あるいはdiam(~G)=3の場合に矛盾を導く方向で考えています。
diam(~G)=1とするとGが空グラフになってしまう、というのは分かるのですが、diam(~G)=3の場合に矛盾を導くところが上手くいきません。
どのような方針で話を進めていけば良いのか、あるいはストレートにdiam(~G)=2を示すもっとスマートな方法があるのか、ご教示いただければ幸いです。
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
No.2のタイプミス修正です。
> ∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (¬(p*x) ∨ ¬(q*x)))
と
> ∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (p.x ∨ q.x)))
は
∃p∃q(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (¬(p*x) ∨ ¬(q*x)))
と
∃p∃q(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (p.x ∨ q.x)))
でなくちゃ。
No.2
- 回答日時:
スマートなやり方はどうも思いつきませんで、もっちゃりしてますけど。
正則次数Δ≧2の連結で正則なグラフGの直径がdiam(G)=3で、しかもdiam(~G)>2だと仮定して矛盾を示しちゃどうでしょうか。
以下、ノードa,bがG上で隣接している(edgeで繋がっている)ことをa.bと書く事にし、Gのノードの集合を(めんどくさいから)Gと書く事にします。
また、ノードa,bが~G上で隣接していることをa*bと書くことにすると、diam(~G)>2とは
∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (¬(p*x) ∨ ¬(q*x)))
ってことですが、補グラフってのは a.b ⇔ ¬(a*b) という意味なのだから、
∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (p.x ∨ q.x)))
である。そのようなp, qを固定します。すると(x=pとかx=qの場合を考えれば明らかに)p.qですね。そして、p, q以外のノードの集合 H = G\{p, q} を
P = {x | x∈H ∧ x.p ∧ ¬(x.q)}
Q = {x | x∈H ∧ x.q ∧ ¬(x.p)}
R = {x | x∈H ∧ x.p ∧ x.q}
と分類します。pもqも枝がΔ本出ているけれども、そのうちの1本の枝はp.qに使ってますから、
|P∪R| = |Q∪R| = Δ-1
です。( |X|は集合Xの要素の個数(濃度)のことです。)
さて、もし
∀x(x∈P → ∃t(t∈Q ∧ x.t)) ∧ ∀x(x∈Q → ∃t(t∈P ∧ x.t))
なら、明らかにdiam(G)≦2。なのでその否定
∃x(x∈P ∧ ∀t(t∈Q → ¬(x.t))) ∨ ∃x(x∈Q ∧ ∀t(t∈P → ¬(x.t)))
が成立つと分かります。これを場合分けします。
∃x(x∈P ∧ ∀t(t∈Q → ¬(x.t)))の場合、このノードx∈Pについて、p以外のお隣さんノードΔ-1個は(P∪R)\{x}の中から選ばれなくてはなりませんが、|(P∪R)\{x}| = Δ-2 だからこれは無理。∃x(x∈Q ∧ ∀t(t∈P → ¬(x.t))) の場合も同じです。
No.1
- 回答日時:
解答が無いようなので、部分的ではありますが、投稿させてもらいます。
Gの正則次数(Δとする)で場合分けする。
(i)Δが0または1の場合)精密に言うには、不連結の場合も含めた直径の定義を知りたいところですが、ともかくdiam(G)=3になり得ないのは明らかですから、題意は自明的に成立する。
(ii)Δが2で連結の場合)この場合、diam(G)=3となるのは、Gが7-サイクルのときのみ。このとき~Gは4-正則。
diam(~G)=2を示すには、~Gの隣接しない2点a、bが~Gにおいて共通隣接点を持つことを示せばよいが、このことは正則次数が4であることから、部屋割り論法で分かる。
他の場合は検討中ですが、このやり方が方針的に正しいかどうかは不明。なお、
>「diam(G)≧3ならばdiam(~G)≦3」というのがあるので(これは証明できました)
であれば、その証明を記載してもらえればそれがヒントになったかもしれない。長いのならば概略でもよいので。
この回答への補足
ご回答ありがとうございます。
正則次数に注目する方法ですね。考えてみようと思います。
>不連結の場合も含めた直径の定義
非連結の場合、異なる連結成分にある2頂点間の距離は無限大で定義しているので、直径も無限大となります。
>diam(G)=3となるのは、Gが7-サイクルのときのみ
Gが6-サイクルの場合もdiam(G)=3になりませんでしょうか?
>「diam(G)≧3ならばdiam(~G)≦3」の証明
u,vをd(u,v)=diam(G)となる頂点とし、wをu,v以外の頂点とすると、d(u,v)≧3よりGにおいて
・uとvは非隣接
・u,vのうち少なくとも一方はwと非隣接
が成り立つので、~Gにおいて
・uとvは隣接
・u,vのうち少なくとも一方はwと隣接
が成り立ち、u,v以外の任意の2頂点w1,w2に対して
・d(u,v)=1
・d(u,w)=1(uとwが隣接)or 2(uとwが非隣接→vとwが隣接)
・d(v,w)=1(vとwが隣接)or 2(vとwが非隣接→uとwが隣接)
・d(w1,w2)=1(w1とw2が隣接)or 2(w1とw2が非隣接かつw1とw2がu,vの同じ頂点と隣接)or 3(w1とw2が非隣接かつw1とw2の一方がuと、もう一方がvと隣接)
となり、どんな2頂点間の距離も3以下となる。
が概要となります。
以上、よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(悩み相談・人生相談) 今晩わ。今日、一般NISA始めました。 今回、DIAM高格付けインカムオープンハッピークローバーやり 1 2022/04/27 23:26
- 不動産投資・投資信託 投資信託 2 2023/04/29 08:29
- 医療保険 投資信託の事 1 2022/08/17 19:04
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- Excel(エクセル) <スプレッドシート>採用進捗 グラフ作成について 3 2022/10/23 15:52
- Excel(エクセル) エクセルの大きなシートでグラフを見つける 4 2022/07/28 10:07
- Excel(エクセル) Excelの複合グラフ(棒グラフと折れ線グラフ)で各棒グラフに名称を表示させたい 1 2022/08/14 23:26
- Excel(エクセル) エクセルで、未来の月の数値を表示させないようにしたい 1 2022/05/07 18:58
- 数学 写真の(1)の問題についてですが、解説を見るとグラフを使って示しているのですが、解説の文章はグラフを 1 2023/02/09 17:48
- 高校 三次関数のグラフにつきまして 3 2022/05/15 11:14
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
幽霊が存在していないことを証...
-
存在しない事を証明するのは悪...
-
数学の証明問題で、「証明終了」...
-
婿養子です、妻と離婚して妻の...
-
証明終了の記号。
-
log(x) が連続 であることの証明
-
数学の「証明」のときなどの接...
-
(4^n)-1が3の倍数であることの...
-
中3数学 2つの続いた整数では、...
-
3,4,7,8を使って10を作る
-
無理数って二乗しても有理数に...
-
【応用解析】特異点 留数 位...
-
夫が亡くなった後の義理家族と...
-
高校範囲での三角関数に関する...
-
ゴールドバッハ予想について考...
-
中間値の定理について
-
群の生成についての問題
-
ブール環
-
素数の性質
-
「証明証」と「証明書」はどう...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
3,4,7,8を使って10を作る
-
証明終了の記号。
-
婿養子に入ったのに出て行けと...
-
数学の証明問題で、「証明終了」...
-
「証明証」と「証明書」はどう...
-
素数の積に1を加算すると素数で...
-
夫が亡くなった後の義理家族と...
-
よって・ゆえに・したがって・∴...
-
学割定期を親に買ってきてもら...
-
(4^n)-1が3の倍数であることの...
-
再婚、奨学金
-
素数の性質
-
なぜ独身だと養子が持てないの...
-
元夫が彼女の存在を隠す理由
-
成人した後両親が離婚し別の人...
-
大学の給付型奨学金について 現...
-
直角三角形の性質
-
通学証明書の契印とは
-
無理数って二乗しても有理数に...
おすすめ情報