ⓘ Free online encyclopedia. Did you know? page 112


                                               

برش بیشینه

در نظریه گراف، برش، تقسیم رئوس گراف به دو زیرمجموعه جدا از هم می‌باشد. "مجموعه-برش" در یک برش، مجموعه یال‌هایی است که دو سر آن‌ها، هر یک، در یک بخش است. یال‌های "عبور" از یک برش به یال‌هایی گویند که در مجموعه-برش آن باشند. در گراف بی وزن، اندازه ...

                                               

پل (نظریه گراف)

در نظریهٔ گراف، یال برشی یالی از گراف است که حذف آن باعث افزایش تعداد مولفه‌های همبندی گراف می‌شود. اگر گراف قبل از حذف آن یال همبند باشد، بعد از حذف ناهمبند می‌شود. یال برشی در شبکه‌های کامپیوتری اهمیت ویژه‌ای دارد چرا که حذف آن کلا اتصال شبکه ر ...

                                               

پوشش گره‌ای

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

                                               

پهنای مسیر

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

                                               

تجزیه گوشی

اگر G {\displaystyle G\ } یک گراف و H {\displaystyle H\ } زیرگرافی از G {\displaystyle G\ } باشد، منظور از یک گوش برای H {\displaystyle H\ } در G {\displaystyle G\ } یک مسیر با طول حداقل یک از G {\displaystyle G\ } است که دو سر این مسیر در H {\di ...

                                               

تطابق (گراف)

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

                                               

توزیع درجه

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

                                               

حدس اردیش–فابر–لوواش

حدس اردیش–فابر–لوواش یک مسئله بسیار عمیق و مهم در بحث رنگ آمیزی گراف‌ها در نظریه گراف‌ها است. این نظریه بیان می‌کند که: اجتماع k کپی از k دسته که هر ۲ دستهٔ متمایز دلخواه حداکثر در یک راس اشتراک دارند دارای عدد رنگی k است. حداد و تاردیف در سال ۲۰ ...

                                               

حدس بازسازی

حدس بازسازی برای اولین بار در سال ۱۹۴۲ مطرح شد. حدس بازسازی ادعا می‌کند هر گراف با استفاده از کارت‌های خود ، قابل‌بازسازی است. اگرچه تلاش‌های زیادی پیرامون این حدس صورت گرفته، اما مسئله در حالت کلی باز مانده‌است.

                                               

درخت (نظریه گراف)

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

                                               

درخت اس‌پی‌کیوآر

در نظریهٔ گراف، یکی از زیرشاخه‌های ریاضیات، مولفه‌های سه‌همبند یک گراف دوهمبند یک دستگاه از گراف‌های کوچک‌تر است که همهٔ برش‌های دوراسی گراف را توصیف می‌کند. درخت SPQR یک داده ساختار درختی است که در علوم رایانه، به ویژه در الگوریتم‌های گراف، برای ...

                                               

درخت پوشای کمینه

درخت پوشای کمینه یا درخت فراگیر مینیمم در گراف‌های ارزش دار ساخته می‌شود. فرض کنید گراف یک گراف همبند باشد یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی ...

                                               

درخت کوتاه‌ترین مسیر

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

                                               

درخت‌های ریشه‌دار

در نظریهٔ گراف، یک درخت ریشه‌دار به درختی گفته می‌شود که یک رأس در آن به عنوان ریشه برچسب خورده باشد. درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است. رأس‌هایی که به طور مستقیم به رأس دیگری متصل اند بچه‌های آن نامیده می‌شوند. مثلاً در شکل ...

                                               

دور اویلری

در نظریه گراف دور اویلری یا مدار اویلری به مسیری گفته می‌شود که از یک رأس شروع شود و از تمامی یال‌ها یکبار بگذرد و به همان رأس بازگردد. اگر مسیر از تمام یال‌ها عبور کند ولی به جای اولش بازنگردد به آن مسیر اویلری می‌گویند. دور اویلری زمانی وجود دا ...

                                               

رنگ آمیزی آزمند

الگوریتم رنگ آمیزی آزمند در میان مسائل گوناگون رنگ آمیزی گراف، یک الگوریتم آزمند برای رنگ آمیزی رئوس یک گراف می‌باشد. این روش رئوس گراف را بر اساس ترتیب مشخصی انتخاب کرده و تلاش می‌کند با رنگ‌هایی که در رنگ آمیزی رئوس قبلی به کار رفته آن را به گو ...

                                               

رنگ‌آمیزی کامل گراف

در نظریه گراف، رنگ‌آمیزی کامل گراف یک نوع از رنگ‌آمیزی یالها و راسهای گراف می‌باشد. اگر این نوع از رنگ آمیزی بدون هیچ شرط و قیدی بیان شود معمولاً اینگونه‌است که هیچ راسی، هیچ یال متلاقی و همچنین هیچ یال و رئوس دو سر آن یک رنگ نباشند. عدد رنگی کام ...

                                               

رنگ‌آمیزی گراف

در نظریه گراف، رنگ‌آمیزی گراف یکی از حالت‌های خاص مسئله‌های برچسب‌گذاری گراف است. رویکرد کلی آن استفاده از نظیر کردن رنگهایی به یالها یا راس‌هاست که این رنگ‌آمیزی محدودیت خاصی را رعایت کند. در ساده‌ترین حالت، رنگ‌آمیزی‌ای مورد نظر است که در آن هی ...

                                               

شاخه و حد

شاخه و حد یک الگوریتم عمومی برای پیدا کردن راه حل‌های بهینه مسائل مختلف است، بخصوص در بهینه‌سازی گسسته و ترکیبی. این الگوریتم تمام راه حل‌های یک مسئله را شمارش می‌کند که در این بین راه حل‌های بی‌ثمر بسیاری هستند که می‌توان با حذف آن‌ها با تخمین م ...

                                               

شبکه پسماند

با در اختیار داشتن شبکه شاره G و جریان f ، شبکه پسماند G f ،متشکل از رئوس گراف و ظرفیت هر یک از آن‌ها می‌باشد. هر یال در شبکه‌ی جریان، ممکن است قادر به عبور مقدار جریان بیشتری از خود باشد. این مقدار، معادل تفاضل ظرفیت و جریان گذرنده از آن یال است ...

                                               

شبکه شاره

برای تحلیل شبکه‌های حمل و نقل که وسیله حمل کالاها از مراکز تولید به بازار هستند یا شبکه‌های مخابراتی که داده‌ها را منتقل می‌کنند یا شبکه‌های رایانه‌ای یا شبکه خطوط انتقال گاز در شهرها را توسط گراف‌های سودار مورد تحلیل قرار می‌دهیم. مشاهده می‌شود ...

                                               

عامل‌بندی گراف

در نظریه گراف، یک عامل از یک گراف G یک زیرگراف فراگیر است، برای مثال یک زیرگرافی که مجموعه رئوس برابری با G دارد. یک k -عامل از یک گراف یک زیرگراف فراگیر k -منتظم است و یک k -عامل‌بندی یال‌های گراف را به k -عامل‌های مستقل افراز می‌کند. گراف G را ...

                                               

عرض درخت

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

                                               

فاصله در گراف

فاصله دو راس: کمینه تعداد یالهایی که باید طی شود تا از راس i به راس j برویم را فاصله i و j گویند و با (D(i,j نشان می‌دهند. برای مثال فاصله ۱ و ۳در گراف فوق ۲ است. خروج از مرکز راس i: به فاصله i از دورترین راس نسبت به i خروج از مرکز i گویند. خروج ...

                                               

فهرست برخی گراف‌های خاص

این مقاله به معرفی و بیان خواص برخی گراف‌های خاص می‌پردازد. این گراف‌ها شامل گراف هی وود ، گراف پترسن ، گراف کنزر ، گراف‌های n {\displaystyle n} -بعدی و ماز همپتون می‌باشند.

                                               

فهرست همسایگی

در نظریهُ گراف یک فهرست همسایگی نمایش همهٔ یال‌های یک گراف به صورت مجموعه‌ای از فهرست‌هاست، اگر گراف بدون جهت باشد، هر واحد از این فهرست‌ها یک مجموعه از دو گره شامل دو سر یال مربوطه است.

                                               

قضیه هال

قضیه هال یا قضیه هال قضیه‌ای مربوط به شاخه ترکیبیات و قضیهٔ گراف در ریاضی است. این قضیه که به ریاضی‌دان انگلیسی، فیلیپ هال نسبت داده می‌شود، شرط لازم و کافی برای وجود تطابق کامل در گراف‌های دوبخشی را بیان می‌کند. گراف‌های دوبخشی به گراف‌هایی گفته ...

                                               

قیاس منطقی دست به دست

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

                                               

کنترل تجزیه و تحلیل جریان

تجزیه و تحلیل جریان کنترل، روش تجزیه و تحلیل استاتیک کد برای تعیین جریان کنترل یک برنامه است.کنترل جریان به عنوان یک گراف کنترل جریان بیان شده‌است. برای بسیاری از زبان ها، کنترل جریان از یک برنامه در کد منبع برنامه صریح و روشن بیان شده‌است.به عنو ...

                                               

گراف (ریاضی)

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

                                               

گراف آرمانی

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

                                               

گراف پترسن

در نظریه گراف ، گراف پترسن گرافی غیر جهت دار، با ۱۰ راس و ۱۵ یال است. این گراف، گرافی کوچک می‌باشد که به عنوان مثالی مفید و همچنین مثال نقض در بسیاری از مسائل نظریه گراف به کار می‌رود. یولیوس پترسن دانشمندی دانمارکی بود که در سال ۱۸۹۸ گرافی را، ک ...

                                               

گراف تصادفی

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

                                               

گراف تقاطع

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

                                               

گراف جهت‌دار

در ریاضیات و به‌طور خاص در نظریهٔ گراف، گراف جهت‌دار یا گراف سودار گرافی است که در آن به هر یال جهتی نسبت داده شده‌است. به زبان ریاضی، یک گراف جهت‌دار زوج مرتبی به صورت G = {\displaystyle G=} است {\displaystyle G=} نیز نمایش داده می‌شود) که در آن ...

                                               

گراف جهت‌دار و کاربردهای آن

گراف جهت دار D، یک سه تایی مرتباست که تشکیل شده از یک مجموعه ناتهی V از راسها و یک مجموعه = Ψ، آنگاه میگوئیم که u,a را به v وصل کرده‌است؛ u، دم v,a سرa نامیده می‌شود. می‌توانیم به هر گراف جهتدار D، یک گراف G با همان مجموعه راس‌ها متناظر کنیم، به ...

                                               

گراف چگال

گراف چگال گرافی است که شمار یال‌های آن به بیشینه شمار یال‌ها نزدیک باشد. در برابر گرافی چگال، گراف تنک گرافی است که یال‌های اندکی داشته باشد. شناسایی گرافی چگال از یک گراف تُنُک وابسته به زمینه و گنگ است. چگالی برای گراف باسو با برابری 2 | E | | ...

                                               

گراف چندگانه

در نظریه گراف چندگانه یا شبه گراف به گرافی گفته می‌شود که مجاز است یالهای چندگانه داشته باشد که به آنها یالهای موازی هم گفته می‌شود. بنابراین دو راس ممکن است با بیش از یک یال بهم متصل شوند. گراف چندگانه را می‌توان بازوج مرتب(G =(V, E معرفی کرد که ...

                                               

گراف دوبخشی

در نظریهٔ گراف ، گراف دوبخشی گرافی است که راس‌هایش را می‌توان به دو مجموعهٔ مجزا مثل U {\displaystyle U} و V {\displaystyle V} تقسیم کرد، طوری که هر یال از آن گراف، یک راس از U {\displaystyle U} را به یک راس از V {\displaystyle V} متصل می‌کند. مع ...

                                               

گراف دوری

در نظریه گراف، گراف دوری به گرافی که متشکل از یک دور باشد گفته می‌شود، یا به عبارت دیگر تعدادی رأس که به صورت زنجیری به یکدیگر متصل شده‌اند. گراف با n {\displaystyle n} رأس با نماد C n {\displaystyle C_{n}} نشان داده می‌شود. گراف دوری گرافی همبند ...

                                               

گراف لایه‌بندی شده

یک گراف لایه بندی شده گراف همبندی است که راس‌های آن به مجموعه‌های L۰ تا Ln تقسیم بندی شده‌است.هر یال وزن صحیح نا منفی دارد و فقط رأس‌های لایه‌های پی در پی را به هم متصل میکند. عرض گراف برابر ماکسیموم تعداد رأس‌های هر لایه هست.

                                               

گراف مسطح

در نظریه گرافها، گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند. یک گراف غیر مسطح گرافی است که نمی‌توان آن را به گونه‌ای رسم کرد که یال‌هایش ...

                                               

گراف منتظم

در نظریه گراف، گراف منتظم به گرافی گفته می‌شود که تمام رئوس آن درجه یکسانی دارند، یا به عبارت دیگر تعداد یال مساوی از تمامی رئوس می‌گذرد. گراف منتظمی که درجه هر رأس l {\displaystyle l} باشد، گراف l {\displaystyle l} -منتظم خوانده می‌شود. گراف کام ...

                                               

گراف مور

طول کوتاه‌ترین دور در یک گراف، کمر گراف نامیده می‌شود که با نماد γG نشان داده می‌شود. به عنوان مثال مکعب کمر به طول ۴ دارد. برای گراف‌های kمنظم و با طول کمر ثابت معمولاً ویژگی‌های جالبی دارند. به عنوان مثال گراف G را یک گراف k منتظم با طول کمر ۴ ...

                                               

گراف وزن‌دار

گراف وزن‌دار ، گرافی است که به هر یال آن عددی نسبت داده شده‌است که وزن آن یال می‌باشد. یا به راس آن عددی نسبت داده شده. وزن یال می‌تواند نشان دهنده هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسنده‌ها به آن گراف شبکه‌ای می‌گویند. ...

                                               

گراف k-مکعب

گراف k- مکعب ∗ گرافی است که رئوس آن دنباله‌های غیر تکراری k تایی از 0 و 1 به صورت باشد. و یالهای آن، میان رئوس رسم شوند که دقیقاً در یک جایگاه متفاوت باشند. این گراف‌ها را که با Q k نمایش می‌دهند خصوصیت‌های جالبی دارند که پس از چند مثال به خواص آ ...

                                               

گراف‌های تماس تلفنی

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

                                               

گراف‌های مسطح با خطوط راست

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

                                               

گره سلطه گر

در گراف های جهت دار، زمانی می‌گوییم گره w {\displaystyle w} بر گره v {\displaystyle v} غلبه می‌کند که به ازای هر گره n {\displaystyle n} همه مسیر ها از n {\displaystyle n} به v {\displaystyle v} ، از گره w {\displaystyle w} عبور کند. در نتیجه می‌ ...

                                               

مؤلفه دوهمبند

در ریاضیات و علوم کامپیوتر، راس برشی راسی از گراف است که حذف آن باعث افزایش تعداد مولفه‌های همبندی گراف می‌شود. اگر گراف قبل از حذف آن راس همبند باشد، بعد از حذف ناهمبند می‌شود. راس برشی در شبکه‌های کامپیوتری اهمیت ویژه‌ای دارد. به‌طور کلی یک گرا ...