- ベストアンサー
グラフ色塗り問題のプログラミングができなくて困っています。
すいません、よろしくお願いします。三色色塗り問題を解きたいのですが、よくわかりません。 条件はこのようになっています。 ノード数 ６ V={X1、X2、X3、X4、X5、X6} 色数 3 接続｛(X1,X2)、(X2,X3)、(X3,X4)、(X4,X5)、(X5,X6)、(X6,X1)、(X2,X5)} 接続がつながっているノード同士は同じになってはいけないという設定なんですが、初心者なものでどうすればよいのか。。。 じぶんで本を読んだりしてみはしましたがさっぱりわからず困っています。 簡単なソースコードを教えてください。よろしくお願いします。
- masassi19830818
- お礼率0% (0/5)
- C・C++・C#
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (1)
- moritan2
- ベストアンサー率25% (168/670)
関連するQ&A
- 色塗り問題の件、お願いします。前回は僕の説明不足でした。。。
すいません、よろしくお願いします。三色色塗り問題を解きたいのですが、よくわかりません。 条件はこのようになっています。 ノード数 ６ V={X1、X2、X3、X4、X5、X6} 色数 3 接続｛(X1,X2)、(X2,X3)、(X3,X4)、(X4,X5)、(X5,X6)、(X6,X1)、(X2,X5)} 接続がつながっているノード同士は同じになってはいけないという設定なんですが、初心者なものでどうすればよいのか。。。 じぶんで本を読んだりしてみはしましたがさっぱりわからず困っています。 簡単なソースコードを教えてください。よろしくお願いします。 moritan2さん、trick--o--さん、回答ありがとうございました！ 実は、この問題のノード数、色数、制約を可変的にしたいのです。よろしければ、ソースコードと、その簡単な説明をお願いします。たびたびすみません。。。
- ベストアンサー
- C・C++・C#
- 色塗り問題について、新たな質問です。よろしくお願いします。
これまでに質問に答えていただいた皆様、また、拙い質問の投稿の不備をご指摘していただいた皆様ありがとうございました。今回、更に課題が出てどうすればいいのか困っています。 それは、ノード間の通信量を計る、というものなのですが、前回のもふくめて問題を書きます。 http://oshiete1.goo.ne.jp/kotaeru.php3?q=1962022にあるmoritan2さんに頂いた回答の「n個目までのノードの色がa[]に入っている時、そこまでリンクのあるノードに同じものがないかをチェックする関数、違反がなければ true、あれば false、n < 2 の時は常に true」というものも併せて教えていただけると幸いです。 「色塗り問題」 ＜条件＞ ノード数 ６ V={X1、X2、X3、X4、X5、X6} 色数 3 接続｛(X1,X2)、(X2,X3)、(X3,X4)、(X4,X5)、(X5,X6)、(X6,X1)、(X2,X5)} 制約 接続がつながっているノード同士は同じ色になってはいけない。 更に、隣のノードと通信をして、制約に違反していなければそのまま配色、違反していればその旨を元のノードに伝え、色の変更を要求する、という機能を追加しなければならなくなりました。 この、通信量を測れるようにするには、どのようなコードを書けばよいのでしょうか？教えてください。よろしくお願いします。
- 締切済み
- C・C++・C#
- ４色定理はなぜグラフ理論で証明できないのでしょうか
４色定理についてですが、引っかかるところがあります。 現在はコンピュータで量的な証明がなされていると聞きますが、グラフ理論で証明されたという話は聞きません。 私の中ではグラフ理論で簡単に説明できるのではないかな、という甘い考えがあります（内容は下記に記載しました）。 ただ、こうした考えは以前もたくさんあって否定されているのだと思います。そこで何が悪いのかを教えて頂きたいのです。 納得できる回答が無かった場合は、私は私の考えが正しいんじゃないかと思っているので、私の胸の内で「私の考えで正しいのだ」と自己完結しようと思います。 この質問の内容は、「下記のようなグラフ理論の考え方で5色の塗りわけは無理＝４色の塗りわけで事足りるので、二次元における地図の塗りわけは４色が最大値であり、４色でことたりる」ということの説明ではどこか不足があるのだろう、その不備を教えて頂ければ、というのが論旨となります。 内容は極めて簡単なのですが、文章が少々難しくなってしまいました。ですが、どなたかお付き合い頂ける方、この論旨の問題点をご存知の方、あるいは少しでもこうではないかとおっしゃって頂ける方がいらっしゃいましたら教えて下さい。 尚、万が一の可能性として「こりゃ世紀の大発見也」みたいなこともあるかもしれませんが（とは言いつつも全く期待してません。まあ、今この文章を書きながら自分自身に笑っていますが）、賛同頂ける方、欠点は無い、と言う方もいらっしゃいましたら教えて下さい。 しかし私自身モヤモヤしているのも事実なので、これが正しいのか穴があるのかを教えて頂きたいのです。 ＜序論＞ 例えば、二次元平面に描かれた任意数のノードとエッジで観察するとき、地図でのいわゆる４色定理の観点から見ると、ノードが国、エッジが国境になります。 もともと４色問題の根源は、地図での色塗りの組み合わせにおいて、本当に必要な色の数として４色が最大値なのか、５色必要なパターンは無いのか、という点が論点であると私は考えています。 つまり、これをグラフ理論から見れば、 ・塗りわけが必要なのは、ノードがエッジによって接続されているケース であり、４色が必要なものは ・４つのノードが「全て」４つともエッジによって接続されているケース を想定するものです。 そして５色が必要なものは ・５つのノードが「全て」５つともエッジによって接続されているケース を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 ＜前提などの説明＞ まず根源的な前提として、エッジを延ばすことのできる条件とはなんでしょうか？ それはノード間において遮蔽物が無いことです。遮蔽物が無いという状況はどんな状況でしょうか。 逆に言えば遮蔽物とは何か、ということなのですが、この地図塗りわけの問題をグラフ理論に適用すると、閉路グラフの「内部」にノードＡを一つプロットし、「外部」にノードＢをプロットします。 今回は地図塗りわけの問題をグラフ問題に展開していますので、エッジ間の交差はありません。 ですので、閉路グラフの内と外にプロットされているノードＡとＢは直接エッジで接続することはできない、というのが前提となります。 三次元での考えではこれらは無視できるのですが、今回は地図塗りわけがお題となるので、二次元平面上での問題となります。 ＜本論＞ 序文にも書きましたが、 ・５つのノードが「全て」５つともエッジによって接続されているケース を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 まず一つずつ考えて生きます。 １．２つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 ○－○を想像して頂ければＯＫです。 この場合２色必要になります。 ２．３つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 正三角形の頂点に○をくっつけた図を想像して頂ければＯＫです。 この場合３色必要になります。 ３．４つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 正三角形の頂点に○をくっつけて、その中央に○を描き、 それらが全て互いに接続されている図を想像して頂ければＯＫです。 ４つのノードが互いに全てエッジによって接続されているケースはトポロジー的に必ずこのようになると思います。 この場合４色必要になります。 ４．５つのノードの場合 さて、それでは５つのノードが互いに全てエッジで接続されるケースを考えてみましょう。 実は上記３．「４つのノードの場合」で閉路グラフが構成されており、どこに５つ目のノードをプロットしようとも、その閉路の中の全てのノードにエッジを届かせることはできません。 ここでは前提として頂点Ａ、Ｂ、Ｃからなる正三角形と、その中央に位置する点Ｄ、そしてこれらの点をノードとし、全て互いにエッジで接続しあったグラフを用います。 そして５つ目の点Ｅを任意の位置にプロットし、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できたなら、地図の塗りわけとして５色必要、こうしたモデルがグラフでできないと証明できたなら５つは必要でなく、地図の塗りわけとしての最大必要色数は４色ということになります。 点Ｅを置く位置としてはグラフ図中の任意の位置となりますが、これを分類すると （１）三角形ＡＢＣの外に点Ｅを置く場合 （２）三角形ＡＢDの内側に点Ｅを置く場合 （３）三角形ＡCDの内側に点Ｅを置く場合 （４）三角形BCDの内側に点Ｅを置く場合 の４種に分けられると思います。 これを一つずつ見ていきましょう。 （１）三角形ＡＢＣの外に点Ｅを置く場合 点Ｅは、三角形ＡＢＣに構成される閉塞グラフの内側にある点Ｄにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （２）三角形ＡＢDの内側に点Ｅを置く場合 点Ｅは、三角形ＡＢＤに構成される閉塞グラフの外側にある点Ｃにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （３）三角形ＡCDの内側に点Ｅを置く場合 点Ｅは、三角形ＡＣＤに構成される閉塞グラフの外側にある点Ｂにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （４）三角形BCDの内側に点Ｅを置く場合 点Ｅは、三角形BＣＤに構成される閉塞グラフの外側にある点Ａにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 以上のことからノードのＡＢＣＤＥが５つ全て互いにエッジで接続できるグラフは存在しない。よって地図塗りわけに対しての必要な最大の色数は４色である。 尚、数学的哲理的考察としては、任意ノード数で、互いに全てのノードをエッジで接続するケースを考えた場合、三つのノードで閉路グラフが形成され、四つ目のノードで「その閉路グラフの内側か外側に」プロットされてしまう。更に上記の例で言えばこの四つ目のノード自体をプロットすることにより、閉路グラフがＡＢＣ、ＡＢＤ、ＡＣＤ、ＢＣＤと四つ形成されてしまう。そしてそこから追加のノード点Ｅをどこに打とうとも、閉路グラフの内側に点Ｅを打てばその外側に、閉路グラフの外側に点Ｅを打てばその内側に、自分とは異なるノードが存在するので、点Ｅからそこのノードに到達するエッジを延ばすことはできない。 となります。 実は、数年前もここで同じような質問をさせて頂いたことはあります。ただ、その時に納得できたように思われたのですが、やはり何か私の心の中でモヤモヤしているものがあったので、再度の質問をさせて頂くことにしました。 どなたかご教授頂ける方がいらっしゃいましたら、宜しくお願い致します。
- 締切済み
- 数学・算数
- 双対問題について教えてください。
変数がたくさんあるものがわからないです。 以下の問題の双対問題はどうなるか教えて下さい。 最大化：3X1+2X2+X3-X4+2X5 >条件：X1+3X2+2X3+X4+X5≦3 > Xi≧0、i=1,2,3,4,5
- ベストアンサー
- 数学・算数
- 数学（確率）の問題です。
数学（確率）の問題です。 座標平面上に、座標がそれぞれ(X1,Y1)(Y1,Y2)であらわされる2個の点をとる。ただし、X1,X2,Y1,Y2は互いに独立で、区間(0,1)上の一様分布に従う確率変数である。U=|X2-X1|,V=|Y2-Y1|とする。 (1)Uの確率密度関数を求めよ。 (2)(U^2+V^2)^(1/2)≦1となる確率を求めよ。 1はたたみこみですか？よくわかりません。解答をよろしくおねがいします。
- ベストアンサー
- 数学・算数
- 線形計画問題について教えてください。
この線形計画問題で、条件を１）と２）で変えたときに 最適解がどう違うのでしょうか？教えてください。 最大化：X1+2X2-X3+3X4+X5+2X6 条件：2X1+X2+3X3+X4+4X5+3X6≦7 １）0≦Xj≦1,j=1,2,3,4,5,6 ２）Xj∈{0,1},j=1,2,3,4,5,6
- ベストアンサー
- 数学・算数
- プログラミングを実際に文字を書いて色々覚えたいのですが、何かいい問題集はないでしょうか？
現在プログラミングを勉強してまして、ただ本に書かれているソースコードをキーボードを使って入力するだけでは構文等に関してしっかりとした知識が頭に定着しないので、 シャーペン等で問題集の問題を解くことによって、あらゆる単語の意味をしっかり理解できるのではないかと考えております。 ＶＢをちょこちょこ勉強している状況なのでＶＢをベースに考えておりますが、その他の言語でも是非いいもの、おすすめの物がありましたら教えていただけたらと思います。 宜しくお願いします。
- 締切済み
- Visual Basic
- プログラミングについての質問です
時速ｘキロメートルの速さを小数第２位までキーボードから入力し,秒速メートルで小数第２位までわかりやすく表示する.という問題のフローチャートとソースコードを教えて下さい.
- ベストアンサー
- C・C++・C#
- 数学の関数の問題です。
数学の関数の問題です。 f(x)=-x^2+4x+a-5、g(x)=x^2+4x+3とおく。 x1、x2が-3≦x1≦3、-3≦x2≦3を満たせば、常にf(x1)>g(x2)となるときはa>【ア】のときであり、 -3≦x1≦3、-3≦x2≦3を満たすx1、x2でf(x1)>g(x2)となるものがあるのはa>【イ】のときである。 という問題の【ア】と【イ】を求めるのですが、 【ア】を求めるときの条件はf(x)のmin＞g(x)のMax 【イ】を求めるときの条件はf(x)のMax＞g(x)のmin なので f(x)とg(x)の-3≦x≦3のグラフをそれぞれ書いて、この範囲でのそれぞれのMax、minを求めて上の条件に代入する方法を思いついたのですが、これだとおかしいでしょうか？ 他に効率のよい方法など知っていましたら教えてください。 よろしくおねがいします(__)
- ベストアンサー
- 数学・算数
