閉路グラフ

の検索結果 (33件 1〜 20 件を表示)

グラフ-閉路・木の用語について

…(1)ある頂点vの子孫による誘導部分グラフを、vを根とする何というか (2)単純閉路が存在するグラフを何というか よろしくお願いします。…

締切

グラフ理論で

…グラフΓがtree(無閉路グラフ)であるとき、♯E(Γ)=♯V(Γ)-1 が成り立つことを証明するという問題がわかりません。 教えていただけませんか?…

解決

ハミルトングラフ

…ハミルトングラフになるときって、頂点がn個で、任意の二つの点v,w隣接してないとき deg(v)+deg(w) ≧n なんで、 つまり頂点vとwの次数の合計がn以上なら、成り立つんですよね? でも閉路グラ...…

解決

4色定理はなぜグラフ理論で証明できないのでしょうか

…4色定理についてですが、引っかかるところがあります。 現在はコンピュータで量的な証明がなされていると聞きますが、グラフ理論で証明されたという話は聞きません。 私の中ではグラ...…

締切

n角形の頂点をt色以下で塗り分けるグラフ彩色

…http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2 によると、 隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。 彩色多項式とは、与えられたグ...…

解決

グラフの名前を教えてください

…グラフの名前を探しています。 (関数のグラフでなく、点を線で結ぶほうのアレです。) たぶん、特別な名前が付いていると思うのですが、 調べた範囲では、見つけることができませんで...…

解決

最長経路探索

…グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ(辺ではなくノードの方に重みがある) ・スタートとゴールのノードが各々1つ与えられ...…

解決

数学の解答お願いします

…点数nが3以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい 1,Gの最長路P=X0X1・・・ ・Xkを考える (X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる となるようなi...…

締切

有向グラフ

…有効グラフGが全域閉路をもつとはどういうことなのでしょうか? もし、知っている方がいらっしゃれば教えてください。…

解決

ハミルトンに関する質問

…点数nが3以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい 1,Gの最長路P=X0X1・・・ ・Xkを考える (X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる となるようなi...…

解決

NPクラス、Pクラス、NP完全問題について教えてください

…こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判...…

解決

グラフ理論

…K1,3のグラフとハミルトングラフと切断点の3つの条件を持たないようなグラフは存在するのですか? もし、するならばどういう特徴を持っているのでしょうか? ハミルトングラフでないグラフ...…

締切

ハミルトン閉路とNP

…ハミルトン閉路問題はNPに属する、という事を証明したいのですが… これって HCがPに属することを証明すれば良いのでしょうか? ちょっと迷走しちゃってます……

締切

関係とグラフについてですが…

…三角形AとBが合同であることは同値関係であること を示すにはどうしたらいいのでしょうか? 反射律・対称律・推移律をどのように適用したら いいのかわかりません。 また、オイラーグラ...…

解決

8人を4人の2グループに分ける

…4人ずつでチームを組んで、4対4の試合をしようと思います。 頻繁にチームを変えようと思うのですが、 組み合わせの偏りが極力出ないようにしたいのです。 組み合わせの通りはXチームとY...…

解決

dag(directed acyclic graph)であらわした算術式の計算

…以下の問題が解けません。 1.演算子として+と*をもつ算術式の木から、共通の部分式をまとめてdagに変えるアルゴリズムを作れ。 (Cでプログラムを作れ) 2.dagで表した算術式の値を求めるア...…

解決

K_nの全域木の数の証明

…K_nはn点からなるグラフ(図形)で、ある任意の点は自分自身以外の点と辺で結ばれています。 つまり各辺の次数がn-1のグラフです。 このグラフの全域木の数は一般的にn^(n-2)個であることが知...…

解決

有向グラフ

…有効グラフに関しての問題なんですがわからないところがあるのでお願いします。 閉路を含まない有向グラフ(G)について以下の問いに答えなさい。 (1)Gの点番号が「トポロジカル・オーダ...…

解決

離散数学 オイラーグラフ、ハミルトングラフの質問です。

…離散数学 オイラーグラフ、ハミルトングラフの質問です。 添付データの画像のグラフについて考えています。 括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフ...…

解決

これらが2部グラフではない理由を教えてください。

…これらのグラフが2部グラフではない理由を教えてください。 また、右下のグラフのグラフ理論での名称を教えてください。…

解決

検索で見つからないときは質問してみよう!

Q質問する(無料)

おすすめ情報

Q&A検索履歴