نظرية الرسم البياني: المفاهيم والمهام الأساسية. الرسوم البيانية كهيكل بيانات. العد. التعارف النظري (البدايات الأولى)

تعتبر نظرية الرسم البياني فرعًا من الرياضيات المنفصلة التي تدرس الأشياء الممثلة كعناصر منفصلة (رؤوس) ووصلات بينها (أقواس ، حواف).

نشأت نظرية الرسم البياني من حل مشكلة جسر كونيجسبيرج عام 1736 بواسطة عالم الرياضيات الشهير ليونارد أويلر(1707-1783: ولد في سويسرا وعاش وعمل في روسيا).

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

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

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

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

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

هناك ثلاثة منازل وثلاثة آبار تقع بطريقة ما على متن الطائرة. ارسم مسارًا من كل منزل إلى كل بئر حتى لا تتقاطع المسارات. تم حل هذه المشكلة (تبين أنه لا يوجد حل) كوراتوفسكي (1896 - 1979) في عام 1930.

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

يتمثل جوهر الحل المنشور في تعداد عدد كبير ولكن محدود (حوالي 2000) من أنواع الأمثلة المضادة المحتملة لنظرية الألوان الأربعة وإظهار أنه لا توجد حالة مثال مضاد. تم إجراء هذا التعداد بواسطة البرنامج في حوالي ألف ساعة من تشغيل الكمبيوتر العملاق.

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

وبالتالي ، يبقى الاعتماد على مؤهلات المؤلفين المبرمجين والاعتقاد بأنهم فعلوا كل شيء بشكل صحيح.

التعريف 7.1. عدد جي= جي(الخامس, ه) هي مجموعة من مجموعتين محددتين: V - تسمى العديد من القمموالمجموعات E من أزواج العناصر من V ، أي دعا EÍV´V حواف كثيرة، إذا كانت الأزواج غير مرتبة ، أو أقواس كثيرةإذا تم ترتيب الأزواج.

في الحالة الأولى ، الرسم البياني جي(الخامس, ه) مُسَمًّى غير موجه، في الثانية الموجهة.

مثال. رسم بياني بمجموعة من الرؤوس V = (أ ، ب ، ج) ومجموعة من الأضلاع E = ((أ ، ب) ، (ب ، ج))

مثال. رسم بياني مع V = (أ ، ب ، ج ، د ، هـ) و E = ((أ ، ب) ، (أ ، هـ) ، (ب ، هـ) ، (ب ، د) ، (ب ، ج) ، (ج ، د)) ،

إذا كانت e = (v 1، v 2) ، eнE ، فإننا نقول أن الحافة e يربطالرؤوس v 1 و v 2.

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

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

عدد رؤوس الرسم البياني جيدل الخامس، وعدد الحواف - ه:

.

التمثيل الهندسي للرسوم البيانية هو كما يلي:

1) رأس الرسم البياني هو نقطة في الفضاء (على المستوى) ؛

2) حافة الرسم البياني غير الموجه هي قطعة ؛

3) قوس الرسم البياني الموجه هو مقطع موجه.

التعريف 7.2.إذا كان في الحافة e = (v 1، v 2) v 1 = v 2 يحدث ، عندئذٍ تسمى الحافة e حلقة. إذا سمح للرسم البياني أن يحتوي على حلقات ، فسيتم استدعاؤه الرسم البياني مع الحلقات أو الكاذبة .

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

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

التعريف 7.3.رسم بياني جي (الخامس , ه ) مُسَمًّى الرسم البياني الفرعي (أو جزء ) عدد جي(الخامس,ه)، لو الخامس الخامس, ه ه. لو الخامس = الخامس، الذي - التي جي مُسَمًّى يمتد الرسم البياني الفرعي جي.

مثال 7 . 1 . يتم إعطاء رسم بياني غير موجه.

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

التهم ك 2 ، ل 3, ل 4 وك 5 .

التعريف 7.5.رسم بياني جي=جي(الخامس, ه) يسمى ديكوت ، لو الخامسيمكن اعتباره اتحاد مجموعات منفصلة ، على سبيل المثال الخامس=أب، بحيث يكون لكل حافة الشكل ( الخامس أنا , الخامس ي)، أين الخامس أنا أو الخامس ي ب.

تربط كل حافة رأسًا من A إلى رأس من B ، لكن لا يوجد رأسان من A أو رأسان من B متصلان.

يسمى الرسم البياني ثنائي الأجزاء ديكوت كامل عدد ك م , ن، لو أيتضمن مقمم بيتضمن نالقمم ولكل منها الخامس أنا أ, الخامس ي بلدينا ( الخامس أنا , الخامس ي)ه.

وهكذا ، لكل منها الخامس أنا أ، و الخامس ي بهناك ميزة تربطهم.

ك 12 ك 23 ك 22 ك 33

مثال 7 . 2 . قم بإنشاء رسم بياني كامل ثنائي الأجزاء ك 2.4 والرسم البياني الكامل ك 4 .

الرسم البياني للوحدةنمكعب الأبعادفي ن .

رؤوس الرسم البياني عبارة عن مجموعات ثنائية ثنائية الأبعاد. تربط الحواف الرؤوس التي تختلف بنفس الإحداثي.

مثال:

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

عن الدورة

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

شكل

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

مصادر المعلومات

1. في.إميليتشيف ، أو آي ميلنيكوف ، في آي سارفانوف ، آر آي تيشكيفيتش. محاضرات عن نظرية الرسم البياني. موسكو: Librocom Book House ، 2009.
2. أ. زيكوف. نظرية الرسوم البيانية المحدودة. نوفوسيبيرسك: ناوكا ، 1969.
3. م.سوامي ، ك.ثولاسرامان. الرسوم البيانية والشبكات والخوارزميات. م: مير ، 1984.
4. إم أيجنر ، جي إم زيجلر. البراهين منكتاب. الطبعة الرابعة. سبرينغر ، 2009.
5. B. Bollobás. نظرية الرسم البياني الحديثة. سبرينغر ، 1998.
6. جيه إيه بوندي ، يو إس آر مورتي. نظرية الرسم البياني. سبرينغر ، 2008.

متطلبات

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

برنامج الدورة

1. مفهوم الرسم البياني وأنواع الرسوم البيانية.
2. تطبيقات مختلفة للرسوم البيانية: من جسور Königsber إلى الإنترنت.
3. اتصال الرسم البياني ، الرسوم البيانية الفرعية ، ودرجة الرأس.
4. التعاريف المتكافئة للأشجار.
5. بلاناريتي ومعيار كوراتوفسكي
6. صيغة أويلر.
7. عدد لوني للرسم البياني المستوي.
8. تعداد الشجرة: كود Prufer وصيغة كايلي.
9. صيغة لعدد الرسوم البيانية أحادية الحلقة.
10. دورات أويلر ومعيار أويلر.
11. دورات هاملتون. معيار ديراك ومعيار خفاتال.
12. مطابقة. نظرية هول وكوينج.
13. نظرية الرسم البياني المتطرفة. نظرية توران.
14. نظير نظرية توران للرسوم البيانية في المستوى.
15. نظرية رامزي. التعارف بين ستة أشخاص.
16. تعريف رقم رامزي.
17. الحدود الدنيا والعليا لأرقام رامزي.

نتائج التعلم

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

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

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

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

تعمل الرسوم البيانية كوسيلة ملائمة لوصف العلاقات بين الكائنات. لقد استخدمنا الرسوم البيانية سابقًا كطريقة لتصور العلاقات الثنائية المحدودة.

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

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

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

• التعاريف الأساسية

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

• طرق العرض

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

• الأشجار

  التعريف 5.5. الشجرة غير الموجهة هي رسم بياني متصل وغير موجه. التعريف 5.6. يُطلق على الشجرة الموجهة اسم الرسم البياني الموجه بدون محيطي والذي يكون فيه مستوى أي قمة هو 1 على الأكثر ويوجد رأس واحد بالضبط ، يسمى جذر الشجرة الموجهة ، والتي تكون القيمة غير المتجانسة فيها 0.

• الشجرة الممتدة الأقل وزنًا

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

• طرق المسح المنهجي لرؤوس الرسم البياني

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

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

• تماثل الرسم البياني

  بالنسبة للرسم البياني الموجه (V ، E) ، يمكن عرض المجموعة E من الأقواس كرسم بياني لعلاقة قابلية الوصول المباشر الثنائية المحددة في مجموعة الرؤوس. في رسم بياني غير موجه (V ، E) ، فإن مجموعة الحواف E هي مجموعة الأزواج غير المرتبة. لكل زوج غير مرتب (u ، v) ∈ E ، يمكننا أن نفترض أن الرؤوس u و v مرتبطة بعلاقة ثنائية متماثلة p ، أي ، (ش ، ت) ∈ ص و (ت ، ش) ∈ ص.

• الفرز الطوبولوجي

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

• عناصر السيكلومات

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

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

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

باتباع هذه القاعدة ، سنكون دائمًا في وضع ملائم ، لأننا عندما نكون عند x = a ، يكون للرسم البياني (للحواف غير المتقاطعة) رأسان من الدرجة الفردية: x و a ؛ إذا تجاهلنا الرؤوس المعزولة ، فسيتبقى لنا رسم بياني متصل ، بحكم النظرية 1 ، له مسار أويلر يبدأ عند x.

محتوى
مقدمة
الفصل 1. تعريفات أساسية
المجموعات والتعيينات متعددة القيم
رسم بياني. المسارات والخطوط
سلاسل وحلقات
الفصل 2
شبه ترتيب محدد بواسطة رسم بياني
الرسم البياني الاستقرائي والقواعد
الفصل 3
Grundy للرسم البياني اللانهائي
اعتبارات عامة للرسوم البيانية اللانهائية
الوظيفة الترتيبية
وظائف غراندي
العمليات على الرسوم البيانية
الفصل 4
رقم سيكلوماتيك
عدد لوني
رقم الاستقرار الداخلي
رقم الاستقرار الخارجي
الفصل 5
نظريات الوجود والتفرد
التطبيق على وظائف غراندي
الفصل 6
لعبة نيم
تعريف عام للعبة (بتفاصيل كاملة)
الاستراتيجيات
الفصل 7
العمليات على مراحل بعض التعميمات
الفصل 8. شبكات النقل
مشكلة التدفق الأكبر مشكلة التدفق الأقل
مشكلة التدفق المتوافق متعدد القيم
شبكات نقل لا نهاية لها
الفصل 9
درجة الخروج والدخول
الفصل 10
مشكلة المطابقة الأكبر
قصور بسيط في الرسم البياني
الخوارزمية المجرية
التعميم على الحالة اللانهائية
تطبيق على نظرية المصفوفة
الفصل 11. العوامل
مسارات هاميلتونيان وخطوط هاملتونيان
إيجاد عامل
البحث عن رسم بياني جزئي باستخدام أنصاف درجات معينة
الفصل الثاني عشر
المراكز
نصف القطر
الفصل 13
الخصائص العامة للرسوم البيانية المتصلة بقوة بدون حلقات
قطر الدائرة
الفصل 14
تطبيق عمليات المصفوفة التقليدية
عد المهام
مشكلة القائد
تطبيق العمليات المنطقية
الفصل الخامس عشر
المصفوفات أحادية الطراز تمامًا
أنظمة أحادية تمامًا
المصفوفات السيكلوماتيكية
الفصل السادس عشر
الأشجار
دراسة تحليلية
أشجار كبيرة
الفصل السابع عشر
دورات أويلر ملامح أويلر
الفصل الثامن عشر
نظرية الدوائر المتناوبة
إيجاد رسم بياني جزئي بدرجات معينة من الرؤوس
مطابقة مثالية
تطبيق لعدد من الاستقرار الداخلي
الفصل التاسع عشر
دورات هاميلتونية وعوامل العوامل
شرط ضروري وكاف لوجود عامل
الفصل 20
نقاط مفصلية
الرسوم البيانية بدون مفاصل
الرسوم البيانية المتصلة ح
الفصل 21
الخصائص الأساسية
تعميم
الاضافات
I. خارج النظرية العامة ، الألعاب
ثانيًا. حول مهام النقل
ثالثا. حول استخدام مفاهيم الإمكانات في شبكات النقل
رابعا. مشاكل غير محلولة وافتراضات غير مثبتة
V. حول بعض المبادئ الأساسية للعد (J. Riga)
السادس. إضافات إلى الترجمة الروسية (A.A. Zykov و G.I. Kozhukhin)
الأدب
نظرية الرسم البياني وكتاب ك.بيرزه (خاتمة للترجمة الروسية)
فهرس الرمز
فهرس الاسم
دليل الموضوع.

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

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

خلاصة

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

إجراء:

Zudina T.V.

فلاديمير 2001

1 المقدمة

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

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

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

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

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

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

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

§1. تاريخ نظرية الجرافيك.

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

"مرة واحدة عرضت علي مشكلة جزيرة تقع في مدينة كونيغسبيرج ومحاطة بنهر يتم إلقاء سبعة جسور عبره. والسؤال هو ما إذا كان بإمكان أي شخص تجاوزها باستمرار ، ويمر مرة واحدة فقط عبر كل جسر. حتى الآن لم يفعل تمكنت من القيام بذلك ، لكن لم يثبت أحد أنه مستحيل ، إلا أن هذا السؤال ، على الرغم من كونه مبتذلاً ، يبدو لي أنه يستحق الاهتمام لأنه لا الهندسة ولا الجبر ولا الفن الاندماجي كافيين لحلها ... بعد الكثير من المداولات ، وجدت قاعدة سهلة ، تستند إلى دليل مقنع تمامًا ، وبمساعدة في جميع المشكلات من هذا النوع ، يمكن للمرء أن يقرر على الفور ما إذا كان يمكن إجراء مثل هذه الدائرة من خلال أي عدد والجسور الموجودة بشكل تعسفي أم لا. بحيث يمكن تمثيلهم في الشكل التالي[رسم بياني 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.يسمى مضلع الرسم البياني المستوي الذي لا يحتوي على أي رؤوس أو حواف للرسم البياني بداخله حافة .