نظرية البيان

قالب:بطاقة تخصص قالب:عن

في الرياضيات، نظرية البيان هي دراسة البيانات (جمع بيان) بوصفها بنى رياضية تستعمل لنمذجة العلاقة المتبادلة بين الأغراض. يتكوَّن البيان من رؤوس، تُسمَّى أيضاً عقداً، ووصلات تُسمَّى أيضاً عقداً أو أقواساً.

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

التسمية

تتفق أغلب المعجمات العربية المتخصصة على ترجمة كلمة قالب:إنج إلى (نظرية).^{[عر ١]} ولكنها تختلف في تعريب المصطلح قالب:إنج:

يستعمل معجم مصطلحات الرياضيات الصادر عن مجمع اللغة العربية بدمشق مصطلح (بيان) مقابلاً عربياً ويبني منه مصطلح نظرية البيان،^{[عر ٢]}، ويتفق معه المعجم الموحد لمصطلحات الرياضيات والفلك الصادر عن مكتب تنسيق التعريب فيذكر بيان ورسم بياني مقابلاً للمصطلح الأجنبي.^{[عر ٣]}
أما مجمع اللغة العربية بالقاهرة فيعتمد مصطلح الشكل البياني والرسم البياني، ويجعل المصطلح المقابل للنظرية نظرية الرسوم أو نظرية المخططات.^{[عر ٤]}
يقترح معجم مصطلحات المعلوماتية الصادر عن الجمعية العلمية السورية للمعلوماتية مصطلح (مِبيَان) أيضاً.^{[عر ٥]}

التعريف

البيان غير المُوجَّه

يُعرَّف البيان $G = (V, E)$ بأنه زوجان مرتبان:^[١]

مجموعة $V$ من الرؤوسقالب:ملا (تسمَّى أيضاً عقداً أو نقاطاً);
مجموعة من الوصلات $E$ ،قالب:ملا تُسمَّى أيضاً أحرفاً^{[عر ٦]} أو خطوط، يُمثَّل كل منها قالب:وإو من الرؤوس، أي أن الوصلة تربط بين رأسين متمايزين. تُعرَّف الوصلة كما يأتي:

قالب:وسط

الاسم الدقيق للكائن الرياضي المُعرَّف بالعلاقة السابقة، لو كان استعمال كلمة بيان مُلبساً مع أنواع أخرى من البيانات، هو بيان بسيط غير مُوجَّه.قالب:ملا

من أجل وصلة ${x, y}$ ، يسمى الرأسان $x$ و $y$ طرفينقالب:ملا. ويُقبل القول أن الوصلة التي تصلقالب:ملا بين الرأسين هي التقاء أو تلاقٍقالب:ملا بين الرأسين $x$ و $y$ .

يمكن نظرياً، حسب هذا التعريف، أن يضم البيان رأساً لا يتصل مع أي رأس آخر، ولكن لا يمكن أن يضم هذا البيان وصلة مضاعَفةقالب:ملا، وهي وصلة تصل الرأس مع نفسه.

قالب:عدة صور يمكن تعميم التعريف ليشمل الوصلات المضاعفة بجعل البيان ثلاثية مرتبةقالب:ملا $G = (V, E, ϕ)$ تتكون من:^[٢]

مجموعة من الرؤوس $V$ .
مجموعة من الوصلات $E$ .
دالة التقاءقالب:ملا $ϕ$ ، تطابق كل وصلة مع زوجين غير مرتبين من الرؤوس المتمايزة، كما يأتي:

قالب:وسط

الاسم الدقيق للكائن الرياضي المُعرَّف بالعلاقة السابقة، هو بيان مُتعدِّد الوصلات غير مُوجَّه، أو اختصاراً بيان مُتعدِّد غير مُوجَّه.قالب:ملا

قالب:وإو قالب:ملا قالب:جمع هي وصلة تربط الرأس مع نفسه. لا يمكن أن يضم البيان عُرَى حسب التعريفين أعلاه، لأن هذا يعني أن الرأس $x$ هو نفسه الرأس $y$ ، وهذا لا يتفق مع الشرط الذي يحدد العضوية في مجموعة الرؤوس $V$ . ليشمل التعريف العُرَى، يلزم توسيعه كما يأتي:

من أجل البيان البسيط غير المُوجَّه، يُعدَّل تعريف مجموعة الوصلات $E$ ليصبح:

قالب:وسط

من أجل البيان المُتعدِّد غير المُوجَّه، يُعدَّل تعريف دالة الالتقاء $ϕ$ ليصبح:

قالب:وسط

الاسم الدقيق للكائن الرياضي المُعرَّف بالعلاقة السابقة، هو بيان بسيط غير موجه يسمح بالعُرَى.قالب:ملا.

تعامل مجموعتا الرؤوس $V$ والوصلات $E$ معاملة المجموعات المحدودة عادةً، ويُفترض أيضاً أن مجموعة الرؤوس ليست خالية، ولا يوجد قيود على كون مجموعة الوصلات خالية. مرتبةقالب:ملا البيان هي عدد رؤوسه $| V |$ . أما حجمقالب:ملا البيان فهو عدد وصلاته $| E |$ .

درجة رأس في بيانقالب:ملا هي عدد الوصلات التي تتلاقى عنده، مع الانتباه إلى أن كل عروة تُحصى مرتين. درجة البيان هي أعلى درجة لرؤوسه. من أجل بيان بسيط غير موجه من المرتبة $n$ ، فإن الدرجة القصوى الممكنة لكل رأس هي $n - 1$ وحجم البيان الأقصى هو $\frac{n (n - 1)}{2}$ .

تُنشئ وصلات البيان البسيط غير الموجه الذي يسمح بالعُرَى علاقة متجانسة رمزها $\sim$ بين رؤوس البيان تُسمَّى علاقة التجاور، ويعبَّر عن ذلك بالصيغة $x \sim y$ من أجل وصلة $(x, y)$ طرفاها $x$ و $y$ ويُقال أنهما متجاوران.قالب:ملا قالب:تحديد

البيان المُوجَّه

قالب:مفصلة

البيان الموجهقالب:ملا $G$ هو بيان يوجد لكل وصلة فيه اتجاه محدد واحد أو اتجاهان،^[٣] يتكون البيان $G = (V, E)$ من زوجين مرتبين كما يلي:

مجموعة من الرؤوس $V$ .
مجموعة من الوصلات $E$ ، تُسمَّى أيضاً الوصلات الموجهةقالب:ملا، وهي زوجان مُرتَّبان من الرؤوس المتمايزة يتصل أحدها مع الآخر، وتُعرَّف كما يأتي:

قالب:وسط

الاسم الدقيق للكائن الرياضي السابق هو بيان بسيط موجَّه.قالب:ملا في نظريتي الزُّمر والمجموعات، يعني الحد $V^{n}$ مجموعة مكونة من $n$ عنصراً مأخوذاً من $V$ ، مع عدم اشتراط تمايزها بعضها عن بعض.

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

يمكن تعميم التعريف ليشمل الوصلات المضاعفة بجعل البيان ثلاثية مرتبةقالب:ملا $G = (V, E, ϕ)$ تتكون من:^[٣]

مجموعة من الرؤوس $V$ .
مجموعة من الوصلات $E$ .
دالة التقاء $ϕ$ ، تطابق كل وصلة مع زوجين مرتبين من الرؤوس المتمايزة، كما يأتي:

قالب:وسط

الاسم الدقيق للكائن الرياضي المُعرَّف بالعلاقة السابقة، هو بيان مُتعدِّد الوصلات غير مُوجَّه، أو اختصاراً بيان مُتعدِّد غير مُوجَّه.قالب:ملا.

يُعمم تعريف قالب:وإو قالب:جمع المُستعمل مع البيان المُوجَّه على البيان غير الموجه: وصلة تربط الرأس مع نفسه. لا يمكن أن يضم البيان غير المُوجَّه عُرَى حسب التعريفين أعلاه، لأن هذا يعني أن الرأس $x$ هو نفسه الرأس $y$ ، وهذا لا يتفق مع الشرط الذي يحدد العضوية في مجموعة الرؤوس $V$ . ليشمل التعريف العُرَى، يلزم توسيعه كما يأتي:

من أجل البيان البسيط المُوجَّه، يُعدَّل تعريف مجموعة الوصلات $E$ ليصبح:

قالب:وسط

من أجل البيان المُتعدِّد غير المُوجَّه، يُعدَّل تعريف دالة الالتقاء $ϕ$ ليصبح:

قالب:وسط

الاسم الدقيق للكائن الرياضي المُعرَّف بالعلاقة السابقة، هو بيان بسيط مُوجَّه يسمح بالعُرَى.قالب:ملا.

يمكن تعميم علافة التجاوز المُعرَّفة للبيان غير المُوجَّه على البيان المُوجَّه.

المسالك وأنواعها

تُفرِّق نظرية البيان بين المسلك والمسار والطريق والدارة والدورة:

المسلكقالب:ملا هو تتابع محدود الطول من الرؤوس والوصلات. طول المسلك هو عدد الوصلات فيه، ولا قيود على تكرار مرور المسلك بالرأس أو الوصلة أكثر من مرة. يوصف المسار بأنه مفتوح قالب:إنج لو كان طوله مغايراً للصفر وكانت نقطة بدايته مغايرة لنقطة نهايته، ويوصف بأنه مغلق قالب:إنج لو كان طوله مغايراً للصفر وكانت نقطة بدايته هي نفسها نقطة نهايته. رياضياً، يمكن أن يُعرَّف المسلك في بيان $G = (E, V, ϕ)$ كما يلي:

تتابع الوصلات $e_{1}, e_{2}, . . . e_{n}$ الذي يرتبط مع تتابع من الرؤوس $v_{1}, v_{2}, . . . v_{n}$ بدالة الالتقاء $ϕ (e_{i}) = {a_{i}, a_{i + 1}}$ ^[٤]
متتالية متناوبة من الوصلات والرؤوس ${v_{0}, e_{1}, v_{1}, e_{2}, v_{2} . . . v_{n}}$ تربط فيه كل $e_{i}$ بين $e_{i} + 1$ و $v_{i}$ من أجل $i = 1, 2 . . . n$ .^{[عر ٧]}

الطريق^{[عر ٨]} أو الرحلة^{[عر ٩]} قالب:ملا هي مسلك مفتوح لا تتكرر فيه الوصلات، ولكن يمكن أن تتكرر رؤوسه. رياضياً، يُشترط أن تكون الوصلات في التتابع $e_{1}, e_{2}, . . . e_{n}$ متمايزة ليصبح المسلك طريقاً.^[٤] يمكن تمثيل الشرط رياضياً: $e_{i} \neq e_{j}$ من أجل $i \neq j$ .^{[عر ٨]}
المسارقالب:ملا هو مسلك لا تتكرر فيه الوصلات، ولا الرؤوس ما خلا رأس البداية. إن لم يتكرر رأس البداية، كان المسار مفتوحاً، وإن تكرر يكون المسار مغلقاً ويُسمَّى دورة قالب:إنج. رياضياً، يُشترط أن تكون الوصلات في التتابع $e_{1}, e_{2}, . . . e_{n}$ والرؤوس $v_{1}, v_{2}, . . . v_{n}$ متمايزة ليصبح المسلك مساراً.
الدارة قالب:إنج هي بيان جزئيقالب:ملا $G^{'}$ من البيان $G$ لا تتكرر فيه الوصلات أبداً، ولكن قد تتكرر رؤوسه. لو تكرر رأس البداية فيه ليكون مسار النهاية نفسه، فإن الدارة تسمى دارة بسيطة أو دورة.^[٥]

نبذة تاريخية

يُنظر إلى الورقة البحثية التي نشرها ليونهارت أويلر سنة 1736م عن جسور كونيغسبرغ السبعة على أنها أقدم دراسة معروفة في نظرية البيان.^[٦] عمم كوشي^{[فر ١]} وقالب:وإو^[٧] الصيغة التي وضعها أويلر لحساب عدد وصلات عديد وجوه ورؤوسه ووجوهه، وينظر إلى هذا العمل على أنه ميلاد فرع جديد في الرياضيات هو الطوبولوجيا.

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

صاغ جيمس سيلفستر مصطلح (البيان) للمرة الأولى في ورقة بحثية نشرها سنة 1878م في مجلة الطبيعة، شبَّه فيها بين الثوابت الكمية والمتغيرات المشتركة في الجبر ومخططات الجزيئات، وجاء في النص:^[١٠]

قالب:اقتباس خاص

وضع دينس كونيغ أول كتاب مخصص لنظرية البيان، ونشره بالألمانية سنة 1936م بعنوان قالب:ألمانية ومعناها: نظرية البيانات المنتهية وغير المنتهية.^[١١]

مبرهنة الألوان الأربعة هي واحدة من أشهر المسائل المرتبطة بنظرية البيان، وهي تحاول حل المشكلة التالية: هل يكفي استعمال أربعة ألوان فقط لتلوين خريطة ثنائية الأبعاد مقسَّمة إلى أقاليم تلويناً لا يكون فيه لأي إقليمين يشتركان بحدود اللون نفسه. طرح فرنسيس غوثري هذه المشكلة سنة 1852م، وصاغها أغسطس دي مورغان في رسالة وجهها إلى وليم هاملتون في العام نفسه. اقترحت براهين عديدة لحل المسألة ولكنها كان غير صحيحة، وبقيت هذه المشكلة من غير لأكثر من قرن حتى العام 1969م عندما نشر قالب:وإو طريقة للحل باستعمال الحاسوب.^[١٢] ثُمَّ أثبت كينيث أبيل وقالب:وإو صحة طريقة هيش ببرهان رياضي بمعونة الحاسوب سنة 1976م.^[١٣]