YouTube

Got a YouTube account?

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

Hindi subtitles

← 02ps-02 Subsets Solution

Get Embed Code
3 Languages

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

  1. सबसेट सवाल का पहला हिस्सा planar रेखांकन और पेड़ों के बारे में पूछते हैं।
  2. नोट के लिए पहली बात यह है कि नहीं सभी planar रेखांकन पेड़ हैं।
  3. उदाहरण के लिए, यहाँ है एक अंगूठी जो एक planar ग्राफ है, और यह एक पेड़ नहीं है।
  4. और पेड़ों की एक सबसेट तो planar रेखांकन नहीं रहे हैं। दूसरी ओर, सभी पेड़ planar रेखांकन कर रहे हैं।
  5. अधिकांश पेड़ों के लिए, यह काफी कैसे यह हवाई जहाज़ में तैयार हो कर सकते हैं देखने के लिए सहज ज्ञान युक्त है।
  6. उदाहरण के लिए, यह एक पहले से ही planar है।
  7. लेकिन अन्य वृक्षों के लिए, यह इसलिए कि हम सब कुछ को पुनर्व्यवस्थित कर सकते हैं स्पष्ट नहीं हो सकता है
  8. यह बाहर विमान में, लेआउट के लिए और यह एक सबूत है कि सभी पेड़ planar है अच्छा होगा तो
  9. बस अंतर्ज्ञान पर भरोसा करने के बजाय।
  10. एक तरह से यह साबित करने के लिए कि किसी भी पेड़ एक त्रिकोण के अंदर तैयार हो कर सकते हैं दिखाने के लिए है।
  11. और फिर बड़ा पेड़ इन त्रिकोण के संयोजन से खड़े हो सकते हैं।
  12. और अधिक औपचारिक रूप से, क्या हम दिखाना चाहते हैं कि किसी भी पेड़ एक त्रिकोण के अंदर एक हवाई जहाज़ में खींचा जा सकता है
  13. त्रिकोण के शीर्ष पर किसी भी दिए गए नोड के साथ।
  14. और तो एक नोड के आधार मामले के लिए, हम नोड त्रिकोण के शीर्ष पर आकर्षित कर सकते हैं
  15. और यह trivially में एक हवाई जहाज़ है।
  16. और तो, हमारे आगमनात्मक कदम लगता है कि दावा कम से कम n नोड्स के साथ सभी रेखांकन के लिए सच है।
  17. और हमें पता चलता है कि दावा सच n नोड्स के साथ सभी रेखांकन के लिए करना चाहते हैं।
  18. तो हम n नोड्स के साथ एक पेड़ के साथ शुरू करेंगे। हम इस उदाहरण के लिए का उपयोग करें।
  19. हम किसी भी नोड पर की तरह यादृच्छिक लेने के लिए जा रहे हैं और हम इसे आर फोन करता हूँ।
  20. उदाहरण के लिए, इस नोड में से एक आर हो। और फिर हम आर निकालें।
  21. क्योंकि हमारे मूल ग्राफ़ एक पेड़ था, यह अलग-अलग विसंधित पेड़ों में ग्राफ अलग करता है।
  22. और अब इन पेड़ों में से प्रत्येक के बाद से n नोड्स की तुलना में कम है,
  23. हम में से हर एक एक त्रिकोण के अंदर आकर्षित कर सकते हैं।
  24. सबसे पहले, हम चार नोड्स के इस पेड़ ले और यह त्रिकोण के अंदर आकर्षित कर सकते हैं।
  25. सूचना है कि नोड के लिए आर से जुड़ा था त्रिभुज का शीर्ष पर है।
  26. और फिर हम अन्य दो पेड़ों के लिए एक ही कर सकता है।
  27. और फिर हमारे पिछले चरण में, हम एक बड़ा त्रिभुज बनाती हूँ और हम पर सर्वोच्च आर डाल
  28. और तब यह अन्य त्रिकोण के apexes करने के लिए कनेक्ट।
  29. यह हमारे दावे की पुष्टि और पता चलता है कि सभी पेड़ ग्राफ़ planar हैं।
  30. वे निश्चित रूप से पेड़ों की परिभाषा के कारण न तो कर रहे हैं।
  31. एक ट्री कोई चक्र है सकते हैं और एक अंगूठी एक चक्र होना चाहिए।
  32. इसका जवाब न तो है। >> हाँ। >> शांत।
  33. मैं कभी नहीं मिला है जो पर्याप्त है लेकिन - था सिर्फ उदाहरण के अलावा एक श्रृंखला के एक सच में विशिष्ट परिभाषा
  34. एक अंगूठी है हाँ, एक ही विचार की तरह एक श्रृंखला एक चक्र है, जबकि नहीं करता।
  35. और दूसरी चीज़ हमें मिल गया था निश्चित रूप से है कि श्रृंखला में किनारों है शून्य से 1 नोड्स की संख्या
  36. और किनारों के रिंग में नोड्स के लिए बराबर है।
  37. इसलिए, हो सकता कोई अंतरराष्ट्रीय उन दोनों के बीच। वे परस्पर अनन्य हैं।
  38. सभी जंजीरों के पेड़ हैं, लेकिन नहीं सभी पेड़ हैं और तो यह पहले से एक है।
  39. यह एक पेड़ ग्राफ कि यह कनेक्टेड है की परिभाषा संतुष्ट करता, लेकिन वहाँ कोई चक्र हैं,
  40. और फिर एक पेड़ का अन्य विवरण ग्राफ कि रेखांकन में नोड्स के प्रत्येक जोड़ी
  41. उन दोनों के बीच एक अद्वितीय पथ है।
  42. मेरा मतलब है कि एक श्रृंखला भी है।
  43. यह निश्चित रूप से एक है कि intuitively का जवाब उदाहरणों को देखना है।
  44. यह 100% विश्वास का दावा है कि बनाने देता है।
  45. हाँ और बस एक त्वरित उदाहरण के - की तरह है कि एक पेड़ और कि एक श्रृंखला तो नहीं है-
  46. सही है। और जिस तरह से मैं यकीन है कि अपने आप को एक उदाहरण के एक hypercube का आ रहा है
  47. कि एक अँगूठी और एक अंगूठी जो एक hypercube नहीं था नहीं था।
  48. जब तक आप एक अंगूठी है कि लेकिन कुछ चार नोड्स है यह एक hypercube नहीं है।
  49. ठीक. >> और किसी भी hypercube लेकिन कुछ चार नोड्स है कि निश्चित रूप से एक की अंगूठी नहीं है।
  50. शानदार. हाँ तो मैं आप के लिए एक आकर्षित करेंगे और यह सिर्फ एक सामान्य घन है।
  51. सही है। >> और पिछले समस्या करने के लिए हमारी दूसरी बस ग्रिड और चेन है।
  52. सभी जंजीरों ग्रिड हैं, लेकिन नहीं सभी ग्रिड चेन हैं तो यह है-चेन ग्रिड के विपरीत कर रहे हैं।
  53. हाँ. >> एक 1xn ग्रिड नोड्स के भीतर किसी भी श्रृंखला है।
  54. एक बार जब आप किसी ग्रिड या तो दो दिशाओं में एक से अधिक है, यह अब एक श्रृंखला है।
  55. और कोई बात नहीं कितना समय आप एक श्रृंखला - कर >> हाँ। तो यह है-
  56. आप चेन - चेन, कि यह नहीं एक ग्रिड के लिए n का एक नोड के लिए एक नोड जोड़ें कर सकते हैं।
  57. पहली बात आप ने कहा कि हम एक 1xn ग्रिड और यह की तरह है की तरह भी लेकिन हाँ एक श्रृंखला है।
  58. हाँ. इस उदाहरण के लिए एक श्रृंखला नहीं है। >> सही। >> शांत।