المسائل والتعريفات

القسم 2.1 المسائل والتعريفات

الأهداف

بعد إكمال هذا القسم، ينبغي أن تكون قادرًا على فعل ما يلي.

1. استخدم لغة نظرية الرسوم البيانية (graph theory) لوصف خصائص الرسوم البيانية (graphs).
2. استعمل تمثيلاتٍ متعددة للرسوم البيانية.
3. طبّق مبرهنة المصافحة (Handshake Lemma) للإجابة عن الأسئلة المتعلقة بالرسوم البيانية وبالمسائل التي تمثّلها.

معاينة القسم

استكشف!

في زمن أويلر، كانت في مدينة كونيجسبرغ (Königsberg) في ولاية بروسيا (Prussia) نهرٌ يجري فيه جزيرتان. وكانتا الجزيرتان موصولتين إلى ضفَّتي النهر بسبعة جسور (كما ترى أدناه). وكانت الجسور جميلةً جدًّا، وفي أيام أفراحهم كان أهل المدينة يقضون وقتًا في المشي فوق هذه الجسور. ومع مرور الوقت، طلع سؤال: هل يمكن التخطيط لمشٍّ بحيث تعبر كل جسر مرةً واحدةً فقط؟ وقد استطاع أويلر الإجابة عن هذا السؤال. أمّا أنت؟

نظرية الرسوم البيانية (graph theory) ميدانٌ جديد نسبيًّا في الرياضيات، بدأ في دراسته أوّلًا عالم الرياضيات الشهير ليونارد أويلر (Leonhard Euler) سنة 1735. ومنذ ذلك الحين ازدهرت حتى غدت أداةً قوية تُستعمل في كلّ فرع تقريبًا من فروع العلوم، وهي الآن ميدان بحث نشط في الرياضيات.

أمّا المسألة أعلاه، المعروفة باسم جسور كونيجسبرغ السبعة (Seven Bridges of Königsberg)، فهي المسألة التي ألهمت في الأصل نظرية الرسوم البيانية. وتأمّل مسألة «مختلفة»: إليك أدناه رسمًا لأربع نقاط موصولة ببعض الخطوط. هل من الممكن أن تمرّ فوق كل خط مرةً واحدةً فقط (دون أن ترفع قلمك، وأن تبدأ وتنتهي عند نقطة)؟

وهناك صلة واضحة بين المسألتين. فأي مسار (path) في رسم النقاط والخطوط يقابل تمامًا مسارًا فوق جسور كونيجسبرغ.

وتُسمّى الصور التي تتألف من نقاط وخطوط من هذا النوع رسومًا بيانية (graphs) (وإن كان الرسم أعلاه تقنيًا متعدد الحواف (multigraph)). ويتكوّن الرسم البياني من مجموعة نقاط تُسمّى رؤوسًا (vertices) ومن خطوط تصل تلك النقاط وتُسمّى حوافّ (edges). فعما يتصل رأسان بحافة نقول إنهما متجاوران (adjacent). والشيء الجميل في النظر إلى رسوم بيانية بدل النظر إلى صور أنهار وجزر وجسور، هو أننا أصبحنا لدينا كائنٌ رياضي ندرسه. فقد استخلّصنا الأجزاء «المهمّة» من صورة الجسور بالنسبة إلى المسألة. فلا يهمّ حجم الجزر، ولا ممّا بُنيت الجسور، ولا ما إذا كان النهر فيه تماسيح، إلخ. إنّما المهمّ هو أيّ الكتل الأرضية موصولة بأيّ الكتل الأرضية الأخرى، وكم مرة. وهذه كانت الرؤية العظيمة التي كانت لأويلر.

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

ورقة العمل: نشاط تمهيدي

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

$G_1\text{:}$

$G_2\text{:}$

$G_3\text{:}$

$G_4\text{:}$

رأس	متجاور مع
$a$	$b, c$
$b$	$a,f$
$c$	$a, d, e$
$d$	$c,e,f$
$e$	$c,d$
$f$	$b,d$

$$\begin{equation*} \begin{pmatrix} 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \\ 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \end{pmatrix} \end{equation*}$$

يُقدَّم الرسم البياني $G_3$ على هيئة قائمة مجاورة (adjacency list)، يُعطى فيها كل رأس قائمةً بالرؤوس الأخرى التي يتجاور معها. أمّا الرسم البياني $G_4$ فيُقدَّم على هيئة مصفوفة مجاورة (adjacency matrix)، حيث تقابل الصفوف والأعمدة الرؤوس، وتكون المداخل 1 إذا كان الرأسان متجاورين و0 خلاف ذلك. وقبل الإجابة عن الأسئلة أدناه، قد يكون من المفيد أن ترسم تمثيلًا أكثر تقليدية لهذه الرسوم البيانية.

1. عدّ الرؤوس والحواف.

أوّلًا، لنعدّ عدد الرؤوس والحواف في كل رسم بياني.

عدد الرؤوس: $G_1\text{:}$ ; $G_2\text{:}$ ; $G_3\text{:}$ ; $G_4\text{:}$ .

عدد الحواف: $G_1\text{:}$ ; $G_2\text{:}$ ; $G_3\text{:}$ ; $G_4\text{:}$ .

2. تتابع الدرجات.

نسمّي عدد الحواف الملاصقة لرأسٍ معيّن (أي عدد الحواف «الخارجة» من ذلك الرأس) درجةَ الرأس (degree). والقائمة التي تضمّ درجات كل الرؤوس مرتّبةً تنازليًّا تُسمّى تتابع الدرجات (degree sequence) للرسم البياني. أوجد تتابع الدرجات لكل رسم بياني.

يتابع درجات $G_1$: .

يتابع درجات $G_2$: .

يتابع درجات $G_3$: .

يتابع درجات $G_4$: .

3. المسارات والدورات.

نهمّ كثيرًا بالمسارات بين الرؤوس في رسم بياني. والرسم البياني يكون متصلًا (connected) إذا كان بين كل زوج من الرؤوس مسار. وأحيانًا يوجد مسار يبدأ عند رأس ثم يعود إليه في النهاية، فيُسمّى دورة (cycle).

(a)

أيُّ الرسوم البيانية متصلة؟

• $\displaystyle G_1$
• $\displaystyle G_2$
• $\displaystyle G_3$
• $\displaystyle G_4$
• لا شيء مما سبق

(b)

أيُّ الرسوم البيانية تحتوي على دورات؟

• $\displaystyle G_1$
• $\displaystyle G_2$
• $\displaystyle G_3$
• $\displaystyle G_4$
• لا شيء مما سبق

(c)

تُسمّى الرسوم البيانية المتصلة التي لا تحتوي على دورات أشجارًا (trees). ولكل رسم بياني، كم حافة يجب أن تحذف كي تحوّله إلى شجرة؟ (وإن كان شجرةً أصلًا، فالجواب هو 0.)

$G_1\text{:}$ ; $G_2\text{:}$ ; $G_3\text{:}$ ; $G_4\text{:}$ .

4. تقاطعات الحواف.

لأيّ من هذه الرسوم البيانية يمكن رسم الرسم البياني بحيث لا تتقاطع أي حافتين؟

• $\displaystyle G_4$
• $\displaystyle G_1$
• $\displaystyle G_3$
• $\displaystyle G_2$
• لا شيء مما سبق

5. تلوين الرؤوس.

لنفترض أننا نلوّن كل رأس في رسم بياني بحيث يكون للرؤوس المتجاورة ألوانٌ مختلفة دائمًا. وأصغر عدد من الألوان اللازم لهذا يُسمّى العدد اللوني (chromatic number) للرسم البياني. أوجد العدد اللوني لكل رسم بياني.

$G_1\text{:}$ ; $G_2\text{:}$ ; $G_3\text{:}$ ; $G_4\text{:}$ .

ملاحظة: لو كانت الرسوم البيانية تمثّل الصداقات بين الناس، لأخبرنا العدد اللوني بأصغر عدد من المجموعات الذي سنحتاجه إن أردنا تقسيم الجميع إلى مجموعات لا يجمع ضمّ بعضهم بعضًا بعد.

ما هو الرسم البياني؟

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

والطريقة التي نتجنّب بها الالتباس في الرياضيات هي أن نقدّم تعريفات ملموسة ودقيقة. وصياغة التعريفات الجيدة ليست سهلة، لكنها بالغة الأهمية. فالتعريف هو نقطة البداية المتّفق عليها التي تنطلق منها كلّ الحقائق في الرياضيات. أفتوجد رسمٌ بياني بلا حواف؟ علينا النظر في التعريف لنرى إن كان هذا ممكنًا.

نريد تعريفًا دقيقًا لا لبس فيه، كما يجب أن يتفق مع حدسنا بشأن الأشياء التي ندرسها. ويجب أن يكون مفيدًا: فينا أن نعرّف الرسم البياني بأنه حيوان ثنائيّ القوائم، لكن ذلك لن يتيح لنا حلّ أي مسألة عن الجسور. وبدلًا من ذلك، إليك التعريف القياسي (الآني) للرسم البياني.

التعريف 2.1.1. الرسم البياني.

الرسم البياني هو زوجٌ مُرتَّب $G = (V, E)$ مكوَّن من مجموعة غير فارغة $V$ (تسمى رؤوسًا) ومجموعة $E$ (تسمى حواف) من المجموعات الجزئية ذات العنصرين من $V\text{.}$

غريب. فلا ذكر للنقاط ولا للخطوط في التعريف إطلاقًا. ومن التعريف، يمكن أن يكون الرسم البياني $$\begin{equation*} (\{a,b,c,d\}, \{\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}\})\text{.} \end{equation*}$$ هنا لدينا رسمٌ بياني بأربعة رؤوس (الحروف $a, b, c, d$) وخمس حواف (الأزواج $\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\})$).

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

غير أننا كان يمكننا أن نرسم الرسم البياني على نحو مختلف. فمثلًا أيّ من هذين:

وينبغي أن نكون حذرين فيما يعنيه أن يكون رسمان بيانيان «متطابقين». وفي الواقع، بمعرفتنا للتعريف، فالأمر سهل: هل مجموعتا الرؤوس متساويتان؟ هل مجموعتا الحواف متساويتان؟ فنحن نعرف ما معنى تساوي مجموعتين، والرسوم البيانية ليست إلا زوجًا من نوعين خاصين من المجموعات.

مثال 2.1.2.

هل الرسمان البيانيان أدناه متساويان؟ $$\begin{equation*} G_1 = (\{a,b,c\}, \{\{a,b\}, \{b,c\}\}); \qquad G_2 = (\{a,b,c\}, \{\{a,c\}, \{c, b\}\})\text{.} \end{equation*}$$

الحل. لا. فمجموعتا الرؤوس في كل رسم بياني متساويتان، وهذا بداية طيّبة. كما أن كلا الرسمين له حافتان. في الرسم الأول لدينا الحافتان $\{a,b\}$ و $\{b,c\}\text{,}$ بينما في الرسم الثاني لدينا الحافتان $\{a,c\}$ و $\{c,b\}\text{.}$ ومن البديهي أن $\{b,c\} = \{c,b\}\text{,}$ فليست هذه هي المشكلة. إنما المشكلة في أن $\{a,b\} \ne \{a,c\}\text{.}$ ولأن مجموعتي حواف الرسمين ليستا متساويتين (بصفتهما مجموعتين)، فإن الرسمين ليسا متساويين (بصفتهما رسمين بيانيين).

حتى لو لم يكن رسمان بيانيان متساويين، فقد يكونان متكافئين في جوهرهما. ويمكن رسم الرسمين في المثال السابق على النحو الآتي:

أمّا الرسوم البيانية المتكافئة في جوهرها (لكنها قد لا تكون متساوية) فتُسمّى متناظرة (isomorphic). وسنقدّم تعريفًا دقيقًا لهذا المصطلح بعد مثالٍ سريع:

مثال 2.1.3.

تأمّل الرسمين البيانيين: $$\begin{equation*} G_1 = (V_1, E_1) \text{ where } V_1 = \{a, b, c\} \text{ and } E_1 = \{\{a,b\}, \{a,c\}, \{b,c\}\}; \end{equation*}$$ $$\begin{equation*} G_2 = (V_2, E_2) \text{ where } V_2 = \{u,v,w\} \text{ and }E_2 = \{\{u,v\}, \{u,w\}, \{v,w\}\}. \end{equation*}$$

هل هذان الرسمان متطابقان؟

الحل. الرسمان البيانيان ليسا متساويين. يكفي أن نلاحظ أن $V_1 \ne V_2$ بما أن $a \in V_1$ ولكن $a \notin V_2\text{.}$ غير أن كلا هذين الرسمين يتكوّن من ثلاثة رؤوس تربط الحواف كل زوج منها. ويمكن رسمهما على النحو الآتي:

ومن الواضح أننا نريد القول إن هذين الرسمين متكافئان في جوهرهما، فمع أنهما ليسا متساويين فإنهما متناظران. ويمكننا إعادة تسمية رؤوس أحد الرسمين فنحصل على الرسم الثاني.

ومن الناحية الحدسية، يكون الرسمان البيانيان متناظرين إذا كانا متكافئين في جوهرهما، أو بمعنى أدقّ إذا كانا متطابقين باستثناء أسماء الرؤوس. ولجعل فكرة إعادة تسمية الرؤوس دقيقة، نقدّم التعريفات التالية:

التعريف 2.1.4.

التناظر (isomorphism) بين رسمين بيانيين $G_1$ و $G_2$ هو دالة تقابل (bijection) $f:V_1 \to V_2$ بين رؤوس الرسمين، بحيث تكون $\{a,b\}$ حافةً في $G_1$ إذا وفقط إذا كانت $\{f(a), f(b)\}$ حافةً في $G_2\text{.}$

ويكون الرسمان البيانيان متناظرين إذا وُجد بينهما تناظر. وعندئذٍ نكتب $G_1 \isom G_2\text{.}$

وليس التناظر سوى دالة تعيد تسمية الرؤوس. ويجب أن تكون هذه الدالة تقابلًا (bijection) بحيث ينال كل رأس اسمًا جديدًا. ويجب أن تربط الحوافُ هذه الرؤوس ذات الأسماء الجديدة بمقدار ما كانت مربوطةً بحوافٍ بأسمائها القديمة.

مثال 2.1.5.

قرّر ما إذا كان الرسمان البيانيان $G_1 = (V_1, E_1)$ و $G_2 = (V_2, E_2)$ متساويين أم متناظرين.

$V_1 = \{a,b,c,d\}\text{,}$ $E_1 = \{\{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\}$

$V_2 = \{a,b,c,d\}\text{,}$ $E_2 = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$

الحل. الرسمان ليسا متساويين، بما أن $\{a,d\} \in E_1$ ولكن $\{a,d\} \notin E_2\text{.}$ غير أنه بما أن كلا الرسمين يضمّ العدد نفسه من الرؤوس والعدد نفسه من الحواف، فقد يكونان متناظرين (وهذا ليس كافيًا في معظم الحالات، لكنه بداية طيّبة).

يمكننا أن نحاول بناء تناظر. كيف لو قلنا $f(a) = b\text{,}$ و $f(b) = c\text{,}$ و $f(c) = d$ و $f(d) = a\text{.}$ وهذه قطعًا دالة تقابل، لكن لكي نتأكد من أن الدالة تناظر، يجب أن نتأكد أنها تحترم علاقة الحواف. ففي $G_1\text{,}$ يتصل الرأسان $a$ و $b$ بحافة. وفي $G_2\text{,}$ يتصل $f(a) = b$ و $f(b) = c$ بحافة. وإلى هنا فالأمر حسن، لكن يجب أن نفحص الحواف الثلاث الباقية. فالحافة $\{a,c\}$ في $G_1$ تقابل $\{f(a), f(c)\} = \{b,d\}\text{,}$ وهنا لدينا مشكلة. إذ لا توجد حافة بين $b$ و $d$ في $G_2\text{.}$ إذن $f$ ليست تناظرًا.

غير أن الأمل لم ينتهِ تمامًا. فكون $f$ ليست تناظرًا لا يعني أنه لا يوجد تناظر على الإطلاق. يمكننا أن نحاول مرة أخرى. وعند هذه النقطة قد يكون من المفيد أن ترسم الرسمين لترى كيف ينبغي أن يتطابقا.

وبدلًا من ذلك، لاحظ أن في $G_1\text{,}$ يكون الرأس $a$ متجاورًا مع كل رأس آخر. وفي $G_2\text{,}$ أيضًا يوجد رأس بهذه الصفة: $c\text{.}$ إذن ابنِ دالة التقابل $g:V_1 \to V_2$ بعرفيتها ابتداءً بـ $g(a) = c$. ثمّ، أين ينبغي أن نرسل $b\text{?}$ في $G_1\text{,}$ لا يتجاور الرأس $b$ إلّا مع الرأس $a\text{.}$ وهناك رأس واحد فقط بهذه الصفة في $G_2\text{,}$ وهو $d\text{.}$ إذن لتكن $g(b) = d\text{.}$ وأمّا الرأسان الأخيران، ففي هذا المثال لدينا خيار حرّ: لتكن $g(c) = b$ و $g(d) = a$ (والبديل بينهما مقبول أيضًا).

وينبغي أن نفحص أن هذا تناظرٌ بالفعل. فهو قطعًا دالة تقابل. ويجب أن نتأكد أن الحواف محترَمة. فالحواف الأربع في $G_1$ هي $$\begin{equation*} \{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\text{.} \end{equation*}$$

وتحت التناظر المقترح تصبح هذه $$\begin{equation*} \{g(a), g(b)\}, \{g(a), g(c)\}, \{g(a), g(d)\}, \{g(c), g(d)\} \end{equation*}$$ $$\begin{equation*} \{c,d\}, \{c,b\}, \{c,a\}, \{b,a\}\text{,} \end{equation*}$$ وهي بالتحديد حواف $G_2\text{.}$ إذن $g$ تناظر، ومن ثمّ $G_1 \cong G_2$

أحيانًا سنتحدّث عن رسمٍ بياني له اسمٌ خاص (مثل $K_n$ أو رسم بترسن) أو قد نرسم رسمًا بيانيًا بلا أي تسميات. وعندئذٍ فالحقيقة أننا نشير إلى كل الرسوم البيانية المتناظرة مع أي نسخة من ذلك الرسم بعينه. وتُسمّى مجموعة الرسوم البيانية المتناظرة في الغالب صنفًا للتناظر (isomorphism class). 1 وهذا ليس مختلفًا عن الهندسة، حيث قد يكون لدينا أكثر من نسخة من مثلثٍ بعينه. وهناك بدلًا من قول متناظرَين نقول متطابقَين (congruent).

وهناك علاقات أخرى بين الرسوم البيانية نهتمّ بها، إضافةً إلى التساوي والتناظر. فمثلًا، قارن زوج الرسوم البيانيين التاليين:

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

ونودّ أن نقول إن الرسم الأصغر رسمٌ بياني جزئي (subgraph) للرسم الأكبر.

وينبغي أن نقدّم تعريفًا دقيقًا لهذا. وفي الواقع، هناك مفهومان معقولان لما ينبغي أن يعنيه الرسم البياني الجزئي.

التعريف 2.1.6. الرسوم البيانية الجزئية.

نقول إن $G' = (V', E')$ رسمٌ بياني جزئي (subgraph) لـ $G = (V, E)\text{,}$ ونكتب $G' \subseteq G\text{,}$ بشرط أن $V' \subseteq V$ وأن $E' \subseteq E\text{.}$

ونقول إن $G' = (V', E')$ رسمًا بيانيًا جزئيًّا مستحَثًّا (induced subgraph) لـ $G = (V, E)$ بشرط أن $V' \subseteq V$ وأن كل حافة في $E$ يكون رأساها ما زالا في $V'$ تكون أيضًا حافةً في $E'\text{.}$

ولاحظ أن كل رسمٍ بياني جزئي مستحث هو أيضًا رسمٌ بياني جزئي عادي، ولكن العكس غير صحيح. فتخيّل الرسم البياني الجزئي نتيجةً لحذف بعض الرؤوس والحواف من الرسم البياني الأكبر. ولكي يكون الرسم الجزئي مستحثًّا، يظل بإمكانك حذف رؤوس، لكنك الآن لا تحذف إلّا الحواف التي تضمّ الرؤوس المحذوفة.

مثال 2.1.7.

تأمّل الرسوم البيانية:

هنا كلٌّ من $G_2$ و $G_3$ رسمٌ بياني جزئي لـ $G_1\text{.}$ غير أن $G_2$ وحده هو رسم مستحثّ. فكل حافة في $G_1$ تصل بين رؤوس في $G_2$ هي أيضًا حافة في $G_2\text{.}$ أمّا في $G_3\text{,}$ فالحافة $\{a,b\}$ موجودة في $E_1$ وليست في $E_3\text{,}$ مع أنّ الرأسين $a$ و $b$ موجودان في $V_3\text{.}$

والرسم البياني $G_4$ ليس رسمًا جزئيًا لـ $G_1\text{,}$ مع أنه يبدو أننا لم نعمل إلّا حذف الرأس $e\text{.}$ والسبب هو أن في $E_4$ لدينا الحافة $\{c,f\}\text{,}$ وهذه ليست عنصرًا في $E_1\text{,}$ فليس لدينا الشرط $E_4 \subseteq E_1\text{.}$

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

لكن ثمة أوقات نريد فيها أن نأخذ في الحسبان الحواف المزدوجة (أو أكثر) وحلقات الحافة الواحدة. فمثلًا، كان «الرسم البياني» الذي رسمناه لمسألة جسور كونيجسبرغ ذا حواف مزدوجة، لأن هنالك جسرين حقًّا يوصلان جزيرةً معيّنة بالضفّة القريبة. وسنسمّي هذه الكائنات رسومًا متعددة الحواف (multigraphs). وهذا اسمٌ جيد: فـالمجموعة المتعددة (multiset) هي مجموعة يُسمح فيها بإدخال العنصر الواحد عدة مرات.

والرسوم البيانية أعلاه متصلة أيضًا: يمكنك الانتقال من أي رأس إلى أي رأس آخر باتباع مسارٍ من الحواف. والرسم البياني غير المتصل يمكن التفكير فيه على أنه رسمان بيانيان منفصلان مرسومان متقاربين. فمثلًا، الرسم البياني التالي ليس متصلًا، إذ لا يوجد مسار من $a$ إلى $b\text{:}$

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

كل رأس في $K_n$ متجاور مع $n-1$ رأسًا آخر. ونسمّي عدد الحواف الصادرة من رأسٍ معيّن درجةَ ذلك الرأس. فكل رأس في $K_n$ درجته $n-1\text{.}$ فكم حافة في $K_n$؟ قد يظنّ أحدهم أن الجواب ينبغي أن يكون $n(n-1)\text{,}$ لأننا نعدّ $n-1$ حافةً $n$ مرات (مرةً لكل رأس). غير أن كل حافة ملاصقة لرأسين، فقد عددنا كل حافةٍ بالضبط مرتين. إذن يوجد $n(n-1)/2$ حافةً في $K_n\text{.}$ وبدلًا من ذلك، يمكننا القول إن عدد الحواف ${n \choose 2}$، إذ لرسم حافة يجب أن نختار 2 من الرؤوس الـ $n$.

وعلى وجه العموم، إذا عرفنا درجات كل الرؤوس في رسمٍ بياني، استطعنا إيجاد عدد الحواف. فمجموع درجات كل الرؤوس سيكون دائمًا ضعف عدد الحواف، لأن كل حافة تضيف إلى درجتي رأسين. ولاحظ أن هذا يعني أن مجموع درجات كل الرؤوس في أي رسم بياني يجب أن يكون زوجيًّا!

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

مُلمة 2.1.8. مبرهنة المصافحة.

في أي رسم بياني، يكون مجموع درجات الرؤوس في الرسم البياني مساويًا دائمًا ضعف عدد الحواف.

وتُسمّى مبرهنة المصافحة 2 وهي عبارةٌ رياضية أهميتها الأساسية أنها تُستعمل لإثبات نتائج أخرى. وتُسمّى أحيانًا صيغة مجموع الدرجات (degree sum formula)، ويمكن كتابتها رمزيًّا على النحو $$\begin{equation*} \sum_{v\in V} d(v) = 2e\text{.} \end{equation*}$$ وهنا نستخدم الرمز $d(v)$ لدرجة الرأس $v\text{.}$

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

مثال 2.1.9.

كم رأسًا وحافة يجب أن يملك رسمٌ بياني إذا كان تتابع دراجاته $$\begin{equation*} (4, 4, 3, 3, 3, 2, 1)\text{?} \end{equation*}$$

الحل. أما عدد الرؤوس فسهل الإيجاد. إنه عدد الدرجات في المتتابع: 7. ولإيجاد عدد الحواف، نحسب مجموع الدرجات $$\begin{equation*} 4 + 4 + 3 + 3 + 3 + 2 + 1 = 20\text{,} \end{equation*}$$ ومن ثمّ يكون عدد الحواف نصفَ هذا المجموع: 10.

وتخبرنا مبرهنة المصافحة أيضًا بما هو غير ممكن.

مثال 2.1.10.

في ندوةٍ رياضية أخيرة، حيّا تسعة من علماء الرياضيات بعضهم بعضًا بالتصافح. فهل من الممكن أن يكون كلُّ عالم رياضيات قد تصافح مع 7 أشخاص بالضبط في الندوة؟

الحل. يبدو أن هذا ينبغي أن يكون ممكنًا. فكلُّ عالم رياضيات يختار شخصًا واحدًا لا يتصافح معه. لكن هذا لا يمكن أن يحدث. فنحن نسأل: هل يمكن أن يوجد رسمٌ بياني له 9 رؤوس، ويكون لكل رأس فيه درجة 7؟ ولو وُجد مثل هذا الرسم، لكان مجموع درجات الرؤوس مساويًا لـ $9\cdot 7 = 63\text{.}$ وهذا ضعف عدد الحواف (المصافحات)، مما ينتج رسمًا بيانيًا بعدد $31.5$ حافة. وهذا غير ممكن. إذن لا بدّ أن واحدًا على الأقل (وفي الحقيقة عددًا فرديًّا) من علماء الرياضيات يكون قد تصافح مع عدد زوجي من الأشخاص في الندوة.

ويمكننا تعميم المثال السابق للحصول على المقولة التالية. 3 والمقولة عبارةٌ رياضية عامة في الرياضيات، شبيهة بالمبرهنة، وإن كانت أهميتها أقلّ عادةً.

مقولة 2.1.11.

في أي رسم بياني، يجب أن يكون عدد الرؤوس ذات الدرجة الفردية زوجيًّا.

البرهان.

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

وسننظر في تطبيقاتٍ إضافية لمبرهنة المصافحة في التمارين.

وأخيرًا تعريفٌ واحد: نقول إن الرسم البياني ثنائيّ الأجزاء (bipartite) إذا أمكن تقسيم رؤوسه إلى مجموعتين $A$ و $B\text{,}$ بحيث لا يتجاور أيُّ رأسين في $A$ ولا أيُّ رأسين في $B$. ويمكن أن يتجاور الرأس في $A$ مع بعض رؤوس $B\text{.}$ أو مع جميعها. فإذا كان كلُّ رأس في $A$ متجاورًا مع كلِّ رأس في $B\text{,}$ فإن الرسم البياني يكون ثنائيّ الأجزاء كاملًا (complete bipartite graph)، ويحصل على اسمٍ خاص: $K_{m,n}\text{,}$ حيث $|A| = m$ و $|B| = n\text{.}$

الرسوم البيانية المسمّاة.

تستعمل بعض الرسوم البيانية أكثر من غيرها فتحصل على أسماء خاصة. $K_n$

الرسم البياني الكامل على $n$ رأسًا.

$K_{m,n}$

الرسم البياني الثنائيّ الأجزاء الكامل بمجموعتين من $m$ و $n$ رأسًا.

$C_n$

الدورة على $n$ رأسًا، أي حلقةً كبيرة واحدة.

$P_n$

المسار على $n+1$ رأسًا (أي $n$ حافة)، أي مسارًا طويلًا واحدًا.

تعريفات نظرية الرسوم البيانية.

هناك تعريفاتٌ كثيرة يجب تتبّعها في نظرية الرسوم البيانية. وإليك مسردًا للمصطلحات التي استعملناها وسنستعملها قريبًا. الرسم البياني (graph)

مجموعة من الرؤوس، بعضها موصل بحواف. والأدقّ أنها زوج من مجموعتين $V$ و $E\text{,}$ حيث $V$ مجموعة رؤوس و $E$ مجموعة من المجموعات الجزئية ذات العنصرين من $V\text{.}$

المتجاور (adjacent)

يتجاور رأسان إذا وُصلا بحافة. وتتجاور حافتان إذا كانتا تشتركان في رأس.

الرسم الثنائيّ الأجزاء (bipartite graph)

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

الرسم الثنائيّ الأجزاء الكامل (complete bipartite graph)

رسمٌ ثنائيّ الأجزاء يكون فيه كلُّ رأس في المجموعة الأولى متجاورًا مع كلِّ رأس في المجموعة الثانية.

الرسم البياني الكامل (complete graph)

رسمٌ بياني يكون فيه كلُّ زوج من الرؤوس متجاورًا.

المتصل (connected)

يكون الرسم البياني متصلًا إذا كان هناك مسار من أي رأس إلى أي رأس آخر.

العدد اللوني (chromatic number)

أصغر عدد من الألوان اللازم في تلوين سليم لرؤوس الرسم البياني.

الدورة (cycle)

مسار (انظر أدناه) يبدأ وينتهي عند الرأس نفسه، ولا يضمّ أي رأس متكرّر سواهما.

درجة الرأس (degree of a vertex)

عدد الحواف الملاصقة لرأس.

مسلك أويلر (Euler trail)

مشيٌّ يستخدم كل حافةٍ مرةً واحدةً بالضبط.

دائرة أويلر (Euler circuit)

مسلكُ أويلر الذي يبدأ وينتهي عند الرأس نفسه.

الرسم متعدد الحواف (multigraph)

يشبه الرسم البياني، لكنه قد يضمّ عدة حواف بين رأسين، إضافةً إلى حلقات أحادية الحافة (أي حافة من رأس إلى نفسه).

المسار (path)

المسار هو مشيٌّ لا يكرّر أي رأس (ولا أي حافة) إلّا ربما الأول وآخر. وإذا بدأ المسار وانتهى عند الرأس نفسه، سُمّي دورةً.

المستوي (planar)

رسمٌ بياني يمكن رسمه (في المستوى) دون أن تتقاطع أي حافتين.

الرسم البياني الجزئي (subgraph)

نقول إن $H$ رسمٌ بياني جزئي لـ $G$ إذا كان كل رأس وكل حافة في $H$ رأسًا أو حافةً في $G\text{.}$ ونقول إن $H$ رسمًا جزئيًّا مستحثًّا لـ $G$ إذا كان كلُّ رأس في $H$ رأسًا في $G$، وكان كلُّ زوج من الرؤوس في $H$ متجاورًا في $H$ إذا وفقط إذا كان متجاورًا في $G$ .

الشجرة (tree)

رسمٌ بياني متصل بلا دورات. (وإن رفعنا شرط اتّصال الرسم البياني، فإن الرسم يُسمّى غابةً (forest).) والرؤوس ذات الدرجة 1 في الشجرة تُسمّى أوراقًا (leaves).

تلوين الرؤوس (vertex coloring)

إسناد ألوان إلى كل رأس من رؤوس الرسم البياني. ويكون تلوين الرؤوس سليمًا (proper) إذا كانت الرؤوس المتجاورة مصوَّغة دائمًا بألوان مختلفة.

المشي (walk)

تتابعٌ من الرؤوس بحيث يكون كلُّ رأسين متتاليين (في المتتابع) متجاورين (في الرسم البياني). ويُسمّى المشي الذي لا تتكرر فيه أي حافة مسلكًا (trail)، ويُسمّى المسلك الذي لا يتكرر فيه أي رأس (إلّا ربما الأول وآخر) مسارًا (path).

أسئلة القراءة

1.

هل يوجد أكثر من رسم بياني واحد له خمسة رؤوس وست حواف؟ اشرح ما الذي يعنيه هذا السؤال أصلًا، وكيف تجيب عنه.

2.

إذا كان رسمٌ بياني له 10 رؤوس، لكلٍّ منها درجة 4، فكم حافة فيه؟

عدد الحواف:

3.

ما الأسئلة التي تدور في ذهنك بعد قراءة هذا القسم؟ اكتب سؤالًا واحدًا على الأقل عن محتوى هذا القسم يثير فضولك.