- 締切済み
グラフ理論
- みんなの回答 （5）
- 専門家の回答
みんなの回答
- arrysthmia
- ベストアンサー率38% (442/1154)
訂正： 解が非連結でも良いのなら、いくらでもありました。 各連結成分が、枝のない閉路、または、No.3 で挙げた２点グラフの どちらかからなるグラフ。ただし、閉路１個のみからなるものは除く。 非連結グラフでハミルトン道の有無を問題にするというのも、 何だか変な話ではありますが。
- arrysthmia
- ベストアンサー率38% (442/1154)
←No.3 補足 ＞ この３つの条件を持つグラフは無数にあるらしいのですが・・・ ＞ １つも見つからない状態です。 No.3 で、１つ挙げましたよ。 「無数に」ということなら、切断点の定義を少し修正すれば、 No.3 で挙げたグラフを任意個集めたもの…も条件を満たします。 非連結グラフになってしまいますが、それでも良ければ。 その他には、無さそうに思いますが…
- arrysthmia
- ベストアンサー率38% (442/1154)
なんとも分かりにくい日本語ですが、 (1) 完全２部グラフ K1,3 を部分グラフとして持たない。 (2) ハミルトン閉路を持たない。 (3) 切断点を持たない。 の３条件を満たすグラフはあるか？という質問 ではないでしょうか。 それなら、「無い」が答えです。 完全２部グラフ Km,n とは、m+n 個の頂点を持つグラフで、 頂点が m 個と n 個の２つのグループに分類されており、 同じグループの頂点間には、辺は無く、 異なるグループの頂点間には、全ての対に辺が有る ような物のことを言います。 K1,n なら、１個の頂点が、他の n 個の頂点との間に １本づつ辺を持つ形のグラフとなり、 これを部分グラフに持つことは、もとのグラフが n 次以上の頂点を持つことと同値です。 ハミルトングラフは、No.2 さんの通り。 切断点とは、２次の頂点のことではなく、 その１点（と、それにつながる辺）をグラフから取り除くと グラフが連結でなくなるような点のことです。 例えば、K1,3 の中央の頂点は、切断点です。 以上を踏まえて… (1) より、このグラフの頂点は、全て２次以下である。 よって、ひとつの閉路のみからなるグラフか、 １本の道のみからなるグラフの、どちらかしかない。 全体がひとつの閉路からなるグラフは、ハミルトングラフだから、 (2) より除外される。 全体が一本の道からなるグラフでは、両端以外の頂点は切断点である。 これは、(3) から除外される。 …いや、在るか。 頂点数２で、その間に辺があるグラフが。
補足
ありがとうございます この３つの条件を持つグラフは無数にあるらしいのですが・・・ １つも見つからない状態です
- Knotopolog
- ベストアンサー率50% (564/1107)
３条件を満たすグラフは， 特徴(1)：K1,3グラフではないこと． 特徴(2)：ハミルトングラフではないこと． 特徴(3)：切断点を持たないこと． でしょう． 特徴(1)を満たすには，頂点の数が５以上であればよい． 特徴(2)を満たすには，ハミルトングラフでなければよい． ハミルトングラフは，グラフのすべての点を通る閉路を持つグラフですから， そうならないグラフなら何でもよい．そして， 特徴(3)を満たすグラフは，切断点を持たないグラフなので， 頂点から２本以上の辺が出ていれば良いのだから，これは簡単でしょう． グラフの状態を示すのに文章で書くのは書きにくいが， 結論として，例えば， 例(1)：漢字の「田」という字を，４本の辺がでる頂点（頂点の次数が４）の数が１． ３本の辺がでる頂点の数が４，と考えればひとつの例です． 例(2)：四角のガラス板を10枚用意する． 四角のガラス板を５枚，直線的に直列に並べる．これと同じことをもう一度やって すぐ下に置く．この四角ガラスの縁をグラフの辺とする．また，ガラスとガラスの境目も グラフの辺と考えれば，一つの例ができると思う．このグラフの頂点は 辺が４本でる頂点の数が４（四角のガラス板のカドの境目）で， 辺が３本でる頂点の数が10（ガラス板の外周境目）で， あとは辺が２本でる頂点を適当に辺の上に決めてやればよい． こんな文章で分かるでしょうか？ 簡単に一言で言うと，頂点の次数が２以上でハミルトングラフではないグラフ ということになります．沢山ありますよ！
補足
ありがとうございます 例を図で書いてみたのですがK1,3の部分グラフを含んでいるので満たしていないのですが・・・ K1,3の完全グラフを部分グラフとして含まないと書き忘れていました。 例１のだと明らかにK1,3の部分グラフを持っています 例１も同様です
- Tacosan
- ベストアンサー率23% (3656/15482)
えぇと.... とりあえず「読んで理解できる日本語」で書いてもらえるようお願いします. 文章の構造から箇条書きにすると ・K1,3 のグラフの条件を持たず ・ハミルトングラフの条件を持たず ・切断点の条件を持たない グラフを探していると読めるのですが, はっきり言ってどれも理解できません. そもそも「K1,3 のグラフの条件」とか「切断点の条件」って何だ?
補足
切断点の条件を持たないとは切断点がないグラフのことです K1,3は完全２部グラフのことです １つの頂点が３つの頂点とすべて隣接しています この場合は鳥の足みたいな形のグラフになります 日本語が分かりづらくてすいません
関連するQ&A
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。 ２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。 ３．オイラーの多面体公式を証明せよ。 ４．以下の問題を証明せよ。 〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。 〔２〕４頂点以上の極大平面グラフGにおいて、 △〔G〕 不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。 〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。 〔４〕K5,K3,3は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論の問題について
Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- K(3,3)完全二部グラフ 非平面性 グラフ理論
連結な平面グラフにおいて位数=p、サイズ=q,とおくと q=<3p-6 という公式？定理？がありますが、 完全二部グラフK(3,3)の非平面性を証明するのに使おうと思ったら 9<=18-6=12 で成り立ってしまいます。 すべての領域が四角形以上なら q=<2p-4というのを使えば証明できるのですが、前の方の公式がこの場合に使えないのはなぜなんでしょう
- 締切済み
- 情報工学
- 確率、グラフ理論(?)の質問です。
以下の問題に途中まででもよいのでご回答よろしくお願いします。 少し間違っててもよいのでアドバイスをお願いします。 解答してみましたが、 I．１．平均：0 分散：2/3*n ２．e(k) = 10/3*e(k - 1) + 10/3*e(k + 1) ３．(不明) II．１．(解答できました) ２．(不明) ３．(不明) という状況です。 整合の方お願いします。 I．１つの粒子が数直線に沿って運動している。粒子は原点０から出発し、毎ステップごとに、等確率1/3でランダムに、-1または０または+1だけ移動する。以下の問いに答えよ。 １．ｎステップ後の粒子の位置の平均および分散を求めよ。ｎは正の整数とする。 ２．Ｌを正の整数とする。粒子は数直線上の-Lまたは+Lに到着すると運動を終了する。粒子がｋに位置するとき、運動を終了するまでに要するステップ数の期待値をe(k)と表す。ただし、ｋは、-L<k<Lを満たす整数であるとする。e(k),e(k-1),e(k+1)の間に成り立つ差分方程式を示せ。 ３．前問で求めた差分方程式の解はｋについての２次式で表される。e(k)を求めよ。ただし、終端条件をe(-L) = e(L) = 0とする。 II．すべての異なる頂点が辺で繋がっているグラフを完全グラフと呼び、頂点数がｎの完全グラフをKnで表す。図６．２と図６．３はそれぞれK5とK6の例である。完全グラフの辺を２通りにラベル付けをする。図６．１に完全グラフK4のラベル付け例を示す。以下では２通りのラベルの辺をそれぞれ実線と点線で表す。このとき次の問いに答えよ。 1. 図 6.1 のラベル付けには，同じラベルの３辺をもつ K3 が含まれない。同様にして，図 6.2 の完全グラフ K5 の辺を２通りにラベル付けして，同じラベルの３辺をもつ K3 が含まれないようにせよ。 2. 「6 人集まれば，互いに知り合いである 3 人組か，互いに見知らぬ 3 人組が必ず存在する」という命題がある。この命題を図6.3 に示した完全グラフ K6 の辺のラベル付けを利用して証明せよ。ただし，一方的に知っているという関係は考えない。 3. 完全グラフ K8 の辺を２通りにラベル付けする。このとき次の２種類の完全グラフを両方とも含まないようなラベル付けの例を示せ。 - 全ての辺が実線である完全グラフ K3 - 全ての辺が点線である完全グラフ K4
- ベストアンサー
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論（木について）の証明
2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。
- 締切済み
- 数学・算数
お礼
ありがとうございました そうですね！頂点数２個の完全グラフならばたしかにできますね！ 気づきませんでした