مقالات

5: نظرية الرسم البياني - الرياضيات


لا تزال خريطة النص هذه قيد الإنشاء. يرجى أن يغفر لنا.


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

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

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

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

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

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

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

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

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

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

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

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

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


2. الروابط وهياكلها

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

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

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

سلسلة. سلسلة من الروابط التي لها اتصال مشترك مع الآخر. الاتجاه لا يهم.

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

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

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

زمرة. الزمرة هي مخطط فرعي كامل أقصى حيث يتم توصيل جميع الرؤوس.

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

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

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

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

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


نظرية الرسم البياني B8.5 (2019-2020)

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

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

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

مقدمة: تعريفات وأمثلة أساسية. الأشجار وتوصيفها. يدور أويلر في مسارات ودورات طويلة. تلوينات الرأس: نظرية بروكس ، متعدد الحدود لوني. تلوين الحواف: نظرية فيزينج. الرسوم البيانية المستوية ، بما في ذلك صيغة أويلر ، الرسوم البيانية المزدوجة. أقصى تدفق - نظرية القطع الأدنى: تطبيقات بما في ذلك نظرية مينجر ونظرية هول. نظرية توت في التوفيق. المشاكل المتطرفة: نظرية توران ، مشكلة Zarankiewicz ، نظرية Erd & # 337s-Stone.

يرجى ملاحظة أن إصدارات الكتب الإلكترونية للعديد من الكتب في قوائم القراءة يمكن العثور عليها في SOLO و ORLO.


5: نظرية الرسم البياني - الرياضيات

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

الرسوم البيانية المتكونة من الخرائط بهذه الطريقة لها خاصية مهمة: إنها كذلك مستو.

التعريف 5.10.1 الرسم البياني $ G $ مستوٍ إذا كان من الممكن تمثيله برسم في المستوى بحيث لا تتقاطع أي حواف. $ مربع $

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

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

نظرية 5.10.2 (صيغة أويلر) لنفترض أن $ G $ هو رسم بياني مستو متصل ، مرسوم بحيث لا تتقاطع أي حواف مع رؤوس $ n $ وحواف $ m $ ، وأن الرسم البياني يقسم المستوى إلى مناطق $ r $. ثم $ r = m-n + 2. $

دليل. والدليل عن طريق الاستقراء على عدد الحواف. الحالة الأساسية هي $ m = n-1 $ ، وهو الحد الأدنى لعدد الأضلاع في الرسم البياني المتصل عند رؤوس $ n $. في هذه الحالة ، $ G $ عبارة عن شجرة ، ولا تحتوي على دورات ، وبالتالي فإن عدد المناطق هو 1 ، وبالفعل $ 1 = (n-1) -n + 2 $.

افترض الآن أن $ G $ يحتوي على أكثر من $ n-1 $ edges ، لذلك فهو يحتوي على دورة. قم بإزالة حافة واحدة من دورة تشكل $ G '$ ، وهي متصلة ولها مناطق $ r-1 $ ، ورؤوس $ n $ ، وحواف $ m-1 $. من خلال فرضية الاستقراء $ r-1 = (m-1) -n + 2 $ ، والتي تصبح $ r = m-n + 2 $ عندما نضيف 1 لكل جانب. $ qed $

Lemma 5.10.3 افترض أن $ G $ هو رسم بياني مستو بسيط متصل ، مرسوم بحيث لا تتقاطع أي حواف ، مع رؤوس $ n ge3 $ وحواف $ m $ ، وأن الرسم البياني يقسم المستوى إلى مناطق $ r $. ثم $ m le 3n-6 $.

دليل. لنفترض أن $ f_i $ هو عدد الحواف المجاورة لرقم المنطقة $ i $ إذا كانت نفس المنطقة على جانبي الحافة ، يتم حساب تلك الحافة مرتين. نسمي الحواف المجاورة للمنطقة حواف حدود المنطقة. نظرًا لأن $ G $ بسيط و $ n ge3 $ ، فإن كل منطقة يحدها ما لا يقل عن 3 حواف. ثم $ sum_^ r f_i = 2m $ ، حيث يتم حساب كل حافة مرتين ، مرة واحدة للمنطقة على كل جانب من جوانب الحافة. من $ r = m-n + 2 $ نحصل على 3r = 3m-3n + 6 $ ، ولأن $ f_i ge 3 $ ، $ 3r le sum_^ r f_i = 2m $ ، لذلك $ 3m-3n + 6 le 2m $ ، أو $ m le 3n-6 $ حسب الرغبة. $ qed $

النظرية 5.10.4 $ K_5 $ ليست مستوية.

دليل. $ K_5 $ له 5 رؤوس و 10 حواف ، و $ 10 not le 3 cdot 5-6 $ ، لذلك من خلال lemma ، $ K_5 $ ليس مستويًا. $ qed $

Lemma 5.10.5 إذا كان $ G $ مستويًا ، فإن $ G $ له رأس درجة على الأكثر 5.

دليل. قد نفترض أن $ G $ متصل (إذا لم يكن كذلك ، فاعمل مع مكون متصل بقيمة $ G $). افترض أن $ d (v_i)> 5 $ لكل $ v_i $. ثم 2 مليون دولار = sum_^ n d (v_i) ge 6n $. بواسطة lemma 5.10.3، $ 3n-6 ge m $ so $ 6n-12 ge 2m $. وبالتالي ، فإن 6n le 2m le 6n-12 $ يمثل تناقضًا. $ qed $

نظرية 5.10.6 (نظرية الألوان الخمسة) يمكن تلوين كل رسم بياني مستو بخمسة ألوان.

دليل. يتم الإثبات عن طريق الاستقراء على عدد الرؤوس $ n $ عندما يكون $ n le 5 $ تافهًا.

افترض الآن أن $ G $ مستوٍ على أكثر من 5 رؤوس بواسطة lemma 5.10.5 بعض الرؤوس $ v $ لديها درجة على الأكثر 5. وفقًا لفرضية الاستقراء ، يمكن تلوين $ G-v $ بخمسة ألوان. قم بتلوين رؤوس $ G $ ، بخلاف $ v $ ، حيث يتم تلوينها بخمسة ألوان من $ G-v $. إذا كان $ d (v) le 4 $ ، فيمكن تلوين $ v $ بأحد الألوان الخمسة لإعطاء تلوين مناسب لـ $ G $ مع 5 ألوان. لذلك نفترض الآن أن $ d (v) = 5 دولارات. إذا كان الجيران الخمسة لـ $ v $ ملونين بأربعة ألوان أو أقل ، فيمكن مرة أخرى تلوين $ v $ لإعطاء تلوين مناسب لـ $ G $ مع 5 ألوان.

الآن نفترض أن جميع الجيران الخمسة لـ $ v $ لديهم لون مختلف ، كما هو موضح في الشكل 5.10.4.

لنفترض أنه في $ G $ يوجد مسار من $ v_1 $ إلى $ v_3 $ ، وأن الرؤوس الموجودة على طول هذا المسار ملونة بالتناوب باللونين الأحمر والأخضر. ثم مع $ v $ ، يصنع هذا المسار دورة مع $ v_2 $ في الداخل و $ v_4 $ في الخارج ، أو العكس. هذا يعني أنه لا يمكن أن يكون هناك مسار بديل أرجواني-أزرق من $ v_2 $ إلى $ v_4 $. لنفترض أن $ v_2 $ موجود داخل الدورة ، قمنا بتغيير ألوان جميع الرؤوس داخل الدورة باللون الأرجواني إلى الأزرق ، وأعيد تلوين جميع الرؤوس الزرقاء باللون الأرجواني. لا يزال هذا تلوينًا مناسبًا لجميع رؤوس $ G $ باستثناء $ v $ ، والآن لا يوجد جار لـ $ v $ بنفسجي ، لذلك من خلال تلوين $ v $ Purple ، نحصل على تلوين مناسب لـ $ G $.

إذا لم يكن هناك مسار بديل أحمر-أخضر من $ v_1 $ إلى $ v_3 $ ، فإننا نعيد تلوين الرؤوس على النحو التالي: قم بتغيير لون $ v_1 $ إلى اللون الأخضر. قم بتغيير كل الجيران الأخضر من $ v_1 $ إلى اللون الأحمر. استمر في تغيير ألوان الرؤوس من الأحمر إلى الأخضر أو ​​الأخضر إلى الأحمر حتى لا يكون هناك تعارض ، أي حتى يتم الحصول على تلوين جديد مناسب. نظرًا لعدم وجود مسار بديل أحمر-أخضر من $ v_1 $ إلى $ v_3 $ ، فلن يتغير لون $ v_3 $. الآن لا يوجد جيران $ v $ ملونًا باللون الأحمر ، لذلك من خلال تلوين $ v $ red ، نحصل على تلوين مناسب لـ $ G $. $ qed $


المواضيع التي سيتم تغطيتها

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

1. المفاهيم الأساسية في نظرية الرسم البياني 1.5 أسبوع.

التعاريف والمسارات والدورات والمسارات وتسلسل الدرجات والرسوم البيانية الموجهة والرسوم البيانية المستوية ودورات هاملتون ودوائر أويلر.

2. الأشجار والخوارزميات 2.5 أسبوع.

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

3. التوافقات والعوامل 3 أسابيع.

المطابقات والأغلفة في الرسم البياني الثنائي ، حالة مطابقة Hall و SDR ، نظريات minmax الخاصة بـ Konig ، المجموعات المستقلة والمجموعات المسيطرة ، مطابقة الوزن القصوى والمطابقة المستقرة ، الخوارزميات ، نظرية Tutte's 1-Factor.

4. الرسوم البيانية والتدفق في الشبكة 2 أسبوع.

Digraphs ، The Ford-Fulkerson Theorem ، نظرية التكامل ، العرض والطلب

5. اتصال الرسم البياني أسبوع 1.

اتصال Vertex ، اتصال الحافة ، نظرية مينجر

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

نظرية بروك ، نظرية رامسي وأرقام رامزي ، (اختياري: عرض لنظرية رامزي ، نظرية فان دير ويردين ، بيان الكثافة ، ومبدأ الاكتناز).

7. نظرية توران ونظرية الرسم البياني القصوى 0.5 أسبوع

8. الجبر الخطي في نظرية الرسم البياني 2 أسبوع

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

9. نظرية ديلورث ونظرية المجموعات القصوى 1 أسبوع

مجموعات مرتبة جزئيًا ، نظرية ديلورث ، نظرية إردوس-كو-رادا ، تابلوه يونغ القياسية ، خوارزمية RSK ونظرية شنستد.

المراجع الرئيسية

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

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

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

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

سياسة حقوق النشر: جميع المواد المطبوعة المنشورة في الفصل أو على الويب محمية بموجب قوانين حقوق النشر. يُسمح بنسخة واحدة من برنامج xerox (أو التنزيل من الويب) للاستخدام الشخصي. يمنع منعا باتا النسخ المتعددة أو بيع أي من هذه المواد.

قانون الأمريكيين ذوي الإعاقة (ADA) هو قانون فيدرالي لمكافحة التمييز يوفر حماية شاملة للحقوق المدنية للأشخاص ذوي الإعاقة. من بين أمور أخرى ، يتطلب هذا التشريع أن يتم ضمان بيئة تعليمية لجميع الطلاب ذوي الإعاقة التي توفر الإقامة المعقولة لإعاقاتهم. إذا كنت تعتقد أن لديك إعاقة تتطلب الإقامة ، فيرجى الاتصال بخدمات الإعاقة ، الموجودة حاليًا في مبنى خدمات الإعاقة في خدمات الطلاب بمجمع وايت كريك في الحرم الجامعي الغربي أو اتصل على 979-845-1637. للحصول على معلومات إضافية ، قم بزيارة http://disability.tamu.edu.

  • ادعاءات الاعتداء الجنسي أو التمييز الجنسي أو التحرش الجنسي عندما يتعلق الأمر بطلاب TAMU أو أعضاء هيئة التدريس أو الموظفين أو أطراف ثالثة تزور الحرم الجامعي.

يمكن للطلاب وأعضاء هيئة التدريس الإبلاغ عن السلوك غير الطارئ الذي يتسبب في قلقهم في Tell Somebody.


B8.5 نظرية الرسم البياني - مادة للعام 2020-2021

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

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

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

مقدمة: تعريفات وأمثلة أساسية. الأشجار وتوصيفها. يدور أويلر في مسارات ودورات طويلة. تلوينات الرأس: نظرية بروكس ، متعدد الحدود لوني. تلوين الحواف: نظرية فيزينج. الرسوم البيانية المستوية ، بما في ذلك صيغة أويلر ، الرسوم البيانية المزدوجة. أقصى تدفق - نظرية القطع الأدنى: تطبيقات بما في ذلك نظرية مينجر ونظرية هول. نظرية توت في التوفيق. المشاكل المتطرفة: نظرية توران ، مشكلة Zarankiewicz ، نظرية Erd & # 337s-Stone.


محررون استشاريون

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

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


اتصال الحافة

دع "G" يكون رسمًا بيانيًا متصلًا. يسمى الحد الأدنى لعدد الحواف التي تؤدي إزالتها إلى فصل "G" إلى اتصال الحافة لـ G.

وبعبارة أخرى ، فإن ملف عدد الحواف في أصغر مجموعة قطع من G يسمى اتصال الحافة لـ G.

إذا كانت "G" لها حافة قصوى ، فإن & lambda (G) هي 1. (اتصال حافة G)

ألق نظرة على الرسم البياني التالي. بإزالة حافتين صغيرتين ، يصبح الرسم البياني المتصل غير متصل. ومن ثم ، فإن اتصال الحافة (& lambda (G)) هو 2.

فيما يلي الطرق الأربع لفصل الرسم البياني عن طريق إزالة حافتين & ناقص


جون أورشيل

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

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

فيما يلي بعض المنشورات المختارة:
1. تقديرات الأخطاء الموحدة لطريقة لانكس ، ما قبل الطباعة (2020) [PDF]
2. بخصوص تخمينين على أقسام Clique و Biclique ، ما قبل الطباعة (2020) [PDF]
3. حول توصيف وتفرد الفسيفساء النقطية للفورونوي ، SINUM (2017) [PDF]
4. تعلم عمليات النقطة الحاسمة مع اللحظات والدورات ، ICML (2017) [PDF]
5. التقسيم الطيفي للرسوم البيانية والترابط ، Lin Alg & App (2014) [PDF]

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

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

الجبر الخطي العددي: يهتم مجال الجبر الخطي العددي بشكل أساسي بالحل العددي للأنظمة الخطية Ax = b ومشكلات القيمة الذاتية Ax = & lambdax. تحتوي هذه الحسابات على تطبيقات في الهندسة والعلوم والبيانات الضخمة / التعلم الآلي ، ويركز العمل في هذا المجال على إنتاج وتحليل الخوارزميات التي تنتج تقريبًا جيدًا لحل دقيق بسرعة نسبيًا. يركز بحثي في ​​الغالب على مشاكل القيمة الذاتية المتماثلة. أنا مهتم بشكل خاص بالخوارزميات السريعة لحساب قيم eigenvalues ​​المتطرفة ، مثل طرق Krylov subspace ، وهي تقنية لتقليل الأبعاد لحل نظام خطي أو مشكلة القيمة الذاتية تقريبًا عن طريق التعيين إلى فضاء فرعي منخفض الأبعاد تم اختياره جيدًا. أحد مجالات التطبيق ذات الأهمية الكبيرة بالنسبة لي هو حساب أزواج eigenpairs ذات الطاقة المنخفضة للرسم البياني Laplacians. أثبتت مساحات eigenspace ذات الأبعاد المنخفضة في Laplacian للرسم البياني أنها مفيدة في عدد من المجالات في علم البيانات ، بما في ذلك تضمين الرسم البياني والتقسيم.

منشورات نموذجية:
1. تقديرات الأخطاء الموحدة لطريقة لانكس ، ما قبل الطباعة (2020) [PDF]
2. تتالي Multigrid Alg. لشركات. ناقل Fiedler لـ Graph Lapl. ، J. Comp. الرياضيات (2015) [PDF]
3. طريقة متعددة الشبكات والزمان. من أجل Num. فال. خيارات الحاجز ، بالاتصالات. في الرياضيات. زعنفة. (2013) [PDF]

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

منشورات نموذجية:
1. بخصوص تخمينين على أقسام Clique و Biclique ، ما قبل الطباعة (2020) [PDF]
2. منفصلة تتبع Thms. والحد الأدنى للطاقة. الربيع امبيد. الرسوم البيانية المستوية ، Lin Alg & App (2021) [PDF]
3. التقسيم الطيفي للرسوم البيانية والترابط ، Lin Alg & App (2014) [PDF]

علم البيانات / تعلم الآلة: علم البيانات هو فئة واسعة من التقنيات والأدوات المستخدمة لاستخراج المعلومات المفيدة من مجموعات البيانات (الكبيرة في كثير من الأحيان) ، ومجال التعلم الآلي المرتبط بالخوارزميات التي تتحسن من خلال الخبرة (أي زيادة البيانات). يعد هذا الموضوع من أكثر مجالات البحث شيوعًا وأهمية في القرن الحادي والعشرين. تشمل مجالات اهتمامي التجميع ، وتصور البيانات ، والنماذج الاحتمالية للتعلم الآلي. يتداخل التجميع وتصور البيانات بشكل كبير مع نظرية الرسم البياني ، لكنني أيضًا أدرس عددًا من الأساليب التي لا تحتوي على صياغة رسومية ، مثل التكميم / الوسائل k. A particularly interesting class of probabilistic models are determinantal point processes (DPPs), a class of repulsive models which originated in quantum physics, and provide a strong alternative to graphical models. A DPP model captures negative correlation between a discrete set of objects, and has proven to be extremely useful in a number of applications, including the subset selection problem. The DPP model has an elegant linear algebraic formulation, as, given a set of n objects, the probability of a subset S appearing as a sample is proportional to the associated principal minor of some matrix. My research on DPPs mostly focuses on learning algorithms with proveable guarantees.

Sample Publications:
1. Maximum Likelihood Estimation of Determinantal Point Processes, Preprint (2020) [PDF]
2. On the Characterization and Uniqueness of Centroidal Voronoi Tessellations, SINUM (2017) [PDF]
3. Learning Determinantal Point Processes with Moments and Cycles, ICML (2017) [PDF]

Regarding Two Conjectures on Clique and Biclique Partitions

Uniform Error Estimates for the Lanczos Method

Maximum Likelihood Estimation of Determinantal Point Processes

Discrete Trace Theorems and Energy Minimizing Spring Embeddings of Planar Graphs


with Ludmil Zikatanov
Linear Algebra and its Applications, 2021. [PDF]

Testing Gap k-Planarity is NP-Complete


with Jake Wellens
Information Processing Letters, to appear. [بي دي إف]

Nodal Decompositions of Graphs


Linear Algebra and its Applications, 2018. [PDF]

On the Characterization and Uniqueness of Centroidal Voronoi Tessellations


SIAM Journal on Numerical Analysis, 2017. [PDF]

Learning Determinantal Point Processes with Moments and Cycles


with Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet
Proceedings of the 34th International Conference on Machine Learning (ICML 2017). [بي دي إف]

Rates of Estimation for Determinantal Point Processes


with Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017). [بي دي إف]

On the Approximation of Laplacian Eigenvalues in Graph Disaggregation

On the Maximal Error of Spectral Approximation of Graph Bisection

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

Spectral Bisection of Graphs and Connectedness


with Ludmil Zikatanov
Linear Algebra and its Applications, 2014. [PDF]

A Space-Time Multigrid Method for the Numerical Valuation of Barrier Options


Communications in Mathematical Finance, 2013. [PDF]

Instabilities in the Sun-Jupiter-Asteroid Three Body Problem


with Joseph Galante
Celestial Mechanics and Dynamical Astronomy, 2013. [PDF]

Math 18.03: Differential Equations, MIT, Spring 2018
Role: Recitation Instructor
Subject Evaluation Report: 6.9/7 [PDF]

Math 232: Integral Vector Calculus, Penn State, Fall 2013
Role: Lecturer
Student Rating of Teaching Effectiveness: 6.71/7 [PDF]

Math 041: Trigonometry and Analytic Geometry, Penn State, Spring 2013
Role: Lecturer
Student Rating of Teaching Effectiveness: 6.59/7 [PDF]

© 2020 John C. Urschel -- template shamelessly stolen from Tselil Schramm.


المساهمون

Jonathan L. Gross, Thomas W. Tucker, Lowell W. Beineke, Robin J. Wilson, Jianer Chen, Yuanqiu Huang, Bojan Mohar, R. Bruce Richter, Joan P. Hutchinson, G. Salazar, Tomaž Pisanski, Arjana Žitnik, Jin Ho Kwak, Jaeun Lee, Jozef Širáň, Arthur T. White, M. J. Grannell, T. S. Griggs, Mark E. Watkins, Dan Archdeacon

This title is available for institutional purchase via Cambridge Core

Cambridge Core offers access to academic eBooks from our world-renowned publishing programme.


شاهد الفيديو: البحوث العمليات شرح موضي 1 طريقه الرسم البياني او الطريقه البيانيه إيجاد الداله وقيد الاله الاولى (شهر اكتوبر 2021).