کمر (نظریه گراف)
ظاهر
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Frucht_graph.neato.svg/220px-Frucht_graph.neato.svg.png)
در نظریه گراف، کمر[۱] (انگلیسی: Girth) یک گراف طول کوتاهترین دور آن است. اگر یک گراف هیچ دوری نداشته باشد و بیدور باشد کمر آن بینهایت خواهد بود. برای نمونه یک چهار-دوری (مربع) دارای کمر ۴ است. یک شبکه هم دارای کمر ۴ است و یک شبکهٔ مثلثی کمر ۳ دارد. یک گراف با کمر ۴ یا بیشتر یک گراف آزاد-مثلث است.
منابع[ویرایش]
- مشارکتکنندگان ویکیپدیا. «Girth (graph theory)». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲۶ مه ۲۰۲۰.