締切済み 情報数学 単純無向グラフについての問題 2012/08/21 02:35 この中で2部グラフはどれか 5個 正則グラフはどれか 4個 補グラフが非連結になるグラフはどれか 3個 オイラーグラフはどれか 3個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか2個 切断点 (cut point) を持つグラフはどれか 4個 分かる方教えてくださいお願いします。 画像を拡大する みんなの回答 (1) 専門家の回答 みんなの回答 Tacosan ベストアンサー率23% (3656/15482) 2012/08/21 23:23 回答No.1 定義は? 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 カテゴリ 学問・教育数学・算数 関連するQ&A 情報数学 単純グラフの問題 この中で2部グラフはどれか 5個 正則グラフはどれか 4個 補グラフが非連結になるグラフはどれか 3個 オイラーグラフはどれか 3個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか2個 切断点 (cut point) を持つグラフはどれか 4個 分かる方教えてくださいお願いします。 情報数学 単純グラフの問題 この中で2部グラフはどれか 5個 正則グラフはどれか 4個 補グラフが非連結になるグラフはどれか 3個 オイラーグラフはどれか 3個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか 2個 切断点 (cut point) を持つグラフはどれか 4個 分かる方教えてくださいお願いします。 情報数学 単純無向グラフについての問題 G が切断点を持てば,G は橋を持つ 正しくない G = (V, E) が連結,かつ |E| < |V | ならば,G は無向木である 正しい すべての完全グラフの直径は 1 である 正しい 節点数 5 の完全グラフ K5 は平面描画可能である 正しくない それぞれの理由を教えてほしいです。 天文学のお話。日本ではどのように考えられていた? OKWAVE コラム 離散数学 オイラーグラフ、ハミルトングラフの質問です。 離散数学 オイラーグラフ、ハミルトングラフの質問です。 添付データの画像のグラフについて考えています。 括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか? また、その理由を教えてください。 このグラフは位数(5)の(完全)グラフであり(4)次の(4-正則)グラフ 3辺形は(5C3= 10個) 4辺形は(5C4 * 2 = 10個) (すべての辺から偶数個の辺が出ているためオイラーグラフ) グラフの証明を教えてください 背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをGとします Gの中のツアーで中で、最も辺の数が多いものをCとします。 そのときGからCの辺をすべて取り除いたグラフの連結成分Hがあるとしたとき Hの各頂点の次数は偶数である。 この証明を教えてください。 オイラーグラフの十分条件について グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 (最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました) また、そもそもGは連結という条件が必要だと思うのですが(非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので)、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか? 以上になります。ご教示いただければ幸いです。 ケー二スバルグの橋の問題(一筆書き) 以前、他の方が、聞いてましたが、もっと具体的にケー二スバルグの橋の問題(一筆書き)を。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど2つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、数学的帰納法を用いて、証明したいんです。自分でやってみたんですが、うまくいかないんです。 力を貸して頂けないでしょうか? どなたか教えていただけないでしょうか? グラフの性質の問題について 以下の問題、よろしくお願いします。 点の集合と点同士とを結ぶ辺の集合とからなる図形をグラフと呼びます。以下では立方体の頂点と辺からなるグラフを一般化して出来るグラフの性質を考察します。正方形は2次元の立方体なので2-cubeと呼ばれます。立方体は3-cubeです。数学では次元の低い方にも一般化を行います。 2点と2点を結ぶ直線からなるグラフは1-cubeです。n-cubeはn次元ユークリッド空間の超立方体の頂点と辺とからなるグラフです。nーcubeに関して以下の問に答えなさい。 問1 全ての辺の長さを1とします。ある点を1度だけ通過して点と点をつなぐ辺を辿り、異なる2点を結ぶ経路をパスと呼びます。あるグラフの上で、任意の2点x,yを結ぶパスp(x,y)の中でその長さ[p(x,y)] の最小値[p(x,y)]を点x,yの距離と呼びます。グラフ上で[p(x,y)]の最大値のグラフを直径と呼びます。n-cubeの直径をnの式で表しなさい。 問2 点の位置や辺の長さを自在に変えて曲線も許すとき、辺が交わらないように平面に作図可能なグラフを平面グラフと呼びます。2-cube、3-cubeは平面グラフですが、4-cubeはそうではありません。平面に描けないグラフを平面に描ける幾つかの部分に分解することができます。このとき、分解の最小数をグラフの厚さと呼びます。n-cubeの厚さをnの式で表しなさい。 離散数学のカット枝について 以下のような問題がありました。回答が掲載されていないので回答例を教えてください 1.切断枝(カット枝、橋)の定義を書け 2.グラフの枝がカット枝であるための必要十分条件は、その枝がどの閉路にも属さないことであることを証明せよ。 よろしくお願いします。 一筆書き可能の証明 ケー二スバルグの橋の問題から、下のことが出てきました。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど2つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、証明したいのですが、なかなかできません。 どなたか教えていただけないでしょうか? 離散数理 Gを2辺連結グラフとする。Gの辺集合に対して二項関係を「2辺が同じかカットセットである」と定義する。以下の問いに答えよ。 (a)この二項関係が同値関係であることを示せ。 (b)一つの同値類に含まれる辺は、Gの一つの閉路上にあることを示せ。 (c)一つの同値類Pに含まれるすべての辺をGから除くと、残りのグラフの各連結成分は2辺連結であることを示せ。 という問題がわからないので、どなたか教えて下さい。某大学のテスト範囲の問題です。 ハミルトングラフの証明 単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。 日本史の転換点?:赤穂浪士、池田屋事件、禁門の変に見る武士の忠義と正義 OKWAVE コラム グラフ生成をGUIで。 説明しづらいのですが、 ============================ Javaによって生成された画面上の任意の点を右クリックして出るポップアップメニューの「生成」なる項目を選択するとダイアログボックスが現れ、例えば名前やIDなどを入力して決定を押すと、その右クリックした地点に●が表示されついでに内部的においても 点を意味する Point なるオブジェクトが生成される。 また任意の場所で右クリックして出るポップアップメニューの「連結」なる項目をクリックし、2つの●をチョンチョンとクリックするとそれらを結ぶ線が表示され、ついでに内部でも 2つのPointオブジェクト同士をリンクさせる. 最後に「保存」なるボタンを押すと、出来上がったグラフの情報(どの位置に点があって、どの点とどの点が結ばれているか等)をファイルに保存する. ========================= つまり単純に無向グラフをGUI操作で生成して、なんらかのファイル形式に保存したいと思っています. ただ、GUI部分をどう始めればよいか見当がつきません. awt の canvas を使って全て作るとなると、「クリックした場所の当たり判定」みたいなことをしなければいけないのかな?なんて思って気が引けてしまいます。 このようなことをしたい場合はどういった方法が考えられるでしょうか. アドバイスをお願いします。 グラフ理論(木について)の証明 2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか? ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 (もし、点の個数を使うときはn,辺の個数はeを用いて教えてください) よろしくお願いします。 接続行列の問題です。 グラフGは連結である(1つの連結成分をもつ)とする。 (1)木はGの点を網羅することを証明せよ (2)規約接続行列の中の1つの非零要素について展開すると、その小行列の中に非零要素が1つだけあることを証明せよ 例を使わない証明は苦手なので困ってます。解答の協力お願いします! 公務員の数的処理の問題でわからないので教えてくださ 右図の正六面体ABCD-EFGHにおいて、点Pは辺EFの、点は辺CGのそれぞれ中点である。この正六面体を三点H、P、Qをとおる平面で切断したとき、頂点Aを含む立体の各面のなかに四角形(正方形をふくむ)はいくつあるか。 切断面は考えないとする。 教えてください “臨界なグラフは連結である。” グラフGが臨界である 内容は理解したのですが、 連結である事が頭が足りなくて 何故そうなるのかはっきりと理解することが出来ません。 調べてみると 「何故なら、もしグラフGが連結でなければ、頂点を共有しない二つ以上の連結部分グラフに分かれる。この時、Gの彩色数は連結部分グラフの彩色数のうち最大のものであり、その他の連結部分グラフから辺や点を除いても彩色数には影響しないから。」 http://www.iis.it-hiroshima.ac.jp/~ohkawa/www32.ocn.ne.jp/~graph_puzzle/1no10.htm 引用 とあったのですがこの内容を 教えてください。 そのままなのかもしれないのですが理解がいまいち出来なくて…。 数学苦手で本当に分かりません 高1の数学です。 数I (1)直角をはさむ2辺の長さの20である直角三角形のうち、斜辺の長さが最小である直角三角形の3辺の長さを求めよ (2)2次関数のグラフが次の条件を満たすとき、その2次関数を求めなさい 1.頂点が点(1,2)で、点(0,4)を通る 数A (1)1から100までの整数を1ずつ書いた100枚のカードがある。この中から1枚のカードを引くとき、その数が9または12で割り切れる確率を求めよ。 (2)3枚の硬貨を投げるとき、少なくとも1枚は表がでる確率を求めよ。 (3)箱の中にくじが12本入っていて、4本が当たるくじである。この中から3本のくじを同時に取り出すとき、少なくとも1本は当たりくじである確率を求めよ。 の求め方を教えてくださいm(__)m Excel 空白をグラフに表示しないようにするには? Excelでグラフを作成しています。 その中で、最大値、最小値を求めるマクロ記述でセルに組み込んでいます。 グラフは折れ線で表示しますが、マーカのみとしています。 <マクロ記述例> =if(C$36=$B5,C$36,"") 最大値(C$36)と現セルの値($B5)と同じだったらグラフ表示セル(マクロ記述位置)に最大値(C$36)を、そうでなければ""(空白)とする。 <問題点> これらをグラフ表示すると(空白)の値まで表示対象になります。 セルの値がクリアな状態(削除)した状態だとそのセル部分は表示されないようです。マクロで(削除)と同じ値を組み込む方法?、それともグラフの設定方法? グラフの軸表示レンジの最小値を0を超える値に設定すると表示しなくなるのですが、0未満のデータも表示されなくなり問題は残ります。 よい解決をご存じの方、お教え願います。 ラーメンの問題 1辺の長さLのLのV型ラーメンがある。 図のように荷重Pを与えて開口させる。 コーナーの角度は90°である。 (2)ラーメンにトラス部材を追加で連結する。(トラス併用構造) 開口変位(P点のP方向の変位)を求めろ。 縦男性係数:E 断面:A 断面2次モーメント:I ひずみエネルギーを考えるなら、 せん断力Qが生み出すひずみエネルギーを無視してよい。 白丸はモーメントフリー (1)は分かったのですが (2)が分かりません 何かヒントでももらえないでしょうか? 注目のQ&A 「You」や「I」が入った曲といえば? Part2 結婚について考えていない大学生の彼氏について 関東の方に聞きたいです 大阪万博について 駅の清涼飲料水自販機 不倫の慰謝料の請求について 新型コロナウイルスがもたらした功績について教えて 旧姓を使う理由。 回復メディアの保存方法 好きな人を諦める方法 小諸市(長野県)在住でスキーやスノボをする方の用具 カテゴリ 学問・教育 人文・社会科学 語学 自然科学 数学・算数 応用科学(農工医) 学校 受験・進学 留学 その他(学問・教育) カテゴリ一覧を見る OKWAVE コラム 突然のトラブル?プリンター・メール・LINE編 携帯料金を賢く見直す!格安SIMと端末選びのポイントは? 友達って必要?友情って何だろう 大震災時の現実とは?私たちができる備え 「結婚相談所は恥ずかしい」は時代遅れ!負け組の誤解と出会いの掴み方 あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど インターネット回線 プロバイダ、光回線など