یال گراف ها

اگر کم‌وزن‌ترین یال گراف یکتا باشد در هر درخت پوشای کمینه‌ای وجود خواهد داشت.

به یک اتوماتای ترکیبی، مستطیلی گفته می‌شود هرگاه شرایط جاری مستقل از حالت‌های کنترلی باشند و متغیرها نیز دو به دو مستقل باشند. به‌طور خاص، در هر وضعیت کنترلی، مشتق اول هر یک از متغیرها دارای مجموعه‌ای از مقادیر است که این مقادیر با توجه به یال‌های گراف تغییری نمی‌کنند. با هر یال گراف یک اتوماتای مستطیلی، مقدار هریک از متغیرها یا تغییری نمی‌کند یا به صورت غیرقطعی به مقداری در یک گسترهٔ جدید تغییر می‌یابد. رفتار متغیرها جدا از هم است، چرا که به دلیل استقلالی که تعریف کردیم مقادیر متغیرها و مشتق آن‌ها نمی‌تواند وابستهٔ به یکدیگر باشد.