گراف چیست و چه کاربردی دارد؟
گراف (ریاضی)
از گراف‌ها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و… استفاده می‌شود. مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتم‌های مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. در این جا به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل رأس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مسئله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود. نظریه گراف
مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتمهای مناسب مانند الگوریتم دایکسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. گرافیت
از گرافیت به دلیل داشتن خاصیت رسانایی الکتریکی بالا، در ساخت الکترودهای کوره‌های قوس الکتریکی، باتری‌ها و صفحات خورشیدی استفاده می‌شود. برخی دیگر از کاربردها شامل استفاده در ساخت مداد (به همین دلیل به عنوان «مغز مداد» نیز شناخته می‌شود)، و روان‌کننده‌ها است. گرافیت برای اولین بار در عصر نوسنگی به عنوان رنگ استفاده شد. از زمان کشف آن در انگلستان در حدود سال ۱۵۶۵ میلادی، استفاده از گرافیت افزایش یافته‌است.
دور (نظریه گراف)
در نظریه گراف، دور گرافی است که تعداد برابری از یال و رأس دارد، به‌طوری‌که رئوس می‌توانند روی یک دایره قرار بگیرند و هر دو رأس این گراف مجاورند، اگر و تنها اگر روی دایرۀ به‌صورت متوالی قرار گرفته باشند. به‌عبارت دقیق‌تر، در یک گراف با مجموعه رئوس "V" و مجموعه یال‌های "E"، یک دور عبارت است از دنباله‌ای به‌شکل formula_1 (formula_2 و formula_3) که formula_4 و به‌جز این دورِ رأس در دنباله همۀ رئوس و همۀ یال‌ها غیرتکراری باشند. تئوری سامانه‌های پویا
مفهوم سیستم‌های دینامیکی گراف (GDS) می‌تواند برای ترسیم طیف وسیعی از فرایندهایی که در گراف‌ها یا شبکه‌ها اتفاق می‌افتد استفاده شود. موضوع اصلی که در تجزیه و تحلیل ریاضی و محاسباتی سیستم‌های دینامیکی گراف استفاده می‌شود، این است که خواص ساختاری خود (به عنوان مثال اتصال شبکه) و نتایج دینامیک جهانی که را به هم مرتبط سازند. نمودار خطی
نمودار خطی () دسته‌ای از نمودارها (یا گراف‌ها) هستند، که دو مقیاس اندازه‌گیری را شامل می‌شوند. در این نمودارها یکی از مقیاس‌ها در امتداد قائم و دیگری در امتداد افقی قرار می‌گیرد. این نوع نمودارها، دقیق‌ترین یا صحیح‌ترین نوع نمودارها را تشکیل می‌دهند. از این نظر در نشان دادن رابطه میان دو سری از اطلاعات، بسیار مفید می‌باشند. نمودارهای خطی، نحوه گسترش یا توسعه اطلاعات را در یک مدت زمان معین به‌خوبی نشان می‌دهند، گرچه هنگامی از این نمودارها استفاده می‌گردد که اطلاعات بسیار زیادی در دست باشد. گراف تهی
formula_1 عمل (درستی پوچ) بیشتر گراف‌های پایه با ویژگی‌هایی مشابه با formula_9 (گرافی با یک رأس و بدون یال) را انجام می‌دهد. برای مثال، formula_10 اندازه صفر، برابر با گراف مکمل آن formula_11، یک جنگل و یک گراف مسطح است. شاید یک گراف جهت دار، بی جهت یا هر دوی آنها در نظر گرفته شود. وقتی جهت دار در نظر گرفته شود، یک گراف جهت دار غیرمدور است و در عین حال یک گراف کامل و یک گراف بی یال است. اگر چه تعریف‌ها برای ویژگی‌های این گراف متفاوت خواهد بود و وابسته به متن است که آیا formula_1 را به شمار می‌آورد یا نه. گراف دوبخشی
گراف دو بخشی را معمولاً به صورت formula_9 نشان می‌دهیم که formula_1 و formula_2 دو بخش گراف و formula_12 مجموعهٔ یال‌های گراف است. اگر یک گراف دوبخشی همبند نباشد، ممکن است بتوان راس‌های آن را به شیوه‌های مختلف به دو بخش تقسیم نمود (یعنی ممکن است formula_1 و formula_2 یکتا نباشند). در این صورت نمایش formula_9 سودمند واقع می‌شود؛ چون به کمک آن می‌توان یک حالت خاص تقسیم رئوس گراف به دو بخش را از بقیهٔ حالات متمایز کرد. اگر formula_16، گراف formula_17 را گراف دوبخشی متوازن می‌نامیم. اگر درجهٔ تمام راس‌های formula_1 با هم و نیز درجهٔ تمام راس‌های formula_2 با هم برابر باشد، گراف formula_17 را گراف دوبخشی شبه منتظم می‌نامیم. گراف (ریاضی)
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می‌باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده‌اند. حال این سؤال مطرح می‌شود که آیا می‌توان به هر متقاضی شغلی متناسب او اختصاص داد؟ برای حل چنین مسئله‌ای که به مسئلهٔ تخصیص موسوم است، با استفاده از گراف می‌توان وضعیت‌های خاص را پیاده‌سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه‌ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه‌ای به نام Y قرار می‌دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال‌ها وصل می‌نماید. به عبارت دیگر گراف به وجود آمده دارای یال‌های xy است که هر متقاضی x را از مجموعه X به شغل‌های مناسب y از مجموعه Y متصل می‌نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X (متقاضیان) یا هیچ دو راس متعلق به مجموعه Y (مشاغل) توسط هیچ یالی به هم متصل نمی‌باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می‌گویند. گراف (ریاضی)
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است. گراف دوبخشی
یک ابرگراف (hypergraph) یک ساختار ترکیبیاتی است که همانند گراف‌های غیر جهتدار، تعدادی راس و یال دارد، ولی هر یال می‌تواند مجموعهٔ دلخواهی از رئوس باشد (به جای این که دقیقاً از دو راس تشکیل شده باشد). از گراف دوبخشی formula_32 می‌توان برای مدل‌سازی ابرگراف‌ها استفاده نمود که در آن formula_1 مجموعهٔ راس‌های ابرگراف و formula_2 مجموعهٔ ابریال‌ها (hyperedges) است و formula_12 شامل یک یال از یک راس ابرگراف مثل formula_38 به یک ابریال مثل formula_39 است، اگر formula_38 یکی از نقاط انتهایی formula_39 باشد. با این تناظر، ماتریس مجاورت یک گراف دوبخشی دقیقاً همان ماتریس وقوع ابرگراف متناظر با آن است. به عنوان یک حالت خاص از این تناظر بین گراف‌های دوبخشی و ابرگراف‌ها، هر گراف چندگانه (گرافی که ممکن است بین دو راس از آن دو یا چند یال وجود داشته باشد) را می‌توان به صورت یک ابرگراف در نظر گرفت که در آن برخی ابریال‌ها مجموعهٔ یکسانی از راس‌ها را دارند و این ابرگراف را می‌توان با یک گراف دوبخشی نشان داد که یال چندگانه ندارد و همهٔ راس‌های یک طرف آن از درجهٔ ۲ هستند. گراف آزاد-مثلث
در حوزه ریاضیات نظریه گراف، یک گراف آزاد-مثلث گرافی بدون جهت است که هیچ سه راس آن تشکیل مثلث ندهند. معادل گراف‌های آزاد-مثلث می‌تواند گراف‌هایی که عدد خوشه‌ای آن‌ها حداکثر ۲ است، گراف‌هایی که کوچکترین دور در آن‌ها حداقل ۴ است، گراف‌های بدون دور ۳تایی یا گراف‌های با استقلال محلی باشد. حدس بازسازی
حدس بازسازی یکی از مشهورترین مسایل نظریهٔ گراف است، که همواره ذهن بسیاری از ریاضی‌دانان را به خود مشغول کرده‌است.  از این مسئله به خاطر ماهیت مسری آن به عنوان بیماری گرافی یاد می‌کرد. بر اساس گزارش‌های ثبت شده، ویسکُنسین در ۱۹۴۱،  و  به عنوان اولین قربانیان این بیماری شناخته می‌شوند. نمادها با توجه به نمادگذاری کتابِ باندی و مورتی انتخاب شده‌است؛ بنابراین گراف formula_1 دارای مجموعه رأس‌های formula_2, مجموعه یال‌های formula_3؛ همچنین دارای formula_4 رأس و formula_5 یال است. زیرگراف formula_6 زیرگراف حاصل از حذف رأسِ formula_7 به همراهِ تمام یال‌های متصل به آن است. شکل(۱) زیرگراف‌های رأس‌حذفی گراف formula_1 را نشان می‌دهد. برای فرمول بندی دقیق حدس نیاز به دو مفهوم زیر داریم: مدل‌های گرافیکی
یک مدل گرافیکی یا مدل گرافیکی احتمالاتی(PGM) یک مدل احتمالاتی است که بیانگر ساختار [conditional dependancy وابستگی شرطی] بین متغیرهای تصادفی توسط یک گراف است. مدل‌های گرافیکی معمولاً در آمار و احتمال (به‌طور دقیق تر در آمار بیزی) و یادگیری ماشین استفاده می‌شوند.  به‌طور کلی مدل‌های گرافیکی احتمالی از یک نمایش مبتنی بر گراف به عنوان پایه و اساس برای رمزگذاری کامل توزیع بیش از یک و چند بعدی در فضا است و یک گراف که نمایش فاکتور سازی شده مجموعه‌ای از عدم وابستگی‌ها در توزیع خاص است استفاده می‌کند. دو شاخه از نمایش‌های گرافیکی از توزیع‌ها معمولاً استفاده می‌شوند، که شبکه‌های بیزی و مارکوف در شبکه‌های نام دارند. هر دو خانواده شامل خواص فاکتور سازی و عدم وابستگی هستند، اما آن‌ها در مجموعه‌ای از عدم وابستگی از توزیع که می‌توانند رمز و فاکتور سازی کنند تفاوت دارند. گراف (ریاضی)
گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال‌هایش یکدیگر را تنها در رأس‌ها قطع کنند. به این گراف هامنی نیز گفته می‌شود. کارت گرافیک
نوعی نوسان‌ساز الکترونیکی است که از قانون تشدید (Resonance) و اثر پیزوالکتریک (Piezoelectric) در کریستال کُوارتز استفاده می‌کند. این نوسان‌ساز برای زمان‌بندی (Timing) و تولید سیگنال ساعت (Clock signal) در مدارهای الکترونیک استفاده می‌شود. گرافیت هسته‌ای
گرافیت هسته‌ای () به کلیه گریدهای گرافیت که به عنوان آرام کننده نوترون و یا Neutron reflector در راکتورهای هسته ای مورد استفاده قرار می‌گیرند گفته می‌شود. گرافیت به دلیل خلوص بالا و مقاومت خوب در برابر درجه حرارت‌های بالا، کاربرد زیادی در صنایع هسته ای دارد. این نوع خاص گرافیت باید فاقد مواد جاذب نوترون از جمله بور باشد. گراف (ریاضی)
گراف همپوشانی منابع غذایی در بوم شناسی یکی از کاربردهای گراف در رشته‌های دیگر مانند زیست‌شناسی است، در این گراف منابع غذایی یک اکوسیستم مدل می‌شوند و آگاهی مناسبی از رقابت‌های میان هر گونه ارائه می‌دهند گراف (ریاضی)
گراف وزن‌دار: گراف وزن‌دار، گرافی است که به هر یک از یال‌ها یا به هریک از راس‌های آن عددی نسبت داده شده‌است که وزن آن یال یا راس می‌باشد. وزن یال می‌تواند نشان دهنده هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسنده‌ها به گراف وزن‌دار گراف شبکه‌ای می‌گویند. قرارداد‌ها: گراف
گراف در زبان انگلیسی به معنای نمودار است. گراف ممکن است به یکی از موارد زیر اشاره داشته باشد: الگوریتم‌های جورسازی گراف
در مجموعه‌ای از افراد، هر فرد با برخی از افراد دیگر سازگار است، یافتن شرایطی که تحت آن بتوانیم افراد را به صورت جفت سازگار باهم دسته‌بندی کنیم. بسیاری از کاربردهای گراف‌ها تضمین‌کنندهٔ چنین جفت سازی‌هایی هستند. یک جورسازی در یک گراف بی سوی G مجموعه‌ای از یال‌های دو به دو مجزا می‌باشد. رأس‌های متعلق به یال‌های یک جورسازی، اشباع شده و سایر رأس‌ها اشباع نشده هستند. اگر یک جورسازی هر راس از G را اشباع کند، آن گاه یک جورسازی تام یا جورسازی کامل است. برای جستجوی یک جورسازی بزرگ، می‌توانیم به‌طور مکرر یالی مجزا شده از یال‌های بیشتر انتخاب شده، را، در نظر بگیریم. این روند یک جورسازی ماکسیمال را به دست می‌دهد، اما لزومی ندارد که یک جورسازی بیشینه رابدهد. یک جورسازی ماکسیمال را نمی‌توان بیشتر نمود، زیرا یال‌های آن با همهٔ یال‌های دیگر متلاقی می‌باشد ولی یک جورسازی بیشینه، یک جورسازی با حداکثر اندازه‌است. طبق قضیه برژ جورسازی‌های بیشینه هیچ مسیر افزوده‌ای ندارند. اگر "G"و"H" گراف‌هایی با مجموعهٔ رأس‌های "V" باشند، آنگاه تفاضل متقارن "GΔH"، گرافی با مجموعهٔ رأس‌های "V"است که یال‌هایش همهٔ یال‌هایی هستند که دقیقادر "G" یا "H" ظاهر شوند. بنابراین اگر "M"و"N" جورسازی باشند آن گاه داریم: اگر گراف "X"، گراف"M"را اشباع کند، آن گاه برای هرformula_1 باید حداقلformula_2راس وجود داشته باشند که دارای همسایه‌هایی در formula_2 باشند.قضیه هال ثابت می‌کند که این شرط لازم و کافی است. مشخص‌سازی مسیر-افزوده برای جورسازی‌های بیشینه به الگوریتم تطابق بیشینه در گراف دوبخشی برای یافتن جورسازی‌های بیشینه می‌انجامد. جستجوی پیاپی مسیرهای افزوده و افزایش آن به اندازهٔ یک یال موجب یافتن این مسیر می‌شود که در صورت عدم پیدا کردن یک مسیر افزوده، پوشش راسی با اندازهٔ جورسازی جاری یافت می‌شود. پروگراف
پروگراف یک زبان برنامه‌نویسی تصویری، شی گرا، جریان داده (چند شیوه‌ای) است و به عنوان موفق‌ترین (از لحاظ تجاری) زبان تصویری که چند هدف را دنبال می‌کند، شناخته شده‌است. این موفقیت تجاری به این دلیل است که پروگراف برنامه‌نویس را از کارهای خسته‌کننده و جزئیات غیرضروری زبان‌های رایج آزاد کرده‌است. پروگراف از علامت‌های آیکونی برای نشان دادن عملیاتی که باید روی داده انجام شود، استفاده می‌کند. محیط‌های تجاری توسعه نرم‌افزاری پروگراف مانند Prograph Classic و Prograph CPX طی چند سال برای سیستم عامل‌های مکینتاش و ویندوز موجود بود اما سرانجام در اواخر دهه ۹۰ میلادی از بازار خارج شد. پشتیبانی از زبان پروگراف در سیستم عامل‌های مک اخیراً با انتشار نرم‌افزار محیط توسعه Marten ممکن شده‌ است. نشاندن گراف
نوع هر گراف حداقل عدد صحیحی است که گراف می‌تواند درون یک سطح نوع n نشانده شود. به‌طور خاص یک گراف مسطح داری نوع صفر می‌باشد زیرا می‌تواند بر روی یک کره بدون تقاطع کشیده شود. گراف غیر جهت‌دار از نوع حداقل عدد صحیح n می‌باشد که گراف می‌تواند در یک سطح غیر جهت‌دار نوع n نشانده شود. گراف چگال
گراف چگال گرافی است که شمار یال‌های آن به بیشینه شمار یال‌ها نزدیک باشد. در برابر گرافی چگال، گراف تنک گرافی است که یال‌های اندکی داشته باشد. شناسایی گرافی چگال از یک گراف تُنُک وابسته به زمینه و گنگ است. چگالی برای گراف باسو با برابری formula_1 تعریف می‌شود. در این برابری‌ها، formula_2 شمار یال‌های گراف و formula_3 شمار گره‌های گراف است. شمار بیشینه‌ی یال‌ها در گراف‌های باسو برابر است با formula_4 و در گراف‌های بی‌سو formula_5 است. از این روی، بیشینه‌ی چگالی یک و کمینه‌ی آن صفر است. کاغذ رسم
کاغذ رسم ، نوعی کاغذ است که با خطوط ظریف یک شبکه منظم بر روی آن چاپ شده‌است. این خطوط اغلب به عنوان راهنمایی برای ترسیم توابع ریاضی یا داده‌های تجربی و رسم نمودارهای دو بعدی استفاده می‌شود. از این نوع کاغذ معمولاً در ترسیم‌های آموزشی ریاضی و مهندسی و در یادداشت‌های آزمایشگاهی استفاده می‌شود. کاغذ گراف به صورت ورق‌های مجزا یا صحافی شده در یک دفترچه در دسترس است. گراف جهت‌دار و کاربردهای آن
۱-طراحی یک استوانه کامپیوتری کارآمد رنگ‌آمیزی گراف
رنگ‌آمیزی گراف کاربردهای زیادی در زمینه‌های عملی و تئوری گوناگون دارد. علاوه بر مسئله‌های کلاسیک تعریف شده در این زمینه، با در نظر گرفتن محدودیت‌های مختلفی روی نوع گرافها، روی روش رنگ‌آمیزی و حتی تعداد و رنگ عناصر گراف مسئله‌های متنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل می‌شود. با وجود اینکه این مسئله از نظر علمی هنوز در حال رشد و بررسی بیشتر می‌باشد، با ظهور جدول سودوکو در بین عموم مردم شناخته و مشهور شده‌است. نظریه گراف
در این‌جا فقط صرفاً ماتریس‌های صفر و یک را در نظر می‌گیریم تا بتوانیم عملیات‌های ضرب و جمع را برای یک مجموعه صفر و یک به دست آوریم. افراز گراف
در ریاضیات، مسئله افراز گراف بر روی داده‌هایی در قالب گراف ("G=("V","E با "V" راس و "E" یال تعریف می‌شود به‌طوری‌که افراز گراف به مؤلفه‌های کوچکتری با ویژگی‌های خاص ممکن باشد. برای مثال، یک تقسیم‌بندی "k"-بخشی مجموعه رئوس را به "k" مؤلفه کوچکتر تقسیم می‌کند. افراز خوب به افرازی گفته می‌شود که تعداد یال‌های بین مؤلفه‌های مجزا از هم کم باشد. افراز یکریخت به نوعی از مسئله افراز گراف گفته می‌شود که تقسیم گراف به به مؤلفه‌ها به صورتی است که مؤلفه‌ها تقریباً هم اندازه باشند و اتصالات کمی بین مؤلفه‌های متفاوت وجود داشته باشد. مهم‌ترین کاربردهای افراز گراف در محاسبات علمی، تقسیم‌بندی قسمت‌های مختلف طراحی مدارهای VLSI و مدیریت زمانبندی کارها در سیستم‌های چندپردازنده‌ای، می‌باشد. اخیراً، استفاده از افراز یکریخت، به دلیل کاربردهای آن در خوشه بندی و یافتن گروه‌ها در شبکه‌های اجتماعی، شبکه‌های زیستی و شبکه‌های بیماری شناختی افزایش یافته‌است. کارت گرافیک
کارت گرافیک (با نام‌های کارت ویدئو، کارت نمایشگر، آداپتور نمایشگر، آداپتور گرافیک و برد گرافیک شناخته می‌شود) یک کارت توسعه است که تصاویر خروجی را برای نمایشگر تولید می‌کند. اکثر کارت‌های گرافیک، توابع مختلفی مانند شتاب دهندهٔ رندر صحنه‌های سه‌بعدی و دوبعدی، رمز گشایی کردن MPEG-2/MPEG-4، خروجی تلویزیون یا قابلیت اتصال چند مانیتور را ارائه می‌کنند. گراف تام
در نظریه گراف، گراف تام ، گرافی است که عدد رنگی آن برای هر زیرگراف القایی اش برابر با مرتبه بزرگترین کلیک آن زیرگراف (عدد کلیکی) باشد. به‌طور معادل می‌توان تعریف اخیر را برحسب نمادها بیان نماد: گراف دلخواهی چون formula_1 تام است اگر و تنها اگر برای تمام formula_2 داشته باشیم formula_3. گراف بازه‌ای
در نظریه گراف‌ها گراف بازه‌ای گرافی اشتراکی از خانواده‌ای از بازه‌هایی روی خط اعداد حقیقی است. به ازای هر بازه یک رأس رسم می‌گردد و بازه‌هایی که دارای اشتراک هستند (اشتراکشان تهی نیست) بین رئوس متناظرشان یال رسم می‌گردد. رنگبندی بخشی گراف
یکی از کاربردهای رنگ‌بندی بخشی گراف شامل زمانبندی فعالیت‌‌ها می‌باشد. در این مورد، گراف G یک گراف ناسازگاری است. یک یال در G بین رئوس v و u نشان می‌دهد که v و u نمی‌توانند همزمان فعال باشند. به عبارتی دیگر، مجموعه رئوس که به صورت همزمان فعال هستند، می‌بایستی یک مجموعه مستقل در گراف G باشند. یک رنگ‌بندی بخشی گراف بهینه در G کوتاه‌ترین زمانبندی ممکن را تولید می‌کند به طوری که هر رأس در مجموع برای حداقل ۱ واحد زمانی فعال باشد و در هر نقطه از زمان، مجموع رئوس فعال یک مجموعه مستقل باشد. اگر ما یک راه حل خطی برای برنامه خطی فوق داشته باشیم، ما به راحتی همه مجموعه‌های مستقل I را به صورت دلخواه پیمایش می‌کنیم. رئوسی که در I می‌باشند را برای مدت XI فعال در نظر می‌گیریم در حالی که رئوسی که در I نیستند را غیر فعال در نظر می‌گیریم. یک نمونه کاربرد واضح‌تر این است که مثلاً: هر رأس G یک انتقال رادیویی بی‌سیم را در یک ارتباط شبکه نشان دهد. یال‌های G تداخل در تبادلات رادیویی را نشان می‌دهند. هر انتقال رادیویی باید در مجموع به اندازه یک واحد زمانی فعال باشد. یک رنگ‌بندی بخشی گراف بهینه، یک زمانبندی با حداقل طول و بدون تداخل را به ما می‌دهد، به عبارت دیگر یک زمانبندی با حداکثر پهنای باند را به ما می‌دهد. گراف
در ریاضیات: گراف ۱-مسطح
یک گراف ۱-مسطح را یک گراف ۱-مسطح بهینه می‌گویند اگر دقیقاً ۴n − ۸ یال داشته باشد، که حداکثر تعداد ممکن است. در یک زیرگراف از یک گراف ۱-مسطح بهینه، یال‌های بدون تقاطع لزوماً تشکیل یک گراف مربعی می‌دهند (یک گراف چندوجهی که هر وجه آن یک چهارضلعی است). از این طریق هر گراف مربعی با اضافه کردن دو قُطر به هر یک از وجوه چهارضلعی‌اش یک گراف ۱-مسطح بهینه را تولید می‌کند. در نتیجه هر گراف ۱-مسطح بهینه یک گراف اویلری است (تمام رئوسش درجهٔ زوج دارند)، که حداقل درجهٔ رئوس در آن ۶ است. همچنین هر گراف ۱-مسطح بهینه حداقل ۸ رأس با درجهٔ دقیقاً ۶ دارد. به علاوه، هر گراف ۱-مسطح بهینه یک گراف ۴-رأس-همبند بوده، و هر بُرش ۴-رأسی در چنین گرافی یک حلقهٔ جداکننده در گراف مربعی زیرین است. گراف (ریاضی)
از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل می‌کنیم و در صورتی‌که در این وب سایت لینکی به وب سایت دیگری بود، یک یال جهت دار از این راس به راسی که وب سایت دیگر را نمایش می‌دهد وصل می‌کنیم. نظریه گراف
پیشرفت‌های اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف شده‌است به گونه‌ای که هم‌اکنون نظریهٔ گراف ابزار بسیار مناسبی برای تحقیق در زمینه‌های گوناگون مانند نظریه کدگذاری، تحقیق در عملیات، آمار، شبکه‌های الکتریکی، علوم رایانه، شیمی، زیست‌شناسی، علوم اجتماعی و سایر زمینه‌ها گردیده‌است. پایگاه داده‌های گراف
در یک پایگاه داده گراف گراف کامل
گراف کامل گراف ساده‌ای است که در آن هر رأس به تمامی راس‌های دیگر به وسیلهٔ یک یال متصل است. معمولاً گراف کاملِ formula_1 راسی را با formula_2 نمایش میدهند. آغاز نظریه گراف‌ها معمولاً با کار اویلر بر روی هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است. با این حال، تاریخچه گرافهای کامل به رسم‌های رامون یوی در قرن سیزدهم بازمی‌گردد، که رئوس گراف را در گوشه‌های چندضلعی منتظم قرار میداد. این رسم‌ها با عنوان گل رز عرفانی نیز شناخته می‌شوند.شکل پایین شامل گرافهای کامل که دارای یک تا هشت رأس هستند می‌باشد: تمامی درایه‌های گراف کامل ۱ هستند به جز درایه‌های روی قطر اصلی که صفر هستند چون گراف کامل طوقه وجود ندارد. همریختی گراف
همریختی گراف در زمینه نظریه گراف در ریاضیات، نوعی نگاشت مرتبط با ساختار در بین دو گراف است. اگر دقیق‌تر بگوییم، همریختی نوعی تابع بین مجموعه راس‌های دو گراف است، که در آن راس‌های مجاور در یک گراف به راس‌های مجاور در گراف دیگر تناظر می‌یابد. گراف (ریاضی)
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأس‌های G و اعضای E را یال‌های G می‌نامیم. به بیان ساده‌تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقه‌ای (یعنی یالی که رأس را به خودش وصل می‌کند) نیز وجود نداشته باشد. نظریه گراف هندسی
گراف هندسی یک گراف است که در آن رأس‌ و یال‌ها با اشیاء هندسی همراه شده‌اند. ساده‌ترین نمونه آن گراف هندسی تصادفی است. نشاندن گراف
گراف نوع اویلر گرافیست از حداقل عدد صحیح n به طوری که گراف می‌تواند در یک سطح جهت دار نوع n/2 یا در یک سطح غیر جهت‌دار نوع n نشانده شود. یک گراف از نوع ساده جهت‌دار می‌باشد اگر عدد اویلر آن کوچکتر از عدد غیر جهت دار آن باشد. ابرگراف
از نیم قرن گذشته،نظریه گراف دارای اهمیت بسیاری در زمینه‌های مختلف از جمله هندسه، نظریه اعداد، بهینه‌سازی، توپولوژی، جبرهای میانی و نظیر آن‌ها بوده‌است. برای حل مسایل ترکیبیاتی جدید، لازم بود که مفهوم گراف توسعه داده شود. حدود سال١٩۶٠مفهوم ابرگراف پدیدار شد و یکی از اهداف ابتدایی آن، تعمیم برخی از نتایج کلاسیک نظریه گراف بود. نظریه ابرگراف، ابزاری مفید برای مسایل بهینه‌سازی گسسته است. نظریه گراف جبری
شاخهٔ اول نظریه گراف جبری شامل مطالعه گراف‌ها با استفاده از جبر خطی است که آن را مطالعه طیف ماتریس مجاورت، یا ماتریس لاپلاس از یک گراف (این بخش از نظریه گراف جبری نظریه گراف طیفی نیز نامیده می‌شود) می‌نامند. برای گراف پترسن، برای مثال، طیف ماتریس مجاورت برابر با (۳, ۱, ۱, ۱, ۱, ۱, ۲-, ۲-, ۲-, ۲-) می‌باشد. نظریه گراف
برای نمایش تصویری گراف‌ها معمولاً از نقطه یا دایره برای کشیدن رأس‌ها و از کمان یا خط راست برای کشیدن یال بین رأس‌ها استفاده می‌شود. رأس (نظریه گراف)
رأس یا گره در ریاضیات و نظریه گراف، یکی از یکاهای بنیانی گراف است. گراف مجموعه‌ای از گره‌ها و لبه‌هایی که این گره‌ها را وصل کرده‌اند (هابندیده‌اند). گرافی بی‌سو مجموعه‌ای از گره‌ها و مجموعه‌ای از یال‌ها (دوتایی‌هایی از گره‌ها) است. گرافی باسو دربردارندهٔ مجموعه‌ای از گره‌ها و مجموعه‌ای از کمان‌ها (دوتایی‌هایی مرتب از گره‌ها) است. برای نمایش گراف، گره‌ها با دایره‌ها (پَرهون‌ها) و لبه‌ها با خط‌هایی یا کمان‌هایی که از گره‌ای بیرون آمده‌اند و به گره‌ای دیگر درمی‌آیند، نمایانیده می‌شوند. گراف لایه‌بندی شده
یک گراف لایه بندی شده گراف همبندی است که راس‌های آن به مجموعه‌های L۰ تا Ln تقسیم بندی شده‌است .هر یال وزن صحیح نا منفی دارد و فقط رأس‌های لایه‌های پی در پی را به هم متصل میکند. عرض گراف برابر ماکسیموم تعداد رأس‌های هر لایه هست. در زیر الگوریتم‌هایی برای لایه بندی کردن یک گراف توضیح داده شده. اولین الگوریتم برای برای نمایش رابطه‌های وابسته در یک شبکه مناسب می‌باشد آگراف
آگراف اصطلاح فرانسوی به معنی گیرهٔ نگهدارندهٔ فلزی (قلاب، کلیپس، منگنه) است. در ساختمان سازی برای اتصال دو لایه مصالح به کار گرفته می‌شود، همچنین برای اتصال جداره‌های دیوار دوجداره کاربرد دارد. گراف (ریاضی)
گراف کامل: گرافی را که هر رأس آن با تمام رئوسِ دیگرِ، مجاور باشد گراف کامل می نامیم. گراف کاملِ n رأسی را با Kn نمایش می دهیم. می توان گفت Kn یک گراف n رأسی وn-1 ــ منتظم است. برازش گراف
در گراف نشاندن گراف formula_1 بر روی سطح Σ نمایش formula_1 بر روی Σ است که نقطه‌های Σ به راسهای گراف و منحنی‌های Σ (همسان‌ریختی تصویری در بازه [0,1]) به یالهای گراف متناظر شده‌اند به طوریکه: در این تعریف سطح فشرده و همبند و ۲-خمینه است. گراف شکافته
در شاخه نظریه گراف از ریاضیات، گراف شکافته (یا گراف شکافته‌شده)، گرافی است که رئوس آن را می‌توان به یک کلیک و یک مجموعه مستقل افراز نمود. گراف‌های شکافته را اولین بار فولدس و همر مطالعه نموده، و همچنین به‌طور مستقل توسط تیشکویچ و چرنیاک معرفی شدند. گراف فاکتور بحرانی
یک گراف critical (بدون قید و شرط) معمولاً این گونه تفسیر می‌شود که حذف هر یک از رأس‌ها تعداد رنگ‌های لازم برای رنگ آمیزی این گراف را کاهش می‌دهد. مفهوم critical بودن به‌طور عمومی در نظریه گراف‌ها اشاره بر این دارد که حذف هر رأسِ ممکن بعضی از ویژگی‌های وابسته به گراف را تغییر می‌دهد و بعضی را تغییر نمی‌دهد. یک matching-critical graph گرافی است که حذف هر رأس اندازه بیشترین تطابق را تغییر نمی‌دهد و طبق تعریف Gallai , گراف‌های matching-critical گراف‌هایی هستند که هر جزء همبند یک factor-critical می‌باشد. گراف مکمل یک گراف critical لزوماً matching-critical می‌باشد، این در واقع اصلی بود که Gallai از آن برای اثبات کران پایین تعداد رأس‌های یک critical graph استفاده کرد. در نظریه گراف پیشرفته، مفهوم factor-criticality با تعریف نوعی از دسته‌های جداشدنی روی matroid و توصیف matroid به عنوان یک factor-critical با این شرط که matroid دسته‌ای جداشدنی داشته باشد که تمام دسته‌ها فرد باشند، به قضیه matroid بسط داده شده‌است. گراف (ریاضی)
اندازه گراف تعداد یال‌های یک گراف است و به صورت formula_8 بیان می‌شود. رنگ‌آمیزی گراف
در نظریه گراف، رنگ‌آمیزی گراف یکی از حالت‌های خاص مسئله‌های برچسب‌گذاری گراف است. رویکرد کلی آن استفاده از نظیر کردن رنگهایی به یالها یا راس‌هاست که این رنگ‌آمیزی محدودیت خاصی را رعایت کند. در ساده‌ترین حالت، رنگ‌آمیزی‌ای مورد نظر است که در آن هیچ دو راس مجاوری هم رنگ نباشند (رنگ‌آمیزی راسها). علاوه بر آن رنگ‌آمیزی یالها به همین صورت تعریف می‌شود. گراف (ساختار داده)
یک ماتریس بولی دو بعدی، که در آن ردیف‌ها نشان دهنده رأس‌ها و ستون هانشان دهنده یال‌ها هستند. ورودی‌ها نشان می‌دهند که آیا رأس یک ردیف به یال یک ستون متصل است یا خیر. پرولوگ
یک نماد ویژه‌به نام گرامرهای قطعی (DCGs) وجود دارد. یک قاعده تعریف شده به عنوان -> به جای -: که با استفاده از آن می‌توان به تجزیه کردن و ایجاد یک رابط مناسب برای یک لیست بکار گرفت. DCG‌ها اغلب برای نوشتن پارسرها یا ژنراتورهای لیست استفاده می‌شوند، زیرا آن‌ها همچنین یک رابط کاربری مناسب برای لیست‌های متفاوت فراهم می‌کنند. در زیر یک مثال از این مورد را می‌بینید:  ::=   ::=  |    ::=  =  ;  ::=  |     ::=  |   ::= a | b  ::= ۰..۹  ::= + | - | * نظریه گراف
یال‌ها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد؛ مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده‌ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنین برای اینکه فاصله بین دو شهر را در گراف نشان دهید، می‌توانید از گراف وزن دار استفاده کنید و مسافت بین شهرها را با یک عدد بر روی هر یال نشان دهید. گراف (ریاضی)
می‌توان از گراف‌های تماس تلفنی رأی مدل کردن تماس‌های تلفنی برقرار شده در یک شبکه مانند شبکه تلفن راه دور استفاده کرد؛ که در ان رأس‌ها شماره تلفن‌ها و یال‌ها ارتباط‌های برقرار شده بین شماره تلفن‌ها است. ماتریس یک‌ها
ماتریس یک‌ها در زمینه ترکیبیات کاربردهایی دارند، به طور خاص‌تر در استفاده از روش‌های جبری برای نظریه گراف . به عنوان مثال، اگر "A" ماتریس همسایگی گراف "n-راسی" و بدون جهت "G" و "J" ماتریس یک‌ها از همان بُعد باشند، آنگاه "G" یک گراف منتظم است اگر و تنها اگر "AJ" = "JA" . رنگ‌آمیزی گراف
معمولاً تا زمانی که ذکر نشده‌است، منظور از رنگ‌آمیزی گراف یک رنگ‌آمیزی مناسب رأس‌های یک گراف است. یا به عبارتی یک برچسب‌گذاری رأس‌های گراف است به شکلی که هیچ دو راسی که یک یال آن‌ها را متصل می‌کنند همرنگ نباشند. از آنجایی که یک طوقه نمی‌تواند این ویژگی را داشته باشد، این گراف‌ها باید بدون طوقه باشند. درخت (نظریه گراف)
در نظریهٔ گراف، درخت گرافی همبند و بدون دور است. درخت‌ها به‌طور گسترده در علوم رایانه و ساختار داده‌ها کاربرد دارند. مثل درخت‌های جستجوی دودویی، پشته‌ها درخت‌های هافمن برای فشرده‌سازی اطلاعات و غیره. نمودار دایره‌ای
نمودار دایره‌ای یا گراف دایره‌ای، نموداری دایره‌ای است که به بخش‌های گوناگون بخش می‌گردد. جدا کردن بخش‌ها در نمودار دایره‌ای، نسبت و تناسب میان اجزای نموداری را تعیین می‌کند. در نمودار دایره‌ای اندازه طول کمان و به پیروی ار آن زاویه و مساحت قطاع هر بخش، میزان بزرگی مؤلفه نموداری را مشخص می‌کند. گراف پترسن
در نظریه گراف ، گراف پترسن گرافی غیر جهت دار، با ۱۰ راس و ۱۵ یال است. این گراف، گرافی کوچک می‌باشد که به عنوان مثالی مفید و همچنین مثال نقض در بسیاری از مسائل نظریه گراف به کار می‌رود.یولیوس پترسن(۱۸۳۹-۱۹۱۰) دانشمندی دانمارکی بود که در سال ۱۸۹۸ گرافی را، که به نام خودش ثبت شد، به عنوان کوچکترین گراف مکعبی (گرافی که هر راس آن از درجه ۳ باشد.) بدون پل ساخت. در واقع این گراف مثال نقضی برای این ادعا بود که یک گراف مکعبی بدون پل متصل، داری یک رنگ آمیزی یالی با ۳ رنگ است. در حالی که این گراف دارای این رنگ آمیزی با ۴ رنگ می‌باشد. با این که این گراف به‌طور عمومی به یولیوس پترسن نسبت داده می‌شود، ولی درحقیقت برای اولین بار ۱۲ سال زودتر از ساختن آن توسط وی، در سال ۱۸۸۶ به وجود آمده بود.دونالد نوث اذعان می‌کند که گراف پترسن، شکل و پیکری قابل توجه‌است که به عنوان مثالی نقض برای بسیاری از اسناد و اثبات‌های خوش بینانه دربارهٔ این که چه چیزهایی ممکن است به‌طور عمومی برای گراف‌ها درست باشد، به کار می‌رود. میتروید
در نظریهٔ گراف می‌توانید یک گراف را بردارید و مجموعهٔ پس‌زمینه را مجموعهٔ گره‌های آن برداشته و یک مجموعه از این گره‌ها را وابسته در نظر بگیرید هر گاه یک دور در زیرگراف القا شده از این گره‌ها وجود داشته باشد. به این میتروید، میتروید گرافی می‌گویند. در جبرخطی می‌توانید یک فضای برداری اتنخاب کرده و یک مجموعه بردار دلخواه از این فضا را به عنوان مجموعهٔ پس‌زمینه بردارید. یک مجموعه از این بردارها را وابسته گوئیم هر گاه وابستهٔ خطی باشند یعنی یک ترکیب خطی نابدیهی از آن‌ها صفر شود. به این میتروید، میتروید ماتریسی می‌گوئیم. علت این نامگذاری این است که می‌توان نمایش برداری این بردارها را در نظر گرفته و با کنار هم قرار دادن آن‌ها یک ماتریس داشت که آنگاه مجموعهٔ پس‌زمینهٔ ما گردایهٔ ستون‌های این ماتریس است. در جبرجابجایی می‌توان رابطهٔ وابستگی میتروید را وابستگی جبری در نظر گرفت. رنگبندی بخشی گراف
و گراف دوبخشی
در علوم کامپیوتر، شبکهٔ Petri net) Petri) یک ابزار مدل‌سازی ریاضی است که در آنالیز و شبیه‌سازی سیستم‌های همزمان استفاده می‌شود. یک سیستم به صورت یک گراف دوبخشی جهتدار با دو بخش مدل‌سازی می‌شود: یک بخش از راس‌های «مکان» که شامل منابع هستند و یک بخش از راس‌های «رخداد» که منابع را مصرف و/یا تولید می‌کنند. محدودیت‌های بیشتری روی راس‌ها و یال‌ها وجود دارند که رفتار سیستم را محدود می‌کنند. شبکهٔ Petri از ویژگی‌های گراف‌های دوبخشی جهتدار و سایر ویژگی‌ها استفاده می‌کند تا امکان ارائهٔ اثبات‌های ریاضی برای رفتار سیستم‌ها و در عین حال پیاده‌سازی سادهٔ شبیه‌سازی‌های سیستم‌ها را فراهم کند. گراف (ریاضی)
کاربرد گراف بازه‌ها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد. جنسیت اتصال‌دهنده‌ها و چفت‌ها
در اصطلاح ریاضی نظریه گراف، یک شبکهٔ توزیع انرژی الکتریکی که از دوشاخه‌ها و پلاگ‌ها ساخته شده یک درخت جهت‌دار است، که جهت فلش‌ها مربوط به انتقال انرژی الکتریکی از ماده به نر از طریق هر اتصالِ «جفت شده» است. این نمونه‌ای است که در آن اتصال دهنده‌های نر و ماده به‌طور عمدی به‌گونه‌ای طراحی و استفاده شده‌اند که در عمل نقش خود را به‌عنوان یک توپولوژی ایمن اجرا کنند. گراف جهت‌دار
در ریاضیات و به‌طور خاص در نظریهٔ گراف، گراف جهت‌دار یا گراف سودار گرافی (مجموعه‌ای از گره‌ها که با یال‌ها به هم متصل شده‌اند) است که در آن به هر یال جهتی نسبت داده شده‌است. به زبان ریاضی، یک گراف جهت‌دار زوج مرتبی به صورت formula_1 است (گاهی به صورت formula_2 نیز نمایش داده می‌شود) که در آن گردآورد (نوع داده انتزاعی)
یک داده ساختار گراف اساساً از یک مجموعهٔ متناهیِ زوج‌های مرتب موسوم به یال شامل واحدهایی به نام رأس یا گره تشکیل می‌شود؛ همان‌طور که در ریاضیات به ازای یک یال (u,v) می‌گوییم که u به v می‌رود یا u و v مجاورند. همچنین می‌توان به هر یال یک گراف یک عدد نسبت داد که در این صورت گراف وزن دار به وجود می آید . گراف‌های پنجه‌آزاد
در نظریه گراف، که بخشی از ریاضیات است، گراف پنجه‌آزاد گرافی است که زیرگراف پنجه نداشته باشد. پنجه نام دیگر گراف دوبخشی کامل formula_1 است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد. افراز گراف
فرض کنید گرافی به صورت ("G=("V","E دارید که "V"، مجموعه‌ای با "n" راس و "E" مجموعه یال هاست. برای یک مسئله افراز متعادل با زوج مرتب ("k","V")، هدف افراز "G" به "k" مؤلفه با حداکثر سایز ("v")("n"/"k") با مینیمم تعداد یال‌های مشترک بین این مؤلفه هاست. یا این که برای "G" و K">1" داده شده "V" را به "K" بخش …,"K1","k2" تقسیم کنید به‌طوری‌که بخش‌ها از هم مجزا باشند و دارای اندازه‌های مساوی بوده به علاوه این که تعداد یال‌هایی که نقاط انتهایی آن‌ها در دو بخش متفاوت قرار دارد کمینه شود. در مورد این مسائل به شکلی مشابه مسئله شیوه افزایش منابع بحث می‌شود. توسعه‌ای از این مسئله در مسئله ابرگراف‌ها مطرح می‌شود که در آن یک یال می‌تواند به بیش از دو راس متصل باشد. یک ابریال قابل برش نیست، اگر همه رأس‌ها در یک افراز باشند، در مقابل دقیقاً یک بار بریده می‌شود، اگر یکی از این رأس‌ها در یک افراز دیگر قرار بگیرد، مستقل از تعداد راس‌هایی که در افراز دیگر قرار گرفته‌اند. از ابراگراف‌ها در خودکارسازی طراحی‌های الکترونیکی استفاده می‌شود. گراف (ریاضی)
مکمل یک گراف: مکمل گرافی مانند G که آن را با G^c یا G ̅ نمایش می دهیم گرافی است که مجموعهٔ رئوس آن همان مجموعهٔ رئوس گراف G است و بین دو رأس از G^cیک یال است اگر و تنها اگر بین همان دو رأس درG یالی وجود نداشته باشد. فهرست برخی گراف‌های خاص
گراف پترسن، گراف مکمل گراف خط formula_2 است. همچنین گراف کنزر formula_3 است به این معنا که اگر برای هر کدام از زیرمجموعه‌های دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعه‌ها ی نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته می‌شود.  گراف پترسن هم با گراف کامل formula_2 و هم با گراف دوبخشی کامل formula_5 همومورف است.  متداول‌ترین شیوهٔ رسم گراف پترسن در یک صفحه، یک پنج ضلعی با یک ستارهٔ پنج رأسی درون آن است که هر یک از رأس‌های ستاره به رأس‌های پنج ضلعی با یک یال وصل می‌شود.این شیوهٔ نمایش متقارن است. در این شکل یال‌ها در ۵ نقطه یکدیگر را قطع می‌کنند.(شکل۱) این روش ترسیم بهترین روش برای مینیمم کردن تعداد تقاطع‌ها نیست. روشی دیگر برای کشیدن گراف پترسن با دو نقطهٔ تقاطع وجود دارد که در شکل۲ نشان داده شده‌است. بنابراین عدد تقاطع گراف پترسن ۲ است.  گراف پترسن همچنین می‌تواند در صفحه به گونه‌ای رسم شود که همهٔ یال‌ها طول یکسان برابر واحد داشته باشند.(شکل۳)  گراف پترسن مسیر هامیلتونی دارد ولی دور هامیلتونی ندارد. گراف پترسن کوچکترین گراف شبه هامیلتونی است یعنی اگرچه دور هامیلتونی ندارد، هر کدام از رأس‌هایش که حذف شوند می‌توان یک دور هامیلتونی در آن پیدا کرد.(شکل۴) در نظریه گراف گراف نسر،formula_6، گرافی است که رأس‌های آن نظیر زیرمجموعه‌های k عضوی از یک مجموعه ی n عضوی است. بین دو رأس یک یال وجود دارد اگر و تنها اگر زیرمجموعه‌های نظیر رأس‌ها ناسازگار باشند(اشتراکشان تهی باشد). این گراف‌ها به نام مارتین کنزر نامگذاری شده‌اند که برای اولین بار آن‌ها را در سال ۱۹۵۵ بررسی کرد. مکعب‌ها با ابعاد مختلف می‌توانند گراف در نظر گرفته شوند. مکعب با بعد n را با formula_10 نشان می‌دهیم. کد گری کدی است که هر کد با کد قبلی فقط در یک بیت تفاوت دارد و کد آخر با کد اول نیز در یک بیت متفاوت است. می‌توانیم این مسئله را با استفاده از formula_10 حل کنیم. هر کدگری دور هامیلتونی در formula_10 است. می‌توانیم formula_10 را از روی formula_14 بسازیم. ابتدا یک کپی از formula_14 رسم می‌کنیم(formula_16). ابتدای بیت‌های formula_14، صفر و ابتدای بیت‌های formula_16، یک می‌گذاریم. سپس رأس‌های متناظر formula_14 و formula_16 را به هم وصل می‌کنیم. گراف کیلی
در ریاضیات یک گراف کیلی، گرافی است که ساختار جبری یک گروه جبری را در خود دارد. نام گراف کیلی پس از قضیهٔ کیلی پیشنهاد شد که در تعریف آن یک گروه به همراه مجموعه‌ای از عناصر آن (معمولاً مولد آن گروه) در نظر گرفته می‌شود. گراف (ریاضی)
گراف دو بخشی کامل گرافی است که رئوس هر کدام از مجموعه‌های v یا u دو به دو با رئوس مجموعهٔ دیگر همسایه باشند. اگر حتی یکی از رئوس با همهٔ اعضای مجموعهٔ مقابل همسایه نباشد گراف دو بخشی کامل نیست. گرافولوژی
مهمترین کاربرد گرافولوژی، گزینش متقاضیان استخدام است. همچنین از گرافولوژی می‌توان در زمینه‌های جرم‌شناسی و برای تشخیص صداقت متهمان نیز استفاده کرد. به‌طور کلی می‌توان کاربرد گرافولوژی را در دو دسته اصلی زیر خلاصه کرد: گراف (ریاضی)
در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضایش به گونه‌ای با هم پیوند دارند. اعضای این مجموعه می‌توانند چند انسان باشند و ارتباط میان آن‌ها دست دادن با یکدیگر باشد. اعضا می‌توانند اتم‌ها در یک مولکول باشند و ارتباطشان پیوندهای شیمیایی باشد یا این که اعضا می‌توانند بخش‌های گوناگون یک زمین و ارتباط میانشان، پل‌هایی باشد که آن‌ها را به هم می‌پیوندند (همانند مسئله کونیگسبرگ). مسئله بزرگترین خوشه
در حوزهٔ ریاضیاتی نظریه گراف، خوشه (clique) یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). به عبارتی یک خوشه، یک زیرگراف کامل است. خوشه‌ها یکی از مفاهیم پایه‌ای نظریهٔ گراف‌ها هستند و از آن‌ها در بسیاری از مسائل استفاده می‌شود. گراف‌ها یکی از مهم‌ترین حوزه‌های مطالعاتی و کاربردی در علوم رایانه هم هستند و به دنبال آن، خوشه‌ها هم مورد توجه زیادی قرار می‌گیرند. علی‌رغم این که مطالعهٔ گراف‌های کامل و زیرگراف‌های کامل به دههٔ سوم قرن بیستم میلادی بازمی‌گردد، اما می‌توان گفت مطالعهٔ خوشه‌ها برای اولین بارها در نیمهٔ این قرن توسط دو دانشمند انجام شدند که می‌خواستند با استفاده از نظریهٔ گراف‌ها و مفهوم خوشه، گروه‌های انسانی‌ای که همگی با یکدیگر ارتباط دارند را مدل کنند (در ساده‌ترین صورت، یک گراف می‌تواند مدل‌سازی ای از روابط اجتماعی باشد: هر راس یک شخص است و دو شخص که با یکدیگر ارتباط داشته باشند، بین راس‌های متناظرشان یال وجود دارد. با این تعاریف، یک خوشه نشان‌دهندهٔ زیرمجموعه‌ای از افراد است که همگی با یکدیگر ارتباط دارند). مسئلهٔ چک کردن موجودیت خوشه‌ای با اندازهٔ مشخص در یک گراف، در دستهٔ مسائل ان‌پی کامل (NP-Complete) قرار می‌گیرد، یعنی برای آن هیچ الگوریتم شناخته‌ای که در زمان چندجمله‌ای قابل اجرا باشد وجود ندارد. با این وجود، الگوریتم‌های زیادی برای حل این مسئله و سایر مسائل مربوط به خوشه‌ها مورد مطالعه و بررسی قرار گرفته‌اند. در گسترهٔ وسیعی از مطالعات و پژوهش‌های علمی از نظریهٔ گراف‌ها و به دنبال آن از خوشه‌ها استفاده می‌شود. برای مثال در علوم اجتماعی محاسباتی برای مدل‌سازی گروه‌های دوستی و انسانی کاربرد فراوان دارد. همچنین در بیوانفورماتیک و شیمی محاسباتی نیز توجه زیادی به خوشه‌ها می‌شود. تطابق (گراف)
که در آن، n تعداد گره‌ها گراف است. هر یک از انواع چندجمله‌ای بالا، کاربردهای مخصوص به خود را دارد. برای کسب اطلاعات بیشتر در این مورد، می‌توانید مقالات مربوط به چندجمله‌ای‌های تطابق را مطالعه کنید. گراف (ساختار داده)
این نوع دوگان گراف از گراف اولیه استخراج می‌شود. به عبارت این نوع دوگان گراف از گراف اولیه دیگر بعد از اینکه گراف اولیه بر اساس دیدگاه‌های رایج آن استخراج شد، سپس دوگان گراف آن بر اساس قوانین خاصی استخراج می‌شود. در این طبقه دو نوع دوگان یعنی دوگان گراف ورونی و دوگان گراف خطی را می‌توان گنجاند. دوگان گراف ورونی تعریف: دوگان گراف ورونی یک گراف مسطح، گرافی است که گره‌های آن نماهای گراف اولیه بوده و یال‌های آن بیانگر ارتباطات همجواری در گراف اولیه باشد این نوع دوگان دارای ویژگی‌های زیر است: -دوگان گراف ورونی یک گراف مسطح یک گراف مسطح است (که ممکن است یال موازی و حلقه نیز داشته باشد(. - اگر G یک گراف همبند وG‘، دوگان گراف ورونی آن باشد، آنگاه G نیز، دوگان گراف ورونیG‘ خواهد بود. -- دوگان‌های گراف ورونی یک گراف منحصر به فرد نیستند ویک گراف می‌تواند چندین دوگان گراف ورونی غیر یک ریخت داشته باشد. زیرا با تغییر نمایش گراف اولیه دوگان گراف ورونی آن نیز تغییر می‌کند این نوع دوگان گراف بیشتر در مسائلی که در آن‌ها نیاز به تقسیم‌بندی فضا است استفاده شده‌است. به عنوان مثال الگوریتم تولید پلیگون‌های تیسن از روی تعدا نقاط یمی از موارد کاربرد این نوع دوگان است. از دوگان ورونی گراف برای تقریب الگوریتم‌های کوتاه‌ترین مسی بر مبنای معیار فاصله استفاده کرده‌اند. چون تعداد گره‌ها در دوگان ورونی گراف به مراتب کمتر از گراف اولیه است، به همین دلیل آن‌ها نشان داده‌اند که جواب تقریبی مسئله کوتاه‌ترین مسیر بر مبنای فاصله را می‌توان در دوگان ورونی گراف اولیه محاسبه کرد. گراف جهت‌دار و کاربردهای آن
گراف جهت داری که دارای هیچ طوقه‌ای نیست و بین هر دو راس آن، هیچ دو کمان هم جهتی قرار ندارد یک گراف جهت دار قوی نامیده می‌شود. گراف (ریاضی)
نظریه گراف یکی از موضوع‌های مهم در ریاضیات گسسته است که به شناخت گراف‌ها و مدل‌بندی مسایل با آن‌ها می‌پردازد. لئونارد اویلر در سال ۱۷۳۶ با حل مسئله پل‌های کونیگسبرگ نظریهٔ گراف‌ها را بنیان گذاشت. اما جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ این مدل‌های ریاضی را گراف نامید. رابطه دوتایی
آیا یک رابطه بیش‌تر از یک گراف آن است؟ ترکیبیات
مسائل ترکیبیات در بخش‌های زیادی از ریاضیات خالص مانند جبر، نظریه احتمالات، توپولوژی و هندسه به‌وجود می‌آیند و ترکیبیات کاربرد بسیاری در بهینه‌سازی، علوم رایانه، نظریه ارگودیک و فیزیک آماری دارد. به‌طور تاریخی بسیاری از مسائل ترکیبیات، راه حلی تک کاره به مسائلی که در بخش‌های مختلف ریاضی پیش آمده‌اند داده‌است. اما در اواخر سده بیستم متدهای کلی و قدرتمندی درست شد که ترکیبیات را به بخشی جدا از ریاضیات تبدیل کرد. یکی از قدیمی‌ترین و دم‌دستی‌ترین تکه‌های ترکیبیات نظریه گراف‌ها است که کاربردهای بسیاری در شاخه‌های مختلف دارد. ترکیبیات در علوم رایانه برای بدست آوردن فرمول‌ها و تخمین‌ها در تحلیل الگوریتم‌ها کاربرد بسیاری دارد. گراف مکمل
در نظریه گراف، مکمّل یا معکوس گراف ، گراف با رئوس یکسان است به طوری‌که دو رأس متمایز مجاورند اگر و فقط اگر آن دو راس در مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال‌های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می‌شوند و تمام یال‌هایی که قبلاً وجود داشتند حذف می‌گردند. گراف باند
روش باند گراف در واقع یک زبان مشترک برای نمایش و مدل‌سازی سیستم‌های دینامیکی مختلف از قبیل مکانیکی، الکتریکی، شیمیایی، سیالاتی و … است. مبنای این روش شارش جریان از منابع تولید کنندهٔ توان به سمت مصرف‌کننده‌ها است که حاصل ضرب دو عامل flow و effort می‌باشد. به عنوان مثال یک مقاومت الکتریکی که در یک مدار به یک منبع متصل است توانی از آن می‌گذرد که حاصل ضرب ولتاژ (effort) و جریان (flow) است. نظریه گراف
تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط (وصل) شده‌اند. گراف مسطح
در نظریه گرافها، گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند. رنگ‌آمیزی فهرستی گراف
در نظریه گراف، که شاخه‌ای از ریاضیات است، رنگ‌آمیزی لیستی نوعی از رنگ‌آمیزی گراف است. در این رنگ‌آمیزی برای هرراس لیستی از رنگ‌ها وجود دارد که آن راس می‌تواند توسط یکی از رنگ‌های این لیست رنگ شود. این شاخه ابتدا توسط ویزینگ، اردوش، رابین و تیلور مورد مطالعه قرار گرفت و بنیان آن بنا شد. گراف (ریاضی)
برای مثال، می‌توانیم از یک گراف ساده برای نمایش این که آیا دو نفر همدیگر را می‌شناسند، یعنی آیا آشنا هستند، استفاده کنیم. پروفایل بار
از این گراف در نیروگاه‌ها (و دیگر تولیدکنندگان انرژی) برای برانامه ریزی مقدار انرژی مورد نیاز و تولید متناسب با آن برای تحویل به مصرف‌کنندگان استفاده می‌شود. گراف (ریاضی)
با اجرای هم‌زمان جملات مشخص یک برنامه کامپیوتری، می‌توان آن برنامه را سریع تر اجرا کرد. مهم است که جمله‌ای که نتایج جملاتی که هنوز اجرا نشده‌اند، نیاز دارد، اجرا نشود. وابستگی جملات به جملات پیشین را می‌توان با یک گراف (ریاضی) جهت دار نمایش داد. هر جمله با یک راس نمایش داده می‌شود و در صورتی یالی بین یک راس و راس دوم در نظر گرفته می‌شود که جمله نشان داده می‌شود با راس دوم نتواند قبل از اجرای جمله نشان داده شده‌است با راس اول اجرا شود. این گراف (ریاضی) یک گراف (ریاضی) تقدم نامیده می‌شود. مسئله بزرگترین خوشه
در حوزهٔ ریاضیاتی نظریهٔ گراف‌ها، خوشه یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). به عبارتی یک خوشه، یک زیرگراف کامل است. زیرگراف، گرافی است که مجموعهٔ راس‌هایش زیر مجموعهٔ راس‌های گراف مادر باشد و مجموعهٔ یال‌هایش هم زیرمجموعهٔ یال‌های گراف مادر باشد. گراف کامل گرافی است که بین هر دو راس مجزای آن، یال موجود باشد. پایگاه داده‌های گراف
اگر تازه وارد عرصه داده‌ها شده باشید حتماً این سؤال به ذهنتان خطور می‌کند که چرا باید اصلاً از یک پایگاه داده استفاده کنید به جای اینکه خودتان داده‌ها را آنطور که به نظرتان می‌آید برای پروژه مورد نظر بهتر و سریع تر است، ذخیره و بازیابی کنید؟ برچسب‌گذاری گراف
به بیان رسمی، برای یک گراف "G "، منظور از برچسب‌گذاری شدهٔ راسی، یک تابع است که رأس‌های گراف "G" را به مجموعه‌ای از برچسب‌ها می‌نگارد. به گرافی که برای آن چنین تابعی تعریف شده باشد یک گراف برچسب‌گذاری شدهٔ راسی می‌گویند. به همین ترتیب، یک برچسب‌گذاری ِیالی یک تابع از یال‌های گراف به مجموعه‌ای از برچسب هاست، که در این حالت گراف را برچسب‌گذاری شدهٔ یالی نام‌گذاری کرده‌اند. اگر برچسب‌های نگاشته شده به یال‌های گراف اعضای یه مجموعهٔ مرتب باشند (برای مثال مجموعهٔ اعداد حقیقی)، گراف را یک گراف وزن دار نیز می‌نامند. گراف (ریاضی)
بزرگ ترین و کوچک ترین درجۀ یک گراف: بزرگ ترین عدد در بین درجات رئوس گراف G را با∆ ( G) و کوچک ترینِ آنها را با δ (G) نمایش می دهیم و به ترتیب آنها را ماکزیمم و مینیمم درجهٔ گراف می نامیم. گراف (ریاضی)
گراف ساده: یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با formula_1 نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که رأس‌ها را به هم وصل می‌کنند و با formula_2 نمایش می‌دهیم. یک چنین گرافی را با formula_3 نشان می‌دهیم. اگر یال formula_4 دو رأس formula_5 و formula_6 را به هم وصل کند می‌نویسیم formula_7. گراف جهت‌دار: منظور از گراف جهت دار گرافی است که یال‌ها در آن دارای جهت هستند. گراف جهت دار G زوج مرتب (V,E) است که V مجموعه‌ای ناتهی و اعضای E زوجهای مرتب از اعضای V هستند. همانند گرافهای ساده، به اعضایV، راسهای G و به اعضای E، یال‌های G می‌گوییم. همچنین به هر گراف جهت‌دار نموداری در صفحه نسبت می‌دهیم. به این صورت که به ازای هر راس G نقطه‌ای در صفحه در نظر می‌گیریم و به ازای هر یال مانند (u,v) کمانی بین u و v رسم می‌کنیم و روی این کمان فلشی از u به v می‌گذاریم. گراف مور
است. گراف وزن‌دار
گراف وزن‌دار ، گرافی است که به هر یال آن عددی نسبت داده شده‌است که وزن آن یال می‌باشد. یا به راس آن عددی نسبت داده شده. وزن یال می‌تواند نشان دهنده هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسنده‌ها به آن گراف شبکه‌ای می‌گویند. از گراف وزن‌دار برای حل مسائلی چون فروشنده دوره گرد استفاده می‌شود. درگراف وزن‌دار، وزن‌ها را در ماتریس مجاورت ذخیره می‌کنند.وزن هر یال یک گراف موزون می‌تواند نشان دهنده یکی از موارد زیر باشد: اینفوگرافیک
در اکثر اوقات موارد استفاده از این نگاره‌ها در جایگاه‌هایی است که نیاز به توضیح ساده یا سریع داده‌ها احساس گردد، برای مثال نقشه‌ها، علائم و تابلوها، پوسترهای آموزشی و روزنامه‌ها از جمله کاربردهای آن‌ها هستند. همچنین ریاضیدانان و متخصصان آمار و کامپیوتر نیز از این ابزار برای به تصویر کشیدن مفاهیم پیچیده بهره می‌برند. یک اطلاع‌نگاشت کامل افزون بر اینکه در یک نگاه کلیات اصلی موضوع را به بیننده می‌رساند، دربرگیرنده جزئیات کلیدی موضوع برای دریافت بیشتر هست. ماتریس هموار
ماتریس‌های هموار در جبر خطی کاربرد زیادی دارند. یکی از کاربردهای آن‌ها تبدیلات خطی می‌باشد که توابع را به ابعاد بالاتر می‌برد. همچنین به عنوان ضریب در معادلات خطی به کار می‌آیند. ماتریس‌ها در زمینه‌های فراوانی کاربرد دارند از جمله در فیزیک یا هندسه اپتیک و در ماشین‌های ماتریسی. نظریه گراف‌ها نیز از ماتریس‌ها برای نگاه داشتن فاصله بین رِاس‌ها استفاده می‌کند. در گرافیک کامپیوتری، از ماتریس‌ها برای تبدیل فضای ۳ بعدی به صفحه نمایش دو بعدی استفاده می‌شوند.