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

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

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Girth (graph theory)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۶ مه ۲۰۲۰.