نتایج جستجو

[[رده:گراف‌های مسطح]] ...

...بیشینه‌ی یال‌ها در گراف‌های باسو برابر است با <math>|V|(|V|-1)</math> و در گراف‌های بی‌سو <math>\frac{1}{2}|V|(|V|-1)</math> است. از این روی، بیشینه‌ی چگالی ی ...دهد که گراف‌های مسطح از نوع گراف (۳,۶)-تنک هستند. همچنین، [[گراف دوبخشی]] مسطح از نوع گراف (۲,۴)-تنک است. ...

...نابراین گراف‌های مسطح (۶و۳)- اسپارس هستند اما هر گراف (۶و۳)- اسپارس، لزوما مسطح نیست. به‌طور مشابه گراف‌های مسطح بیرونی (۳و۲)- اسپارس و گراف‌های مسطح دوبخشی (۴و۲)-اسپارس هستند. ...

!colspan="2"|گراف‌های نمونه ! مسطح || غیرمسطح ...

در [[نظریه گراف]] '''ضخامت''' گراف G، به حداقل تعداد [[گراف مسطح]]<nowiki/>ی که با یال‌های گراف G می‌توان ساخت گویند. به طوری که اگر k گراف مسطح وجود داشته باشد که همه شامل رئوس یکسانی باشد و حاصل اجتماع این گراف‌ها براب ...

...[[نامساوی ایزوپریمتریک]] برای گراف‌های مسطح است که بیان می‌کند که هر گراف مسطح را می‌توان با حذف کردن تعداد کمی از رئوس به قطعات کوچکتر تقسیم کرد. به‌طور قضیه جداکننده سطحی بیان می‌کند که در هر گراف مسطح n راسی ، <math>G=(V,E)</math> افرازی برای رئوس وجود دارد که G را به سه مجمو ...

...«ردهٔ اول» آنهایی هستند که {{math|Δ}} رنگ، برای رنگ‌آمیزی آن‌ها کافی است و گراف‌های «ردهٔ دوم» آن‌هایی هستند که {{math|Δ + ۱}} رنگ، برای رنگ‌آمیزی آن‌ها لازم ا ...دو یال مجاوری ندارد و [[رنگ‌آمیزی گراف|عدد رنگی]] یالی آن یک است. پس، تمام گراف‌های با {{math|1=Δ(''G'') = ۱}} جزء گرافهای ردهٔ اول هستند. ...

...گراف‌هایی که کوچکترین دور در آن‌ها حداقل ۴ است، گراف‌های بدون دور ۳تایی یا گراف‌های با استقلال محلی باشد. ...ی گراف است. [[اثر ماتریس]] صفر است اگر و فقط اگر گراف آزاد-مثلث باشد. برای گراف‌های متراکم بهتر است از این الگوریتم ساده استفاده شود که مبتنی بر [[ضرب ماتریسی] ...

...راف‌های عمومی به صورت P-کامل می‌باشد. شمارش تعداد تطابق، حتی برای گراف‌های مسطح نیز به صورت P-کامل می‌باشد. ایده اصلی، تبدیل مسئله به یک پردازش از ماتریس متقارن مورب که از جاسازی مسطح گراف به دست آمده است می‌باشد. بدین ترتیب این ماتریس به سرعت از الگوریتم است ...

[[رده:گراف‌های مسطح]] ...

...راوِش]]، شاخه‌ای از ریاضیات است که به توضیح رفتار خوشه‌ها در [[گراف تصادفی|گراف‌های تصادفی]] می‌پردازد. علت نامگذاری این حدس، شباهت آن به ساختار [[تخت دوطبقه] ...sue=1|pages=113711|doi=10.1016/j.disc.2023.113711|issn=0012-365X}}</ref> و گراف‌های جهت‌دار منتشر شده است.             ...

...صفر، برابر با گراف مکمل آن <math>\overline K_0</math>، یک جنگل و یک [[گراف مسطح]] است. شاید یک گراف جهت دار، بی جهت یا هر دوی آنها در نظر گرفته شود. وقتی ج [[رده:گراف‌های منتظم]] ...

...مسئله دربارهٔ اینکه آیا یگ [[گراف دو بخشی]] با ۶ راس (<math>k_{3,3}</math>)مسطح است یا خیر. این گراف معادل با گراف دایره‌ای (<math>C_{i6}(1,3)</math> است. ...بر نتیجهٔ قضیه [[خم جردن]] Jordan curve theorem باشد. حکم کاملی که دربارهٔ گراف‌های مسطحه در ''Kuratowski reduction theorem'' آمده شامل این نتیجه می‌شود. ...

#اگر ''G'' یک [[گراف مسطح]] باشد ch(''G'') ≤ 5. <ref> [//en.wikipedia.org/wiki/Carsten_Thomassen Tho #اگر ''G'' یک گراف مسطح [[گراف دوبخشی|دوبخشی]] باشد ch(''G'') ≤ 3. <ref>[//en.wikipedia.org/wiki/No ...

هر [[گراف مسطح|گراف مسطحی]] ''H'' جزئی از ''h'' است&#x2009;×&#x2009;''h'' grid، که در آن < [[رده:گراف‌های مسطح]] ...

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

...etrop'' 8, 128–40.</ref> در سال ۱۷۵۲ قضیهٔ اویلر برای [[گراف مسطح|گراف‌های مسطح]] ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمین ...دشوار نیست، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که [[گراف‌های بیسوی]] حاوی [[مسیر همیلتونی|مسیر]] یا [[دور همیلتونی|دورهای همیلتونی]] را ...

...ه به مطالعه دورهای همیلتونی می‌پردازد، قضیه تات به این معنی است که هر گراف مسطح ۴-همبند دارای دور همیلتونی است. همچنین چندجمله‌ای تات برای یک گراف (و یک ما === قطعه‌ها و گراف‌های همیلتونی === ...

=== تطابق بیشینه در گراف‌های دو بخشی === ...ارای یک وزنی است که به آن نسبت داده شده‌است. '''تطابق بیشینهٔ وزن‌دار برای گراف‌های دو بخشی'''، تطابق کاملی است که در آن مجموع مقادیر (وزن‌ها) روی یال‌های تطاب ...

'''درخت''': گراف هم‌بندی را که هیچ دوری نداشته باشد درخت می‌نامیم. گراف‌های K1 و K2 درخت اند و به ترتیب «تنها» درخت‌های با یک و دو راس هستند. ثابت می‌ش === [[لیست برخی گراف‌های خاص|گراف کنسر]](Kneser) === ...