نتایج جستجو

...م''' است، اگر و تنها اگر مسیر '''M-افزوده'''(مسیری که یال‌هایش یکی در میان در تطابق باشد و همچنین اولین و آخرین یال هم جزء تطابق نباشد) نداشته باشیم. قضیه ایست که Claude Berge ریاضیدان فرانسوی در سال 1957 آن را به اثبات خود در آورد. ...

...دسته مجزا قابل افراز هستند بگونه‌ای که تمامی [[یال (نظریه گراف)|یال‌های]] گراف بین گره‌های بین دو دسته مختلف باشند. ۱-مسیر M-متناوب: مسیری است که یالهای آن یکی در میان در تطابق M باشد. ...

...شینه میان یک [[گره (نظریه گراف)|گره‌ی]] چشمه (سرِ جریان) و یک [[گره (نظریه گراف)|گره‌ی]] چاه (تهِ جریان) هم‌ارز است با یافتن برشی کمینه برای چشمه و چاه. ...یال‌هایی از گراف است به گونه‌ای که این گراف را به دو بخش ناهمبند بِبُرد که در هر کدام از این بخش‌ها تنها یکی از گره‌های چشمه یا چاه جای دارند. هم‌چنین، ه ...

[[قضیه]] پنج رنگ نتیجه‌ای است از [[نظریه گراف]] که صفحه‌ای به چند منطقه تقسیم شده داده می‌شود. مناطق به گونه‌ای به پنج رن ...یه بر مبنای تلاش شکست خورده‌ای برای اثبات [[قضیه چهار رنگ]] توسط آلفرد کمپ در سال ۱۸۷۹ می‌باشد. یازده سال بعد پرسی جان هیوود یک خطا از آن پیدا کرد و بر م ...

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

...راس از یک گراف n راسی (جایی که O نماد O بزرگ را فراخوانی می‌کند) می‌تواند گراف را به زیرگراف‌های ناهمبند که هر یک <math>2n/3</math> راس دارند افراز کند. ....5})</math> راس دارد. همچنین یالی وجود ندارد که یک سر آن در A و سر دیگر آن در B باشد. نیازی نیست که A و B زیرگراف‌های همبند G باشند. S را نیز جداکننده بر ...

...y's formula|فرمول کیلی]] است که تعداد درخت‌های پوشا در یک [[Complete graph|گراف کامل]] به دست می‌آورد. ...تلاف بین [[Degree matrix|ماتریس درجه]] (یک [[ماتریس قطری]] با درجهٔ راس‌ها در قطرها) و [[Adjacency matrix|ماتریس مجاورت]] آن است. ...

...ی از اعداد صحیح غیرمنفی می دهد که دنباله درجات یک گراف ساده باشد. این قضیه در سال 1960 توسط پال اردوش و تیبور گالای منتشر شد که به نام آنها نامگذاری شده ...\geq d_n</math> را می توان به عنوان دنباله درجه یک گراف ساده متناهی n راسی در نظر گرفت اگر و فقط اگر <math>d_1+\cdots+d_n</math> زوج باشد و ...

...با حداکثر یکی بیشتر از بیشترین [[درجه (نظریه گراف)|درجه]] {{math|Δ}} رئوس گراف [[رنگ‌آمیزی یالی|رنگ]] کرد. ...«ردهٔ اول» آنهایی هستند که {{math|Δ}} رنگ، برای رنگ‌آمیزی آن‌ها کافی است و گراف‌های «ردهٔ دوم» آن‌هایی هستند که {{math|Δ + ۱}} رنگ، برای رنگ‌آمیزی آن‌ها لا ...

{{اشتباه نشود|نظریه رمزی}} ...یا زیر گراف کاملی با <math>s</math> راس وجود دارد که کاملاً قرمز شده باشد. در این جا <math>R(r,s)</math> به عدد صحیحی دلالت می‌کند که به <math>r</math> و ...