بيان (رياضيات متقطعة)
المحتويات

بدايةً، في الرياضيات المتقطعة، وخاصة في نظرية البيان، البيان بنية مكونة من مجموعة الأغراض التي ترتبط بعضها مع بعض بوصلات. تُمثَّل الأغراض بمفهوم مجرَّد يُسمَّى الرأس والروابط بمفهوم آخر يُسمَّى الوصلة. يُصوَّر البيان عادة برسم توضيحي فيه مجموعة من النقاط أو الدوائر تُمثِّل الرؤوس مرتبطةٌ بعضها مع بعض بخطوط مستقيمة أو منحنية تُمثِّل الوصلات. ونتناول فيما يلي مزيدًا من التفاصيل.
الانتظام
ومن ناحية أخرى، أما البيان ثماني الرؤوس ثلاثي الاننظام فله 5 حالات يبينها الشكل:
كذلك، يكون البيان منتظمًا إذا كانت لرؤوسه كلها الدرجة نفسها، ويُوصف بأنه كافي الانتظام إذا كانت درجة رؤوسه (ك).
في هذا الإطار، يوجد كذلك حالتان فقط للبيان البسيط سداسي الرؤوس ثلاثي الانتظام يبينهما الشكل التالي:
ومن جهة أخرى، أما البيان خماسي الرؤوس فله ثلاث حالات انتظام فقط: البيان خماسي الرؤوس الخالي (ك = 0)، والبيان الخماسي الحلقي (ك = 2) والبيان الخماسي التام (ك = 4).
ومن جهة أخرى، من أجل ك= 1، 3، 4 على الترتيب، فإن فلا يوجد إلا بيانٌ بسيط واحد رباعي الرؤوس لكل من الحالات السابقة على الترتيب.
البيان
وفي هذا الصدد، إذا وصلت وصلة واحدة بين رأسين، يُقال أنهما متجاوران تجاورًا بسيطًا، وإذا كان الرأسان متمايزين فإن الوصلة تُوصَف بأنها وصلة فعلية، أما لو وصلت وصلات عديدة بين رأسين متطابقين، ليكونا مثلًا: و، فإنها تُسمََّى وصلة متعددة، ويُسمَّى عدد الوصلات بين و بأضعاف الوصلات. أما لو كانت النقطتان الطرفيتان هي العقدة نفسها، فإن الوصلة تُسمَّى عندها عُروَة أو حلقة.
ومن جهة أخرى، يتكون البَيان من مجموعتين من و، تُسمَّى الأولى مجموعة الرؤوس، التي تسُمَّى كذلك عُقَدًا، والثانية مجموعة الوصلات،، يُلحق بكل وصلة مجموعة فيها رأس واحدٌ على الأقل، تُسمَّى مجموعة النقاط الطرفية، ويُقال بأن الوصلة تصِل بين نقاطها الطرفية، وبأن الرأس الذي يُشكِّل نقطة طرفية لوصلة يقع عليها، والعكس بالعكس: الوصلة تقع على الرأس. يُقال أن الرأسين اللذين تصل بينهما وصلة جارين أو متجاورين، وبالمثل يُقال أن الوصلتين اللتين تشتركان بنقطة طرفية متجاورتان.
علاوةً على ذلك، يُسمَّى البيان الذي لا عُرى فيه ولا وصلات متعددة بيانًا بسيط أما البيان الذي له رأس واحد ليس فيه أي وصلة فيسمَّى بيانًا تافهًا، أما إذا كان البيان لا يتضمَّن أي وصلة، فيُسمَّى بيانًا صفريًا.. مع أن مُصطلَح (البيان) يُعني ضمنًا إمكانية وجود عُرى وصلات متعددة، فإن مُصطلَحًا آخرَ يُستعمل في هذا الصدد عند الحاجة لتأكيد هذه المفاهيم هو البيان العام. أما البيان الذي لا عُرى فيه فيُسمَّى البيان عديم العُرى وأيضًا البيان المُتعدِّد، ويُبنى عليه تعريف : بيان عديم العُرى له رأسان فقط تصل بينهما وصلة، رمزه . أما فهو بيانٌ وحيد العقدة له عُروة.
مجموعة من الرؤوس.
علاوةً على ذلك، مجموعة من الوصلات ، يُمثَّل كل منها من الرؤوس، أي أن الوصلة تربط بين رأسين متمايزين. تُعرَّف الوصلة كما يأتي:
من جانب آخر، يمكن تعميم التعريف ليشمل الوصلات المتعددة والعُرَى بجعل البيان ثلاثية مرتبة تتكون من:
يُعرَّف البيان البسيط رياضيًا بأنه زوجان مرتبان:
- مجموعة من الرؤوس .
- مجموعة من الوصلات :
- دالة التقاء ، تطابق كل وصلة مع زوجين غير مرتبين من الرؤوس المتمايزة، كما يأتي:
تماكل بيانين
ومن ناحية أخرى، تماكل (تماثل شكل) بيانين و، يعني تطابقهما بنيويًا: رأس لرأس ووصلة لوصلة، ويُقال عندها أن البيانين متماكلان،، ويكتب ذلك: .
من جهة ثانية، أما تماكل بيانين عامين، و، فيُعرَّف رياضيًا بأنه بأنه دالتي تقابل و يقنرن فيه كل زوجين من الرؤوس وما بينهما من الوصلات من ، اقترانًا تقابليًا مع مجموعة وصلات من تربط بين الرأسين و.
في هذا الإطار، لو نُقِل الرأس في البيان إلى موقع متناظر مرآتيًا بالنسبة للوصلة ثُمَّ دُوِّر البيان مع حركة عقارب الساعة 90 درجة حول مركز تناظره فإن الناتج سيكون مشابهًا للبيان . يمكن رياضيًا عمل الانتقال السابق على مصفوفة التجاور بالتبديل بين الصفين و ثُمَّ بين العمودين و، فتؤول المصفوفة إلى .
في هذا الإطار، يُعرَّف تماكل بيانين بسيطين، و، رياضيًا بأنه دالة تقابل للرؤوس معرَّفة كما يأتي: ، من أجل أي رأسين يكون الرأس مجاورًا للرأس ، إذا وفقط إذا، كان مجاورًا لـ في البيان . توجد بالمثل كذلك دالة تقابل للوصلات يكون فيها .
البيانان في الأسفل متماكلان تحت الاقتران التالي:
وفي هذا الصدد، تُعرَّف مصفوفة التجاور أبعادها لبيان بسيط رؤوسه مرتبة كما يأتي:
العمليات على البنيان
تصنيف البيانات
وفي هذا السياق، ضمُ بيانين، مثلًا و، تُنتج بيانًا جديدًا، يُرمز للعملية ، وتُعرَّف كما يأتي:
وفي السياق ذاته، إزالة رأس إلى البيان لا تقتصر على حذف الرأس وحده، بل يلزم إزالة كل الوصلات المرتبطة بهذا البيان، يُرمز لهذه العملية: .
ليكن البيان ، يُمكن تعريف العمليات التالية عليه:
في هذا الإطار، إضافة رأس إلى البيان تنتج بيانًا جديدًا مجموعة رؤوسه ومجموعة وصلاته كما هي من غير تغيير، وهذا يعني أن الرأس المُضاف سيكون معزولًا لا تربطه أي وصلة مع البيان الأساس، يُرمز لهذه العملية: .
علاوةً على ذلك، إضافة وصلة أو للبيان تنتج بيانًا جديدًا مشابًها لـ يرتبط فيه الرأسان و بالوصلة ، أي تكون مجموعة الرؤوس في البيان الناتج هي نفسها، ومجموعة الوصلات ، ويُرمز لهذه العملية: .
من جانب آخر، إزالة وصلة من البيان تعني حذف تلك الوصلة وحدها من البيان مع الإبقاء على الرؤوس الأخرى المتصلة معها ضمن البيان،يُرمز لهذه العملية: . لو كانت إزالة الوصلة تسبب زيادة مركبات البيان، أي تفصله أو تفصل جزءًا منه إلى بيانين جزئيين، فإن الوصلة تُسمَّى وصلة قطع.
إضافةً إلى ذلك، الجُداء الديكارتي لبيانين، يُنتج بيانًا جديدًا، يُرمز للعملية ، وتُعرَّف كما يأتي:
في هذا الإطار، اتحاد بيانين و، يُنتج بيانًا جديدًا مجموعة رؤوسه هي اجتماع مجموعتي روؤس البيانين الأصل، ومجموعة وصلاته هي اجتماع مجموعتي وصلات البيانين الأصل، يُرمَز للعملية .
علاوةً على ذلك، تكميل وصلات البيان، تنتج بيانًا جديدًا ، لها رؤوس البيان الأصل نفسها، تضم مجموعة وصلاته كل الوصلات الممكنة بين الرؤوس، إذا وفقط إذا، لم تكن ضمن البيان الأصل.
درجة الرأس
وفي السياق ذاته، درجة رأس بيان هي عدد الوصلات الفعلية تتلاقى فيه مضافًا لها ضعفا عدد العُرى، أي أن درجة الرأس في البيان البسيط هي عدد جيرانه. أما متتالية درجات بيان فتشَأ بترتيب درجات رؤوسه ترتيبًا تصاعديًا. أما في البيان المُوجَّه، فتُعرَّف درجة الدخول لرأس ما بأنها عدد الوصلات المُوجَّهة إليه من رؤوس أخرى، ودرجة الخروج بأنها عدد الوصلات الموجَّهة منه إلى رؤوس أخرى. تعدُّ العروة عند حساب درجة رؤوس بيان مُوجَّه مرتين: مرة باعتبارها داخلة ومرة باعتبارها خارجة.
تذاكل بيان
وعلى صعيد آخر، تذاكلالبيان وهو تشاكله الذاتي، أي تماكله مع ذاته. يُعرَّف مدار رأسٍ في بيان بأنه مجموعة كل الرؤوس والتي تٌحقِّق تذاكلًا ، ويُعرَّف مدار حرفٍ في بيان بأنه مجموعة كل الحروف والتي تٌحقِّق تذاكلًا . يُوصف بيانٌ ما بأنه انتقالي الرؤوس لو كانت رؤوسه كلها في مدار الرؤوس نفسه، ويوصف بأنه انتقالي الحروف لو كانت حروفه كلها في مدار الحروف نفسه.
التسمية
ومن ناحية أخرى، يقترح معجم مصطلحات المعلوماتية الصادر عن الجمعية العلمية السورية للمعلوماتية مصطلح (مِبيَان) كذلك.
أما المعجمات العربية فتختلف في ترجمة المصطلح:
من جهة ثانية، يستعمل معجم مصطلحات الرياضيات الصادر عن مجمع اللغة العربية بدمشق مصطلح (بيان) مقابلاً عربياً ويبني منه مصطلح نظرية البيان،، ويتفق معه المعجم الموحد لمصطلحات الرياضيات والفلك الصادر عن مكتب تنسيق التعريب فيذكر بيان ورسم بياني مقابلاً للمصطلح الأجنبي.
وفي السياق ذاته، يُسمَّى البيان ، ويذكر معجم أكسفورد الكبير للغة الإنكليزية أن معنى هذه الكلمة: "نوع من المخططات الرمزية (مستعملة في الرياضيات والكيمياء ... إلخ)، يُعبَّر فيه عن نظام من الوصلات بنقاط أو دوائر تتصل أزواج منها ببعضٍ بخط واحد أو أكثر". كما يذكر أن أقدم استعمال مُوثَّق لهذه الكلمة بهذا المعنى يرجع إلى ورقة بحثية نشرها جِمس سِلفستر سنة 1878م في الدورية الأمريكية للرياضيات.
تعاريف
ومن ناحية أخرى، أما مجمع اللغة العربية بالقاهرة فيعتمد مصطلح الشكل البياني والرسم البياني، ويجعل المصطلح المقابل للنظرية نظرية الرسوم أو نظرية المخططات.
البيان المُوجَّه
يُعرَّف البيان المُوجَّه رياضيًا بأنه زوجان مرتبان كما يلي:
من جهة ثانية، الأصل في البيان أن تُنشئ الوصلة مسارًا ثنائي الاتجاه بين رأسين، ولكن يمكن أن يكون للوصلة اتجاه مُحدَّد من رأس إلى آخر، تسمَّى الوصلة عندها قوسًا، ويُسمَّى الرأس الذي تنطلق الوصلة منه صدرًا والرأس الذي تصل إليه عجزًا ، أما البيان الذي تكون وصلاته من هذا النوع بيانًا موجَّهًا ويُعبَّر بالرسم عن اتجاه الوصلة برأس سهم يُشير إلى العجز دومًا ويُوضع على الخط الذي يُمثِّل الوصلة.
وفي السياق ذاته، يُمكن تعميم مفاهيم البيان غير المُوجَّه على البيان الموجه: تُسمَّى مجموعة الوصلات المتعددة التي تضم قوسين على الأقل، يصلان بين الصدر والعجز نفسهما بالقوس المتعدِّد، ويُسمَّى القوس عروةً لو كان صدره هو نفسه عجزه، ويُسمَّى البيان غير الموجه الذي لا عُرى فيه ولا أقواس متعددة بالبيان المُوجَّه البسيط.، يلزم الانتباه إلى أن البيان المُوجَّه البسيط يمكن أن يحوي على قوسين يصلان بين الصدر والعجز نفسهما إذا كان لكل منهما اتجاه مختلف.
- مجموعة من الرؤوس .
- مجموعة من الوصلات :
- دالة التقاء ، تطابق كل وصلة مع زوجين مرتبين من الرؤوس المتمايزة، كما يأتي:
في هذا الإطار، يمكن تعميم التعريف ليشمل الوصلات المضاعفة والعُرى بجعل البيان ثلاثية مرتبة تتكون من:
وعلى صعيد آخر، يَصح أن يُسمَّى البيان الذي تكون وصلاته غير موجَّهة بالبيان غير الموجَّه، أما إذا حوى البيان على وصلات موجهة وأخرى غير مُوجَّهة، فإنه يُسمَّى بيانًا مُختلَطًا لكل بيانٍ مُوجَّه أو مختلط بيانٌ تحتيّ، وهو بيان نُزِع اتجاه وصلاته فأصبح غير مُوجّه.
مجموعة من الرؤوس .
علاوةً على ذلك، مجموعة من الوصلات ، ترتبط كل منها بزوجين مُرتَّبين من الرؤوس المتمايزة فتصل أحدها مع الآخر، وتُعرَّف كما يأتي:
البيان الجزئي
ومن جهة أخرى، البيان الجُزئي من بيان بيانٌ تكون رؤوسه وحروفه . أما البيان الجُزئي المُحدَث لمجموعة رؤوس ، ورمزه ، فهو بيانٌ جزئي يضم مجموعة الرؤوس وكل الوصلات المرتبطة بها. أما البيان الجزئي الباسط فهو بيان جزئي من بيان يُحقِّق . أما مُرَكِّبة بيانٍ فهي بيان جُزئي مترابط منه دون أن يكون محتوىً تمامًا في أي بيان جزئي مترابط آخر، أي أنه بيان جزئي مترابط أعظم من البيان .
الخواص
انتقالية الرؤوس
وفي هذا الصدد، ترتبط البيانات انتقالية الرؤوس بالجبر والهندسة الرياضية، أشهرها بيان كايلي والبيان الدائر.
- مصطلحات
- المراجع
- فهرس المراجع
- بالعربية
- بالإنجليزية
- معلومات المراجع كاملة
- المقالات
- الكتب
- بالعربية
المسافة بين رأسين
ومن ناحية أخرى، يُعرَّف التباعد المركزي لرأس ما في بيان مترابط بأنه المسافة التي تفصل هذا الرأس عن أبعد رأس عنه، ويُعرَّف نصف قطر البيان بأنه قيمة أصغر تباعد مركزي فيه، وقطره بأنه قيمة أكبر تباعد مركزي فيه.
علاوةً على ذلك، المسافة بين رأسين في بيان ما هي طول أقصر مسلك يصل بينهما. أما المسافة الموجهة من رأس ما إلى رأس آخر في بيانٍ مُوجَّه فهي طول أقصر مسلكٍ مُوجَّهٍ يصل بينهما. يُوصَف البيان بأنه مترابط إذا وجد مسلك بين أي زوحين من الرؤوس فيه. أما البيان المُوجَّه فيوصف بأنه:
ومن جهة أخرى، قوي الترابط: إذا وُجِد مسلك موجَّه بين بين زوجين من الرؤوس فيه.
ضعيف الترابط: إذا كان بيانه التحتي مُتصِلًا.
المسالك وأنواعها
ومن جهة أخرى، الدارة بيان جزئي من البيان لا تتكرر فيه الوصلات أبداً، ولكن قد تتكرر رؤوسه. لو تكرر رأس البداية فيه ليكون مسار النهاية نفسه، فإن الدارة تسمى دارة بسيطة أو دورة.
في هذا الإطار، متتالية متناوبة من الوصلات والرؤوس تربط فيه كل بين و من أجل .
متتالية الوصلات التي ترتبط مع متتالية الرؤوس بدالة الالتقاء
ومن ناحية أخرى، المسار مسلك لا تتكرر فيه الوصلات، ولا الرؤوس ما خلا رأس البداية. إن لم يتكرر رأس البداية، كان المسار مفتوحاً، وإن تكرر يكون المسار مغلقاً ويُسمَّى دورة. رياضياً، يُشترط أن تكون الوصلات في المتتالية والرؤوس متمايزة ليصبح المسلك مساراً.
من جهة ثانية، الطريق، أو الرحلة ، مسلك مفتوح لا تتكرر فيه الوصلات، ولكن يمكن أن تتكرر رؤوسه. رياضياً، يُشترط أن تكون الوصلات في المتتالية متمايزة ليصبح المسلك طريقاً. يمكن تمثيل الشرط رياضياً: من أجل .
ومن جهة أخرى، المسلك متتالية محدودة الطول من الرؤوس والوصلات. طول المسلك هو عدد الوصلات فيه، ولا قيود على تكرار مرور المسلك بالرأس أو الوصلة أكثر من مرة. يوصف المسار بأنه مفتوح لو كان طوله مغايراً للصفر وكانت نقطة بدايته مغايرة لنقطة نهايته، ويوصف بأنه مُغلَق لو كان طوله مغايراً للصفر وكانت نقطة بدايته هي نفسها نقطة نهايته. رياضياً، يمكن أن يُعرَّف المسلك في بيان بطريقتين كما يلي:
يُعرَّف المسلك والمسار والطريق والدارة والدورة كما يأتي:
البيانات الابتدائية
- البيان الخالي أو البيان عديم الوصلات بيانٌ له رأس وليس له أي ضلعٍ، رمزه .
- البيان الصفري بيانٌ ليس فيه رؤوس ولا وصلات، رمزه .
- البيان التافه، بيانٌ فيه رأس واحد، وليس فيه أي وصلة، رمزه .
- البيان ثنائي القطب، بيان متعدد الوصلات فيه رأسان تصل بينهما وصلة، رمزه .
- بيان الباقة، بيان وحيد الرأس، له عروة .
- بيان مساري بيان مفتوح يُمثل مسارًا، فيه رأس و وصلة، رمزه .
- بيان دوري بيانٌ مغلق فيه رأس و وصلة تتموضع لتشكل دورة واحدة، رمزه .
- البيانات المتناظرة
وفي السياق ذاته، تُسمَّى هذه البيانات كذلك وحدات البناء، وتتميز بأنها بيانات تضم عددًا قليلًا من الوصلات أو عددًا غير محدد منها تصل بين عدد محدد من الرؤوس، أو أقل عدد ممكن من الوصلات لعدد محدد الرؤوس:
وعلى صعيد آخر، البيان التام بيانٌ بسيط يتصل أي زوجين من الرؤوس فيه بوصلة واحدة، لو كان عدد رؤوسه يُرمز له . أما البيان الموجَّه التام.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟