Introduction to Graphs

الفصل التاسع: مقدمة في نظرية الرسوم البيانية

الهدف: تصنيف الرسوم (Graphs)، حساب الدرجات (Degrees)، والتمييز بين مسارات أويلر وهاملتون.
1

Types of Graphs

الرسم البياني $G = (V, E)$ يتكون من رؤوس (Vertices) وحواف (Edges).

النوع Edges (الحواف) Multiple Edges؟ Loops؟
Simple Graph Undirected No No
Multigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Directed Graph Directed (Arrows) No Yes
2

Handshaking Theorem

درجة الرأس (Degree)

في الرسم غير الموجه: عدد الحواف المتصلة بالرأس. (Loop يحسب بـ 2).
في الرسم الموجه: $\deg^-(v)$ (الداخلة) و $\deg^+(v)$ (الخارجة).

Undirected Graph
$$ 2|E| = \sum_{v \in V} \deg(v) $$

مجموع الدرجات دائماً عدد زوجي.

Directed Graph
$$ |E| = \sum \deg^- = \sum \deg^+ $$

مجموع الداخل = مجموع الخارج = عدد الحواف.

3

Special Graphs Gallery

Complete ($K_n$)

كل زوج من الرؤوس متصل.

Edges: $n(n-1)/2$
Cycle ($C_n$)

دائرة مغلقة ($n \ge 3$).

Edges: $n$
Wheel ($W_n$)

دائرة $C_n$ + رأس في المنتصف.

Vertices: $n+1$
Bipartite

يمكن تقسيم الرؤوس لمجموعتين منفصلتين.

No Odd Cycles
4

Euler & Hamilton Paths

Euler Circuit/Path

المرور بكل حافة (Edge) مرة واحدة بالضبط.

  • Euler Circuit: يبدأ وينتهي بنفس النقطة. الشرط: جميع الدرجات زوجية.
  • Euler Path: نقطة البداية تختلف عن النهاية. الشرط: بالضبط رأسان درجتهما فردية.

Hamilton Circuit/Path

المرور بكل رأس (Vertex) مرة واحدة بالضبط.

تنبيه: لا يوجد شرط "بسيط" وكافٍ (مثل أويلر) لمعرفة وجود مسار هاملتون. إنها مشكلة صعبة (NP-Complete).
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / المصفوفات

Adjacency Matrix Symmetry

مصفوفة التجاور للرسم غير الموجه (Undirected) تكون دائماً متماثلة ($A = A^T$).
أما للرسم الموجه (Directed)، فليست بالضرورة متماثلة.

CHECK / تحقق

Graph Isomorphism Invariants

للتأكد أن رسمين متماثلين (Isomorphic)، يجب أن يتساويا في:
1. عدد الرؤوس.
2. عدد الحواف.
3. تسلسل الدرجات (Degree Sequence).
إذا اختلف أحدها $\to$ غير متماثلين.

→ السابق (Ch 8) الفصل التالي (Ch 10) ←