تطبيق واسع لنظرية الرسم البياني في علوم الكمبيوتر. استخدام الرسوم البيانية في مجالات مختلفة من حياة الناس

البلدية المستقلة للتعليم العام مؤسسة التعليم الثانوي التعليم الثانوي № 2

معد

Legkokonets فلاديسلاف ، 10A طالبة

التطبيق العملي لنظرية الرسم البياني

مشرف

L.I. نوسكوفا ، مدرس رياضيات

سانت بريوخوفيتسكايا

2011

1.مقدمة ……………………………………………………………………………………. ………… .3

2. تاريخ ظهور نظرية الرسم البياني …………………………………………… .. ……… ..4

3 التعاريف والنظريات الأساسية لنظرية الرسم البياني ............................................................. ............... 6

4. المهام التي تم حلها بمساعدة الرسوم البيانية …………………………… .. …………………… .. 8

4.1 المهام الشهيرة …………………………………… .. ………………………… ... 8

4.2 بعض المهام الشيقة …………………………………… .. …………… .. 9

5. تطبيق الرسوم البيانية في مختلف مجالات حياة الناس ……………………………… ... 11

6. حل المشكلات …………………………………………………………………………………… ... 12

7. الخلاصة …………………… .. ………………………………………………………………………………… .13

8. قائمة المراجع …………. ………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………………………………….

9. الملحق ……………………………………………………………………………… .. ………… 15

مقدمة

ولدت في حل الألغاز والألعاب المسلية ، أصبحت نظرية الرسم البياني الآن أداة بسيطة وسهلة الوصول وقوية لحل المشكلات المتعلقة بمجموعة واسعة من المشاكل. الرسوم البيانية موجودة في كل مكان حرفيًا. في شكل رسوم بيانية يمكنك مثلا تفسير خرائط الطريق والدوائر الكهربائية ، الخرائط الجغرافيةوالجزيئات مركبات كيميائية، الروابط بين الناس ومجموعات الناس. على مدى العقود الأربعة الماضية ، أصبحت نظرية الرسم البياني واحدة من أسرع فروع الرياضيات تطورًا. هذا مدفوع بمتطلبات مجال التطبيق الآخذ في التوسع بسرعة. يتم استخدامه في تصميم الدوائر المتكاملة ودوائر التحكم ، في دراسة الأوتوماتا ، والدوائر المنطقية ، ومخططات تدفق البرنامج ، في الاقتصاد والإحصاء ، والكيمياء والبيولوجيا ، في نظرية الجدولة. لهذا السبب ملاءمةيرجع الموضوع ، من ناحية ، إلى شعبية الرسوم البيانية وأساليب البحث ذات الصلة ، ومن ناحية أخرى ، نظام متكامل غير مطور لتنفيذه.

يتطلب حل العديد من مشاكل الحياة حسابات طويلة ، وأحيانًا لا تحقق هذه الحسابات نجاحًا. هذا ما تتكون منه مشكلة بحث. السؤال الذي يطرح نفسه: هل من الممكن إيجاد حل بسيط وعقلاني وقصير وأنيق لحلها. هل من الأسهل حل المشكلات إذا كنت تستخدم الرسوم البيانية؟ حددت موضوع بحثي: "التطبيق العملي لنظرية الرسم البياني"

هدف، تصويبتم البحث بمساعدة الرسوم البيانية لتعلم كيفية حل المشكلات العملية بسرعة.

فرضية البحث.تعتبر طريقة الرسم البياني مهمة جدًا وتستخدم على نطاق واسع في مختلف مجالات العلوم وحياة الإنسان.

أهداف البحث:

1. دراسة الأدبيات ومصادر الإنترنت حول هذا الموضوع.

2. التحقق من فعالية طريقة الرسم البياني في حل المشكلات العملية.

3. التوصل إلى استنتاج.

أهمية عمليةابحاثهي أن النتائج ستثير بلا شك اهتمام الكثير من الناس. ألم يحاول أي منكم بناء شجرة عائلة لعائلتك؟ وكيف نفعل ذلك بشكل صحيح؟ ربما يتعين على رئيس شركة النقل حل مشكلة الاستخدام الأكثر ربحية للنقل عند نقل البضائع من وجهة إلى عدة مستوطنات. واجه كل طالب مهام نقل الدم المنطقية. اتضح أنه يتم حلها بمساعدة الرسوم البيانية بسهولة.

يتم استخدام الطرق التالية في العمل: الملاحظة ، البحث ، الاختيار ، التحليل.

تاريخ ظهور نظرية الرسم البياني

يعتبر عالم الرياضيات ليونارد أويلر (1707-1783) مؤسس نظرية الرسم البياني. يمكن تتبع تاريخ ظهور هذه النظرية من خلال مراسلات العالم العظيم. إليكم ترجمة للنص اللاتيني مأخوذ من رسالة أويلر إلى عالم الرياضيات الإيطالي والمهندس مارينوني ، المُرسلة من سانت بطرسبرغ في 13 مارس 1736.

"ذات مرة أُعطيت مشكلة بشأن جزيرة تقع في مدينة كونيغسبيرغ ومحاطة بنهر مرمي عبره سبعة جسور.

[الملحق الشكل 1]السؤال هو ما إذا كان يمكن لأي شخص الالتفاف حولهم بشكل مستمر ، ويمر مرة واحدة فقط من كل جسر. وبعد ذلك تم إخباري أنه لم يتمكّن أحد من القيام بذلك ، لكن لم يثبت أحد أنه مستحيل. هذا السؤال ، على الرغم من تافه ، بدا لي ، جدير بالملاحظةحقيقة أنه لا الهندسة ولا الجبر ولا الفن الاندماجي كافيان لحلها. بعد الكثير من التفكير ، وجدت قاعدة سهلة ، تستند إلى دليل مقنع تمامًا ، وبمساعدة جميع المشكلات من هذا النوع ، يمكن للمرء أن يقرر على الفور ما إذا كان يمكن إجراء مثل هذه الجولة من خلال أي عدد والجسور الموجودة بشكل تعسفي أم لا. توجد جسور Konigsberg بحيث يمكن تمثيلها في الشكل التالي [الملحق الشكل 2]، حيث تشير A إلى جزيرة ، و B و C و D هي أجزاء من القارة مفصولة عن بعضها البعض بفروع النهر

فيما يتعلق بالطريقة التي اكتشفها لحل مشاكل من هذا النوع ، كتب أويلر:

"يبدو أن هذا الحل ، بطبيعته ، ليس له علاقة بالرياضيات ، ولا أفهم لماذا يجب توقع هذا الحل من عالم رياضيات وليس من أي شخص آخر ، لأن هذا الحل مدعوم بالعقل وحده ، وهناك لا داعي للتورط في إيجاد هذا الحل ، أي قوانين متأصلة في الرياضيات. لذلك ، لا أعرف كيف اتضح أن الأسئلة التي لا علاقة لها بالرياضيات من المرجح أن يتم حلها بواسطة علماء الرياضيات أكثر من غيرهم ".

فهل من الممكن الالتفاف حول جسور كونيجسبيرج بالمرور مرة واحدة فقط عبر كل من هذه الجسور؟ للعثور على الإجابة ، دعنا نتابع رسالة أويلر إلى مارينوني:

"السؤال هو تحديد ما إذا كان من الممكن الالتفاف على كل هذه الجسور السبعة ، مروراً بكل منها مرة واحدة فقط أم لا. تؤدي قاعدتي إلى الحل التالي لهذا السؤال. أولاً وقبل كل شيء ، تحتاج إلى إلقاء نظرة على عدد الأقسام مفصولة بالماء - مثل ، التي ليس لها انتقال آخر من واحد إلى آخر ، إلا من خلال الجسر. في هذا المثال ، هناك أربعة أقسام من هذا القبيل - أ ، ب ، ج ، د. بعد ذلك ، تحتاج إلى التمييز ما إذا كان عدد تكون الجسور المؤدية إلى هذه الأقسام الفردية زوجية أو فردية. لذلك ، في حالتنا ، تؤدي خمسة جسور إلى القسم أ وثلاثة جسور إلى باقي الجسور ، أي أن عدد الجسور المؤدية إلى الأقسام الفردية فردي ، وهذا يكفي بالفعل حل المشكلة وعندما يتم تحديد ذلك ، نطبق القاعدة التالية: إذا كان عدد الجسور المؤدية إلى كل قسم فردي متساويًا ، فعندئذٍ في السؤال، سيكون ممكنًا ، وفي نفس الوقت سيكون من الممكن بدء هذا الانعطاف من أي قسم. ومع ذلك ، إذا كان اثنان من هذه الأرقام فرديين ، لأن رقمًا واحدًا فقط لا يمكن أن يكون فرديًا ، فعندئذٍ حتى ذلك الحين يمكن أن يحدث الانتقال ، كما هو موصوف ، ولكن يجب بالضرورة أخذ بداية التجاوز من أحد هذين القسمين. عدد فردي يؤدي الجسور. أخيرًا ، إذا كان هناك أكثر من قسمين يؤدي إليهما عدد فردي من الجسور ، فإن مثل هذه الحركة مستحيلة عمومًا ... إذا كان من الممكن ذكر مشاكل أخرى أكثر خطورة هنا ، فقد تكون هذه الطريقة أكثر فائدة ولا ينبغي. تكون مهملة ".

التعاريف الأساسية ونظريات نظرية الرسم البياني

نظرية الرسم البياني هي تخصص رياضي تم إنشاؤه بجهود علماء الرياضيات ، لذلك يتضمن عرضها التعاريف الدقيقة اللازمة. لذلك ، دعنا ننتقل إلى التقديم المنظم للمفاهيم الأساسية لهذه النظرية.

التعريف 1.الرسم البياني عبارة عن مجموعة عدد محدودنقاط ، تسمى رؤوس الرسم البياني ، وتربط زوجيًا بعض رؤوس الخطوط هذه ، تسمى حواف أو أقواس الرسم البياني.

يمكن صياغة هذا التعريف بشكل مختلف: الرسم البياني هو مجموعة غير فارغة من النقاط (الرؤوس) والمقاطع (الحواف) ، وكلا طرفيها ينتميان إلى مجموعة معينة من النقاط

في المستقبل ، سوف نشير إلى رؤوس الرسم البياني بالأحرف اللاتينية A و B و C و D. في بعض الأحيان يتم الإشارة إلى الرسم البياني ككل بواحد الحرف الكبير.

التعريف 2.تسمى رؤوس الرسم البياني التي لا تنتمي إلى أي حافة معزولة.

التعريف 3.الرسم البياني الذي يتكون فقط من رؤوس معزولة يسمى صفر - عدد .

تدوين: O "- رسم بياني برؤوس وبدون حواف

التعريف 4.الرسم البياني الذي يرتبط فيه كل زوج من الرؤوس بحافة يسمى مكتمل.

التعيين: U " – رسم بياني يتكون من رؤوس n وحواف تربط جميع الأزواج الممكنة من هذه الرؤوس. يمكن تمثيل هذا الرسم البياني على أنه n-gon حيث يتم رسم جميع الأقطار

التعريف 5.درجة الرأس هي عدد الحواف التي ينتمي إليها الرأس.

التعريف 6.يُطلق على الرسم البياني الذي تتساوى درجات جميع رءوسه k بالرسم البياني المتجانس للدرجة k .

التعريف 7.تكملة الرسم البياني المحدد عبارة عن رسم بياني يتكون من جميع الحواف ونهاياتها التي يجب إضافتها إلى الرسم البياني الأصلي للحصول على رسم بياني كامل.

التعريف 8.الرسم البياني الذي يمكن تمثيله في مستوى بحيث تتقاطع حوافه فقط عند الرؤوس يسمى مستوي.

التعريف 9.يسمى مضلع الرسم البياني المستوي الذي لا يحتوي على أي رؤوس أو حواف للرسم البياني بداخله وجهه.

تُستخدم مفاهيم الرسم البياني المستوي وأوجه الرسم البياني في حل المشكلات من أجل التلوين "الصحيح" للخرائط المختلفة.

التعريف 10.المسار من A إلى X هو سلسلة من الحواف الممتدة من A إلى X بحيث يكون لكل حافتين متجاورتين رأس مشترك ولا تظهر أي حافة أكثر من مرة.

التعريف 11.الدورة عبارة عن مسار تتشابه فيه نقطتا البداية والنهاية.

التعريف 12.الدورة البسيطة هي دورة لا تمر عبر أي من رؤوس الرسم البياني أكثر من مرة.

التعريف 13.طريق طويل , وضعت على حلقة , هو عدد حواف هذا المسار.

التعريف 14.يسمى رأسان A و B في الرسم البياني متصلين (غير متصلين) إذا كان هناك (غير موجود) مسار يؤدي من A إلى B فيه.

التعريف 15.يسمى الرسم البياني متصل إذا كان كل رأسين متصلين ؛ إذا كان الرسم البياني يحتوي على زوج واحد على الأقل من الرؤوس غير المتصلة ، فإن الرسم البياني يسمى غير متصل.

التعريف 16.الشجرة هي رسم بياني متصل لا يحتوي على دورات.

النموذج ثلاثي الأبعاد لشجرة الرسم البياني هو ، على سبيل المثال ، شجرة حقيقية بتاجها المتفرّع بشكل معقد ؛ يشكل النهر وروافده أيضًا شجرة ، ولكنها مسطحة بالفعل - على سطح الأرض.

التعريف 17.يُطلق على الرسم البياني المنفصل المكون فقط من الأشجار اسم الغابة.

التعريف 18.تسمى الشجرة ، التي تم ترقيم جميع رؤوسها من 1 إلى n ، شجرة ذات رؤوس مُعاد ترقيمها.

لذلك ، فقد درسنا التعريفات الرئيسية لنظرية الرسم البياني ، والتي بدونها سيكون من المستحيل إثبات النظريات ، وبالتالي حل المشكلات.

حل المشكلات باستخدام الرسوم البيانية

التحديات الشهيرة

مشكلة البائع المتجول

تعد مشكلة البائع المتجول إحدى المشكلات الشهيرة في نظرية التوافقية. تم طرحه في عام 1934 ، وكسر أفضل علماء الرياضيات أسنانهم حيال ذلك.

بيان المشكلة هو التالي.
يجب على البائع المتجول (التاجر المتجول) مغادرة المدينة الأولى ، وزيارة المدن 2،1،3..n مرة واحدة بترتيب غير معروف ، والعودة إلى المدينة الأولى. المسافات بين المدن معروفة. ما هو الترتيب الذي يجب اجتيازه المدن بحيث يكون المسار المغلق (جولة) البائع المتجول هو الأقصر؟

طريقة لحل مشكلة البائع المتجول

خوارزمية الجشع "اذهب إلى أقرب مدينة (لم تدخلها بعد)."
تسمى هذه الخوارزمية "الجشع" لأنه في الخطوات الأخيرة عليك أن تدفع ثمناً باهظاً مقابل الجشع.
ضع في اعتبارك على سبيل المثال الشبكة في الشكل [شكل التطبيق 3]تمثل المعين الضيق. دع البائع يبدأ من المدينة 1. ستأخذه خوارزمية "اذهب إلى أقرب مدينة" إلى المدينة 2 ، ثم 3 ، ثم 4 ؛ في الخطوة الأخيرة ، سيتعين عليك دفع ثمن الجشع ، والعودة على طول القطر الطويل من المعين. والنتيجة ليست الأقصر ، بل هي الأطول.

مشكلة جسور كونيجسبيرج.

تمت صياغة المهمة على النحو التالي.
تقع مدينة كونيجسبيرج على ضفاف نهر بريجيل وجزيرتين. ارتبطت أجزاء مختلفة من المدينة بسبعة جسور. في أيام الأحد ، كان سكان البلدة يتجولون في أنحاء المدينة. سؤال: هل من الممكن أن تمشي في مثل هذه الطريقة ، بعد مغادرة المنزل ، والعودة ، مرورا مرة واحدة بالضبط فوق كل جسر.
توجد الجسور فوق نهر بريجيل كما في الصورة[الملحق الشكل 1].

ضع في اعتبارك رسمًا بيانيًا يتوافق مع مخطط الجسر [الملحق الشكل 2].

للإجابة على سؤال المشكلة ، يكفي معرفة ما إذا كان الرسم البياني هو أويلر. (يجب أن يحتوي رأس واحد على الأقل على عدد زوجي من الجسور). من المستحيل ، التجول في المدينة ، المرور عبر جميع الجسور مرة واحدة والعودة.

عدة تحديات مثيرة للاهتمام

1. "الطرق".

مهمة 1

كما تتذكر ، الصياد ارواح ميتةزار تشيتشيكوف ملاك الأراضي المشهورين مرة واحدة لكل منهم. زارهم بالترتيب التالي: مانيلوف ، كوروبوتشكا ، نوزدريف ، سوباكيفيتش ، بليوشكين ، تينتنيكوف ، الجنرال بيتريشوف ، بيتوخ ، كونستانزولغو ، العقيد كوشاريف. تم العثور على رسم تخطيطي رسمه تشيتشيكوف الترتيب المتبادلالعقارات والطرق الريفية التي تربطهم. حدد أي ملكية تعود لمن ، إذا لم يمر شيشيكوف بأي من الطرق أكثر من مرة [الملحق الشكل 4].

المحلول:

وفقًا لخارطة الطريق ، يمكن ملاحظة أن تشيتشيكوف بدأ رحلته مع ملكية E ، وانتهت بحوزة O. لاحظنا أن طريقين فقط يؤديان إلى العقارات B و C ، لذلك اضطر Chichikov للقيادة على طول هذه الطرق. دعنا نميزهم بخطوط غامقة. تم تحديد مقاطع المسار المار عبر A: AC و AB. لم يسافر تشيتشيكوف على الطرق AE و AK و AM. دعونا نشطبها. دعونا نحتفل بخط سميك ED ؛ شطب DK. اشطب MO و MN ؛ علامة بخط غامق MF ؛ شطب FO ؛ نحدد FH و NK و KO بخط سميك. دعونا نجد الطريق الوحيد الممكن في ظل هذه الحالة. ونحصل على: الحوزة E - تنتمي إلى Manilov ، D - Korobochka ، C - Nozdrev ، A - Sobakevich ، V - Plyushkin ، M - Tentetnikov ، F - Betrishchev ، N - Petukh ، K - Konstanzholgo ، O - Koshkarev [شكل التطبيق 5].

المهمة 2

يوضح الشكل خريطة المنطقة [الملحق الشكل 6].

يمكنك فقط التحرك في اتجاه الأسهم. لا يمكن زيارة كل نقطة أكثر من مرة. ما هو عدد الطرق التي يمكنك الانتقال بها من النقطة 1 إلى النقطة 9؟ أي طريق هو الأقصر وأيها هو الأطول.

المحلول:

"قسِّم" المخطط بالتتابع إلى شجرة ، بدءًا من الرأس 1 [شكل التطبيق 7]. دعنا نحصل على شجرة. رقم الطرق الممكنةالضربات من 1 إلى 9 تساوي عدد رؤوس الشجرة "المعلقة" (هناك 14 منهم). من الواضح أن أقصر طريق هو 1-5-9 ؛ الأطول هو 1-2-3-6-5-7-8-9.

2 "المجموعات ، المواعدة"

مهمة 1

وقد التقى المشاركون في المهرجان الموسيقي وتبادلوا المظاريف مع العناوين. اثبت ذلك:

أ) تم إرسال عدد زوجي من المغلفات في المجموع ؛

ب) كان عدد المشاركين الذين تبادلوا المغلفات عددًا فرديًا من المرات زوجيًا.

الحل: اجعل المشاركين في المهرجان من أ 1 ، أ 2 ، أ 3. . . ، و n هي رؤوس الرسم البياني ، وتربط الحواف أزواج من الرؤوس تمثل الرجال الذين تبادلوا المغلفات [الملحق الشكل 8]

المحلول:

أ) درجة كل رأس A i تبين عدد المغلفات التي قدمها المشارك A لأصدقائه. الرقم الإجماليالمغلفات المنقولة N تساوي مجموع درجات جميع رؤوس الرسم البياني N = الخطوة. 1 + خطوة. أ 2 +. . . + خطوة. و n -1 + خطوة. و n ، N = 2p ، حيث p هو عدد حواف الرسم البياني ، أي N هو زوجي. لذلك ، تم إرسال عدد زوجي من المغلفات ؛

ب) في المساواة N = الخطوة. 1 + خطوة. أ 2 +. . . + خطوة. و n -1 + خطوة. و n يجب أن يكون مجموع الحدود الفردية زوجيًا ، ويمكن أن يكون هذا فقط إذا كان عدد الحدود الفردية زوجيًا. وهذا يعني أن عدد المشاركين الذين تبادلوا المغلفات عددًا فرديًا من المرات هو عدد زوجي.

المهمة 2

بمجرد موافقة Andrei و Boris و Volodya و Dasha و Galya على الذهاب إلى السينما في المساء. قرروا الاتفاق على اختيار السينما والدورة عبر الهاتف. كما تقرر أنه إذا لم يكن من الممكن الاتصال بشخص ما ، فسيتم إلغاء الرحلة إلى السينما. في المساء ، لم يكن الجميع قد تجمعوا في السينما ، وبالتالي توقفت زيارة السينما. في اليوم التالي ، بدأوا في معرفة من الذي اتصل بمن. اتضح أن أندري دعا بوريس وفولوديا ، فولوديا دعا بوريس وداشا ، بوريس يُدعى أندري وداشا ، داشا يُدعى أندري وفولوديا ، وغاليا يُدعى أندري ، فولوديا وبوريس. من الذي لم يتمكن من الاتصال وبالتالي لم يحضر الاجتماع؟

المحلول:

لنرسم خمس نقاط ونعينها بالأحرف A ، B ، C ، D ، E. هذه هي الأحرف الأولى من الأسماء. دعونا نربط تلك النقاط التي تتوافق مع أسماء الأشخاص الذين اتصلوا ببعضهم البعض.

[شكل التطبيق 9]

يتضح من الصورة أن كل من الرجال - أندريه وبوريس وفولوديا - اتصلوا بأي شخص آخر. لهذا جاء هؤلاء الرجال إلى السينما. لكن Galya و Dasha فشلا في الاتصال ببعضهما البعض (النقطتان D و D غير متصلتين بقطعة) وبالتالي ، وفقًا للاتفاقية ، لم يأتيا إلى السينما.

استخدام الرسوم البيانية في مجالات مختلفة من حياة الناس

بالإضافة إلى الأمثلة المقدمة ، تُستخدم الرسوم البيانية على نطاق واسع في البناء والهندسة الكهربائية والإدارة واللوجستيات والجغرافيا والهندسة الميكانيكية وعلم الاجتماع والبرمجة وأتمتة العمليات والصناعات التكنولوجية وعلم النفس والإعلان. لذلك ، مما سبق ، فإن القيمة العملية لنظرية الرسم البياني تتبع بشكل لا يقبل الجدل ، وكان الدليل على ذلك هو الهدف من هذه الدراسة.

في أي مجال من مجالات العلوم والتكنولوجيا ، تلتقي بالرسوم البيانية. الرسوم البيانية هي كائنات رياضية رائعة يمكنك من خلالها حل المشكلات الرياضية والاقتصادية والمنطقية ، والألغاز المختلفة وتبسيط شروط المشكلات في الفيزياء والكيمياء والإلكترونيات والأتمتة. من الملائم صياغة العديد من الحقائق الرياضية بلغة الرسوم البيانية. تعد نظرية الرسم البياني جزءًا من العديد من العلوم. تعتبر نظرية الرسم البياني من أجمل النظريات الرياضية البصرية. في الآونة الأخيرة ، وجدت نظرية الرسم البياني المزيد والمزيد من التطبيقات في القضايا التطبيقية. ظهرت حتى كيمياء الكمبيوتر - وهو مجال حديث نسبيًا في الكيمياء يعتمد على تطبيق نظرية الرسم البياني.

الرسوم البيانية الجزيئية، المستخدمة في الكيمياء الفراغية والطوبولوجيا الهيكلية ، وكيمياء العناقيد ، والبوليمرات ، وما إلى ذلك ، هي رسوم بيانية غير موجهة تعرض بنية الجزيئات [شكل التطبيق 10]. تتوافق رؤوس وأطراف هذه الرسوم البيانية مع الذرات المقابلة والروابط الكيميائية بينها.

الرسوم البيانية الجزيئية والأشجار: [شكل التطبيق 10]أ ، ب - تتابع الرسوم البيانية. الإيثيلين والفورمالديهايد. في مول. ايزومرات البنتان (الأشجار 4 ، 5 متشابهة للشجرة 2).

في الكيمياء الفراغية للكائنات الحية ، أكثر من غيرها غالبًا ما تستخدم الأشجار الجزيئية - الأشجار الرئيسية للرسوم البيانية الجزيئية ، والتي تحتوي فقط على جميع الرؤوس المقابلة لذرات الكربون. تسمح لك الأشجار وإنشاء تماثلها بتحديد الرصيف. الهياكل والعثور عليها الرقم الإجماليايزومرات الألكانات والألكينات والألكينات

شبكات البروتين

شبكات البروتين - مجموعات من البروتينات المتفاعلة جسديًا والتي تعمل في خلية بشكل مشترك وبطريقة منسقة ، وتتحكم في العمليات المترابطة التي تحدث في الجسم [شكل التطبيق. أحد عشر].

الرسم البياني للنظام الهرميتسمى الشجرة. سمة مميزةمن الشجرة أن هناك مسارًا واحدًا فقط بين أي رأسين من رؤوسها. لا تحتوي الشجرة على دورات وحلقات.

عادة ما تمثل الشجرة نظام هرمي، يتم تخصيص رأس رئيسي واحد يسمى جذر الشجرة. كل رأس من الشجرة (باستثناء الجذر) له سلف واحد فقط - الكائن المعين من قبله ينتمي إلى فئة واحدة من المستوى الأعلى. يمكن لأي رأس من الشجرة أن يولد العديد من المتحدرين - الرؤوس المقابلة لفئات المستوى الأدنى.

لكل زوج من رؤوس الأشجار ، هناك مسار فريد يربط بينهما. تُستخدم هذه الخاصية عند البحث عن جميع الأسلاف ، على سبيل المثال ، في السلالة الذكورية ، لأي شخص يتم تقديم شجرة عائلته في شكل شجرة عائلة ، وهي "شجرة" بمعنى نظرية الرسم البياني أيضًا.

مثال على شجرة عائلتي [شكل الملحق 12].

مثال آخر. يوضح الشكل شجرة العائلة التوراتية [الملحق الشكل 13].

حل المشاكل

1. مهمة النقل. يجب ألا تكون هناك قاعدة بالمواد الخام في مدينة كراسنودار ، والتي يجب زراعتها في مدن كريمسك ، وتيمريوك ، وسلافيانسك أون كوبان ، وتيماشيفسك في جولة واحدة ، مع قضاء أقل وقت ممكن والوقود قدر الإمكان والعودة مرة أخرى إلى كراسنودار.

المحلول:

أولاً ، لنقم بإنشاء رسم بياني لجميع المسارات الممكنة. [شكل التطبيق 14]مع مراعاة الطرق الحقيقية بين هذه المستوطنات والمسافة بينها. لحل هذه المشكلة ، علينا إنشاء رسم بياني آخر ، شجرة [شكل التطبيق 15].

لتسهيل الحل ، نشير إلى المدن ذات الأرقام: Krasnodar - 1 ، Krymsk - 2 ، Temryuk - 3 ، Slavyansk - 4 ، Timashevsk - 5.

نتج عن ذلك 24 حلاً ، لكننا نحتاج فقط إلى أقصر الطرق. من بين جميع الحلول ، تم استيفاء حلين فقط ، وهما 350 كم.

وبالمثل ، فمن الممكن ، وأعتقد أنه من الضروري حساب النقل الحقيقي من منطقة إلى أخرى.

مهمة منطقية لنقل الدم.يوجد 8 لترات من الماء في دلو ، وهناك قدران بسعة 5 و 3 لترات. يُطلب سكب 4 لترات من الماء في قدر سعة خمسة لترات وترك 4 لترات في دلو ، أي صب الماء بالتساوي في دلو وإناء كبير.

المحلول:

يمكن وصف الوضع في أي لحظة بثلاثة أرقام [الملحق الشكل 16].

نتيجة لذلك ، حصلنا على حلين: أحدهما في 7 حركات والآخر في 8 حركات.

خاتمة

لذا ، لكي تتعلم كيفية حل المشكلات ، عليك أن تفهم ماهيتها ، وكيف يتم ترتيبها ، ومن أين الأجزاء المكونةإنها تتكون من الأدوات المستخدمة في حل المشكلات.

حل المشكلات العملية بمساعدة نظرية الرسم البياني ، أصبح من الواضح أنه في كل خطوة ، في كل مرحلة من مراحل حلها ، من الضروري تطبيق الإبداع.

منذ البداية ، في المرحلة الأولى ، تكمن في حقيقة أنك بحاجة إلى أن تكون قادرًا على تحليل حالة المشكلة وتشفيرها. المرحلة الثانية عبارة عن تدوين تخطيطي ، والذي يتكون من التمثيل الهندسي للرسوم البيانية ، وفي هذه المرحلة يكون عنصر الإبداع مهمًا للغاية لأنه ليس من السهل العثور على تطابق بين عناصر الشرط والعناصر المقابلة للرسم البياني .

عند حل مشكلة النقل أو مشكلة تجميع شجرة العائلة ، استنتجت أن طريقة الرسم البياني مثيرة للاهتمام وجميلة ومرئية بالتأكيد.

كنت مقتنعًا بأن الرسوم البيانية تستخدم على نطاق واسع في الاقتصاد والإدارة والتكنولوجيا. تُستخدم نظرية الرسم البياني أيضًا في البرمجة ، ولم تتم مناقشة هذا في هذه الورقة ، لكنني أعتقد أن هذه مجرد مسألة وقت.

في هذا العمل العلمي ، يتم النظر في الرسوم البيانية الرياضية ، ومجالات تطبيقها ، ويتم حل العديد من المشكلات بمساعدة الرسوم البيانية. تعد معرفة أساسيات نظرية الرسم البياني ضرورية في مختلف المجالات المتعلقة بإدارة الإنتاج والأعمال (على سبيل المثال ، مخطط شبكة البناء وجداول تسليم البريد). بالإضافة إلى ذلك ، أثناء عملي في عمل علمي ، أتقنت العمل على الكمبيوتر في النص محرر WORD. وهكذا ، المهام عمل علميمنجز.

لذلك ، مما سبق ، فإن القيمة العملية لنظرية الرسم البياني تتبع بشكل لا يقبل الجدل ، والتي كان الدليل عليها هو الهدف من هذا العمل.

المؤلفات

بيرج ك.نظرية الرسم البياني وتطبيقاتها. -M: IIL ، 1962.

Kemeny J.، Snell J.، Thompson J.مقدمة في الرياضيات المحدودة. -M: IIL ، 1963.

خام O.الرسوم البيانية وتطبيقها. -M: مير ، 1965.

هراري ف.نظرية الرسم البياني. -م: مير ، 1973.

زيكوف أ.نظرية الرسوم البيانية المحدودة. - نوفوسيبيرسك: نوكا ، 1969.

بيريزينا ل.الرسوم البيانية وتطبيقها. -م: التربية 1979. -144 ص.

"مجلة سوروس التعليمية" رقم 11 1996 (مقالة "رسوم بيانية مسطحة") ؛

Gardner M. "الترفيه الرياضي" ، M. "Mir" ، 1972 (الفصل 35) ؛

Olekhnik S. N.، Nesterenko Yu. V.، Potapov M. K. "Old Entertainment problems"، M. "Nauka"، 1988 (part 2، section 8؛ Appendix 4)؛

الملحق

أرز. 6

أرز. 7

أرز. 8

تطبيق

الملحق

أرز. أربعة عشرة

تطبيق

الملحق

تجد نظرية الرسم البياني تطبيقًا ، على سبيل المثال ، في أنظمة المعلومات الجغرافية (GIS). تعتبر المنازل والهياكل والأرباع القائمة أو المصممة حديثًا بمثابة رؤوس ، والطرق التي تربطها ، والشبكات الهندسية ، وخطوط الطاقة ، وما إلى ذلك - كحواف. يسمح استخدام الحسابات المختلفة التي تم إجراؤها على مثل هذا الرسم البياني ، على سبيل المثال ، بالعثور على أقصر منعطف أو أقرب متجر بقالة ، لتخطيط أفضل طريق.

تحتوي نظرية الرسم البياني على عدد كبير من المشكلات التي لم يتم حلها والفرضيات غير المثبتة.

المجالات الرئيسية لتطبيق نظرية الرسم البياني:

في الكيمياء (لوصف الهياكل وطرق التفاعلات المعقدة ، يمكن أيضًا تفسير قاعدة الطور على أنها مشكلة في نظرية الرسم البياني) ؛ كيمياء الكمبيوتر هي مجال كيميائي حديث العهد نسبيًا يعتمد على تطبيق نظرية الرسم البياني. نظرية الرسم البياني هي الأساس الرياضي للمعلومات الكيميائية. تتيح نظرية الرسم البياني إمكانية التحديد الدقيق لعدد الأيزومرات الممكنة نظريًا للهيدروكربونات والمركبات العضوية الأخرى ؛

في علوم الكمبيوتر والبرمجة (مخطط الرسم البياني للخوارزمية) ؛

في أنظمة الاتصالات والنقل. على وجه الخصوص ، لتوجيه البيانات على الإنترنت ؛

في الاقتصاد؛

في اللوجستيات

في هندسة الدوائر (طوبولوجيا الترابط بين العناصر على لوحة الدوائر المطبوعة أو الدائرة المصغرة هي رسم بياني أو رسم بياني).

هناك نوع خاص من الرسم البياني ، خشب.خشبهو رسم بياني غير دوري متصل. الاتصال يعني وجود مسارات بين أي زوج من الرؤوس ، وتعني الحدة عدم وجود دورات وحقيقة أن هناك مسارًا واحدًا فقط بين أزواج الرؤوس. على ال الشكل 1.3مقدم شجرة ثنائية.

شجرة ثنائيةهي بنية بيانات شبيهة بالشجرة تحتوي كل عقدة فيها على اثنين على الأكثر أحفاد(الأطفال). عادة ما يسمى الأول عقدة الأمويتم تسمية الأطفال يساريو ورثة الحق.

تمثيل المصفوفة من الرسوم البيانية. مصفوفة الحوادث.

يتطلب تطوير الأساليب الحسابية لتحليل خصائص الرسوم البيانية طرقًا معينة لوصف الرسوم البيانية الأكثر ملاءمة للحسابات العملية ، بما في ذلك تلك التي تستخدم أجهزة الكمبيوتر. ضع في اعتبارك الطرق الثلاث الأكثر شيوعًا لتمثيل الرسوم البيانية.

افترض أن جميع الرؤوس وجميع حواف الرسم البياني غير المباشر أو جميع الرؤوس وجميع الأقواس (بما في ذلك الحلقات) للرسم البياني الموجه مرقمة بدءًا من واحد. يمكن تمثيل الرسم البياني (غير المباشر أو الموجه) كمصفوفة من النوع ، حيث يوجد عدد الرؤوس ، وعدد الأضلاع (أو الأقواس). بالنسبة للرسم البياني غير المباشر ، يتم إعطاء عناصر هذه المصفوفة على النحو التالي:

بالنسبة للرسم البياني الموجه ، يتم إعطاء عناصر المصفوفة على النحو التالي:

يسمى نوع المصفوفة المعرفة بهذه الطريقة مصفوفة الحادث.

مثال على الحصول على مصفوفة الوقوع. للرسم البياني الموضح أدناه ( أرز. 2.1 أالشكل 2.1 ب).

الشكل 2.1 أ الشكل. 2.1 ب

مصفوفة الجوار.

على الرغم من حقيقة أن تمثيل الرسم البياني في شكل مصفوفة الوقوع يلعب دورًا مهمًا للغاية في الدراسات النظرية ، إلا أن هذه الطريقة غير فعالة في الممارسة العملية. بادئ ذي بدء ، لا يوجد سوى عنصرين غير صفريين في المصفوفة في كل عمود ، مما يجعل هذه الطريقة في تمثيل الرسم البياني غير اقتصادية مع وجود عدد كبير من الرؤوس. بالإضافة إلى ذلك ، فإن حل المشكلات العملية باستخدام مصفوفة الوقوع عملية شاقة للغاية.

دعونا نقدر ، على سبيل المثال ، الوقت المستغرق في حل مثل هذه المشكلة البسيطة في رسم بياني موجه باستخدام مصفوفة الوقوع: بالنسبة إلى قمة معينة ، ابحث عن "بيئتها" - مجموعة الخلف ومجموعة أسلاف الرأس ، أي مجموعة كل الرؤوس التي يمكن الوصول إليها مباشرة ، ومجموعة كل الرؤوس التي يمكن الوصول إليها مباشرة منها.

لحل هذه المشكلة ، في مصفوفة الوقوع للرسم البياني الموجه ، تحتاج إلى متابعة الصف مع الرقم حتى يظهر عنصر غير صفري (+1 أو -1). إذا تم العثور على +1 ، في العمود المقابل ، تحتاج إلى العثور على السطر الذي كتب فيه الرقم -1. يعطي رقم السطر الذي يحتوي على هذا الرقم رقم الرأس الذي يمكن الوصول إليه مباشرة من الرأس المحدد. إذا تم العثور على -1 ، في العمود تحتاج إلى العثور على السطر الذي كتب فيه 1 ، والحصول على رقم الرأس الذي يمكن الوصول إليه مباشرة رأس معين. للحصول على "البيئة" بأكملها ، تحتاج إلى إجراء البحث المحدد لجميع العناصر غير الصفرية للصف k-th. الإجراء الأكثر استهلاكا للوقت هو العثور على عنصر غير فارغ في عمود. عدد إجراءات البحث هذه يساوي درجة الرأس. في هذه الحالة ، سنقول أن تعقيد الخوارزمية لتحليل بيئة الرأس هو (بترتيب).

يمكن ملاحظة أن إيجاد "البيئة" لجميع الرؤوس سيستغرق وقتًا وفقًا لترتيب حاصل ضرب عدد رؤوس الرسم البياني الموجه مضروبًا في مجموع درجات جميع الرؤوس ، والتي يمكن إثبات أنها متناسبة مع عدد أقواس الرسم البياني الموجه. وبالتالي ، فإن تعقيد خوارزمية البحث عن "البيئة" هو ، أي يستغرق البحث وقتًا حسب ترتيب حاصل ضرب عدد الرؤوس وعدد الأقواس.

هيكل مصفوفة أكثر كفاءة يمثل الرسم البياني هو مصفوفة تجاور قمة الرأس، أو مصفوفة منطقيةرسم بياني. هذه مصفوفة مربعة بالترتيب ن، والتي يتم تحديد عناصرها على النحو التالي:

لرسم بياني غير موجه:

لرسم بياني موجه:

للرسم البياني الموضح أدناه ( أرز. 2.2 أ) ستكون مصفوفة الوقوع هي المصفوفة الممثلة في ( الشكل 2.2 ب).

تُعزى بداية نظرية الرسم البياني بالإجماع إلى عام 1736 ، عندما حل إل أويلر مشكلة جسور كونيغسبير ، التي كانت شائعة في ذلك الوقت. ومع ذلك ، ظلت هذه النتيجة هي النتيجة الوحيدة لنظرية الرسم البياني لأكثر من مائة عام. فقط في منتصف القرن التاسع عشر ، طور المهندس الكهربائي ج. كيرشوف نظرية الأشجار لدراستها الدوائر الكهربائية، وعالم الرياضيات أ. كايلي ، فيما يتعلق بوصف بنية الهيدروكربونات ، وحل المشكلات التعدادية لثلاثة أنواع من الأشجار.

ولدت أثناء حل الألغاز والألعاب المسلية (مشاكل حول حصان الشطرنج ، والملكات ، " رحلة حول العالم"، مشاكل حول حفلات الزفاف والحريم ، وما إلى ذلك) ، أصبحت نظرية الرسم البياني الآن أداة بسيطة وسهلة الوصول وقوية لحل الأسئلة المتعلقة بمجموعة واسعة من المشاكل. الرسوم البيانية موجودة في كل مكان حرفيًا. في شكل رسوم بيانية ، على سبيل المثال ، يمكن للمرء أن يفسر مخططات الطرق والدوائر الكهربائية ، والخرائط الجغرافية ، وجزيئات المركبات الكيميائية ، والصلات بين الناس ومجموعات الناس. على مدى العقود الأربعة الماضية ، أصبحت نظرية الرسم البياني واحدة من أسرع فروع الرياضيات تطورًا. هذا مدفوع بمتطلبات مجال التطبيق الآخذ في التوسع بسرعة. يتم استخدامه في تصميم الدوائر المتكاملة ودوائر التحكم ، في دراسة الأوتوماتا ، والدوائر المنطقية ، ومخططات تدفق البرنامج ، في الاقتصاد والإحصاء ، والكيمياء والبيولوجيا ، في نظرية الجدولة. إلى حد كبير ، من خلال نظرية الرسوم البيانية ، يتم الآن تغلغل الأساليب الرياضية في العلوم والتكنولوجيا.

في هذه الورقة ، لا نأخذ في الاعتبار المشكلات الخاصة بنظرية الرسم البياني ، ولكن كيف يتم استخدامها دورة مدرسيةالهندسة.

لذلك ، ترجع أهمية موضوع البحث ، من ناحية ، إلى شعبية الرسوم البيانية وطرق البحث ذات الصلة ، والتي تتخلل تقريبًا جميع الرياضيات الحديثة على مستويات مختلفة ، ومن ناحية أخرى ، نظام متكامل لتنفيذه في لم يتم تطوير مسار الهندسة.

الغرض من الدراسة هو دراسة استخدام الرسوم البيانية في مقرر الهندسة المدرسية.

الكائن هو عملية تدريس الهندسة.

الموضوع - الأنشطة الصفية واللامنهجية

المهام: 1) تحديد جوهر ومحتوى استخدام الرسوم البيانية في مقرر الهندسة المدرسية.

2) لتطوير PMK لإجراء دروس الهندسة في الصفوف 7-9.

الموضوع الرئيسي هو بناء نموذج الرسم البياني لإثبات النظريات الهندسية.

اساس نظرى:

1. تم تطوير نظرية الرسوم البيانية ، التي نشأت في عام 1736 (ليونارد أويلر (1708-1783) بسرعة ، ولا تزال ذات صلة حتى الآن ، لأنه في الحياة اليوميةيتم استخدام الرسوم التوضيحية الرسومية والتمثيلات الهندسية وغيرها من تقنيات وطرق التخيل بشكل متزايد.

1. تجد نظرية الرسم البياني تطبيقًا في مختلف مجالات الرياضيات الحديثة وتطبيقاتها العديدة (ليباتوف إي.بي.)

2. تُستخدم نظرية الرسم البياني في مجالات الرياضيات مثل المنطق الرياضي والتوافقية وما إلى ذلك.

تكمن الأهمية النظرية للعمل في:

تحديد مجالات تطبيق نظرية الرسم البياني ؛

استخدام نظرية الرسم البياني لدراسة المسائل والنظريات الهندسية.

تكمن الأهمية العملية للعمل في استخدام الرسوم البيانية في براهين النظريات الهندسية وفي حل المشكلات.

ونتيجة لهذا العمل ، تم إنشاء ما يلي:

برمجيات ومجمع منهجي لإجراء دروس الهندسة في الصفوف 7-9.

أصعب شيء في إيجاد حل لمشكلة ما هو إنشاء سلسلة من النتائج المنطقية التي تؤدي إلى بيان يمكن إثباته. من أجل التفكير المنطقي بكفاءة ، من الضروري تطوير مهارات هذا التفكير ، والتي من شأنها أن تساعد في بناء حقائق هندسية متباينة في علاقات منطقية.

تلعب الأشكال دورًا خاصًا في تنمية مهارات ثقافة التفكير. جاري الكتابةالطلاب. تعد أشكال العمل المكتوبة من أهم الأنشطة التي تشكل مهارات ثابتة في التفكير المنطقي عند إثبات النظريات وحل المشكلات. إن شكل كتابة شروط المشكلة والاختصارات المعقولة والتدوين في الحسابات وإثباتات المشاكل منضبط التفكير ويعزز الرؤية الهندسية. كما تعلم ، فإن الرؤية تؤدي إلى التفكير. تبرز المشكلة: كيفية إنشاء روابط منطقية بين الحقائق الهندسية المتباينة وكيفية ترتيبها في شكل كل واحد. لمعرفة التقدم المحرز في إثبات النظريات وحل المشكلات ، تسمح طريقة مخططات الرسم البياني ، مما يجعل الإثبات أكثر وضوحًا ويسمح لك بإيجاز ودقة براهين النظريات وحل المشكلات.

لهذا ، يتم استخدام الرسم البياني الشجري.

يتم عرض رؤوس "الشجرة" (حالة نظرية أو مشكلة وسلسلة من الوصلات المنطقية) كمستطيلات مع المعلومات الموضوعة فيها ، والتي يتم ربطها بعد ذلك بواسطة الأسهم. تحتوي نهاية مخطط الرسم البياني على التأكيد المراد إثباته. يعتبر الشكل الموصوف لإثبات النظريات وحل المشكلات مفيدًا وملائمًا للطلاب ، لأنه يجعل من الممكن التمييز بسهولة بين المراحل الرئيسية لإثبات النظرية وحل مشكلة ما.

جزء البحث.

القسم 1. دراسة تاريخ ظهور نظرية الرسم البياني.

"بمجرد أن عرضت علي مشكلة جزيرة تقع في مدينة كونيغسبيرج ومحاطة بنهر يتم إلقاء سبعة جسور عبره. والسؤال هو ما إذا كان بإمكان أي شخص تجاوزها باستمرار ، ويمر مرة واحدة فقط عبر كل جسر. حتى الآن لم يفعل تمكنت من القيام بذلك ، لكن لم يثبت أحد أنه مستحيل ، إلا أن هذا السؤال ، على الرغم من كونه مبتذلاً ، بدا لي أنه يستحق الاهتمام لأنه لا الهندسة ولا الجبر ولا الفن الاندماجي كافيين لحلها. بعد الكثير من المداولات ، لقد وجدت قاعدة سهلة ، تستند إلى دليل مقنع تمامًا ، وبمساعدتها ، في جميع المشكلات من هذا النوع ، يمكن للمرء أن يقرر على الفور ما إذا كان يمكن إنشاء مثل هذه الدائرة من خلال أي رقم والجسور الموجودة بشكل تعسفي أم لا. يمكن تمثيلها في الشكل التالي ، حيث تشير A إلى جزيرة ، و B و C و D هي أجزاء من القارة ، مفصولة عن بعضها البعض بفروع النهر. يتم تمييز الجسور بالأحرف أ ، ب ، ج ، د ، هـ ، و ، ز ".

كتب أويلر بخصوص الطريقة التي اكتشفها لحل مشاكل من هذا النوع

"السؤال هو تحديد ما إذا كان من الممكن الالتفاف على كل هذه الجسور السبعة ، مروراً بكل منها مرة واحدة فقط أم لا. تؤدي قاعدتي إلى الحل التالي لهذا السؤال. أولاً وقبل كل شيء ، تحتاج إلى إلقاء نظرة على عدد الأقسام مفصولة بالماء - مثل ، التي ليس لها انتقال آخر من واحد إلى آخر ، إلا من خلال الجسر. في هذا المثال ، هناك أربعة أقسام من هذا القبيل - أ ، ب ، ج ، د. بعد ذلك ، تحتاج إلى التمييز ما إذا كان عدد تكون الجسور المؤدية إلى هذه الأقسام الفردية زوجية أو فردية. لذلك ، في حالتنا ، تؤدي خمسة جسور إلى القسم "أ" وثلاثة جسور للباقي ، أي أن عدد الجسور المؤدية إلى الأقسام الفردية فردي ، وهذا يكفي بالفعل لـ حل المشكلة عندما يتم تحديد ذلك ، نطبق القاعدة التالية: إذا كان عدد الجسور المؤدية إلى كل قسم فردي متساويًا ، فسيكون الانعطاف المعني ممكنًا ، وفي نفس الوقت سيكون من الممكن بدء هذا الانعطاف من أي قسم. سيكون غريبًا ، لأن قسمًا واحدًا فقط يكون فرديًا لا يمكن ، حتى ذلك الحين يمكن إجراء الانتقال ، كما هو موصوف ، ولكن يجب بالتأكيد أخذ بداية الالتفاف من أحد هذين القسمين اللذين يؤدي إليهما عدد فردي من الجسور. أخيرًا ، إذا كان هناك أكثر من قسمين يؤدي إليهما عدد فردي من الجسور ، فإن مثل هذه الحركة تكون مستحيلة بشكل عام ؛ إذا كان من الممكن ذكر مشاكل أخرى أكثر خطورة هنا ، فقد تكون هذه الطريقة أكثر فائدة ولا ينبغي إهمالها .

يمكن العثور على الأساس المنطقي للقاعدة المذكورة أعلاه في رسالة من L.Euler إلى صديقه Eler بتاريخ 3 أبريل من نفس العام. سوف نعيد سرد مقتطف من هذه الرسالة أدناه.

كتب عالم الرياضيات أن الانتقال ممكن إذا لم يكن هناك أكثر من منطقتين في قسم التفرع من النهر ، والذي يؤدي إليه عدد فردي من الجسور. لتسهيل تخيل ذلك ، سنمحو الجسور التي تم تمريرها بالفعل في الشكل. من السهل التحقق من أننا إذا بدأنا في التحرك وفقًا لقواعد أويلر ، وعبرنا جسرًا واحدًا وقمنا بمحوه ، فسيظهر الشكل مقطعًا لا يوجد فيه أكثر من منطقتين يؤدي إليهما عدد فردي من الجسور ، وفي وجود مناطق بها عدد فردي من الجسور سنكون موجودين في إحداها. مع الاستمرار في المضي قدمًا ، سنمر عبر جميع الجسور مرة واحدة.

تاريخ جسور مدينة كونيغسبيرغ له استمرار حديث.

المشكلة توجد سبع جزر على البحيرة مترابطة كما هو موضح في الشكل 2. أي جزيرة يجب أن يأخذ القارب المسافرين إليها حتى يتمكنوا من المرور عبر كل جسر ومرة واحدة فقط؟ لماذا لا يمكن اصطحاب المسافرين إلى الجزيرة "أ"؟

المحلول. نظرًا لأن هذه المشكلة تشبه مشكلة جسر كونيجسبيرج ، فسنستخدم أيضًا قاعدة أويلر لحلها. نتيجة لذلك ، حصلنا على الإجابة التالية: يجب أن يأخذ القارب المسافرين إلى الجزيرة E أو F حتى يتمكنوا من المرور فوق كل جسر مرة واحدة. تشير قاعدة أويلر نفسها إلى أن الانعطاف المطلوب مستحيل إذا بدأ من الجزيرة أ.

في وقت لاحق ، عمل كونيغ (1774-1833) وهاملتون (1805-1865) على الرسوم البيانية بين علماء الرياضيات المعاصرين - ك.

تاريخيا ، ولدت نظرية الرسم البياني منذ أكثر من مائتي عام في سياق حل الألغاز. لفترة طويلة جدًا ، كانت بعيدة عن الاتجاهات الرئيسية لأبحاث العلماء ، وكانت في عالم الرياضيات في منصب سندريلا ، التي تم الكشف عن مواهبها بالكامل فقط عندما كانت في مركز الاهتمام العام.

ظهر أول عمل عن نظرية الرسم البياني لعالم الرياضيات السويسري الشهير L. التوافقية ، التي تربطها بها أوثق العلاقات ، زادت بشكل كبير. بدأ استخدام الرسوم البيانية في بناء مخططات الدوائر الكهربائية والدوائر الجزيئية. كتخصص رياضي منفصل ، تم تقديم نظرية الرسم البياني لأول مرة في عمل عالم الرياضيات المجري كونيج في الثلاثينيات من القرن العشرين.

في الآونة الأخيرة ، تتخلل الرسوم البيانية وطرق البحث ذات الصلة بشكل عضوي جميع الرياضيات الحديثة تقريبًا على مستويات مختلفة. تعتبر نظرية الرسم البياني أحد فروع الطوبولوجيا ؛ كما أنه يرتبط ارتباطًا مباشرًا بالجبر ونظرية الأعداد. تُستخدم الرسوم البيانية بشكل فعال في نظرية التخطيط والإدارة ، ونظرية الجدولة ، وعلم الاجتماع ، واللغويات الرياضية ، والاقتصاد ، وعلم الأحياء ، والطب ، والجغرافيا. تستخدم الرسوم البيانية على نطاق واسع في مجالات مثل البرمجة ، ونظرية الأوتوماتيكية المحدودة ، والإلكترونيات ، في حل المشكلات الاحتمالية والتوافقية ، أقصر مسافة، إلخ. تعد المرح والألغاز الرياضية أيضًا جزءًا من نظرية الرسم البياني. تتطور نظرية الرسم البياني بسرعة ، وتجد تطبيقات جديدة.

القسم 2. الأنواع الرئيسية والمفاهيم وهيكل الرسوم البيانية.

نظرية الرسم البياني هي تخصص رياضي تم إنشاؤه بجهود علماء الرياضيات ، لذلك يتضمن عرضها التعاريف الدقيقة اللازمة.

الرسم البياني عبارة عن مجموعة من عدد محدود من النقاط ، تسمى رؤوس الرسم البياني ، وتربط زوجيًا بعض رؤوس الخطوط هذه ، تسمى حواف أو أقواس الرسم البياني.

رقم اسم الرسم البياني التعريف الشكل مثال على استخدام هذا النوع من الرسم البياني

1 رسم بياني صفري رؤوس الرسم البياني التي لا تنتمي المشكلة: أركادي ، بوريس. تصافح فلاديمير وغريغوري وديمتري في الاجتماع مع عدم وجود أحد ، وصافح كل واحد مع كل واحد مرة واحدة. كم عدد الحواف في المجموع تسمى معزولة. تم المصافحة؟ الموقف المقابل للحظة التي لم تحدث فيها المصافحة بعد هو مخطط منقط يظهر في الشكل.

يسمى الرسم البياني الذي يتكون فقط من الرؤوس المعزولة بالرسم البياني الفارغ.

تدوين: O "- رسم بياني برؤوس وبدون حواف

2 رسوم بيانية كاملة رسم بياني فيه كل زوج من الرؤوس لاحظ أنه إذا كان الرسم البياني الكامل يحتوي على رؤوس n ، فسيكون عدد الحواف هو كل المصافحة.

تدوين: U "هو رسم بياني يتكون من n 10.

الرؤوس والحواف التي تربط جميع الأزواج الممكنة من هذه الرؤوس. يمكن تمثيل هذا الرسم البياني على أنه n-gon حيث يتم رسم جميع الأقطار

3 رسوم بيانية غير مكتملة الرسوم البيانية التي لم يتم بناء جميعها فيها الحالة التي لم تكتمل فيها جميع المصافحة بعد ، تصافح A و B و A و D و E وتسمى الحواف المحتملة D و C و E.

4 المسار في الرسم البياني. دورة. مسار في الرسم البياني من رأس إلى آخر عند النقطة أ يوجد مرآب كاسح ثلج. وقيل إن سائق السيارة تلقى تعليمات بإزالة الجليد من شوارع الجزء الموضح في الصورة من المدينة. هل يمكن أن يكمل عمله عند التقاطع حيث يقع المرآب ، إذا كان من الممكن أن يمد طريقًا بين هذه الشوارع من قسمه من المدينة على طول كل منها مرة واحدة فقط؟

القمم.

في هذه الحالة ، يجب ألا تحدث حافة المسار أكثر من مرة. الرأس ، من مستحيل ، لأن المسار المغلق الذي يمر عبر جميع حواف الرسم البياني ، والذي يتم وضع المسار على طوله ، يُستدعى لكل حافة مرة واحدة فقط ، إذا كانت درجات جميع رؤوس الرسم البياني متساوية.

بداية المسار ، القمة في نهاية الطريق -

نهاية المسار. الدورة عبارة عن مسار ، في الشكل ، باستخدام رسم بياني ، يظهر رسم تخطيطي للطرق بين المناطق المأهولة بالسكان حيث تتطابق البداية مع النهاية. نقاط بسيطة.

الدورة هي دورة لا تمر ، على سبيل المثال ، من النقطة A (أعلى الرسم البياني) إلى النقطة H يمكن الوصول إليها بمسارات مختلفة: ADGH ، AEH ، AEFCEH ، ABCEH.

من خلال أحد رؤوس الرسم البياني أكثر من واحد ما هو الفرق بين مسار AEH وطريق AEFCEH؟

مرات. حقيقة أنه في الطريق الثاني عند "مفترق الطرق" عند النقطة E قمنا بزيارة مرتين.

هذا المسار أطول من AEH. يمكن الحصول على مسار AEH من الطريق

إذا كانت الدورة تشتمل على جميع الحواف ، فقم "بحذف" مسار FCE من آخر واحد.

الرسم البياني مرة واحدة ، ثم هذه الدورة المسار AEH هو مسار في الرسم البياني ، لكن المسار AEFCEH ليس مسارًا.

يسمى خط أويلر.

الرسوم البيانية المتصلة وغير المتصلة. التعريف 1: هل من الممكن عمل إطار مكعب بحافة طول من سلك طوله 12 dm

يسمى رأسان من الرسم البياني متصلان ، 1 دسم ، دون كسر السلك؟

إذا كان هناك مسار في الرسم البياني ينتهي عند هذه الرؤوس. إذا لم يكن هناك مثل هذا المسار ، فإن القمم تسمى غير متصلة.

نظرًا لأن المسار الذي يمر عبر جميع حواف الرسم البياني ، وعلى طول كل حافة مرة واحدة فقط ، يوجد فقط في الحالات التالية:

1) عندما تكون درجة كل رأس زوجية (المسار مغلق)

2) عندما يكون هناك رأسان فقط بدرجة فردية.

التعريف 2:

يسمى الرسم البياني متصل إذا كان كل زوج من رؤوسه متصلًا.

يسمى الرسم البياني غير متصل إذا كان يحتوي على زوج واحد على الأقل من الرؤوس غير المتصلة.

6 الأشجار الشجرة هي أي رسم بياني متصل ، الملحق رقم 1. شجرة النسب Zholmurzaeva Tomiris.

قمم. يُطلق على الرسم البياني المنفصل المكون فقط من الأشجار اسم الغابة.

7 رسوم بيانية متشابهة. تعطي الرسوم البيانية الموضحة في الشكل نفس المعلومات. تسمى هذه الرسوم البيانية متشابهة (متطابقة).

8 مفهوم الرسم البياني المستوي رسم بياني يمكن تمثيله في مهمة. في ثلاثة منازل مختلفة ، تعيش ثلاث طائرات في جيران تشاجروا مع بعضهم البعض. هناك ثلاثة آبار ليست بعيدة عن مكان تقاطع ضلوعها عن منازلهم. هل من الممكن فقط من عند القمم ، ويسمى كل بيت مسطّح لكل من الآبار. حتى لا يتقاطع اثنان منهم؟

الحل: بعد رسم ثمانية مسارات ، يمكنك التأكد من عدم إمكانية رسم المسار التاسع الذي لا يتقاطع مع أي من المسارات المرسومة مسبقًا.

نقوم ببناء رسم بياني رؤوسه

أ ، ب ، ج ، 1 ، 2 ، 3

تتوافق ظروف المشكلة مع المنازل والآبار ، وسنحاول إثبات أن المسار التاسع - حافة الرسم البياني ، التي لا تتقاطع مع الحواف الأخرى ، لا يمكن رسمها.

حواف مرسومة في الرسم البياني في الشكل

A1 و A2 و A3 و B1 و B2 و VZ (المقابلة للمسارات من المنازل A و B إلى جميع الآبار).

قسم الرسم البياني المركب المستوى إلى ثلاث مناطق: X ، Y ، Z. يقع Vertex B ، اعتمادًا على موقعه على المستوى ، في إحدى هذه المناطق الثلاث. إذا كنت تفكر في كل من ضربات الرأس الثلاثة

B إلى إحدى المناطق X أو Y أو Z ، ثم تأكد من أنه في كل مرة يكون أحد رؤوس الرسم البياني هو 1 أو 2 أو 3

(أحد الآبار) سيكون "غير قابل للوصول" إلى الرأس B (أي أنه لن يكون من الممكن رسم أحد الحواف B1 أو B2 أو B3 التي لن تتقاطع مع الحواف الموجودة بالفعل في الرسم البياني).

سيكون الجواب على سؤال المهمة: "مستحيل!"

الرسوم البيانية الموجهة تسمى حافة الرسم البياني بالحافة الموجهة إذا اعتبر أحد رؤوسه البداية والآخر نهاية هذه الحافة.

يسمى الرسم البياني الذي يتم فيه توجيه جميع الحواف بالرسم البياني الموجه.

لذلك ، فقد نظرت في المفاهيم الأساسية لنظرية الرسم البياني ، والتي بدونها سيكون من المستحيل إثبات النظريات ، وبالتالي حل المشكلات.

استنتاج بشأن العمل المنجز:

تعلمت كيفية هيكلة جميع المواد الإعلامية في جدول.

يساهم تكوين المادة النظرية في التمثيل المرئي لأنواع الرسوم البيانية وتطبيقها ؛

عملت على أمثلة لتطبيق نظرية الرسم البياني في تجميع شجرة عائلتها.

طلب رقم 1.

شجرة علم الوراثة

بناء شجرة عائلة Zholmurzaeva Tomiris.

طريقة الحل.

طريقة رسومية لحل المشكلة.

طريقة رسومية لحل المشكلة هي رسم "شجرة الشروط المنطقية". تعبر "الشجرة" في شكل رسم بسيط عن العلاقة المنطقية بين الأقارب. كل جيل على الشجرة يتوافق مع فرع واحد.

على سبيل المثال ، أخذت شجرة عائلتي.

القسم 3. تطبيق نظرية الرسم البياني.

نحن نلتقي بالرسوم البيانية أكثر مما هو ممكن ، يبدو للوهلة الأولى. يمكن أن تكون أمثلة الرسوم البيانية أي خريطة طريق ، أو دائرة كهربائية ، أو رسم مضلعات ، إلخ. لفترة طويلة ، كان يُعتقد أن نظرية الرسم البياني تُستخدم أساسًا في حل المشكلات المنطقية. عند حل المشكلات المنطقية ، غالبًا ما يكون من الصعب تذكر الشروط العديدة الواردة في المشكلة ، وإنشاء اتصال بينها ، حيث تساعد الرسوم البيانية في حل مثل هذه المشكلات ، مما يجعل من الممكن تصور العلاقة بين بيانات المشكلة. تم النظر إلى نظرية الرسم البياني نفسها كجزء من الهندسة. ومع ذلك ، في القرن العشرين ، تم العثور على تطبيقات واسعة لنظرية الرسم البياني في الاقتصاد ، وعلم الأحياء ، والكيمياء ، والإلكترونيات ، وتخطيط الشبكات ، والتوليفات ، وغيرها من مجالات العلوم والتكنولوجيا. ونتيجة لذلك ، بدأت تتطور بسرعة وتحولت إلى نظرية متفرعة مستقلة ، وتم تبسيط حل العديد من المشكلات الرياضية إذا كان بإمكان المرء استخدام الرسوم البيانية. عرض البيانات في شكل رسم بياني يمنحهم الرؤية. يتم أيضًا تبسيط العديد من الأدلة وتصبح أكثر إقناعًا إذا تم استخدام الرسوم البيانية.

3. 1. تطبيق الرسوم البيانية في مشاكل هندسيةوالنظريات.

بمساعدة الرسوم البيانية ، يمكن للمرء بسهولة إنشاء سلاسل من النتائج المنطقية التي تؤدي إلى بيان يمكن إثباته. اذكر بإيجاز ودقة إثبات النظرية وحل المشكلة.

اثبت ذلك مثلث متساوي الساقينالمنصفات المستمدة من الرؤوس عند القاعدة متساوية.

طرق الحل.

إثبات المشكلة بالاستدلال.

لنفترض أن ABC هو مثلث متساوي الساقين

B1 A1 قاعدة AB والمنصفات AA1 و BB1.

ضع في اعتبارك ∆ABB1 و ∆BAA1. لديهم ∟B1AB =

∟A1BA كزاوية عند قاعدة المثلث متساوي الساقين ∆ABC. ∟ABB1 = ∟A1AB

A B منذ AA1 و BB1 هما منصف الزوايا عند قاعدة مثلث متساوي الساقين. AB هو الجانب المشترك. وسائل

∆ABB1 = ∆BAB1 بطول الجانب وزاويتين متجاورتين له. من المساواة بين المثلثات يتبع المساواة بين الجانبين AA1 و BB1.

إثبات المشكلة باستخدام الرسم البياني.

إثبات: AA = BB

دعونا نستخدم الرسم البياني للتفكير. رؤوس الرسم البياني هي شروط النظرية أو المسألة ومراحل البرهان.

حواف الرسم البياني هي نتائج منطقية. نهاية مخطط الرسم البياني هو التأكيد الذي يجب إثباته.

يستخدم اللون لإبراز المكونات. حالة النظرية والمشكلة زرقاء. التأكيد المراد إثباته أحمر. خطوات الإثبات باللون الأسود.

يعتبر الشكل الموصوف لإثبات النظريات وحل المشكلات مفيدًا وملائمًا للطلاب ، لأنه يجعل من الممكن تحديد المراحل الرئيسية لإثبات النظرية وحل مشكلة ما.

3. 2. برنامج منهجي معقد.

أ) دليل المعلم.

تم تجميع الدليل المقترح وفقًا لكتاب الهندسة للصفوف 7-9 بواسطة A.V.Pogorelov. الغرض الرئيسي منه هو تزويد عملية دراسة الهندسة بالوسائل اللازمة للتخيل ، لمساعدة المعلم في تدريس الهندسة: لتسهيل عملية إثبات النظريات ، واستيعاب المواد النظرية في عملية حل المشكلات. الرسوم البيانية للرسم البياني متعددة الأوجه ويمكن ، اعتمادًا على أهداف وأشكال الفئات ، استخدامها بطرق مختلفة: كتوضيح ، تهدف إلى تعزيز الرؤية عند شرح مادة نظرية جديدة ، عند تعميم وتنظيم مادة جديدة (الرسوم البيانية مع النظريات) ؛ كبطاقات تستخدم في إجراء المسوحات الفردية والأمامية (الرسوم البيانية مع المهام). يتم تقديم هذا الدليل دفتر العملللطلاب. يمكن استخدام المصنف للتنظيم عمل مستقلالطلاب أثناء وبعد ساعات الدوام المدرسي.

ب) مصنف للطلاب.

الدليل في شكل مصنف. يتضمن الدليل 28 مخططًا بيانيًا مع نظريات و 28 مخططًا بيانيًا مع المهام. تحتوي مخططات الرسم البياني على مادة البرنامج الرئيسية ، والتي يتم تقديمها بالوضوح اللازم وتمثل إطار العمل للحل. يقوم الطلاب بملء الخلايا الفارغة بالتسلسل بالمعلومات التي تشكل حل المشكلة.

يستخدم اللون لإبراز المكونات. حالة النظرية والمشكلة زرقاء ، والتأكيد الذي يتم إثباته أحمر ، ومراحل الإثبات سوداء.

الدليل مفيد للطلاب في الصفوف 7-9.

ج) الدليل الإلكتروني.

نتائج العمل ومناقشتها. المشروع هو نتيجة دراسة لمدة عامين لاستخدام الرسوم البيانية في دورة الرياضيات المدرسية.

إنشاء برمجيًا - مجمع منهجيوتم تنفيذه في سياق:

إجراء فصول لنادي "أرسطو" حول موضوع "حل المشكلات المنطقية باستخدام الرسوم البيانية".

تطبيقات الرسوم البيانية في البراهين على النظريات والمسائل الهندسية

في دروس الهندسة في الصف 8.9.

عروض مع المشروع في المدرسة علمية وعمليةالمؤتمرات.

خاتمة.

تلخيصًا لنتائج دراسة استخدام الرسوم البيانية في مقرر الهندسة المدرسية ، توصلت إلى الاستنتاج التالي:

1. إن ميزة إثبات الرسم البياني للنظريات وحل المشكلات على النظريات التقليدية هي توضيح ديناميكيات إثبات النظريات والمشكلات.

2. تساعد مقدمة في عملية إثبات النظريات الهندسية ومشكلات طريقة مخطط الرسم البياني على تقوية مهارات الطلاب في تكوين البراهين.

3. البرنامج المطور والمجمع المنهجي لدراسة الهندسة في الصفوف 7-9: أ) دليل المعلم. ب) كتاب عمل للطلاب. ج) الدليل الإلكتروني مفيد للطلاب في الصفوف 7-9.

إرسال عملك الجيد في قاعدة المعرفة أمر بسيط. استخدم النموذج أدناه

سيكون الطلاب وطلاب الدراسات العليا والعلماء الشباب الذين يستخدمون قاعدة المعرفة في دراساتهم وعملهم ممتنين جدًا لك.

وثائق مماثلة

استعادة الرسوم البيانية من مصفوفات تجاور قمة معينة. بناء لكل رسم بياني لمصفوفة تجاور الحواف ، والوقوع ، وإمكانية الوصول ، وإمكانية الرد. ابحث عن تكوين الرسوم البيانية. تحديد الدرجات المحلية لرؤوس الرسم البياني. ابحث عن قاعدة الرسوم البيانية.

العمل المخبري ، تمت الإضافة في 01/09/2009

نظرية الرسم البياني كفرع من الرياضيات المنفصلة التي تدرس خصائص المجموعات المحدودة مع علاقات معينة بين عناصرها. المفاهيم الأساسية لنظرية الرسم البياني. مصفوفات الجوار والوقوع و الاستخدام العمليعند تحليل الحلول.

الملخص ، تمت الإضافة 06/13/2011

المفاهيم الأساسية لنظرية الرسم البياني. درجة الرأس. الطرق والسلاسل والدورات. الاتصال وخصائص الرسوم البيانية الموجهة والمستوية ، خوارزمية للتعرف عليها ، تماثل الشكل. عمليات عليها. نظرة عامة على كيفية تحديد الرسوم البيانية. دورات أويلر وهاملتونيان.

العرض ، تمت الإضافة في 11/19/2013

وصف رسم بياني بواسطة مجموعات من الرؤوس V والأقواس X ، قوائم الجوار ، مصفوفة الوقوع والمجاورة. مصفوفة الوزن للرسم البياني المقابل غير المباشر. تحديد أقصر مسار شجرة باستخدام خوارزمية Dijkstra. العثور على الأشجار على الرسم البياني.

ورقة المصطلح ، تمت إضافة 09/30/2014

المفاهيم الأساسية لنظرية الرسم البياني. المسافات في الرسوم البيانية والقطر ونصف القطر والمركز. استخدام الرسوم البيانية في الأنشطة البشرية العملية. تعريف أقصر الطرق. الرسوم البيانية لأويلر وهاملتونيان. عناصر نظرية الرسم البياني في الفصول الاختيارية.

تمت إضافة أطروحة 19/07/2011

تمثيل المصفوفة والمفهوم للرسوم البيانية. الرسوم البيانية الموجهة وغير الموجهة. تعريف مصفوفة الجوار. الطرق والسلاسل والدورات وخصائصها. الخصائص المترية للرسم البياني. تطبيق نظرية الرسم البياني في مختلف مجالات العلوم والتكنولوجيا.

ورقة مصطلح ، تمت الإضافة في 02/21/2009

الوصف الرياضي للنظام تحكم تلقائىباستخدام الرسوم البيانية. رسم الرسم البياني وتحويله والتخلص من الفروق. تحسين الرسوم البيانية الموجهة وغير الموجهة ، وتجميع مصفوفات التقارب والوقوع.

العمل المخبري ، تمت الإضافة في 03/11/2012

يتم وضع نص العمل بدون صور وصيغ.
النسخة الكاملةالعمل متاح في علامة التبويب "ملفات العمل" بتنسيق PDF

مقدمة

عالمنا مليء ليس فقط بالأحرف والأرقام ، ولكن أيضًا بمجموعة متنوعة من الصور. هذه لوحات وجميع أنواع الصور بالإضافة إلى العديد من الرسوم البيانية. توجد المخططات على شعارات الشركات والسيارات ، إشارات الطريقوالخرائط. إذا نظرت إلى خريطة المترو أو طريق الحافلة، إنها مجرد خطوط بها نقاط. تسمى مخططات الخطوط (الحواف) والنقاط (الرؤوس) الرسوم البيانية.

ظهرت نظرية الرسوم البيانية بفضل مشكلة مسلية واحدة حلها ليونارد أويلر. يقول التاريخ أنه في عام 1736 توقف عالم الرياضيات اللامع في كونيجسبيرج. تم تقسيم المدينة بواسطة النهر إلى 4 أجزاء ، متصلة بسبعة جسور. كان من الضروري تحديد ما إذا كان من الممكن تجاوز جميع الجسور بالمرور فوق كل منها مرة واحدة بالضبط. قرر أويلر أنه من المستحيل حل المشكلة. تم تدمير جسور كونيغسبيرغ خلال الحرب العالمية الثانية ، لكن هذه القصة أدت إلى ظهور نظرية رياضية جميلة - نظرية الرسم البياني.

في القرن العشرين ، تلقت نظرية الرسم البياني تطورًا مذهلاً ، ووجدت العديد من التطبيقات في التخطيط والهندسة المعمارية والهندسة ، وخاصة في علوم الكمبيوتر والاتصالات السلكية واللاسلكية. ترتبط الرسوم البيانية بالتوافقيات والرياضيات المنفصلة والطوبولوجيا ونظرية الخوارزمية وفروع الرياضيات الأخرى.

ما هي الفرص التي يحصل عليها الطالب الذي يمتلك هذه النظرية؟ هل سيتمكن من تحقيق أي نجاح في دراسته أم الحياة العادية؟ هذا المشروع مخصص لمثل هذا البحث.

الهدف من المشروع:تبين أن أساليب نظرية الرسم البياني تمنح الطالب أداة لحل مشاكل الأولمبياد المعقدة ، وفي الحياة - لتنظيم نقل المعلومات العاجلة بين الناس.

الفرضيات:

بمساعدة الرسوم البيانية ، يمكنك بسهولة حل العديد من مشكلات الأولمبياد

تساعد نظرية الرسم البياني في إنشاء نظام للإخطار العاجل للفريق

مهام:

تعلم كيفية حل المشاكل باستخدام الرسوم البيانية

قم بتطوير موقع ويب لاختبار مهام الأولمبياد

تصميم نظام تنبيه عاجل للفصول الدراسية باستخدام رسم بياني

كائنات البحث:مشاكل الأولمبياد وأنظمة الإنذار

موضوع الدراسة:نظرية الرسم البياني ، برمجة الويب.

طرق البحث:

طرق نظرية الرسم البياني

طرق برمجة الويب

خطة البحث:

تعرف على تاريخ نظرية الرسم البياني

تعلم قواعد حل مسائل الأولمبياد باستخدام الرسوم البيانية

خذ دورة مدرسة "برمجة الويب" تقنيات المعلومات"حقيقة"

تطوير موقع لاختبار مسائل الأولمبياد في نظرية الرسم البياني واختباره على الأصدقاء

تصميم نظام تنبيه الفصل الدراسي العاجل (SOK)

إجراء تجربة لاختبار نظام SOC

الفصل 1. نظرية الرسم البياني في حياتنا

1.1 تطبيق نظرية الرسم البياني في مناطق مختلفة

تُستخدم الرسوم البيانية في مجموعة متنوعة من المجالات: في تصميم الدوائر الكهربائية ، وشبكات الهاتف ، وعند البحث عن الطرق بين المستوطنات ، وفي الاقتصاد.

في الكيمياء ، تُستخدم الرسوم البيانية لتمثيل مركبات مختلفة. يمكن استخدام الرسوم البيانية للتمثيل جزيئات بسيطةوالمركبات العضوية المعقدة نوعًا ما.

تلعب نظرية الرسم البياني دورًا رئيسيًا في مراحل مختلفة من المشاريع المعمارية. بعد تحديد أجزاء المشروع وقبل الانتقال من الرسومات التخطيطية إلى الرسومات ، سيكون من المفيد إنشاء رسم بياني للعلاقة لعناصر المشروع. سيساعد تحليل الرسوم البيانية في المباني العامة في تحديد درجة إمكانية الوصول إلى الأقسام المختلفة ، وموقع المباني (البوفيه ، والمكتبة ، وما إلى ذلك) ، بالإضافة إلى حالات الهروب من الحريق. تسمح لك الرسوم البيانية بتبسيط التحليل بشكل ملحوظ المواقف الصعبة.

في عصرنا ، بفضل الإنترنت - "شبكة من الشبكات" التي تربط أجهزة الكمبيوتر حول العالم ، أصبحت الثورة الرقمية ممكنة. زادت قوة أجهزة الكمبيوتر بشكل مطرد ، ولكن بفضل الشبكات كان من الممكن تحقيق قفزة عملاقة في العالم الرقمي. الرسوم البيانية والاتصالات سارت دائمًا جنبًا إلى جنب.

يوضح الشكل 1.1 مخططات مختلفة لتوصيل أجهزة الكمبيوتر ببعضها البعض. غالبًا ما توجد ثلاث طرق لتوصيل أجهزة الكمبيوتر بشبكة محلية: "ناقل عام" و "نجمة" و "حلقة". يحتوي كل رسم تخطيطي على رسم بياني ، لذلك يتم استخدام مصطلح "طوبولوجيا الشبكة". طوبولوجيا الشبكة هي تكوين رسم بياني تكون رؤوسه أجهزة كمبيوتر وأجهزة توجيه ، والحواف عبارة عن خطوط اتصال (كبل) بينها. في الشكل 1.2 ، يتم عرض جميع الهياكل على هيئة رسوم بيانية.

الشجرة هي رسم بياني بسيط للغاية حيث يوجد مسار واحد فقط بين أي رأسين. تُستخدم الأشجار في علم الوراثة لتوضيح الروابط الأسرية (أشجار العائلة) ، وكذلك في تحليل احتمالات الأحداث المختلفة.

الشكل 1.1. خيارات لبناء شبكات الكمبيوتر المحلية

الشكل 1.2. خيارات لبناء شبكات الكمبيوتر المحلية

أ - الحافلة المشتركة ، ب - نجمة ، ج - الحلقة

هناك العديد من الألعاب التي تحتاج فيها إلى إنشاء رسم بياني معين (ألعاب المتاهة) ، أو استخدام الرسم البياني لتحديد ما إذا كانت هناك استراتيجية رابحة.

يعد نظام تحديد المواقع العالمي (GPS) والخرائط واتجاهات القيادة على الويب مثالًا رائعًا آخر على كيفية استخدام الرسوم البيانية. حوافها عبارة عن شوارع وطرق ، والرؤوس كذلك المستوطنات. رؤوس هذه الرسوم البيانية لها أسماء ، وتتوافق الحواف مع أرقام تشير إلى المسافة بالكيلومترات. وبالتالي ، يتم تمييز مثل هذا الرسم البياني وتثمينه. تساعد الرسوم البيانية في تصور أنماط النقل العام ، مما يسهل التخطيط لرحلتك.

تستخدم الرسوم البيانية أيضًا في صناعة النفط والغاز في أنظمة نقل النفط والغاز. بمساعدة الطرق التحليلية الرسومية لأنظمة نقل الغاز ، من الممكن اختيار الخيار الأقصر من جميع الطرق الممكنة لتجاوز خط الأنابيب.

أدى تطور علوم الكمبيوتر إلى حقيقة أن العديد من النماذج الرياضية قد تم استخدامها في العمليات التلقائية. يمكن للآلة التعامل بسهولة مع الحسابات ، ولكن اختيار الخيار الأفضل من المجموعة في ظل عدم اليقين يعد مهمة أكثر صعوبة. ظهرت خوارزميات جديدة تستخدم آليات تذكرنا بالثورة البيولوجية. يستخدمون الرسوم البيانية كطريقة لتصور العمليات. شكلت نمذجة الخلايا العصبية في الدماغ البشري ومبدأ عملها الأساس نظرية جديدة- نظريات الشبكات العصبية.

1.2 استنتاجات الفصل.

وجدت نظرية الرسم البياني تطبيقها في العديد من مجالات العلوم والتكنولوجيا والحياة اليومية. ومع ذلك ، على الرغم من تطبيقه الواسع في مختلف المجالات ، إلا أنه يتم إيلاء الاهتمام السطحي له في دورة الرياضيات المدرسية. في الوقت نفسه ، تظهر التجارب المختلفة في مجال التعليم أن عناصر نظرية الرسم البياني لها قيمة تعليمية عالية ، وبالتالي يجب إدراجها في المناهج المدرسية.

في الواقع ، سيكون مفيدًا جدًا لطلاب المدارس المتوسطة أن يتعلموا أساسيات نظرية الرسم البياني ، لأنهم سيساعدونهم في إتقان الدورة الأساسية للرياضيات ، وخاصة في حل مشاكل الأولمبياد في التوافقية ونظرية الاحتمالات.

الفصل 2

2.1. نظرية الرسم البياني في مشاكل الأولمبياد

متنوع الأولمبياد الرياضية، مثل "Kangaroo" و "Dino-Olympiad Uchi.ru" والأولمبياد الدولي للإرشاد "Owlet" ، غالبًا ما تتضمن أيضًا مشكلات في نظرية الرسم البياني في صيغ مختلفة.

كما تعلم ، فإن الأطفال مغرمون جدًا بكل ما يتعلق بأجهزة الكمبيوتر والإنترنت ، وليس من السهل وضعهم على الطاولة مع كتاب عن الرياضيات. من أجل إثارة اهتمام تلاميذ المدارس بنظرية الرسم البياني ، طور مؤلفو المقال ، استنادًا إلى الدورات التدريبية حول برمجة الويب في مدرسة تقنيات المعلومات "REAL-IT" ، محاكيًا عبر الإنترنت يتضمن اختبارًا في نظرية الرسم البياني ، الموجود في صفحة مدرسة تيومين الخاصة "Evolventa": evolventa-tmn.github.io. تتم دعوة تلاميذ المدارس لحل ست مشاكل بمستويات صعوبة مختلفة ، ويقوم بإدخال الإجابات في المربعات ، ثم بالضغط على زر "إنهاء" ، يتم عرض النتيجة: عدد المشكلات التي حلها بشكل صحيح (الشكل 2.1).

الشكل 2.1. جزء من شاشة الموقع مع خيارات الاختبار

بطبيعة الحال ، سيبدأ الطفل الماكر فورًا في البحث عن إجابات على محركات البحث ، لكنه لن يجد مثل هذه الصياغات بالضبط ، فقط صيغ مماثلة ، على سبيل المثال ، على موقع المجلة الإلكترونية العلمية والمنهجية "Concept". لذلك ، للحصول على النتيجة المرجوة: 6 مهام من أصل 6 يجب على الطالب فهمها مبادئ عامةحل المشكلات باستخدام نظرية الرسم البياني. وفي المستقبل ، ستساعده المعرفة المكتسبة على حل مشاكل المدرسة والأولمبياد بنجاح.

عندما كان الموقع جاهزًا تمامًا ، تم اختباره ونشره على الإنترنت ، تلقى زملائنا في الفصل رابطًا له. كان الاهتمام بالموقع عظيماً: بناءً على عداد الزيارة ، تمت زيارته أكثر من 150 مرة في الأسبوع الأول! حاول العديد من الرجال حل المشكلات ، لكنهم بدوا صعبًا عليهم. حتى بعض الآباء مع أعلى التعليم التقني، حيرة عدد من المهام ، وهذا يشير إلى أن نظرية الرسم البياني لم تدرس حتى في جميع المستويات العليا المؤسسات التعليمية. هذا يعني أن الاختبار الذي أعدناه سيكون مفيدًا ليس فقط لأطفال المدارس ، ولكن أيضًا للكبار!

2.2. نظرية الرسم البياني في تصميم نظام تنبيه الفصل

حاليًا ، يتم إعطاء مجال نظام إدارة الموظفين العاجل في المنظمات اهتمام كبيروذلك لأن هذه الأنظمة تلعب دورًا مهمًا في تنظيم جميع أنشطة الموظفين.

في البداية ، تم تصميم أنظمة إدارة الخطاب العام والإخلاء لإبلاغ الموظفين والموظفين والضيوف بشكل عاجل عن حريق في المبنى ، وتوفير المعلومات وبث معلومات مهمة من أجل إخلاء سريع وناجح للأشخاص. اليوم ، يمكن ملاحظة هذه الأنظمة ليس فقط في إطار منظمة أو مؤسسة واحدة ، ولكن في جميع أنحاء بلدنا ، وتستخدم لتحسين سلامة الناس.

وتجدر الإشارة إلى أن معظم أنظمة الإنذار المستخدمة تستهدف البالغين. لكن أخطر سن هو الأطفال. يحتاج الأطفال أيضًا إلى أنظمتهم الخاصة لتنبيه معظم أقرانهم في أقصر وقت ممكن بشأن خطر وشيك أو تغيير في الموقف.

في المدرسة ، يقضي كل طفل جزءًا كبيرًا من وقته: خمسة إلى ستة أيام في الأسبوع لعدة ساعات. لذلك ، فإن إنشاء نظام تحذير للأطفال سيجعل من الممكن تنظيم كل طفل لرد فعل سريع ومختص للوضع المتغير.

على سبيل المثال ، سيكون هذا النظام مفيدًا جدًا عند إرسال رسالة حول الخطر أو معلومات حول تجمع عاجل أو حول تغيير في الموقف عندما يكونون في أجزاء مختلفة من المدرسة أو بشكل عام في الغابة في إجازة (الشكل 2.2)

الشكل 2.2. صفنا في رحلة إلى GAU DO TO "المركز الإقليمي للتدريب قبل التجنيد والتعليم الوطني" Outpost "

في هذا العمل ، جرت محاولة لإنشاء نظام إعلام جماعي باستخدام مثال فئة واحدة مؤسسة تعليمية: MAOU SOSH رقم 89.

نظرًا لأن الأطفال أنفسهم يجب أن ينشروا المعلومات ، يجب عليهم استخدام أنواع الاتصال المتاحة لهم فقط - الاتصالات المتنقلة. يجب إخطار كشف رواتب الفصل بأكمله ، لذلك ، من أجل تحليل أي من الأطفال مستعد لإخطار أي من أصدقائهم ، تم إجراء مسح للفصل. في الاستبيانات ، تم وضع قيد مبدئي: يستطيع كل طفل الاتصال بأربعة أصدقاء كحد أقصى ، وإذا كان هناك وقت ، اثنان آخران.

أظهر الاستطلاع نشاطًا كبيرًا إلى حد ما للرجال: بشكل عام ، سيتم إجراء حوالي 118 مكالمة في الفصل. يكاد يكون من المستحيل تحليل مثل هذا الحجم من المعلومات في العقل ، لذلك تقرر استخدام تكنولوجيا المعلومات. من الأفضل تمثيل نموذج إخطار الفريق كرسم بياني. الأطراف فيه مكالمات (أو رسائل نصية) ، والرؤوس أطفال. نظرًا لأن رؤوس الرسم البياني لها أسماء ، وتتوافق الحواف مع الأرقام التي تشير إلى احتمال المكالمة (1 أو 0.5) ، عندئذٍ يتم تصنيف هذا الرسم البياني وتثمينه. يساعد الرسم البياني في تصور نظام إعلام الفريق ، مما يسهل النمذجة.

تقرر تصور الرسم البياني باستخدام أداة RAMUS CASE ، لأنها تتيح لك العمل مع لون الرؤوس والحواف ، كما تسمح لك بتحريك رؤوس الرسم البياني بالحواف المرفقة بها من أجل الوضوح. يوضح الشكل 2.3 رسمًا بيانيًا لنظام RNS.

في 19 نوفمبر 2017 ، تم اختبار نظام SOK المصمم. في البداية ، خططنا أن يتم الإشعار على مدى ثلاث لفات. بالنسبة للدائرة الأولى (بداية الإشعار) ، اخترنا طفلين لا يرغب أحد في الاتصال بهما ، لكنهما جاهزان للاتصال ، بالإضافة إلى مؤلفي المشروع أنفسهم (الشكل 2.3 ، الكتل الوردية). يتم إرسال مزيد من المعلومات إلى الدائرة الثانية للإخطار (الشكل 2.4 ، المربعات الصفراء). وفي دائرة الإخطار الثالثة (الشكل 2.4 ، الكتل الخضراء) سيتم إبلاغ الفصل بأكمله. لكن خلال التجربة ، رأينا أن بعض الأطفال يتدربون لمدة تتراوح بين 1.5 و 2 ساعة ولا ينظرون إلى الهاتف ، والبعض الآخر بتوازن سلبي ، وبالتالي لا يمكنهم الاتصال.

الشكل 2.3. رسم بياني للفصل الدراسي

الشكل 2.4. دوائر تنبيه SOK

لذلك ، في الواقع ، تم إخطار فصلنا في 490 دقيقة فقط - أي 8 ساعات و 10 دقائق. لكنها كانت كلها 100٪. الشيء المهم هنا هو أن نظامنا ليس له هيكل شجرة ، بل رسم بياني. وفيه ، هناك عدة مسارات تؤدي من قمة إلى أخرى ، لذلك على أي حال ، سيتم إخطار الجميع!

يوضح الشكل 2.6 رسمًا بيانيًا لتنبيهات الفصل (عدد الأشخاص الذين تم تنبيههم) مقابل الوقت (بالدقائق).

الشكل 2.6. جدول تنبيه الفصل

لتسهيل تتبع الإخطارات ، أثناء عملية الاختبار ، كان على الأطفال إخبار مؤلفي المشروع بموضوعهم المفضل ، واحتفظوا بسجل متى ومن يقوم بالإبلاغ عن المعلومات.

نتيجة اختبار أخرى - دراسة استقصائية للمواضيع المفضلة (الشكل 2.7) ، أظهرت أن الأطفال في فصلنا يحبون الرياضيات وعلوم الكمبيوتر والألعاب الخارجية أكثر من أي شيء آخر! وهذا يعني أنهم قد يحبون نظرية الرسم البياني بقدر ما نحبهم.

الشكل 2.7. مخطط دائري لعناصر الفصل المفضل

2.3 استنتاجات الفصل.

اختبرنا كلا الفرضيتين. ساعد الموقع الذي قمنا بتطويره لاختبار مسائل الأولمبياد في نظرية الرسم البياني في إثبات أن عددًا من مشكلات الأولمبياد ببساطة لا يمكن حلها دون معرفة بنظرية الرسم البياني ، وحتى بالنسبة للمهندسين البالغين. تم تأكيد الفرضية الأولى.

كما تبين أن الفرضية الثانية صحيحة. سمح نظام الإخطار الجماعي المصمم والمختبَر ، باستخدام مثال فصل واحد ، بإخطار فريق الأطفال بأكمله في 8 ساعات و 10 دقائق. من خلال تحسين الرسم البياني ، يمكنك تحقيق نتائج أسرع.

خاتمة.

نأمل بعد التعرف على نظرية الرسم البياني وتطبيقاتها العديدة في مختلف المجالات ، أن يوقظ الطلاب اهتمامهم بنظرية الرسم البياني ، وسيواصلون دراسة هذا الفرع من الرياضيات بأنفسهم. ستكون نتيجة الدراسة نتائج أعلى في الأولمبياد.

فيما يتعلق بتطبيق نظرية الرسم البياني في الحياه الحقيقيه، يتم التأكيد على أهمية الموضوع قيد النظر من خلال حقيقة أن إنشاء نظام تحذير للأطفال سيزيد من سرعة نقل المعلومات العاجلة ، ويغطي معظم فريق الأطفال الذي سيتم استخدام هذا النظام من أجله ، ويقلل من وقت الاستجابة من الأطفال ، وكذلك ضمان أقصى درجات الأمان لفريق الأطفال. كل هذا يشير إلى المزايا الواضحة لتنفيذ النظام المصمم.

فهرس

بيلوبورودوفا أ. تنمية التفكير المكاني بمساعدة ألعاب المتاهة / أ. Beloborodova // "المنتدى العلمي للطلاب": مواد الإلكترونية الثامنة للطلاب الدوليين مؤتمر علمي.- 2017. https://www.site/2017/7/26746

بيلوبورودوفا ، أ. تطوير محاكي ويب لدراسة نظرية الرسم البياني / A.A. بيلوبورودوفا ، S.V. باختين ، أ. Frolov // تقنيات المعلومات الجديدة في صناعة النفط والغاز والتعليم: مواد المؤتمر العلمي والتقني الدولي السابع ؛ Resp. إد. هل هو. كوزياكوف. - تيومين: TIU، 2017. - S.156-159.

بيلوبورودوفا أ. لا تضيع في الرياضيات! / أ. Beloborodova // XVIII All-Russian Children مسابقة البحث العلمي. والأعمال الإبداعية "الخطوات الأولى في العلوم": مجموعة من الملخصات. - م: تكامل NS ، مجلس الدوما التابع للجمعية الفيدرالية للاتحاد الروسي ، وزارة التعليم والعلوم في روسيا. - 2016. - ص 110-111 .

جيندينشتاين ، ل. أليس في أرض الرياضيات. حكاية / للمبتدئين. ومتوسط سن المدرسة - خاركيف: إد - تجاري. مؤسسة "باريتيت" المحدودة ، 1994. - 288 ص ، سوء.

Davletshin ، M.I. دراسة فعالية طرق إزالة ضوضاء الصورة / M.I. Davletshin، K.V. Syzranteva // توفير الطاقة و تقنيات مبتكرةفي مجمع الوقود والطاقة: مواد Int. علمي عملي. أسيوط. الطلاب وطلاب الدراسات العليا والعلماء الشباب والمتخصصين. T.1 / otv. المحرر A.N. كالين. - تيومين: TIU، 2016. - S. 25-29.

كارنوخوفا ، أ. استخدام نظرية الرسم البياني في حل المشكلات في الاقتصاد / أ. كارنوخوفا ، أ. Dolgopolova // وقائع المؤتمر العلمي الإلكتروني الدولي للطلاب السابع "المنتدى العلمي للطلاب". http://www.scienceforum.ru/2015/991.

كيرن ، جي متاهات العالم. سانت بطرسبرغ: دار النشر "Azbuka-classika" ، 2007 ، 448 ص.

كراوس ، م. تطبيق تقنيات المعلومات لتصميم نظام الإخطار الجماعي / M.V. كراوس ، أ. بيلوبورودوفا ، إي. Arbuzova // تقنيات المعلومات الجديدة في صناعة النفط والغاز والتعليم: مواد المؤتمر العلمي والتقني الدولي السابع ؛ Resp. إد. هل هو. كوزياكوف. - تيومين: TIU، 2017. - S. 153-156.

الدورة التدريبية "إنشاء مواقع الويب" كلية تكنولوجيا المعلومات "REAL-IT" http://it-schools.org/faculties/web/

عالم الرياضيات: في 40 مجلداً.الخامس 11: كلودي السينا. خرائط المترو وشبكات القطارات. نظرية الرسم البياني. / لكل. من الإسبانية - م: De Agostini، 2014. - 144 ص.

Moskevich L.V. الأولمبياد التعليمي - أحد أشكال الأنشطة اللامنهجية في الرياضيات / L.V. Moskevich // المجلة الإلكترونية العلمية والمنهجية "المفهوم". - 2015. - T. 6. - س 166-170. - URL: http://e-koncept.ru/2015/65234.htm.

مذكرة للسكان "إخطار السكان في حالة وجود تهديد وحالة طوارئ" http://47.mchs.gov.ru/document/1306125

روميانتسيف ، ف. النمذجة الرياضيةلنظام نقل الغاز باستخدام نظرية الرسم البياني / V.O. Rumyantsev // مشاكل الجيولوجيا وتنمية المعادن: Sat. علمي آر. / TPU. - تومسك ، 2017. - س 340 - 342.

موقع وزارة حالات الطوارئ في الاتحاد الروسي http://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves