کاکتوس (نظریه گراف)

یک گراف کاکتوسی

در نظریه گراف ، کاکتوس (که بعضاً درخت کاکتوس نامیده می شود) گرافی ساده و همبند است که در آن هر دو دور ساده دلخواه، حداکثر یک راس مشترک دارند. به تعبیری دیگر، گراف ساده و همبندی است که در آن هر یال حداکثر به یک دور ساده تعلق دارد.به طور معادل (برای یک کاکتوس غیربدیهی) میتوان گفت ، هر بلوک (یعنی زیرگراف ماکسیمال بدون راس برشی) یک یال یا یک دور است.

منابع

• https://en.wikipedia.org/wiki/Cactus_graph
• White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, 2001. p. 57