مجموعة محدبة هي واحدة من الأشياء الهامة للدراسة في الرياضيات والتحسين. ولكن كيف تعرف ما إذا كانت المجموعة محدبة حقا? للقيام بذلك ، هناك العديد من النظريات والأساليب الأساسية التي تسمح لك بإثبات تحدب المجموعة.
المفهوم الرئيسي في مشكلة إثبات التحدب هو مزيج محدب. هذا مزيج خطي من نقاط مجموعة حيث تكون جميع المعاملات غير سالبة ومجموع المعاملات هو 1. إذا كانت المجموعة المحدبة لجميع نقاط المجموعة تكمن أيضا في هذه المجموعة ، فهي محدبة.
طريقة واحدة لإثبات التحدب من مجموعة هو استخدام تعريف التحدب. تتلخص المشكلة في إثبات أنه بالنسبة لأي نقطتين من المجموعة ، فإن الجزء الذي يربطهما يقع تماما داخل المجموعة. للقيام بذلك ، يمكنك استخدام طريقة الافتراض المعاكس أو طريقة الحث الرياضي.
الافتراض المعاكس هو أننا نفترض أن هناك قطعة تربط نقطتين من المجموعة ، وإحدى نقاطها لا تقع داخل المجموعة. ثم نظهر أن مثل هذا الافتراض يؤدي إلى تناقض ، وبالتالي فإن المجموعة محدبة.
يتضمن الاستقراء الرياضي إثبات تحدب مجموعة لنقطة واحدة ، ثم لأي عدد من النقاط. لإثبات تحدب مجموعة من نقطة واحدة ، يكفي إظهار أن أي مجموعة محدبة من هذه النقطة تقع أيضا في المجموعة. ثم نفترض أن التحدب من مجموعة ثبت ل ن نقاط وإثبات أنه صحيح ل ن + 1 نقطة. وهكذا ، باستخدام طريقة الحث الرياضي ، نثبت التحدب لأي عدد من النقاط في المجموعة.
- نحدد تعريف مجموعة محدبة
- دعونا نثبت النظرية على معيار مجموعة محدبة
- دعونا نناقش مفهوم بدن محدب
- دعونا ندرس طرق إثبات إدراج نقطة في مجموعة محدبة
- النظر في نظرية بدن محدب من النقاط
- دعونا نلقي نظرة على الطرق الممكنة لإثبات تحدب الوظيفة
- دعنا ندرس الخوارزميات للتحقق من تحدب مجموعة على الكمبيوتر
- سؤال وجواب
- كيف يمكن للمرء أن يثبت أن مجموعة محدبة?
- الطريقة التي وجدت أكبر استخدام في إثبات التحدب?
- ما هو بوليتوب اندماجي محدب وكيف يمكن إثباته?
- هل من الممكن إثبات تحدب مجموعة باستخدام المصفوفات والمتجهات?
- ما هي الخصائص التي تحتوي عليها مجموعة محدبة?
نحدد تعريف مجموعة محدبة
تسمى المجموعة محدبة إذا كانت جميع النقاط الموجودة على المقطع الذي يربط أي نقطتين من مجموعة معينة تنتمي أيضا إلى هذه المجموعة.
بشكل أكثر رسمية ، تسمى المجموعة محدبة إذا لأي نقاط س و ص تنتمي إلى المجموعة ، ولأي رقم ر مثل 0 t ر 1 1 ، النقطة (1-ر)س + تاي ينتمي أيضا إلى المجموعة.
بمعنى آخر ، إذا كانت أي نقطة ملقاة على الجزء الذي يربط نقطتين من مجموعة تنتمي أيضا إلى هذه المجموعة ، فهي محدبة.
على سبيل المثال ، الدائرة عبارة عن مجموعة محدبة ، لأن أي جزء يربط نقطتين داخل الدائرة يقع تماما داخل الدائرة.
تستخدم المجموعات المحدبة على نطاق واسع في الرياضيات وتطبيقاتها ، بما في ذلك التحسين ونظرية الألعاب والهندسة والاقتصاد.
دعونا نثبت النظرية على معيار مجموعة محدبة
في نظرية التحليل المحدب ، هناك نظرية أساسية تسمح لك بالتحقق مما إذا كانت مجموعة معينة محدبة. تسمى هذه النظرية نظرية معيار المجموعة المحدبة.
نظرية: مجموعة $X\فرعية\mathbb{R}^n$ محدب إذا و فقط إذا كان لأي نقطتين $x, y\في X$ الجزء $[x,y] =\{(1-t)x+ty : 0\leq t\leq 1\}$ تماما الواردة في مجموعة $X$.
بمعنى آخر ، لأي نقطتين من المجموعة X س X ، تنتمي جميع النقاط الموجودة على المقطع الذي يربط هذه النقاط أيضا إلى المجموعة X س..
لإثبات هذه النظرية ، من الضروري استخدام تعريف مجموعة محدبة وخصائص تركيبة محدبة.
التعريف. مجموعة $X$ يسمى محدب إذا أي نقطة $x, y\في X$ وأي $t\في [0 ، 1]$, نقطة $(1-t)x +تاي$ ينتمي أيضا إلى مجموعة $X$.
خاصية مزيج محدب: لأي مجموعة من النقاط-س_1, س_2,... والمعاملات غير السالبة \ \ لامدا_1, \ لامدا_2,... مثل ذلك lamb \ لامدا_1 + \ لامدا_2+... + \ لامدا_ك = 1$ ، مزيج محدب من هذه النقاط \ \ مجموع_{أنا = 1}^{ك} \ لامدا_ي س_ي belongs ينتمي أيضا إلى مجموعة X س X.
النظر في نقطتين $x, y\في X$ و نفترض أن قطاع $[x,y]$ ليس تماما الواردة في مجموعة $X$. هذا يعني أن هناك نقطة في المقطع لا تنتمي إلى المجموعة X س$. لكن هذا يتناقض مع تعريف مجموعة محدبة. لذلك ، فإن المجموعة X س convex محدبة.
على العكس من ذلك ، نفترض أن مجموعة X س convex ليست محدبة. وهذا يعني أن هناك نقطة $x, y\في X$ التي يوجد نقطة على شريحة $[x,y]$ التي لا تنتمي إلى مجموعة $X$. لكن هذا يتناقض مع نظرية معيار المجموعة المحدبة. لذلك ، فإن المجموعة X س convex محدبة.
وبالتالي ، فإن نظرية معيار المجموعة المحدبة تحدد شرطا ضروريا وكافيا لتحدب المجموعة X س provides ويوفر طريقة بسيطة للتحقق من التحدب.
دعونا نناقش مفهوم بدن محدب
الهيكل المحدب هو أصغر مجموعة محدبة تحتوي على جميع نقاط المجموعة الأصلية. بمعنى آخر ، الهيكل المحدب هو متعدد السطوح محدب أو مجموعة متعددة الأبعاد تحدها وجوه محدبة.
يمكن تمثيل الهيكل المحدب على أنه اتحاد لجميع المجموعات المحدبة لنقاط المجموعة الأصلية. تعتبر مجموعة النقاط محدبة إذا كانت أوزان كل نقطة غير سالبة ومجموعها 1. على سبيل المثال ، بالنسبة لنقطتين أ و ب ، ستبدو التركيبة المحدبة كما يلي: ج = أأ + ß ، أين weights و are هي أوزان غير سالبة.
يمكن تمثيل الهيكل المحدب كسلسلة محدودة من الرؤوس والحواف التي تربط هذه الرؤوس. هناك خوارزميات مختلفة لهذا الغرض. على سبيل المثال ، يمكن أن تكون خوارزمية جراهام أو خوارزمية جارفيس السريعة بناء على عبور مجموعة من النقاط.
تحتوي الهياكل المحدبة على مجموعة واسعة من التطبيقات في مختلف المجالات ، بما في ذلك رسومات الكمبيوتر ، والتحسين ، والتعرف على الأنماط ، وما إلى ذلك. يمكن استخدامها لحل مشاكل مثل العثور على أكبر مستطيل داخل مضلع أو تحديد ما إذا كانت النقطة تقع داخل متعدد السطوح.
بالإضافة إلى ذلك ، يمكن تعميم مفهوم الهيكل المحدب على حالة الوظائف المستمرة أو المساحات المترية التعسفية. في هذه الحالة ، تكون القشرة هي أصغر منطقة محدبة تحتوي على جميع نقاط الدالة أو المساحة.
دعونا ندرس طرق إثبات إدراج نقطة في مجموعة محدبة
في دراسة المجموعات المحدبة ، أحد الأسئلة المهمة هو إثبات إدراج نقطة في مثل هذه المجموعة. هناك العديد من الطرق التي تسمح لك بالقيام بذلك.
الطريقة 1: التعريف الهندسي لمجموعة محدبة.
- وفقا للتعريف الهندسي ، تكون المجموعة محدبة إذا كان الجزء الذي يربط هذه النقاط يقع أيضا في المجموعة المحددة لأي نقطتين في مجموعة معينة.
- لإثبات إدراج نقطة في مجموعة محدبة ، من الضروري التحقق من استيفاء هذا الشرط لنقطة معينة وجميع أزواج النقاط في مجموعة معينة.
- أي أنك تحتاج إلى التحقق من أنه بالنسبة لأي نقطتين في المجموعة ، فإن المقطع الذي يربط هذه النقاط يقع بالكامل في المجموعة.
الطريقة 2: البرمجة الخطية.
- هناك طريقة أخرى لإثبات إدراج نقطة في مجموعة محدبة وهي استخدام البرمجة الخطية.
- يتمثل جوهر هذه الطريقة في صياغة مشكلة التحسين مع القيود ، حيث تكون النقطة التي يجب إثبات تضمينها في مجموعة محدبة حلا صالحا.
- بعد ذلك ، باستخدام خوارزمية البرمجة الخطية ، يمكنك العثور على الحل الأمثل والتحقق من أن نقطة البداية التي سيتم إثباتها المضمنة في المجموعة تفي بقيود مشكلة التحسين.
في كلتا الطريقتين ، يجب إجراء فحص شامل للتأكد من أن نقطة معينة تنتمي حقا إلى مجموعة محدبة معينة. قد يتطلب ذلك استخدام أدوات وأساليب رياضية مختلفة ، اعتمادا على الموقف المحدد.
النظر في نظرية بدن محدب من النقاط
نظرية بدن محدب من النقاط هي واحدة من النظريات الرئيسية للهندسة محدبة. يسمح لنا بإثبات أن مجموعة معينة من النقاط في فضاء ثنائي الأبعاد أو متعدد الأبعاد هي مجموعة محدبة.
تعريف بدن محدب من النقاط: الهيكل المحدب لنقاط مجموعة معينة من النقاط هو مجموعة محدبة صغيرة تحتوي على كل هذه النقاط.
تنص نظرية البدن المحدب للنقاط على أن الهيكل المحدب لنقاط المجموعة هو مجموعة محدبة. هناك طرق مختلفة لإثبات هذه النظرية.
تعتمد إحدى طرق إثبات نظرية بدن محدب للنقاط على التمثيل الموصوف في شكل عملية "لف" مجموعة من النقاط. تستخدم هذه الطريقة معاملات التحدب للنقاط ، والتي يتم حسابها عن طريق تحديد تحدب المجموعة.
تعتمد الطريقة الثانية لإثبات نظرية بدن محدب للنقاط على استخدام خوارزمية جراهام. تتيح لك هذه الخوارزمية العثور على الحد الأدنى من المجموعة المحدبة التي تحتوي على مجموعة معينة من النقاط. تعتمد خوارزمية جراهام على بناء بدن محدب على مستوى عن طريق عبور النقاط وبناء بدن محدب في هذه النقاط.
وبالتالي ، فإن نظرية الهيكل المحدب للنقاط هي نتيجة مهمة في مجال الهندسة المحدبة وتستخدم لإثبات تحدب المجموعات. لديها طرق إثبات مختلفة ، بما في ذلك طريقة "التفاف" وخوارزمية غراهام.
دعونا نلقي نظرة على الطرق الممكنة لإثبات تحدب الوظيفة
يعد إثبات تحدب الوظيفة مهمة مهمة في الرياضيات والتحسين. هناك عدة طرق للتحقق من تحدب الوظيفة وصياغة دليل مناسب. دعونا ننظر إلى بعض منهم:
- إثبات باستخدام تعريف التحدب. وفقا للتعريف ، وظيفة و (س)محدب على الفاصل الزمني [أ ، ب] إذا كان عدم المساواة التالية يحمل أي س1 ، س2 من هذه الفترة ولأي رقم ر من الجزء [0 ، 1]: و(تكس1 + (1-ر) س2 )f تف(س1) + (1-ر)و(س2). لإثبات تحدب الوظيفة باستخدام التعريف ، من الضروري أخذ النقاط التعسفية س1 و س2 من الفاصل الزمني [أ ، ب] ، حدد ر التعسفي من الجزء [0 ، 1] ، استبدل القيم في عدم المساواة وتأكد من أنها عادلة.
- إثبات تحدب دالة باستخدام المشتق الثاني. إذا كانت الوظيفة قابلة للتفاضل مرتين ، فيمكن إثبات تحدب الوظيفة على الفاصل الزمني [أ ، ب] باستخدام المشتق الثاني. إذا كان المشتق الثاني غير سالب خلال الفاصل الزمني بأكمله [أ ، ب] ، فإن الوظيفة تكون محدبة خلال هذا الفاصل الزمني.
- دليل على تحدب وظيفة من خلال عدم المساواة. في بعض الحالات ، لإثبات تحدب وظيفة ما ، يمكنك استخدام الخصائص المعروفة للوظيفة وتطبيق عدم المساواة المختلفة ، وتبسيط التعبير الأصلي والحصول على البيان اللازم حول التحدب.
- دليل على تحدب دالة باستخدام الرسم البياني. يمكن أن يساعد رسم وظيفة في إثبات التحدب البصري. إذا كان الرسم البياني للدالة له شكل منحنى "محدب" ، فيمكننا أن نستنتج أن الوظيفة نفسها محدبة.
يعتمد اختيار طريقة لإثبات تحدب الوظيفة على خصائصها ، وسهولة استخدام النظريات والتعاريف ، فضلا عن توفر الحسابات الرياضية والتفسير الرسومي. كل طريقة لها مزاياها ويمكن أن تكون مفيدة في المواقف المختلفة.
دعنا ندرس الخوارزميات للتحقق من تحدب مجموعة على الكمبيوتر
تستخدم خوارزميات التحقق من تحدب المجموعة على نطاق واسع في هندسة الكمبيوتر. إنها تسمح لك بتحديد ما إذا كانت مجموعة معينة محدبة أم لا. يمكن استخدام هذه الميزة المفيدة لمجموعة الانتفاخ في مجالات مختلفة مثل رؤية الكمبيوتر والروبوتات والرسومات والتصميم.
هناك العديد من الخوارزميات التي تسمح لك بالتحقق من تحدب مجموعة على الكمبيوتر. دعونا ننظر إلى بعض منهم:
- خوارزمية للتحقق من التحدب بحكم التعريف.
- خوارزمية جراهام لإيجاد الهيكل المحدب.
- حدد النقطة ذات الحد الأدنى من الإحداثيات.
- قم بفرز النقاط المتبقية حسب الزاوية القطبية بالنسبة للنقطة المحددة.
- انتقل من خلال النقاط التي تم فرزها وأضف كل نقطة إلى المكدس. إذا شكلت النقطة الأخيرة الحالية والنقطتين السابقتين منعطفا يمينا عند إضافة نقطة ، فقم بإزالة النقطة الأخيرة من المكدس.
- تحقق من ترك النقاط من المجموعة الأولية فقط في المكدس.
- خوارزمية تشن لإيجاد مجموعات محدبة.
- فرز النقاط من قبل س تنسيق.
- انتقل من خلال النقاط وقسمها إلى مجموعتين: النقاط على اليسار والنقاط على اليمين.
- لكل مجموعة من النقاط ، قم ببناء بدن محدب باستخدام خوارزمية جراهام.
- الحصول على تقاطع اثنين من هياكل محدبة.
تعتمد هذه الخوارزمية على تعريف مجموعة محدبة. تعتبر المجموعة محدبة إذا كان المقطع الذي يربط هذه النقاط ينتمي أيضا إلى المجموعة لأي نقطتين من هذه المجموعة. تتكون خوارزمية فحص التحدب ، بحكم تعريفها ، من التحقق من هذا الشرط لجميع أزواج النقاط الممكنة. إذا كانت جميع الأجزاء التي تربط نقاط المجموعة داخل المجموعة ، فإن المجموعة محدبة.
تتيح لك هذه الخوارزمية العثور على الهيكل المحدب لمجموعة من النقاط واستخدامه للتحقق من تحدب المجموعة. تتكون الخوارزمية من الخطوات التالية:
تتيح لك هذه الخوارزمية العثور على جميع المجموعات المحدبة في مجموعة معينة من النقاط. تتكون الخوارزمية من الخطوات التالية:
كل من هذه الخوارزميات لها مزاياها وعيوبها. اعتمادا على المهمة والمتطلبات ، يمكنك اختيار الخوارزمية المناسبة للتحقق من تحدب مجموعة على جهاز الكمبيوتر. إنها أدوات فعالة وواسعة الانتشار للعمل مع الكائنات الهندسية على الكمبيوتر.
سؤال وجواب
كيف يمكن للمرء أن يثبت أن مجموعة محدبة?
هناك عدة طرق أساسية لإثبات تحدب المجموعة. واحد منهم هو فحص التعريف. إذا كانت أي نقطتين من المجموعة ولأي رقم (من 0 إلى 1) تنتمي مجموعتهما أيضا إلى المجموعة ، فهي مجموعة محدبة.
الطريقة التي وجدت أكبر استخدام في إثبات التحدب?
حاليا ، وجدت طريقة المجموعة المترافقة المزعومة أكبر استخدام في إثبات التحدب. يعتمد على استخدام المجموعة المترافقة وخصائص الطائرات الفائقة المنفصلة.
ما هو بوليتوب اندماجي محدب وكيف يمكن إثباته?
أ بوليتوب اندماجي محدب هو بدن محدب لمجموعة محدودة من النقاط في ن-الفضاء الأبعاد. لإثبات التحدب الثابت للبوليتوب التوافقي ، يكفي التحقق من تحدب كل وجه من وجوهه وتحقيق حالة جاليركين.
هل من الممكن إثبات تحدب مجموعة باستخدام المصفوفات والمتجهات?
نعم ، يمكنك. هناك طريقة للتحقق من تحدب مجموعة بناء على العمل مع المصفوفات والمتجهات. هذه الطريقة تسمى طريقة المصفوفة. وهو يتألف من حل عدم المساواة المصفوفة التي تحدد مجموعة محدبة.
ما هي الخصائص التي تحتوي عليها مجموعة محدبة?
مجموعة محدبة لديها العديد من الخصائص الهامة. أولا ، سيتم احتواء أي جزء يربط نقطتين من المجموعة بالكامل فيه. ثانيا ، تتقاطع المجموعة المحدبة دائما مع أي شعاع يتم إطلاقه من نقطتها الداخلية. ثالثا ، بالنسبة لنقطتين تعسفيتين من المجموعة ، فإن النقطة الثالثة الموجودة على الجزء الذي يربط هذه النقاط ستنتمي أيضا إلى المجموعة.