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

الرسم البياني (يُسمى أحيانًا الرسم البياني غير الموجه لتمييزه عن الرسم البياني الموجه ، أو الرسم البياني البسيط لتمييزه عن الرسم البياني المتعدد ) ^{[ 4 ] [ 5 ]} هو زوج G = ( V , E ) ، حيث V هي مجموعة عناصرها تسمى رؤوسًا (مفردها: رأس)، و E هي مجموعة من الأزواج غير المرتبة.${\displaystyle \{v_{1},v_{2}\}}$من الرؤوس، التي تسمى عناصرها الحواف (أحيانًا الروابط أو الخطوط ).

الرسم البياني الفارغ هو رسم بياني يحتوي على مجموعة فارغة من الرؤوس (وبالتالي مجموعة فارغة من الحواف). رتبة الرسم البياني هي عدد رؤوسه | V |، ويُرمز لها عادةً بالرمز n . حجم الرسم البياني هو عدد حوافه | E | ، ويُرمز لها عادةً بالرمز m . مع ذلك، في بعض السياقات، مثل التعبير عن التعقيد الحسابي للخوارزميات، يُستخدم مصطلح " الحجم " للدلالة على مجموع | V | + | E | (وإلا، فقد يكون حجم الرسم البياني غير الفارغ صفرًا). درجة أو تكافؤ الرأس هو عدد الحواف المتصلة به؛ بالنسبة للرسوم البيانية التي تحتوي على حلقات، تُحسب الحلقة مرتين.

يُطلق على الرأسين u و v لحافة { u , v } اسم نهايتي الحافة . ​​يُقال إن الحافة تربط u و v وتكون متصلة بهما. قد لا ينتمي رأس ما إلى أي حافة، وفي هذه الحالة لا يكون متصلاً بأي رأس آخر ويُسمى رأسًا معزولًا .${\displaystyle \{u,v\}}$إذا وُجدت الرؤوس u و v ، فإنها تُسمى متجاورة .

الرسم البياني المتعدد هو تعميم يسمح بوجود زوج واحد من نقاط النهاية لعدة حواف. في بعض المراجع، يُطلق على الرسوم البيانية المتعددة ببساطة اسم الرسوم البيانية. ^{[ 6 ] [ 7 ]}

أحيانًا، يُسمح للرسوم البيانية باحتواء حلقات ، وهي حواف تربط رأسًا بنفسه. وللسماح بالحلقات، يجب السماح لأزواج الرؤوس في الرسم البياني E بتكرار نفس العقدة مرتين. تُسمى هذه الرسوم البيانية المعممة بالرسوم البيانية ذات الحلقات، أو ببساطة الرسوم البيانية عندما يكون واضحًا من السياق أن الحلقات مسموحة.

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

في الرسم البياني من الرتبة n ، تكون الدرجة القصوى لكل رأس هي n − 1 (أو n + 1 إذا كانت الحلقات مسموحة، لأن الحلقة تساهم بـ 2 في الدرجة)، ويكون الحد الأقصى لعدد الحواف هو n ( n − 1)/2 (أو n ( n + 1)/2 إذا كانت الحلقات مسموحة).

تُحدد حواف الرسم البياني علاقة تناظرية بين الرؤوس، تُسمى علاقة التجاور . تحديدًا، يكون الرأسان x و y متجاورين إذا كانت { x , y } حافة. ​​يُحدد الرسم البياني بالكامل بواسطة مصفوفة التجاور A ، وهي مصفوفة مربعة من الرتبة n × n ، حيث تُحدد A_{_ij} عدد الاتصالات من الرأس i إلى الرأس j . في الرسم البياني البسيط، تكون A _{_ij} إما 0، مما يدل على عدم وجود اتصال، أو 1، مما يدل على وجود اتصال؛ علاوة على ذلك ، A_ij = 0 لأن الحافة في الرسم البياني البسيط لا يمكن أن تبدأ وتنتهي عند نفس الرأس. تتميز الرسوم البيانية ذات الحلقات الذاتية بأن بعض أو كل قيم A _{_ij} تساوي عددًا صحيحًا موجبًا، وتتميز الرسوم البيانية المتعددة (ذات الحواف المتعددة بين الرؤوس) بأن بعض أو كل قيم A _{_ij} تساوي عددًا صحيحًا موجبًا. تتميز الرسوم البيانية غير الموجهة بمصفوفة تجاور متناظرة (أي أن A _{_ij} = A _{_ji} ).

الرسم البياني الموجه أو الرسم البياني الموجه هو رسم بياني تكون فيه الحواف ذات اتجاهات.

في أحد المعاني المحدودة ولكن الشائعة جدًا للمصطلح، ^{[ 8 ]} الرسم البياني الموجه هو زوج G = ( V , E ) يتألف مما يلي:

• V ، مجموعة من الرؤوس (تسمى أيضًا العقد أو النقاط )؛
• E ، وهي مجموعة من الحواف (تسمى أيضًا الحواف الموجهة ، أو الروابط الموجهة ، أو الخطوط الموجهة ، أو الأسهم ، أو الأقواس )، وهي عبارة عن أزواج مرتبة من الرؤوس المتميزة:${\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}$.

ولتجنب الغموض، يمكن تسمية هذا النوع من الكائنات تحديداً بالرسم البياني البسيط الموجه .

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

بمعنى أعم للمصطلح يسمح بوجود حواف متعددة، ^{[ 8 ]} يُعرَّف الرسم البياني الموجه أحيانًا بأنه ثلاثية مرتبة G = ( V , E , ϕ ) تتألف مما يلي:

• V ، مجموعة من الرؤوس (تسمى أيضًا العقد أو النقاط )؛
• E ، مجموعة من الحواف (تسمى أيضًا الحواف الموجهة ، والروابط الموجهة ، والخطوط الموجهة ، والأسهم أو الأقواس )؛
• ϕ ، دالة وقوع تربط كل حافة بزوج مرتب من الرؤوس (أي أن الحافة مرتبطة برأسين مختلفين):${\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}$.

ولتجنب الغموض، يمكن تسمية هذا النوع من الكائنات تحديداً بالرسم البياني المتعدد الموجه .

الحلقة هي حافة تربط رأسًا بنفسه. لا يمكن أن تحتوي الرسوم البيانية الموجهة، كما هو مُعرَّف في التعريفين أعلاه، على حلقات، لأن الحلقة التي تربط رأسًا${\displaystyle x}$الحافة بالنسبة لنفسها (بالنسبة للرسم البياني البسيط الموجه) أو تقع على (بالنسبة للرسم البياني المتعدد الموجه).${\displaystyle (x,x)}$وهو ليس في${\displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}$لذا، للسماح بالحلقات، يجب توسيع التعريفات. بالنسبة للرسوم البيانية البسيطة الموجهة، فإن تعريف${\displaystyle E}$ينبغي تعديلها إلى${\displaystyle E\subseteq V^{2}}$بالنسبة للرسوم البيانية المتعددة الموجهة، فإن تعريف${\displaystyle \phi }$ينبغي تعديلها إلى${\displaystyle \phi :E\to V^{2}}$ولتجنب الغموض، يمكن تسمية هذه الأنواع من الكائنات على وجه التحديد بالرسم البياني البسيط الموجه الذي يسمح بالحلقات والرسم البياني المتعدد الموجه الذي يسمح بالحلقات (أو السهم ) على التوالي.

تُعرف العلاقة المتجانسة ~ على رؤوس الرسم البياني G البسيط الموجه الذي يسمح بوجود حلقات ، باسم علاقة التجاور في G. وبالتحديد، لكل حافة ( x , y ) ، يُقال إن نقطتي نهايتها x و y متجاورتان ، ويُرمز لذلك بـ x ~ y .

الرسم البياني المختلط هو رسم بياني قد تكون فيه بعض الحواف موجهة وبعضها الآخر غير موجه. وهو عبارة عن ثلاثية مرتبة G = ( V , E , A ) للرسم _{البياني} البسيط المختلط ، و G = ( V , E , A , ϕE , ϕA ₎ للرسم البياني المتعدد المختلط ، حيث V و E (الحواف غير الموجهة)، و A (الحواف الموجهة)، و ϕE و ϕA معرفة كما سبق . _{وتُعدّ الرسوم} البيانية الموجهة وغير الموجهة حالات خاصة.

الرسم البياني الموزون أو الشبكة ^{[ 9 ] [ 10 ]} هو رسم بياني يُخصص فيه رقم (الوزن) لكل حافة. ^{​​[ 11 ]} قد تُمثل هذه الأوزان، على سبيل المثال، التكاليف أو الأطوال أو السعات، وذلك بحسب المسألة المطروحة. تظهر هذه الرسوم البيانية في سياقات عديدة، مثل مسائل أقصر مسار ، كمسألة البائع المتجول .

يُعرَّف الرسم البياني الموجه بأنه رسم بياني موجه لا يمكن أن يكون فيه أكثر من ضلع واحد من بين ( x , y ) أو ( y , x ) . أي أنه رسم بياني موجه يمكن تشكيله كتوجيه لرسم بياني غير موجه (بسيط).

يستخدم بعض المؤلفين مصطلح "الرسم البياني الموجه" بمعنى "الرسم البياني الموجه". بينما يستخدمه آخرون بمعنى أي اتجاه لرسم بياني غير موجه أو متعدد الرسوم البيانية.

الرسم البياني المنتظم هو رسم بياني يكون فيه لكل رأس نفس عدد الجيران، أي أن لكل رأس نفس الدرجة. يُسمى الرسم البياني المنتظم ذو الرؤوس من الدرجة k بالرسم البياني المنتظم من الدرجة k أو الرسم البياني المنتظم من الدرجة k .

الرسم البياني الكامل هو رسم بياني يتم فيه ربط كل زوج من الرؤوس بحافة. ​​يحتوي الرسم البياني الكامل على جميع الحواف الممكنة.

الرسم البياني المحدود هو رسم بياني تكون فيه مجموعة الرؤوس ومجموعة الحواف مجموعتين محدودتين . وإلا، فإنه يُسمى رسمًا بيانيًا غير محدود .

في نظرية المخططات، يُفترض ضمنيًا في أغلب الأحيان أن المخططات التي تتم مناقشتها محدودة. أما إذا كانت المخططات غير محدودة، فيتم ذكر ذلك صراحةً.

في الرسم البياني غير الموجه، يُطلق على زوج الرؤوس غير المرتب { x , y } اسم متصل إذا كان هناك مسار يؤدي من x إلى y . وإلا، يُطلق على الزوج غير المرتب اسم غير متصل .

الرسم البياني المتصل هو رسم بياني غير موجه تكون فيه كل أزواج الرؤوس غير المرتبة متصلة. وإلا، فإنه يُسمى رسمًا بيانيًا غير متصل .

في الرسم البياني الموجه، يُطلق على زوج الرؤوس المرتب ( x , y ) اسم "متصل بقوة" إذا كان هناك مسار موجه يؤدي من x إلى y . وإلا، يُطلق على الزوج اسم "متصل بشكل ضعيف" إذا كان هناك مسار غير موجه يؤدي من x إلى y بعد استبدال جميع حوافه الموجهة بحواف غير موجهة. وإلا، يُطلق على الزوج اسم " غير متصل" .

الرسم البياني المتصل بقوة هو رسم بياني موجه تكون فيه كل زوج مرتب من الرؤوس متصلة اتصالاً قوياً. أما إذا كانت كل زوج مرتب من الرؤوس متصلة اتصالاً ضعيفاً، فيُسمى الرسم البياني المتصل اتصالاً ضعيفاً. وإلا فيُسمى الرسم البياني غير المتصل .

الرسم البياني المتصل بـ k رأسًا أو k حافة هو رسم بياني لا توجد فيه مجموعة من k − 1 رأسًا (أو حافة) تؤدي إزالتها إلى فصل الرسم البياني. ويُطلق على الرسم البياني المتصل بـ k رأسًا غالبًا اسم الرسم البياني المتصل بـ k .

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

في الرسم البياني الثنائي الكامل ، تكون مجموعة الرؤوس عبارة عن اتحاد مجموعتين منفصلتين، W و X ، بحيث يكون كل رأس في W مجاورًا لكل رأس في X ولكن لا توجد حواف داخل W أو X.

الرسم البياني المساري أو الرسم البياني الخطي من الرتبة n ≥ 2 هو رسم بياني يمكن فيه ترتيب الرؤوس v1 ، _v2 ، ...، _vn بحيث تكون الحواف هي { vi _، vi _{+ 1} } حيث i = 1 ، 2، ...، n - 1. يمكن وصف الرسوم البيانية المسارية بأنها رسوم بيانية متصلة تكون فيها درجة جميع الرؤوس باستثناء رأسين هي 2 _، ودرجة الرأسين المتبقيين هي 1. إذا ظهر رسم بياني مساري كرسم بياني فرعي لرسم بياني آخر، فإنه يمثل مسارًا في ذلك الرسم البياني.

الرسم البياني المستوي هو رسم بياني يمكن رسم رؤوسه وحوافه في مستوى بحيث لا يتقاطع أي حافتين.

الرسم البياني الدوري أو الدائري من الرتبة n ≥ 3 هو رسم بياني يمكن فيه ترتيب الرؤوس v1 ، v2 _{، ...} ، vn بحيث تكون الحواف هي { vi _، vi _{+ 1} } حيث i = 1، 2، ...، n - 1، بالإضافة إلى الحافة _{ vn _، v1 } . يمكن وصف الرسوم البيانية الدورية بأنها رسوم بيانية متصلة تكون فيها درجة _جميع الرؤوس 2. إذا ظهر رسم بياني دوري كرسم بياني فرعي من رسم بياني آخر، فإنه يُسمى دورة أو دائرة في ذلك الرسم البياني.

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

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

الشجرة المتعددة (أو الشجرة الموجهة أو الشجرة الموجهة أو الشبكة المتصلة بشكل فردي ) هي رسم بياني موجه غير دوري (DAG) يكون الرسم البياني غير الموجه الأساسي الخاص بها عبارة عن شجرة.

الغابة المتعددة (أو الغابة الموجهة أو الغابة الموجهة ) هي رسم بياني موجه غير دوري يكون الرسم البياني الأساسي غير الموجه عبارة عن غابة.

أما الأنواع الأكثر تقدماً من الرسوم البيانية فهي:

• مخطط بيترسن وتعميماته؛
• رسوم بيانية مثالية ؛
• الرسوم البيانية ؛
• الرسوم البيانية الوترية ؛
• الرسوم البيانية الأخرى ذات مجموعات التماثل الذاتي الكبيرة : الرسوم البيانية المتعدية على الرؤوس ، والرسوم البيانية المتعدية على الأقواس ، والرسوم البيانية المتعدية على المسافة ؛
• الرسوم البيانية المنتظمة بقوة وتعميماتها: الرسوم البيانية المنتظمة المسافة .