wiki: شبکه شاره است.
یک مسیر متناوب مسیری است که در آن، یال ها یک در میان یال های تطابقی و غیر تطابقی باشند.
یک مسیر افزایشی مسیر متناوبی است که از یک گره آزاد (اشباع نشده) شروع و به گره آزاد دیگری ختم می شود.
در گراف داده شدهٔ G با مجموعهٔ یال ها و گره ها مشخص که می توان آن را به صورت (G(V,E نشان داد، به مجموعه ای از یال های ناهمسایه که هیج یک از دو یال آن گره هموند نداشته باشند، یک تطابق در G می گویند و آن را با M نشان می دهند.
در صورتی که گرهی در یکی از دو انتهای یکی از یال ها در تطابق گراف G واقع شده باشد، به آن گره منطبق شده (یا اشباع) می گویند. در غیر این صورت، آن گره منطبق نشده است.
تطابق ماکسیمال یکی از تطابق های بدست آمده برای گراف G است، با این ویژگی که اگر به آن، هر یک از یال هایی که در گراف G وجود دارد اما در تطابق M نیامده است را اضافه کنیم، گراف به وجود آمده خاصیت تطابق بودن خود را از دست می دهد؛ بنابراین چنانچه تطابق M یک زیرمجموعهٔ محض از تطابق دیگری برای گراف G نباشد، آنگاه M یک گراف تطابق ماکسیمال است. به عبارت دیگر در صورتی M می تواند یک تطابق ماکسیمال برای گراف G باشد که هر یال از گراف G، حداقل با یکی از یال های M، تقاطع ناتهی داشته باشد (منظور از تقاطع، تنها در دو سر یک یال است)