ریاضیات

ویژگی‌های

ویژگی‌های گراف ساده متناهی

اگر G یک گراف ساده با n راس و q یال باشد، روابط اساسی زیر برقرارند:

• قضیه دست دادن:

∑ d(vi) = 2q

• کران درجات:δ ≤ 2q/n ≤ Δ
• شرط همبندی: اگر δ(G) ≥ (n-1)/2 باشد، آنگاه G همبند است.

روابط گراف مکمل (G):

برای گراف مکمل داریم:

q(G) = C(n, 2) - q

• Δ(G) + δ(G) = n - 1
• δ(G) + Δ(G) = n - 1

گراف ساده متناهی

اگر G یک گراف ساده با n راس و q یال باشد، روابط اساسی زیر برقرارند:

• قضیه دست دادن:

​​​​​​​​​​​​​​​​​​​​​∑ d(vi) = 2q

• کران درجات: δ ≤ 2q/n ≤ Δ
• شرط همبندی: اگر δ(G) ≥ (n-1)/2 باشد، آنگاه G همبند است.

روابط گراف مکمل (G):

برای گراف مکمل داریم:

• q(G) = C(n, 2) - q
• Δ(G) + δ(G) = n - 1
• δ(G) + Δ(G) = n - 1