کمر (نظریه گراف)

در نظریه گراف، کمرhttps://opedia.ir/آموزش/الگوریتم/شناسایی_کمر_گراف () یک گراف طول کوتاه‌ترین دور آن است. اگر یک گراف هیچ دوری نداشته باشد و بی‌دور باشد کمر آن بی‌نهایت خواهد بود. برای نمونه یک چهار-دوری (مربع) دارای کمر ۴ است. یک شبکه هم دارای کمر ۴ است و یک شبکهٔ مثلثی کمر ۳ دارد. یک گراف با کمر ۴ یا بیشتر یک گراف آزاد-مثلث است.

 منابع 



رده:ویژگی‌های گراف