Just to illustrate this example, imagine we'd start up with some graph H. It's a little bit of a mess.
There's a lot of edges in here but we're going to do is convert this to a new graph G,
which is the complement of H, and so every place in H where there is an edge we leave the edge out,
and every place where there is not an edge, we add an edge.
For example, this node is not connected to this one or this one.
So in the complement graph, we connect it that one and that one.
This node is connected to three on the top, one on the bottom.
So we connect it to this one on the top and these two on the bottom.
This one on the top and these two in bottom.
So we carefully constructed this complement graph G and the thing that you need to realize now is that
G, this new graph, which is the complement of H has an S-clique
if and only if H has an S independent set.
In fact, it's the same set of nodes. So here's our four clique for example.
This is similar to the graph that we looked at before.
This is our four clique in G and if we look that corresponds exactly to a four independent set in H
because it has all the pairwise edges in G and then it has to fail to have all those pairwise edges in H.
So that's how can use the solution into the clique problem to solve the independent set problem.
Now in this particular example, well it illustrates a general idea
which is we take instances of one problem and we transform them into instance of another.
In this case the transformation is really very straightforward.
Maybe it wasn't obvious to you at first. Now that I putted that, it's probably pretty straightforward.
Some of these reduction actually can be much more involved.
This one actually is also really easily reversed.
So if we have an algorithm for independent set.
We can use that to solve the clique problem the same way.
Invert the graph where I complement the graph, look for the independent set and that tells us
what the clique is in the original graph,
but sometimes again the connection is not always so straightforward.
बस इस उदाहरण को वर्णन करने के लिए, हम कुछ ग्राफ एच. के साथ शुरू होगा की कल्पना करो यह एक गड़बड़ का एक छोटा सा है।
किनारों में यहाँ के एक बहुत है लेकिन हम जा रहे हैं करने के लिए परिवर्तित यह एक नया ग्राफ जी, करने के लिए है
जो है H और H में तो हर जगह के पूरक हैं जहां हम छोड़ बाहर, बढ़त बढ़त
और हर जगह जहां एक छोर नहीं है, हम एक एज जोड़ें।
उदाहरण के लिए, इस नोड के लिए यह एक या यह एक से जुड़ा नहीं है।
तो पूरक के ग्राफ में, हम यह कि एक और उस एक कनेक्ट।
इस नोड तीन शीर्ष पर, नीचे एक के लिए जुड़ा हुआ है।
तो हम इसे इस एक के ऊपर और नीचे पर इन दोनों के लिए कनेक्ट।
यह एक शीर्ष और तल में इन दो पर।
तो हम ध्यान से इस पूरक ग्राफ जी का निर्माण किया और अब का एहसास करने के लिए आवश्यक बात यह है कि
एक S-गुट है जी, इस नए ग्राफ़, जो H के पूरक है
H एक S स्वतंत्र सेट है यदि और केवल यदि।
वास्तव में, यह नोड्स के एक ही सेट है। तो यहाँ है हमारे चार गुट उदाहरण के लिए।
इस ग्राफ कि हम पर ध्यान से पहले करने के लिए समान है।
यह हमारे चार गुट जी में है और अगर हम कि देखो बिल्कुल एक चार स्वतंत्र H में निर्धारित करने के लिए संगत हो
क्योंकि यह है सब pairwise किनारों में जी और तब यह उन सभी pairwise किनारों में एच. है करने के लिए असफल हो गया है
ताकि का कैसे समाधान स्वतंत्र सेट समस्या को हल करने के लिए में गुट समस्या का उपयोग कर सकते हैं।
अब इस विशिष्ट उदाहरण में, अच्छी तरह से यह एक सामान्य विचार दिखाता है
जो है हम ले एक समस्या के उदाहरण और हम उन्हें एक और की आवृत्ति में बदलना।
इस स्थिति में परिवर्तन वास्तव में बहुत सरल है।
शायद यह पहली बार में आप के लिए स्पष्ट नहीं था। अब है कि मैं कि putted, यह शायद बहुत सीधा है।
इन कटौती के कुछ वास्तव में बहुत कुछ शामिल हो सकते हैं।
यह एक वास्तव में सच में आसानी से बदल गई है।
तो अगर हम स्वतंत्र सेट के लिए एक एल्गोरिथ्म है।
हम इसी तरह गुट समस्या को हल करने के लिए उपयोग कर सकते हैं।
जहाँ मैं ग्राफ, देखो स्वतंत्र सेट के लिए पूरक ग्राफ पलटें और हमें बताता है कि
क्या मूल ग्राफ में गुट में शामिल है,
लेकिन कभी कभी फिर से कनेक्शन हमेशा इतना सरल नहीं है।
これがイメージ図になります
グラフHから始めましょう
ここにあるエッジを
Hを補完する新しいグラフGに置き換えます
Hにおいてエッジがある部分はすべて
Gではエッジがないままにしておきます
例えばこのノードはこことここにつながっていません
補完グラフでつなげます
このノードは上列のこの3つと
下列の1つとつながっていますが
補完グラフではその他のノードにつなげます
上列の1つと下列の2つとですね
注意深くつなげていくと補完グラフGは
sクリークを持っていることが分かりますね
Hが独立s点集合問題を持っていた場合のみです
実際にノードの集合は同じです
この例では4つのクリークがあります
前に出たグラフと似ていますね
Gの中に4つのクリークがあり対応する箇所では
Hの中に4つの独立点集合があります
Gの中にペアのエッジがすべてあり
Hの中にはないからです
これが独立点集合問題を解くための
クリーク問題の解き方です
一例として一般的なアイデアを紹介しましょう
ある問題のインスタンスを
他のインスタンスに変換します
この場合変換はとても直接的です
最初はよく分からないかも知れませんが
とても直接的なんですよ
還元も関係してきます
この例では逆の還元も簡単に行えます
独立点集合をアルゴリズムに持つ場合
クリーク問題を同じ方法で解くために使えます
補完グラフを元のグラフに反転し
独立点集合を確認します
元のグラフにクリークが存在するか確認してください
ただいつも問題と問題の関係が
こんなに直接的であるとは限りません