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

تصغير|بيان فيه 6 رؤوس و7 وصلات

في الرياضيات المتقطعة، وخاصة في نظرية البيان، البيان بنية مكونة من مجموعة الأغراض التي ترتبط بعضها مع بعض بوصلات. تُمثَّل الأغراض بمفهوم مجرَّد يُسمَّى الرأس والروابط بمفهوم آخر يُسمَّى الوصلة. يُصوَّر البيان عادة برسم توضيحي فيه مجموعة من النقاط أو الدوائر تُمثِّل الرؤوس مرتبطةٌ بعضها مع بعض بخطوط مستقيمة أو منحنية تُمثِّل الوصلات.

## التسمية
يُسمَّى البيان ، ويذكر معجم أكسفورد الكبير للغة الإنكليزية أن معنى هذه الكلمة: "نوع من المخططات الرمزية (مستعملة في الرياضيات والكيمياء ... إلخ)، يُعبَّر فيه عن نظام من الوصلات بنقاط أو دوائر تتصل أزواج منها ببعضٍ بخط واحد أو أكثر". كما يذكر أن أقدم استعمال مُوثَّق لهذه الكلمة بهذا المعنى يرجع إلى ورقة بحثية نشرها جِمس سِلفستر سنة 1878م في الدورية الأمريكية للرياضيات.

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

## تعاريف
### البيان
تصغير|مثال عن بيان: مجموعة الرؤوس: <math>\{U, V, W, X\}</math>، مجموعة الوصلات <math>\{a, b, c, e, d, f\}</math>، المجموعة <math>\{a, b\}</math> وصلة متعددة نقطتاها الطرفيتان: <math>U</math> و<math>V</math>، والوصلة <math>c</math> عروة.
يتكون البَيان G=(V,E) من مجموعتين من V وE، تُسمَّى الأولى مجموعة الرؤوس، التي تسُمَّى أيضًا عُقَدًا، والثانية مجموعة الوصلات،، يُلحق بكل وصلة مجموعة فيها رأس واحدٌ على الأقل، تُسمَّى مجموعة النقاط الطرفية، ويُقال بأن الوصلة تصِل بين نقاطها الطرفية، وبأن الرأس الذي يُشكِّل نقطة طرفية لوصلة يقع عليها، والعكس بالعكس: الوصلة تقع على الرأس. يُقال أن الرأسين اللذين تصل بينهما وصلة جارين أو متجاورين، وبالمثل يُقال أن الوصلتين اللتين تشتركان بنقطة طرفية متجاورتان.

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

يُسمَّى البيان الذي لا عُرى فيه ولا وصلات متعددة بيانًا بسيط أما البيان الذي له رأس واحد ليس فيه أي وصلة فيسمَّى بيانًا تافهًا، أما إذا كان البيان لا يتضمَّن أي وصلة، فيُسمَّى بيانًا صفريًا.. مع أن مُصطلَح (البيان) يُعني ضمنًا إمكانية وجود عُرى وصلات متعددة، فإن مُصطلَحًا آخرَ يُستعمل في هذا الصدد عند الحاجة لتأكيد هذه المفاهيم هو البيان العام. أما البيان الذي لا عُرى فيه فيُسمَّى البيان عديم العُرى وأيضًا البيان المُتعدِّد، ويُبنى عليه تعريف : بيان عديم العُرى له رأسان فقط تصل بينهما n وصلة، رمزه D_n. أما  فهو بيانٌ وحيد العقدة له n عُروة.


General Graph.svg| بيان عام، مجموعة الوصلات \{uv, vw, vx, wx\}
Dipole Graph D3.svg| بيان ثنائي القطب ثلاثي الوصلات D_3
Bouquet Graph D4.svg| بيان الباقة رباعي العُرى B_4


يُعرَّف البيان البسيط G=(V,E) رياضيًا بأنه زوجان مرتبان:
* مجموعة V من الرؤوس.
* مجموعة من الوصلات E، يُمثَّل كل منها  من الرؤوس، أي أن الوصلة تربط بين رأسين متمايزين. تُعرَّف الوصلة كما يأتي:

يمكن تعميم التعريف ليشمل الوصلات المتعددة والعُرَى بجعل البيان ثلاثية مرتبة G=(V,E,\phi) تتكون من:

* مجموعة من الرؤوس V.
* مجموعة من الوصلات E:

* دالة التقاء \phi، تطابق كل وصلة مع زوجين غير مرتبين من الرؤوس المتمايزة، كما يأتي:

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

تصغير|بيان مُوجَّه عام فيه 3 رؤوس <math>\{u, v, w\}</math> و5 وصلات <math>\{a, b, c, d, f\}</math> منها وصلة متعددة <math>\{d, f\}</math> وعروة <math>a</math>.
الأصل في البيان أن تُنشئ الوصلة مسارًا ثنائي الاتجاه بين رأسين، ولكن يمكن أن يكون للوصلة اتجاه مُحدَّد من رأس إلى آخر، تسمَّى الوصلة عندها قوسًا، ويُسمَّى الرأس الذي تنطلق الوصلة منه صدرًا والرأس الذي تصل إليه عجزًا ، أما البيان الذي تكون وصلاته من هذا النوع بيانًا موجَّهًا ويُعبَّر بالرسم عن اتجاه الوصلة برأس سهم يُشير إلى العجز دومًا ويُوضع على الخط الذي يُمثِّل الوصلة.

يَصح أن يُسمَّى البيان الذي تكون وصلاته غير موجَّهة بالبيان غير الموجَّه، أما إذا حوى البيان على وصلات موجهة وأخرى غير مُوجَّهة، فإنه يُسمَّى بيانًا مُختلَطًا لكل بيانٍ مُوجَّه أو مختلط بيانٌ تحتيّ، وهو بيان نُزِع اتجاه وصلاته فأصبح غير مُوجّه.

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


Underlying Graph.svg|بيان مُوجَّه (يسار) وبيانه التحتي (يمين)
Simple digraph whose underlying graph is not simple.svg|بيان موجَّه بسيط بيانه التحتي ليس بسيطًا


يُعرَّف البيان المُوجَّه G=(V,E) رياضيًا بأنه زوجان مرتبان كما يلي:

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

يمكن تعميم التعريف ليشمل الوصلات المضاعفة والعُرى بجعل البيان ثلاثية مرتبة G=(V,E,\phi) تتكون من:

* مجموعة من الرؤوس V.
* مجموعة من الوصلات E:

* دالة التقاء \phi، تطابق كل وصلة مع زوجين مرتبين من الرؤوس المتمايزة، كما يأتي:

### البيان الجزئي
تصغير|180بك|البيان H1 بيانٌ جزئي باسط (ليس مُحدَُث) من G والبيان H2 بيان جزئيٌ مُحدَث من G (ليس باسطًا)
البيان الجُزئي H من بيان G بيانٌ تكون رؤوسه V_H \sub V_G وحروفه E_H \sub E_G. أما البيان الجُزئي المُحدَث لمجموعة رؤوس W = \{w_1, ... ,w_k \}، ورمزه G(W)، فهو بيانٌ جزئي يضم مجموعة الرؤوس W وكل الوصلات المرتبطة بها. أما البيان الجزئي الباسط فهو بيان جزئي H من بيان G يُحقِّق V(H) = V(G). أما مُرَكِّبة بيانٍ G فهي بيان جُزئي مترابط منه دون أن يكون محتوىً تمامًا في أي بيان جزئي مترابط آخر، أي أنه بيان جزئي مترابط أعظم من البيان G.

## الخواص
### درجة الرأس

درجة رأس بيان v  هي عدد الوصلات الفعلية تتلاقى فيه مضافًا لها ضعفا عدد العُرى، أي أن درجة الرأس في البيان البسيط هي عدد جيرانه. أما متتالية درجات بيان فتشَأ بترتيب درجات رؤوسه ترتيبًا تصاعديًا. أما في البيان المُوجَّه، فتُعرَّف درجة الدخول لرأس ما بأنها عدد الوصلات المُوجَّهة إليه من رؤوس أخرى، ودرجة الخروج بأنها عدد الوصلات الموجَّهة منه إلى رؤوس أخرى. تعدُّ العروة عند حساب درجة رؤوس بيان مُوجَّه مرتين: مرة باعتبارها داخلة ومرة باعتبارها خارجة.

### المسالك وأنواعها
يُعرَّف المسلك والمسار والطريق والدارة والدورة كما يأتي:
تصغير|الفرق بين المسلك والمسار والطريق والدارة والدورة مع خواص كل منها ومثال.
* المسلك متتالية محدودة الطول من الرؤوس والوصلات. طول المسلك هو عدد الوصلات فيه، ولا قيود على تكرار مرور المسلك بالرأس أو الوصلة أكثر من مرة. يوصف المسار بأنه مفتوح لو كان طوله مغايراً للصفر وكانت نقطة بدايته مغايرة لنقطة نهايته، ويوصف بأنه مُغلَق لو كان طوله مغايراً للصفر وكانت نقطة بدايته هي نفسها نقطة نهايته. رياضياً، يمكن أن يُعرَّف المسلك في بيان G=(E,V, \phi)  بطريقتين كما يلي:
::# متتالية الوصلات e_1, e_2, ... e_n التي ترتبط مع متتالية الرؤوس v_1, v_2, ... v_n بدالة الالتقاء \phi(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 لا تتكرر فيه الوصلات أبداً، ولكن قد تتكرر رؤوسه. لو تكرر رأس البداية فيه ليكون مسار النهاية نفسه، فإن الدارة تسمى دارة بسيطة أو دورة.

### المسافة بين رأسين

المسافة بين رأسين في بيان ما هي طول أقصر مسلك يصل بينهما. أما المسافة الموجهة من رأس ما u إلى رأس آخر v في بيانٍ مُوجَّه فهي طول أقصر مسلكٍ مُوجَّهٍ يصل بينهما. يُوصَف البيان بأنه مترابط إذا وجد مسلك بين أي زوحين من الرؤوس فيه. أما البيان المُوجَّه فيوصف بأنه:
* ضعيف الترابط: إذا كان بيانه التحتي مُتصِلًا.
* قوي الترابط: إذا وُجِد مسلك موجَّه بين بين زوجين من الرؤوس فيه.

يُعرَّف التباعد المركزي لرأس ما في بيان مترابط بأنه المسافة التي تفصل هذا الرأس عن أبعد رأس عنه، ويُعرَّف نصف قطر البيان بأنه قيمة أصغر تباعد مركزي فيه، وقطره بأنه قيمة أكبر تباعد مركزي فيه.

### تماكل بيانين

300بك|تصغير|مثال عن بيانين متماكلين مع أن شكلهما يبدو مختلفًا، رُقِّمت الرؤوس لتسهيل تبيان التماكل.
تماكل (تماثل شكل) بيانين G وH، يعني تطابقهما بنيويًا: رأس لرأس ووصلة لوصلة، ويُقال عندها أن البيانين متماكلان،، ويكتب ذلك:  H\cong G.

يُعرَّف تماكل بيانين بسيطين، G وH، رياضيًا بأنه دالة تقابل \phi للرؤوس معرَّفة كما يأتي: \phi: V_G \rarr V_H، من أجل أي رأسين u, v \isin V_G يكون الرأس u مجاورًا للرأس v، إذا وفقط إذا، كان \phi(u) مجاورًا لـ \phi(v) في البيان H. توجد بالمثل أيضًا دالة تقابل للوصلات E_G \rarr E_H يكون فيها uv \rarr \phi(u)\phi(v).

أما تماكل بيانين عامين، G وH، فيُعرَّف رياضيًا بأنه بأنه دالتي تقابل \phi_v: V_G \rarr V_H و\phi_E: E_G \rarr E_H يقنرن فيه كل زوجين من الرؤوس u, v \isin V_G وما بينهما من الوصلات من E_G، اقترانًا تقابليًا مع مجموعة وصلات من E_H تربط بين الرأسين \phi(u) و\phi(v).

تُعرَّف مصفوفة التجاور A_G (i,j) أبعادها n  \times n لبيان بسيط رؤوسه مرتبة v_1, v_2, ... v_n كما يأتي:

البيانان في الأسفل متماكلان تحت الاقتران التالي:

لو نُقِل الرأس u_4 في البيان G إلى موقع متناظر مرآتيًا بالنسبة للوصلة u_3u_2 ثُمَّ دُوِّر البيان مع حركة عقارب الساعة 90 درجة حول مركز تناظره فإن الناتج سيكون مشابهًا للبيان H. يمكن رياضيًا عمل الانتقال السابق على مصفوفة التجاور A_G بالتبديل بين الصفين u_3 وu_4 ثُمَّ بين العمودين u_3 وu_4، فتؤول المصفوفة A_G إلى A_H.

### تذاكل بيان

تصغير|200بك|مدارا الرأس <math>\{u_1, u_4\}</math> و <math>\{u_2, u_3\}</math> ومدارا الوصلات <math>\{u_1u_2, u_1u_3, u_2u_4, u_3u_4\}</math> و<math>\{u_2u_3\}</math>

تذاكلالبيان وهو تشاكله الذاتي، أي تماكله مع ذاته. يُعرَّف مدار رأسٍ u في بيان G بأنه مجموعة كل الرؤوس v \isin V_G والتي تٌحقِّق تذاكلًا \phi(u) = v، ويُعرَّف مدار حرفٍ d في بيان G بأنه مجموعة كل الحروفe \isin E_G والتي تٌحقِّق تذاكلًا \phi(d) = e. يُوصف بيانٌ ما بأنه انتقالي الرؤوس لو كانت رؤوسه كلها في مدار الرؤوس نفسه، ويوصف بأنه انتقالي الحروف لو كانت حروفه كلها في مدار الحروف نفسه.


Graph isomorphism example.svg|كل من هذين البيانين المتماكلين انتقالي الرؤوس وانتقالي الحروف في الوقت نفسه


## العمليات على البنيان
ليكن البيان G = (V, E)، يُمكن تعريف العمليات التالية عليه:
* إضافة رأس u \notin V  إلى البيان تنتج بيانًا جديدًا مجموعة رؤوسه V \cup {u}  ومجموعة وصلاته E كما هي من غير تغيير، وهذا يعني أن الرأس المُضاف سيكون معزولًا لا تربطه أي وصلة مع البيان الأساس، يُرمز لهذه العملية: G \cup {u} .
* إزالة رأس u \notin V  إلى البيان لا تقتصر على حذف الرأس وحده، بل يلزم إزالة كل الوصلات المرتبطة بهذا البيان، يُرمز لهذه العملية: G - u .
* إضافة وصلة d أو u  للبيان تنتج بيانًا جديدًا مشابًها لـ G يرتبط فيه الرأسان u وv بالوصلة d، أي تكون مجموعة الرؤوس في البيان الناتج هي V نفسها، ومجموعة الوصلات E \cup {d} ، ويُرمز لهذه العملية: G \cup {d} .
* إزالة وصلة d من البيان تعني حذف تلك الوصلة وحدها من البيان مع الإبقاء على الرؤوس الأخرى المتصلة معها ضمن البيان،يُرمز لهذه العملية: G - d . لو كانت إزالة الوصلة تسبب زيادة مركبات البيان، أي تفصله أو تفصل جزءًا منه إلى بيانين جزئيين، فإن الوصلة تُسمَّى وصلة قطع.
* تكميل وصلات البيان، تنتج بيانًا جديدًا \bar{G}، لها رؤوس البيان الأصل نفسها، تضم مجموعة وصلاته كل الوصلات الممكنة بين الرؤوس، إذا وفقط إذا، لم تكن ضمن البيان الأصل.
* ضمُ بيانين، مثلًا G وH، تُنتج بيانًا جديدًا، يُرمز للعملية G + H، وتُعرَّف كما يأتي:

* الجُداء الديكارتي لبيانين، يُنتج بيانًا جديدًا، يُرمز للعملية G \times H، وتُعرَّف كما يأتي:

* اتحاد بيانين G وH، يُنتج بيانًا جديدًا مجموعة رؤوسه هي اجتماع مجموعتي روؤس البيانين الأصل، ومجموعة وصلاته هي اجتماع مجموعتي وصلات البيانين الأصل، يُرمَز للعملية G \cup H.

Graph Edge Complementation.svg|تكميل الوصلات
Join Operation.svg|ضم بيانين
Graph Cartesian Product.svg|الجداء الديكارتي
Graph Union.svg|اتحاد بيانين


## تصنيف البيانات
### البيانات الابتدائية

تُسمَّى هذه البيانات أيضًا وحدات البناء، وتتميز بأنها بيانات تضم عددًا قليلًا من الوصلات أو عددًا غير محدد منها تصل بين عدد محدد من الرؤوس، أو أقل عدد ممكن من الوصلات لعدد محدد الرؤوس:

* البيان التام بيانٌ بسيط يتصل أي زوجين من الرؤوس فيه بوصلة واحدة، لو كان عدد رؤوسه n يُرمز له K_n. أما البيان الموجَّه التام.
* البيان الخالي أو البيان عديم الوصلات  بيانٌ له n رأس وليس له أي ضلعٍ، رمزه \bar{K_n}.
* البيان الصفري بيانٌ ليس فيه رؤوس ولا وصلات، رمزه K_0.
* البيان التافه، بيانٌ فيه رأس واحد، وليس فيه أي وصلة، رمزه K_1.
* البيان ثنائي القطب، بيان متعدد الوصلات فيه رأسان تصل بينهما n وصلة، رمزه D_n.
* بيان الباقة، بيان وحيد الرأس، له n عروة B_n.
* بيان مساري بيان مفتوح يُمثل مسارًا، فيه n رأس وn-1 وصلة، رمزه P_n.
* بيان دوري بيانٌ مغلق فيه n رأس وn وصلة تتموضع لتشكل دورة واحدة، رمزه C_n.

Complete graph example.svg|البيانات التامة الخمسة الأولى: K_1 إلى K_5 يُسمَّى الأول أيضًا بيانًا تافهًا.
Edgeless Graph K6.svg|بيان خالٍ \bar{K_6}
Bouquet Graph B1 to B4.svg|بيانات الباقة الأربعة الأولى B_1 إلى B_4
Connected Graph.svg| بيان دوري ثلاثي الرؤوس C_3
Path Graph P4.svg|بيان مساري رباعي الرؤوس P_4


### البيانات المتناظرة
#### الانتظام
يكون البيان منتظمًا إذا كانت لرؤوسه كلها الدرجة نفسها، ويُوصف بأنه كافي الانتظام إذا كانت درجة رؤوسه (ك).

من أجل ك= 1، 3، 4 على الترتيب، فإن فلا يوجد إلا بيانٌ بسيط واحد رباعي الرؤوس لكل من الحالات السابقة على الترتيب.
مركز|300بك
أما البيان خماسي الرؤوس فله ثلاث حالات انتظام فقط: البيان خماسي الرؤوس الخالي \bar{K_5} (ك = 0)، والبيان الخماسي الحلقي C_5 (ك = 2) والبيان الخماسي التام K_5 (ك = 4).
مركز|300بك
يوجد أيضًا حالتان فقط للبيان البسيط سداسي الرؤوس ثلاثي الانتظام يبينهما الشكل التالي:
مركز|200بك
أما البيان ثماني الرؤوس ثلاثي الاننظام فله 5 حالات يبينها الشكل:
مركز|400بك

#### انتقالية الرؤوس
ترتبط البيانات انتقالية الرؤوس بالجبر والهندسة الرياضية، أشهرها بيان كايلي والبيان الدائر.

## مصطلحات

## المراجع
### فهرس المراجع
;بالعربية

;بالإنجليزية

### معلومات المراجع كاملة
;المقالات

* 
* 
* 

;الكتب
:بالعربية

* 
* 
* 
* 
* 
* 

:بالإنجليزية

* 
* 
* 

تصنيف:نظرية البيان