• 締切済み

辺彩色のアルゴリズム

グラフ理論についての質問です。 平面グラフを辺彩色するのに必要な色の最小の数を求めるアルゴリズムがあるとききました。 しかし、調べてみましたがどのようなものかわかりません。 知っている方いましたら教えてください。

みんなの回答

  • azt82280
  • ベストアンサー率0% (0/0)
回答No.2

定理により 辺彩色に必要な色は次数に依存し， 辺彩色に必要な色数は最大次数以上で最大次数＋1以下の範囲ですべて彩色できます． 大概は最大次数と同じ色で彩色でき， 完全グラフの場合の時に最大次数＋1必要となります，

全文を見る
すると、全ての回答が全文表示されます。
  • sgwjn
  • ベストアンサー率70% (47/67)
回答No.1

組合せ最適化問題の辺彩色のことですよね？ であるなら、必ず『必要な色の最小の数を求める』アルゴリズムは、総当りの列挙法しかないと思います。 理論上は、この方法で必ず最適解を求めることができます。 ただ、グラフの規模が大きくなると現実的な時間で解を求められなくなります。 ですので、組合せ最適化問題では、最適解の近似解を求める近似解法を使用するのが現実的です。 現在は、研究も近似解法についての研究が一般的なはずです。 組合せ最適化問題に対するこの辺のくだりはご存知ですよね？ この手のNP困難な問題に対する解法の研究は世界中で行われています。 最も高性能な近似解法をご希望であれば、それこそ国際学会で発表されるような研究者の論文を読むしかありません。 このような場所でポンっと最適な解法を挙げることができるような問題ならば、世界中で研究はされていないと思います。 以下に挙げる書籍で、辺彩色についてのアルゴリズムが紹介されているようです。 購入されて、ご自分でアルゴリズムを考えてみてはいかがでしょうか？ 離散構造とアルゴリズム１ 藤重 悟 編 徳山 豪／室田 一雄／加藤 直樹／西関 隆夫／中野 眞一／上野 修一　著 1992年7月15日 初版発行, ISBN4-7649-0194-3, 近代科学社

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • ３彩色問題について質問です。

    下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。 ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。

  • 遺伝的アルゴリズムの遺伝子の長さについて

    今、グラフ理論と遺伝的アルゴリズム（以下ＧＡ）の勉強をしています。 グラフ理論の最小全域木問題をＧＡを使って解こうと考えています。そこで、個体の遺伝子の長さをそのグラフの点の数Ｎにすればよいのではないかと考えました。 しかし、グラフが大きく、点の数Ｎが１００や１０００になった場合は、遺伝子の長さも非常に長くなってしまいます。これはＧＡとして問題があるかないかについて教えてください。 よろしくお願いします。

  • グラフ理論の彩色問題

    G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ． この問題の証明が出来なくて困ってます。 誰かわかりやすく解説お願いします。

  • グラフ理論の問題について

    Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。

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

    http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2 によると、 隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。 彩色多項式とは、与えられたグラフをt色以下で彩色したときの彩色の組合せ数を求める式である。 閉路グラフC_n(つまり、n角形)をt色以下で彩色したときの彩色多項式は、 (t-1)^n+(-1)^n*(t-1) これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。

  • 最小全域木について

    　現在、最小全域木の問題はグラフ理論や遺伝的アルゴリズムの文献など様々な分野で解説されていますが、この「最小全域木」について気になることがあります。 最小全域木とは辺に対して一つの重みがあるものですが、この重みが多重化すること、つまり一つの辺に対して二つ以上の重みが存在する最小全域木とは存在しないのでしょうか？？ つまりは「二重の重みを持つグラフ」を対象とした研究とは世の中では行われていないのでしょうか？？ 厳密な解を求めるのが不可能など、様々な問題が生じてくるから不可能なのかなと思ったりしたのですが、、、違うのでしょうか？？ もし、この分野に詳しい方がいらっしゃったら返事をお願いしたいです。

  • ２点同士の距離の平均が最小となる木

    グラフ理論に関してです。 ネットや手持ちのグラフ理論入門書で探しても見つけられなかったので質問させて下さい。 重みつき連結グラフにおいて, 入力が「グラフ上の複数(>=2)の節点」であり、出力が「節点同士の距離平均が最小であるような木」となるようなアルゴリズムはあるでしょうか。 もしくはそれに対する近似的なアルゴリズムでもかまいません。 言い直すと、入力された節点集合を U として (　　Σ<iとjの距離> ) / |U| 　i,j∈U, i≠j が最小となるような木です。

  • グラフ理論について

    全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。

  • 平面グラフの問いです。

    平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。 その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。 つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。

  • 彩色に慣れるには？

    自分は彩色や着色が苦手で イラストでは、線画やクリンナップまで はうまくいきますし、デッサンでも それなりに本物のようには 描けるのですが、着色などをすると 絵がぐちゃぐちゃになってしまいます。 小さい頃から絵は好きでずっと描いていて、 鉛筆だけを使うだけなら、気持ちよく描く 事ができるのですが、着色すると絵が台無しになってしまいます。 色相の統一とかトーンの事も知ってはいるのですが、 色をいじればいじるほど悪くなり最後には ごちゃごちゃで何が何だかわからなくなって 手をつけられなくなって結局失敗して 終わりというパターンを小学校の写生の時 からずっと繰り返してきました。 きれいな色をつけて絵を完成させてみたい という気持ちはあるのですが 自分が色をつけるとすべて汚くなってしまうので 手がつけられない状態になってしまいました。 やはり彩色能力に著しく欠ける人間というのは いるものなのでしょうか。 お金を払って先生に習えばうまくなれるのでしょうか。 なにか練習方法などご存知の方がおりましたら 是非教えて下さい。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する