Hindi subtitles

← 06-27 Find the Strangers

Get Embed Code
3 Languages

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

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