YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Hindi subtitles

← 06-29 Reducing to Clique

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. बस इस उदाहरण को वर्णन करने के लिए, हम कुछ ग्राफ एच. के साथ शुरू होगा की कल्पना करो यह एक गड़बड़ का एक छोटा सा है।
  2. किनारों में यहाँ के एक बहुत है लेकिन हम जा रहे हैं करने के लिए परिवर्तित यह एक नया ग्राफ जी, करने के लिए है
  3. जो है H और H में तो हर जगह के पूरक हैं जहां हम छोड़ बाहर, बढ़त बढ़त
  4. और हर जगह जहां एक छोर नहीं है, हम एक एज जोड़ें।
  5. उदाहरण के लिए, इस नोड के लिए यह एक या यह एक से जुड़ा नहीं है।
  6. तो पूरक के ग्राफ में, हम यह कि एक और उस एक कनेक्ट।
  7. इस नोड तीन शीर्ष पर, नीचे एक के लिए जुड़ा हुआ है।
  8. तो हम इसे इस एक के ऊपर और नीचे पर इन दोनों के लिए कनेक्ट।
  9. यह एक शीर्ष और तल में इन दो पर।
  10. तो हम ध्यान से इस पूरक ग्राफ जी का निर्माण किया और अब का एहसास करने के लिए आवश्यक बात यह है कि
  11. एक S-गुट है जी, इस नए ग्राफ़, जो H के पूरक है
  12. H एक S स्वतंत्र सेट है यदि और केवल यदि।
  13. वास्तव में, यह नोड्स के एक ही सेट है। तो यहाँ है हमारे चार गुट उदाहरण के लिए।
  14. इस ग्राफ कि हम पर ध्यान से पहले करने के लिए समान है।
  15. यह हमारे चार गुट जी में है और अगर हम कि देखो बिल्कुल एक चार स्वतंत्र H में निर्धारित करने के लिए संगत हो
  16. क्योंकि यह है सब pairwise किनारों में जी और तब यह उन सभी pairwise किनारों में एच. है करने के लिए असफल हो गया है
  17. ताकि का कैसे समाधान स्वतंत्र सेट समस्या को हल करने के लिए में गुट समस्या का उपयोग कर सकते हैं।
  18. अब इस विशिष्ट उदाहरण में, अच्छी तरह से यह एक सामान्य विचार दिखाता है
  19. जो है हम ले एक समस्या के उदाहरण और हम उन्हें एक और की आवृत्ति में बदलना।
  20. इस स्थिति में परिवर्तन वास्तव में बहुत सरल है।
  21. शायद यह पहली बार में आप के लिए स्पष्ट नहीं था। अब है कि मैं कि putted, यह शायद बहुत सीधा है।
  22. इन कटौती के कुछ वास्तव में बहुत कुछ शामिल हो सकते हैं।
  23. यह एक वास्तव में सच में आसानी से बदल गई है।
  24. तो अगर हम स्वतंत्र सेट के लिए एक एल्गोरिथ्म है।
  25. हम इसी तरह गुट समस्या को हल करने के लिए उपयोग कर सकते हैं।
  26. जहाँ मैं ग्राफ, देखो स्वतंत्र सेट के लिए पूरक ग्राफ पलटें और हमें बताता है कि
  27. क्या मूल ग्राफ में गुट में शामिल है,
  28. लेकिन कभी कभी फिर से कनेक्शन हमेशा इतना सरल नहीं है।