グラフ理論

質問

K1,3のグラフとハミルトングラフと切断点の３つの条件を持たないようなグラフは存在するのですか？もし、するならばどういう特徴を持っているのでしょうか？
ハミルトングラフでないグラフは定理がないので調べようがないので困っています・・・
よろしくお願いします

回答No.5

arrysthmia

訂正：　解が非連結でも良いのなら、いくらでもありました。
各連結成分が、枝のない閉路、または、No.3 で挙げた２点グラフの
どちらかからなるグラフ。ただし、閉路１個のみからなるものは除く。

非連結グラフでハミルトン道の有無を問題にするというのも、
何だか変な話ではありますが。

お礼

ありがとうございました
そうですね！頂点数２個の完全グラフならばたしかにできますね！
気づきませんでした

回答No.4

arrysthmia

←No.3 補足
＞ この３つの条件を持つグラフは無数にあるらしいのですが・・・
＞ １つも見つからない状態です。

No.3 で、１つ挙げましたよ。

「無数に」ということなら、切断点の定義を少し修正すれば、
No.3 で挙げたグラフを任意個集めたもの…も条件を満たします。
非連結グラフになってしまいますが、それでも良ければ。

その他には、無さそうに思いますが…

回答No.3

arrysthmia

なんとも分かりにくい日本語ですが、
(1) 完全２部グラフ K1,3 を部分グラフとして持たない。
(2) ハミルトン閉路を持たない。
(3) 切断点を持たない。
の３条件を満たすグラフはあるか？という質問
ではないでしょうか。

それなら、「無い」が答えです。

完全２部グラフ Km,n とは、m+n 個の頂点を持つグラフで、
頂点が m 個と n 個の２つのグループに分類されており、
同じグループの頂点間には、辺は無く、
異なるグループの頂点間には、全ての対に辺が有る
ような物のことを言います。
K1,n なら、１個の頂点が、他の n 個の頂点との間に
１本づつ辺を持つ形のグラフとなり、
これを部分グラフに持つことは、もとのグラフが
n 次以上の頂点を持つことと同値です。

ハミルトングラフは、No.2 さんの通り。

切断点とは、２次の頂点のことではなく、
その１点（と、それにつながる辺）をグラフから取り除くと
グラフが連結でなくなるような点のことです。
例えば、K1,3 の中央の頂点は、切断点です。

以上を踏まえて…

(1) より、このグラフの頂点は、全て２次以下である。
よって、ひとつの閉路のみからなるグラフか、
１本の道のみからなるグラフの、どちらかしかない。

全体がひとつの閉路からなるグラフは、ハミルトングラフだから、
(2) より除外される。

全体が一本の道からなるグラフでは、両端以外の頂点は切断点である。
これは、(3) から除外される。

…いや、在るか。
頂点数２で、その間に辺があるグラフが。

補足

ありがとうございます
この３つの条件を持つグラフは無数にあるらしいのですが・・・
１つも見つからない状態です

回答No.2

Knotopolog

３条件を満たすグラフは，

特徴(1)：K1,3グラフではないこと．
特徴(2)：ハミルトングラフではないこと．
特徴(3)：切断点を持たないこと．

でしょう．
特徴(1)を満たすには，頂点の数が５以上であればよい．
特徴(2)を満たすには，ハミルトングラフでなければよい．
ハミルトングラフは，グラフのすべての点を通る閉路を持つグラフですから，
そうならないグラフなら何でもよい．そして，
特徴(3)を満たすグラフは，切断点を持たないグラフなので，
頂点から２本以上の辺が出ていれば良いのだから，これは簡単でしょう．

グラフの状態を示すのに文章で書くのは書きにくいが，
結論として，例えば，
例(1)：漢字の「田」という字を，４本の辺がでる頂点（頂点の次数が４）の数が１．
３本の辺がでる頂点の数が４，と考えればひとつの例です．

例(2)：四角のガラス板を10枚用意する．
四角のガラス板を５枚，直線的に直列に並べる．これと同じことをもう一度やって
すぐ下に置く．この四角ガラスの縁をグラフの辺とする．また，ガラスとガラスの境目も
グラフの辺と考えれば，一つの例ができると思う．このグラフの頂点は
辺が４本でる頂点の数が４（四角のガラス板のカドの境目）で，
辺が３本でる頂点の数が10（ガラス板の外周境目）で，
あとは辺が２本でる頂点を適当に辺の上に決めてやればよい．

こんな文章で分かるでしょうか？

簡単に一言で言うと，頂点の次数が２以上でハミルトングラフではないグラフ
ということになります．沢山ありますよ！

補足

ありがとうございます
例を図で書いてみたのですがK1,3の部分グラフを含んでいるので満たしていないのですが・・・
K1,3の完全グラフを部分グラフとして含まないと書き忘れていました。

例１のだと明らかにK1,3の部分グラフを持っています
例１も同様です

回答No.1

Tacosan

えぇと.... とりあえず「読んで理解できる日本語」で書いてもらえるようお願いします. 文章の構造から箇条書きにすると
・K1,3　のグラフの条件を持たず
・ハミルトングラフの条件を持たず
・切断点の条件を持たない
グラフを探していると読めるのですが, はっきり言ってどれも理解できません.
そもそも「K1,3 のグラフの条件」とか「切断点の条件」って何だ?

補足

切断点の条件を持たないとは切断点がないグラフのことです
K1,3は完全２部グラフのことです
１つの頂点が３つの頂点とすべて隣接しています
この場合は鳥の足みたいな形のグラフになります

日本語が分かりづらくてすいません