ریاضیات

نظریه گراف: شروط همبندی و روابط درجات

در این یادداشت، ویژگی‌های گراف ساده \(G\) با مرتبه \(n\) و تعداد یال‌های \(q\) (یا \(e\)) بررسی شده است.

۱. شروط کافی برای همبند بودن گراف

• برحسب حداقل درجه: اگر حداقل درجه گراف (\(\delta\)) از نصف مرتبه گراف (منهای یک) کمتر نباشد، گراف همبند است:

  \(\delta(G) \ge \frac{n-1}{2} \Longrightarrow G \text{ is connected}\)

• برحسب تعداد یال‌ها (مسأله ۲۶): برای اینکه یک گراف ساده با \(n\) رأس قطعاً همبند باشد، حداقل تعداد یال‌های مورد نیاز عبارت است از:

  \(q \ge \frac{(n-1)(n-2)}{2} + 1\)

  (این رابطه تضمین می‌کند که گراف حتی در بدترین حالت که شامل یک مؤلفه کامل \(K_{n-1}\) و یک رأس تنها باشد، باز هم با اضافه شدن یک یال همبند شود.)

۲. روابط مجموعه‌ها و زیرگراف‌ها

در یادداشت‌ها به روابط مجموعه‌ای برای رئوس اشاره شده است:

• شرط افراز یا جدایی مجموعه‌ها: \(M \cap M^c = \varnothing\) و \(V = V(G)\).
• گزاره منطقی عضویت: \(x \in V \Rightarrow x \notin M^c \text{ or } x \in M\).

۳. کران‌ها و روابط پارامتری (استخراج شده از ستون‌ها)

روابط زیر از بخش‌های مختلف دست‌نویس استخراج شده‌اند که به تحلیل ساختاری گراف اشاره دارند:

• \(q \ge n\) (شرط وجود دور یا ساختارهای فراتر از درخت)
• \(1 \le N \le \frac{q}{2}\)
• \(\delta \ge n - m \ge 1\)
• \(\frac{n}{m} - 1 = c \le \bigcup_{i=1}^{m} |V_i| \le \frac{3n}{6}\)