عناصر نظرية الرسم البياني والبرمجة الرياضية. المسارات والحلقات

طبعة تعليمية

يويوكين نيكولاي ألكسيفيتش

LR لا. وقعت للطباعة

أوتش. إد. ل .. ،.

جامعة فورونيج الحكومية التقنية

394026 فورونيج ، شارع موسكوفسكي. أربعة عشرة

دليل القرص المغناطيسي

 قسم، أقسام رياضيات أعلىوالنمذجة الفيزيائية والرياضية

على ال. يويوكين

الرياضيات التمييزية الجزء الأول. عناصر نظرية المخططات

الدورة التعليمية

على ال. يويوكين

الرياضيات التمييزية الجزء الأول. عناصر نظرية المخططات

الدورة التعليمية

فورونيج 2004

المقدمة

يمكن استخدام هذا الدليل في مقرر "الرياضيات المتقطعة" من قبل طلاب VSTU الذين يدرسون في التخصصات التالية:

090102 - أمن الحاسوب ؛

090105 - أمن المعلومات الشامل للأنظمة الآلية ؛

090106 - أمن المعلوماتأنظمة الاتصالات السلكية واللاسلكية.

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

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

في دليل الدراسةيحدد الأسس والأساليب الأساسية والخوارزميات لنظرية الرسم البياني. هنا الرسوم البيانية و digraphs ؛ تماثل. الأشجار؛ الرسوم البيانية لأويلر الرسوم البيانية المستوية أغطية ومجموعات مستقلة ؛ اتصال قوي

في ديغرافس. تحليل الرسم البياني لسلسلة ماركوف ؛ خوارزميات لإيجاد أقصر المسارات في الرسوم البيانية ؛ مشكلة إيجاد دورة هاميلتونية

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

الهدف من الدورة هو تكوين الطلاب معرفة نظرية، المهارات العملية في مجال عمليات النمذجة والظواهر في العلوم الطبيعية والتكنولوجيا

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

تعمل المهام التالية على تحقيق هذا الهدف:

لدراسة أوسع مجموعة ممكنة من مفاهيم نظرية الرسم البياني ؛

اكتساب المهارات في حل المشكلات التعليمية والعملية ؛

طرق رئيسية للتحسين.

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

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

1. المفاهيم الأساسية لنظرية الرسم.

1.1 مشاكل نظرية الرسم البياني.

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

كانت المشكلات الأولى في نظرية الرسم البياني تتعلق بحل المشكلات الترفيهية والألغاز.

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

السؤال الذي يطرح نفسه: هل من الممكن ، بعد الخروج من المنزل ، العودة ، مرورا بكل جسر مرة واحدة بالضبط؟

المهمة الثانية. مشكلة ثلاثة منازل وثلاثة آبار. هناك ثلاثة منازل وثلاثة آبار.

يشترط رسم مسار من كل منزل إلى كل بئر حتى لا تتقاطع المسارات. كانت المهمة

تم حلها بواسطة Pontryagin وبشكل مستقل بواسطة Kuratovsky in

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

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

1.2 التعاريف الأساسية.

الرسم البياني G = (V ، E) هو مجموعة من مجموعتين - مجموعة غير فارغة من الرؤوس V ومجموعة من أزواج الرؤوس غير المرتبة والمرتبة. فيما يلي ، سيتم النظر في الرسوم البيانية المحدودة ، أي الرسوم البيانية مع مجموعة محدودة من الرؤوس وعائلة محدودة من الأزواج. زوج من القمم غير مرتبة يسمى حافة ، والزوج المرتب يسمى القوس.

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

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

تسمى القمم التي لا تنتمي إلى أي حافة (قوس) معزولة. تسمى القمم المتصلة بحافة أو قوس متجاورة. تسمى الحافة (القوس) وأي من رأسيها الحادث.

يقولون أن الحافة (u ، v) تربط الرؤوس u و v ، والقوس (u ، v) يبدأ عند الرأس u وينتهي عند الرأس v ، بينما تسمى u بالبداية ، و v هي نهاية هذا القوس.

يمكن توصيل زوج من الرؤوس بحافتين أو أكثر (أقواس في نفس الاتجاه). تسمى هذه الحواف (الأقواس) بالمضاعفات. يمكن أن يبدأ القوس (أو الحافة) أو ينتهي عند نفس الرأس. يسمى هذا القوس (الحافة) بالحلقة. يسمى الرسم البياني الذي يحتوي على حلقات الرسم البياني الزائف. يسمى الرسم البياني الذي يحتوي على عدة حواف (أقواس) الرسم البياني المتعدد.

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

يُطلق على الرسم البياني الذي يتكون من رأس واحد معزول (K 1) اسم تافه.

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

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

1.3 ارسم درجات الرؤوس.

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

إذا كانت درجات جميع رؤوس الرسم البياني n تساوي k ، فسيتم استدعاء الرسم البياني منتظم (متجانس)درجات ك. إذا كانت درجة الرأس تساوي 0 ، فيتم عزلها. إذا كانت درجة الرأس تساوي 1 ، فيُطلق على الرأس اسم المحطة الطرفية (معلقة ، طريق مسدود).

بالنسبة إلى الرسم البياني ، يسمى عدد الأقواس الخارجة من قمة الرأس v

فيتسيا نصف درجة النتيجة				(ت) واردة - شبه

غروب الشمس الجديد د			(v) ، بينما العلاقة d (v) =

	(ت) +	(الخامس).

نظرية أويلر: مجموع درجات رؤوس الرسم البياني هو

ضعف عدد الحواف ، أي

د (السادس)



			(الخامس)

حيث n هو عدد الرؤوس ؛ م هو الرقم

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

1.4 تماثل الرسم البياني.

يسمى الرسم البياني باسم (أو أعيد ترقيمه) إذا كانت رؤوسه تختلف عن بعضها البعض بطريقة ما.

علامات & أمبير؛ أرقام). يعتبر العد محددة تماما بالمعنى الدقيق للكلمة، إذا كان ترقيم الرؤوس والحواف ثابتًا. في هذه الحالة ، يسمى الرسمان البيانيان G 1 و G 2 متساويين (رمز G 1 = G 2) ، إذا تطابقت مجموعات الرؤوس والحواف. يطلق على رسمين بيانيين أو رسمين زائفين G 1 = (V 1 ، E 1) و G 2 = (V 2 ، E 2) -

	متماثل (تدوين G	اذا كان هناك

	تعيينات واحد لواحد: 1)	: V 1V 2
: E 1 E 2 مثل أي رأسين u ، v في الرسم البياني
	العلاقة ((ش ، ت)) ((ش) ، (ت)) صالحة.

	رسمان بيانيان بسيطان (بدون حلقات وحواف متعددة) G 1		و G2

تبين أن تكون متشابهة إذا كانت هناك متطابقة بشكل متبادل

تعيين القيمة

: V 1V 2

مثل ذلك

(ش ، ت) ((ش) ، (ت)).

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

انعكاسية -

G1 ،

علاوة على ذلك ، التحيز

هي الوظيفة المتطابقة.

تناظر.

مع التحيز

عبورية.

G1G2

انحياز

1 ، أ

مع التحيز

ثم G G

مع التحيز

2 (1) .

جامعة ولاية فلاديمير البيداغوجية

مقال

"نظرية الرسم البياني"

إجراء:

Zudina T.V.

فلاديمير 2001

1 المقدمة

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

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

4. النظريات الأساسية في نظرية الرسم البياني

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

6. تطبيق نظرية الرسم البياني في دورة مدرسيةالرياضيات

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

8. أخر الانجازاتنظرية الرسم البياني

§واحد. تاريخ نظرية الجرافيك.

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

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

(الشكل 1.1)

فيما يتعلق بالطريقة التي اكتشفها لحل مشاكل من هذا النوع ، كتب أويلر [انظر. ص 102-104]:

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

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

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

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

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

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

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

(الشكل 1.2)

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

في الختام ، نلاحظ أن مشكلة جسور كونيجسبيرج والمشكلات المماثلة ، جنبًا إلى جنب مع مجموعة من الأساليب لدراستها ، مهمة جدًا في من الناحية العمليةفرع الرياضيات يسمى نظرية الرسم البياني. ينتمي أول عمل على الرسوم البيانية إلى L.Euler وظهر في عام 1736. في وقت لاحق ، عمل كونيغ (1774-1833) ، هاملتون (1805-1865) على الرسوم البيانية ، بين علماء الرياضيات المعاصرين - ك.بيرج ، أو.أور ، أ. زيكوف.

§2. النظريات الأساسية في نظرية الرسوم

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

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

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

(الشكل 2.1)

فيما يلي ، سيتم الإشارة إلى رؤوس الرسم البياني بأحرف لاتينية أ , ب ,ج ,د. في بعض الأحيان يتم الإشارة إلى الرسم البياني ككل بواحد الحرف الكبير.

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

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

تعيين: ا " - رسم بياني برؤوس ليس لها حواف (الشكل 2.2).

(الشكل 2.2)

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

تعيين: يو " – يتكون الرسم البياني من نالرؤوس والحواف التي تربط جميع الأزواج الممكنة من هذه الرؤوس. يمكن تمثيل هذا الرسم البياني كـ ن- مربع يتم فيه رسم جميع الأقطار (الشكل 2.3).

(الشكل 2.3)

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

تعيين: ص (أ) – درجة الرأس أ . على سبيل المثال ، في الشكل 2.1: ص (أ)=2, ص (ب)=2, ص (ج)=2, ص (د)=1, ص (ه)=1.

التعريف 2.06.العد ، درجة كل شيء كالتي رؤوسها هي نفسها يسمى متجانس عدد الدرجة العلمية ك .

يوضح الشكلان 2.4 و 2.5 رسوم بيانية متجانسة للدرجتين الثانية والثالثة.

(الشكل 2.4 و 2.5)

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

يوضح الشكل 2.6 الرسم البياني الأصلي جي , يتكون من أربعة رؤوس وثلاثة أجزاء ، وفي الشكل 2.7 - تكملة هذا الرسم البياني - الرسم البياني جي " .

(الشكل 2.6 و 2.7)

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

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

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

(الشكل 2.8)

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

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

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

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

من الملائم وصف الرسوم البيانية والتعريفات الأساسية بالصور ، لذلك يجب إرفاق الصور لقراءة هذه الصفحة.

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

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

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

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

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

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

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

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

مؤسسة البلدية المستقلة للتعليم العام مدرسة التعليم الثانوي 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 هي أجزاء من القارة مفصولة عن بعضها البعض بفروع النهر

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

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

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

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

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

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

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

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

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

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

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

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

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

التعريف 6.يُطلق على الرسم البياني الذي تكون درجات جميع رءوسه متطابقة في الرسم البياني المتجانس للدرجة 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.

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

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

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

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

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

Olechnik S. N.، Nesterenko Yu. V.، Potapov M.K "Old مهام مسلية"، M." Nauka "، 1988 (الجزء 2 ، القسم 8 ؛ التذييل 4) ؛

طلب

أرز. 6

أرز. 7

أرز. ثمانية

طلب

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

طلب

المفاهيم الأساسية لنظرية الرسم البياني.

أمثلة على استخدام نظرية الرسم البياني.

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

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

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

اقترح د. كونيغ تسمية هذه المخططات بـ "الرسوم البيانية" ودراسة خصائصها بشكل منهجي.

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

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

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

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

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

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

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

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

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

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

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

أويلر (1707-1782) هو والد نظرية الرسم البياني (بالإضافة إلى الطوبولوجيا) ، الذي حل في عام 1736 مشكلة كانت معروفة على نطاق واسع في ذلك الوقت ، تسمى مشكلة جسر كونيجسبيرج.

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

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

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

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

الشكل 1. متنزه في مدينة Koenigsberg ، 1736

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

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

اتضح "العد". يظهر هذا الرسم البياني في الشكل 2. ، حيث يتم تمييز النقاط بنفس الأحرف مثل الأجزاء الأربعة من الأرض.

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

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

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

الدوائر الكهربائية

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

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

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

الشكل 3. الشبكة N ، الرسم البياني المقابل لها G.

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

الايزومرات الكيميائية

التعامل مع المهام العملية البحتة الكيمياء العضوية، اكتشف كايلي في عام 1857 فئة مهمة من الرسوم البيانية تسمى الأشجار.

سعى إلى سرد أيزومرات الهيدروكربونات المشبعة (المشبعة) منن ح 2 n + 2 مع عدد معين n من ذرات الكربون ؛ الشكل 4.

الشكل 4. Isobutane

في علم النفس الاجتماعي.

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

على هذه الخريطة ، تمثل المناطق أنواع مختلفةأنشطة الشخص ، على سبيل المثال ، ما يفعله في العمل أو المنزل أو هوايته.

الشكل 5. رسم خريطة والرسم البياني المقابل لها.

نؤكد أن K. Lev وتعامل n بالفعل مع الرسوم البيانية ، كما يتضح من الشكل 5.

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

ينطبق اقتراح ليفين فقط على الخرائط المستوية ، لأنه دائمًا ما كان يرسم رسوماته على متن طائرة. بعد ذلك ، تم تطوير فكرة K.Levin في إجراءات القياس الاجتماعي.

في نظرية التنظيم

يمكن تمثيل الرسوم البيانية ليس فقط في الشكل الكلاسيكي الصارم. لذلك يتم تقديم دورة حياة شركة I. Adizes بالشكل التالي.

الشكل 6 دورة الحياةشركات

وظيفي الهيكل التنظيمي إنه مبني على مبدأ توزيع الوظائف داخل المنظمة وإنشاء بنى فرعية شاملة لإدارة الوظائف.

اقسام الانتاج

أرز. الهيكل التنظيمي الوظيفي

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

أصبحت هذه النظرية "نظرية الرسم البياني".

المفاهيم الأساسية لنظرية الرسم البياني

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

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

نظرية الرسم البياني- فرع من فروع الرياضيات ، خصوصية منهج هندسي لدراسة الأشياء

نظرية الرسم البياني- لغة رياضية لتعريف رسمي للمفاهيم المتعلقة بتحليل وتركيب هياكل الأنظمة والعمليات.