انواع گراف چیست و چه کاربردی دارد؟
گراف (ریاضی)
از گراف‌ها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و… استفاده می‌شود. مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتم‌های مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. در این جا به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل رأس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مسئله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.
نظریه گراف
مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتمهای مناسب مانند الگوریتم دایکسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. آپاچی اسپارک
GraphX یک کتابخانه برای پردازش گراف‌ها و انجام پردازش‌های موازی بروی داده‌های گراف می‌باشد. GraphX همانند مؤلفه‌های اسپارک استریمینگ و اسپارک SQL, APIهای RDDها را توسعه داده و ما را قادر می‌سازد تا گراف‌های جهت‌دار با نسبت دادن مشخصات به هر گره و یال ایجاد کنیم. GraphX همچنین عملگرهای مختلفی را برای تغییر گراف‌ها (نظیر subgraph و mapVertices) و کتابخانه‌ای از الگوریتم‌های گراف (نظیر PageRank و شمارش مثلث‌های گراف) فراهم آورده‌است. مدل گرافی
یک مدل گرافی مدلی احتمالاتی است که در آن استقلال شرطی بین متغیرها توسط یک گراف نشان‌داده می‌شود. دو نوع مدل گرافی وجود دارد: مدل با گراف جهت‌دار که شبکه بیزی نامیده می‌شود و مدل با گراف ساده که میدان تصادفی مارکفی نامیده می‌شود. مدل‌های گرافی به وفور در نظریه احتمالات و آمار به ویژه در آمار بیزی و یادگیری ماشین به‌کار می‌روند. گراف جهت‌دار و کاربردهای آن
گراف جهت دار D، یک سه تایی مرتب((Ψ(D و (A(D و (V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راسها و یک مجموعه (A (D مجزای از (V(Dاز کمانها و یک تابع وقوع(Ψ(D که به هر کمان D یک زوج مرتب از راسهای D- که الزاماً متمایز نیستند- را نسبت می‌دهد. اگر a یک کمان وu,v دو راس باشند به طوری که(u,v) = Ψ(D)(a)، آنگاه میگوئیم که u,a را به v وصل کرده‌است؛ u، دم v,a سرa نامیده می‌شود. گراف (ریاضی)
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه‌ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می‌نامند. به عنوان مثال گراف زیر یک گراف دو بخشی است: گراف مکمل
در نظریه گراف، مکمّل یا معکوس گراف ، گراف با رئوس یکسان است به طوری‌که دو رأس متمایز مجاورند اگر و فقط اگر آن دو راس در مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال‌های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می‌شوند و تمام یال‌هایی که قبلاً وجود داشتند حذف می‌گردند. جامعه‌شناسی ریاضی
علاوه بر این، آشنایی "پیوند مثبت" است ولی "روابط منفی" مانند دشمنی بین افراد چطور؟ برای مقابله با این مساله، نظریه گراف که مطالعه ریاضی نمایش‌های انتزاعی شبکه‌های نقاط و خطوط است، می‌توان این دو نوع پیوند را در نظر گرفت و در نتیجه مدل‌هایی طراحی کرد که روابط احساسات هم مثبت و هم منفی را نشان می‌دهد که به صورت گراف امضا شده نمایش داده می‌شوند. اگر حاصل ضرب علایم همه روابط در هر چرخه (پیوندها در هر چرخه نمودار) مثبت باشد، گراف علامت‌دار نظریه تعادل نامیده می‌شود. از طریق رسمی‌سازی توسط ریاضیدان فرانک هراری، این کار قضیه اساسی این نظریه را تولید کرد که می‌گوید اگر شبکه‌ای از پیوندهای مثبت و منفی مرتبط به هم متوازن باشد، به عنوان مثال همان‌طور که با اصل روان‌شناختی که "دشمن دوست من، دشمن من است" نشان داده شده‌است، پس از آن از دو زیرشبکه تشکیل شده‌است به طوری که هر کدام پیوندهای مثبتی در بین گره‌های خود دارند و تنها پیوندهای منفی بین گره‌ها در زیرشبکه‌های مجزا وجود دارد. تصویر در اینجا مربوط به یک نظام اجتماعی است که به دو کلیک تقسیم می‌شود. با این حال، یک مورد خاص وجود دارد که یکی از دو زیرشبکه خالی است، که ممکن است در شبکه‌های بسیار کوچک رخ دهد. گراف کوانتومی
گراف‌های کوانتومی در ریاضیات و فیزیک به یک ساختار خطی شبکه گون ازرئوس گفته می‌شود که توسط یال‌ها بهم وصل شده‌اند، و یک عملگر دیفرانسیلی یا پسودو دیفرانسیلی بر روی تابع‌های تعریف شده روی یال‌ها عمل می‌کند. چنین دستگاههایی در ابتدا توسط لینوس پالینگ در سال ۱۹۳۰ برای مدلسازی از الکترون‌های آزادِ درون مولکول‌های آلی مورد مطالعه قرار گرفت. آن‌ها در زمینه‌های مختلف ریاضیات بکار می آیند، مثل مدل سیستم‌ها در بی نظمی کوانتومی، در مطالعه موجبرها، در بلورههای فوتونیک، و در محلی سازی اندرسون یا به عنوان حد برای کوچک شدن سیم‌های نازک. گراف‌های کوانتومی تبدیل به مدل‌های برجسته ای درفیزیک مزوسکوپی شده‌اند که برای به دست آوردن یک درک نظری از فناوری نانو مورد استفاده قرارمی گیرد .ربات کوانتومی نظریه گراف جبری
شاخهٔ اول نظریه گراف جبری شامل مطالعه گراف‌ها با استفاده از جبر خطی است که آن را مطالعه طیف ماتریس مجاورت، یا ماتریس لاپلاس از یک گراف (این بخش از نظریه گراف جبری نظریه گراف طیفی نیز نامیده می‌شود) می‌نامند. برای گراف پترسن، برای مثال، طیف ماتریس مجاورت برابر با (۳, ۱, ۱, ۱, ۱, ۱, ۲-, ۲-, ۲-, ۲-) می‌باشد. گراف مکعب
براساس تئوری ویزینگ هر گراف مکعبی نیازمند ۳ یا ۴ رنگ برای رنگ آمیزی یال‌ها می‌باشد. گراف‌هایی که نیازمند ۳ رنگ برای رنگ آمیزی یال‌های آن هستیم به رنگ آمیزی تیت (tait) معروف هستند. حال براساس تئوری کونیگ هر گراف دوبخشی دارای رنگ آمیزی تیت می‌باشد. نظریه گراف
نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و… است. گراف‌های پنجه‌آزاد
در نظریه گراف، که بخشی از ریاضیات است، گراف پنجه‌آزاد گرافی است که زیرگراف پنجه نداشته باشد. پنجه نام دیگر گراف دوبخشی کامل formula_1 است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد. رنگ‌آمیزی یالی
در صورتی که ذکر نشود همه گراف‌ها را گراف ساده فرض می‌کنیم. در مقابل گراف ساده، گراف‌های چندگانه تعریف می‌شود که گرافی است که یال‌ها بتوانند ابتدا و انتهای یکسانی داشته باشند یعنی بین دو رأس چندین یال وجود داشته باشد یا گراف طوقه داشته باشد. در بسیاری از مسائل رنگ‌آمیزی یالی، الگوریتم‌ها برای گراف ساده و گراف چندگانه متفاوت خواهد بود و برای تبدیل راه‌حل‌های رنگ‌آمیزی گراف ساده به گراف چندگانه ملاحظات بسیاری مورد نیاز است. پایگاه داده‌های گراف
برای مثال پایگاه داده Neo4j قابلیت استفاده در زبان‌های (Java , .NET , Python , Ruby , PHP , JavaScript) را دارا می‌باشد. البته باید مدنظر داشت که در صورتی که از هاست‌های Cpanel استفاده می‌کنید در حال حاضر نمی‌توانید از پایگاه داده گراف استفاده کنید و باید به سیستم آزادتری مثل یک Server یا VPS (سرور مجازی) یا ابر . . . . سایت خود را منتقل کنید. گراف جهت‌دار غیرمدور
استفاده از گراف جهت‌دارِ غیرمدور، برخی الگوریتم‌ها را ساده‌تر و چابک‌تر می‌کند. DAG در الگوریتم‌های مسیریابی، شبکه‌های پردازش داده، شبکه‌های بیزی، تبارنامه‌ها، روش‌های فشرده‌سازی داده و بسیاری موارد دیگر کاربرد دارد. رنگ‌آمیزی گراف
رنگ‌آمیزی گراف کاربردهای زیادی در زمینه‌های عملی و تئوری گوناگون دارد. علاوه بر مسئله‌های کلاسیک تعریف شده در این زمینه، با در نظر گرفتن محدودیت‌های مختلفی روی نوع گرافها، روی روش رنگ‌آمیزی و حتی تعداد و رنگ عناصر گراف مسئله‌های متنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل می‌شود. با وجود اینکه این مسئله از نظر علمی هنوز در حال رشد و بررسی بیشتر می‌باشد، با ظهور جدول سودوکو در بین عموم مردم شناخته و مشهور شده‌است. نظریه گراف
پیشرفت‌های اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف شده‌است به گونه‌ای که هم‌اکنون نظریهٔ گراف ابزار بسیار مناسبی برای تحقیق در زمینه‌های گوناگون مانند نظریه کدگذاری، تحقیق در عملیات، آمار، شبکه‌های الکتریکی، علوم رایانه، شیمی، زیست‌شناسی، علوم اجتماعی و سایر زمینه‌ها گردیده‌است. گراف فراخوانی
گراف‌های فراخوانی می‌توانند پویا یا ایستا باشند. یک گراف فراخوانی پویا یک ثبت از اجرای برنامه است، به عنوان مثال به عنوان خروجی توسط یک پروفایلر؛ بنابراین، یک گراف فراخوانی پویا می‌تواند دقیق باشد، اما فقط یک بار اجرای برنامه را توصیف می‌کند. یک گراف فراخوانی ایستا یک گراف فراخوانی است که طراحی شده‌است تا همهٔ اجراهای ممکن برنامه را نمایش دهد. داشتن گراف فراخوانی استاتیک کاملاً دقیق یک مسئله حل نشدنی است، بنابراین الگوریتم‌های گراف فراخوانی استاتیک معمولاً با تقریب بیش از حد به دست آمده‌اند؛ یعنی هر رابطه فراخوانی که رخ می‌دهد در گراف نشان داده می‌شود، و احتمالاً برخی از روابط فراخوانی که هرگز در اجرای واقعی برنامه رخ نمی‌دهند نیز در گراف نمایش داده می‌شوند. افراز گراف
در ریاضیات، مسئله افراز گراف بر روی داده‌هایی در قالب گراف ("G=("V","E با "V" راس و "E" یال تعریف می‌شود به‌طوری‌که افراز گراف به مؤلفه‌های کوچکتری با ویژگی‌های خاص ممکن باشد. برای مثال، یک تقسیم‌بندی "k"-بخشی مجموعه رئوس را به "k" مؤلفه کوچکتر تقسیم می‌کند. افراز خوب به افرازی گفته می‌شود که تعداد یال‌های بین مؤلفه‌های مجزا از هم کم باشد. افراز یکریخت به نوعی از مسئله افراز گراف گفته می‌شود که تقسیم گراف به به مؤلفه‌ها به صورتی است که مؤلفه‌ها تقریباً هم اندازه باشند و اتصالات کمی بین مؤلفه‌های متفاوت وجود داشته باشد. مهم‌ترین کاربردهای افراز گراف در محاسبات علمی، تقسیم‌بندی قسمت‌های مختلف طراحی مدارهای VLSI و مدیریت زمانبندی کارها در سیستم‌های چندپردازنده‌ای، می‌باشد. اخیراً، استفاده از افراز یکریخت، به دلیل کاربردهای آن در خوشه بندی و یافتن گروه‌ها در شبکه‌های اجتماعی، شبکه‌های زیستی و شبکه‌های بیماری شناختی افزایش یافته‌است. گراف جهت‌دار و کاربردهای آن
همانند گشت‌ها در گراف‌ها، غالباً گشت جهت دار (u0,a1,u1,….. , ak , uk) را به‌طور ساده با دنباله راس‌های (u0,u1, …. , uk) نمایش می‌دهیم. گذرگاه جهت دار، گشت جهت داری است که گذرگاه باشد. مسیرهای جهت دار، دورهای جهت دار و تورهای جهت دار نیز به‌طور مشابه تعریف می‌شوند. افراز گراف
به علاوه، خوشه بندی طیفی مبتنی بر PCA هسته‌ای، از یک چارچوب مبتنی بر کمترین مربعات بردار، بهره می‌برد و به این ترتیب امکان تصویر مدخل‌های داده را به هسته PCA، که ویژگی‌هایی همچون واریانس بالا را داراست، فراهم می‌کند؛ بنابراین یک جداسازی در سطح بالا را بین گروه‌های تصویر شده پیاده می‌کند. برخی دیگر از روش‌ها، افراز گراف‌ها را به مانند یک بهینه‌سازی چندضابطه‌ای بیان می‌کنند. این دسته از مسائل بهینه‌سازی را می‌توان با استفاده از روش‌های محلی که در چارچوب علمی بیان می‌شوند، حل کرد. در این مسائل هر راس می‌تواند افراز خود را خود انتخاب کند. گراف (ریاضی)
گرافی است که بتوان رئوس آن را به گونه‌ای به دو مجموعهٔ u و v تقسیم کرد که گراف‌های هر زیرگروه (v یا u)دو به دو با هم همسایه نبوده اما با حداقل یکی از رئوس مجموعهٔ دیگر همسایگی داشته باشند. گرافولوژی
مهمترین کاربرد گرافولوژی، گزینش متقاضیان استخدام است. همچنین از گرافولوژی می‌توان در زمینه‌های جرم‌شناسی و برای تشخیص صداقت متهمان نیز استفاده کرد. به‌طور کلی می‌توان کاربرد گرافولوژی را در دو دسته اصلی زیر خلاصه کرد: حلقه (نظریه گراف)
بسته به زمینه مورد بحث، نوعی از گراف ممکن است بر اساس وجود یا عدم وجود حلقه تعریف شود. برای نمونه، برخی ریاضی‌دانان، شبه‌گراف را حالت خاصی از گراف چندگانه غیرجهت‌دار تعریف می‌کنند که مجاز به داشتن حلقه باشد. گراف جهت‌دار و کاربردهای آن
که در این بردار، امتیاز مرتبه دوم هر بازیکن عبارت است از مجموع امتیازات بازیکنانی که از این بازیکن شکست خورده‌اند. در این حالت بازیکن ۳ رتبه اول را کسب می‌کند. با ادامه دادن این فرا یند، بردارهای دیگر به صورت زیر به دست می‌آیند. گراف دوبخشی
یک ابرگراف (hypergraph) یک ساختار ترکیبیاتی است که همانند گراف‌های غیر جهتدار، تعدادی راس و یال دارد، ولی هر یال می‌تواند مجموعهٔ دلخواهی از رئوس باشد (به جای این که دقیقاً از دو راس تشکیل شده باشد). از گراف دوبخشی formula_32 می‌توان برای مدل‌سازی ابرگراف‌ها استفاده نمود که در آن formula_1 مجموعهٔ راس‌های ابرگراف و formula_2 مجموعهٔ ابریال‌ها (hyperedges) است و formula_12 شامل یک یال از یک راس ابرگراف مثل formula_38 به یک ابریال مثل formula_39 است، اگر formula_38 یکی از نقاط انتهایی formula_39 باشد. با این تناظر، ماتریس مجاورت یک گراف دوبخشی دقیقاً همان ماتریس وقوع ابرگراف متناظر با آن است. به عنوان یک حالت خاص از این تناظر بین گراف‌های دوبخشی و ابرگراف‌ها، هر گراف چندگانه (گرافی که ممکن است بین دو راس از آن دو یا چند یال وجود داشته باشد) را می‌توان به صورت یک ابرگراف در نظر گرفت که در آن برخی ابریال‌ها مجموعهٔ یکسانی از راس‌ها را دارند و این ابرگراف را می‌توان با یک گراف دوبخشی نشان داد که یال چندگانه ندارد و همهٔ راس‌های یک طرف آن از درجهٔ ۲ هستند. گراف دوبخشی
وقتی رابطهٔ بین دو گروه مختلف از اشیا را مدل‌سازی می‌کنیم، معمولاً گراف‌های دوبخشی به طور طبیعی ظاهر می‌شوند. به عنوان مثال، فرض کنید یک گراف داشته باشیم که راس‌های آن نمایانگر بازیکنان فوتبال و باشگاه‌ها باشند. یک بازیکن را به یک باشگاه وصل می‌کنیم، اگر آن بازیکن برای آن باشگاه بازی کرده باشد. این گراف نمونه‌ای از شبکه‌های وابستگی (affiliation network) است. این شبکه‌ها نوعی گراف دوبخشی هستند و از آن‌ها در آنالیز شبکهٔ اجتماعی (social network analysis) استفاده می‌شود. کاغذ رسم
کاغذ رسم ، نوعی کاغذ است که با خطوط ظریف یک شبکه منظم بر روی آن چاپ شده‌است. این خطوط اغلب به عنوان راهنمایی برای ترسیم توابع ریاضی یا داده‌های تجربی و رسم نمودارهای دو بعدی استفاده می‌شود. از این نوع کاغذ معمولاً در ترسیم‌های آموزشی ریاضی و مهندسی و در یادداشت‌های آزمایشگاهی استفاده می‌شود. کاغذ گراف به صورت ورق‌های مجزا یا صحافی شده در یک دفترچه در دسترس است. گراف جهت‌دار و کاربردهای آن
در یک تورنمنت تنیس، تعدادی بازیکن شرکت دارند که هر بازیکن با تمام بازیکنان دیگر مسابقه می‌دهد. اگر نتایج بازی‌ها را داشته باشیم، چگونه می‌توانیم بازیکنان را رتبه بندی کنیم؟ به‌طور مثال، تورنمنت شکل (۶) را در نظر بگیرید. این تورنمنت نتایج بازی‌های بین شش بازیکن را نشان می‌دهد بازیکن ۱، بازیکنان ۲، ۴، ۵، ۶ را شکست داده و مغلوب بازیکن ۳ شده‌است و الی آخر. فهرست برخی گراف‌های خاص
گراف پترسن، گراف مکمل گراف خط 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 را به هم وصل می‌کنیم. گراف (ساختار داده)
هر سه راه قابل اجرا برای گراف جهت دار و بدون جهت است. نمایش لیست مجاورت معمولاً ترجیح داده می‌شود چرا که یک روش فشرده برای نمایش گراف‌های کم یال فراهم می‌کند. اگر گراف متراکم یا همان پر یال باشد، نمایشِ ماتریس مجاورت مقدم است. همچنین در مواقعی که نیاز داریم سریعاً بدانیم که آیا به ازای دو رأس داده شده یال متصل‌کنندهٔ بینشان وجود دارد یا خیر، از لیست مجاورت استفاده می‌کنیم. طبقه‌بندی انواع دوگان گراف دوگان گراف‌هایی که تاکنون در علوم مختلف تعریف و استفاده شده‌اند، بر اساس نحوه استخراج به دو گروه بر مبنای گراف اولیه و مفهومی تقسیم‌بندی شده‌اند. در ادامه وجه تسمیه و مشخصات آن‌ها شرح داده شده‌اند. اینفوگرافیک
در اکثر اوقات موارد استفاده از این نگاره‌ها در جایگاه‌هایی است که نیاز به توضیح ساده یا سریع داده‌ها احساس گردد، برای مثال نقشه‌ها، علائم و تابلوها، پوسترهای آموزشی و روزنامه‌ها از جمله کاربردهای آن‌ها هستند. همچنین ریاضیدانان و متخصصان آمار و کامپیوتر نیز از این ابزار برای به تصویر کشیدن مفاهیم پیچیده بهره می‌برند. یک اطلاع‌نگاشت کامل افزون بر اینکه در یک نگاه کلیات اصلی موضوع را به بیننده می‌رساند، دربرگیرنده جزئیات کلیدی موضوع برای دریافت بیشتر هست. رنگبندی بخشی گراف
و نظریه گراف جبری
در نهایت، سومین شاخه از گراف جبری مربوط به نظریهٔ ویژگی‌های جبری گراف، به خصوص چند جمله‌ای رنگی یا چند جمله‌ای کروماتیک (Chromatic polynomial)، چند جمله‌ای تآت (Tutte polynomial)و ویژگیهای گره (Knot invariant) می‌باشد. چند جمله‌ای رنگی از یک گراف، شمارش تعداد رنگهای راس‌های مناسب آن است. برای گراف پترسون، این چند جمله‌ای به گونهٔ زیر است: formula_1 گراف ۱-مسطح
یک گراف ۱-مسطح را یک گراف ۱-مسطح بهینه می‌گویند اگر دقیقاً ۴n − ۸ یال داشته باشد، که حداکثر تعداد ممکن است. در یک زیرگراف از یک گراف ۱-مسطح بهینه، یال‌های بدون تقاطع لزوماً تشکیل یک گراف مربعی می‌دهند (یک گراف چندوجهی که هر وجه آن یک چهارضلعی است). از این طریق هر گراف مربعی با اضافه کردن دو قُطر به هر یک از وجوه چهارضلعی‌اش یک گراف ۱-مسطح بهینه را تولید می‌کند. در نتیجه هر گراف ۱-مسطح بهینه یک گراف اویلری است (تمام رئوسش درجهٔ زوج دارند)، که حداقل درجهٔ رئوس در آن ۶ است. همچنین هر گراف ۱-مسطح بهینه حداقل ۸ رأس با درجهٔ دقیقاً ۶ دارد. به علاوه، هر گراف ۱-مسطح بهینه یک گراف ۴-رأس-همبند بوده، و هر بُرش ۴-رأسی در چنین گرافی یک حلقهٔ جداکننده در گراف مربعی زیرین است. گراف (ساختار داده)
یک داده ساختار گراف اساساً از یک مجموعهٔ متناهیِ زوج‌های مرتب موسوم به یال شامل واحدهایی به نام رأس یا گره تشکیل می‌شود؛ همان‌طور که در ریاضیات به ازای یک یال (u,v) می‌گوییم که u به v می‌رود یا u و v مجاورند. همچنین می‌توان به هر یال یک گراف یک عدد نسبت داد که در این صورت گراف وزن دار به وجود می‌آید. گراف مسطح
در نظریه گرافها، گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند. گراف (ریاضی)
گراف‌های همکاری برا مدل کردن همکاری نویسندگان در نوشتن مقالات علمی، می‌توان از یک گراف همکاری استفاده کرد. در یک گراف همکاری، رئوس، افراد (شاید محدود به اعضای یک انجمن دانشگاهی خاص) را نمایش می‌دهند و یال‌ها در صورتی دو نفر را بهم وصل می‌کند که آن دو نفر، مقاله‌ای را به‌طور مشترک نوشته باشند. گردآورد (نوع داده انتزاعی)
یک داده ساختار گراف اساساً از یک مجموعهٔ متناهیِ زوج‌های مرتب موسوم به یال شامل واحدهایی به نام رأس یا گره تشکیل می‌شود؛ همان‌طور که در ریاضیات به ازای یک یال (u,v) می‌گوییم که u به v می‌رود یا u و v مجاورند. همچنین می‌توان به هر یال یک گراف یک عدد نسبت داد که در این صورت گراف وزن دار به وجود می آید . گراف مکعب
نمونه‌هایی از گراف‌های مکعبی می‌توان به: utility graph, گراف پترسن, گراف هی‌وود، Möbius–Kantor graph, the Pappus graph, Desargues graph, Nauru graph, Coxeter graph, Tutte–Coxeter graph, Dyck graph, Foster graph ,Biggs-Smith graph. ویلیام توماس تات اشاره کرد. تطابق (گراف)
که در آن، n تعداد گره‌ها گراف است. هر یک از انواع چندجمله‌ای بالا، کاربردهای مخصوص به خود را دارد. برای کسب اطلاعات بیشتر در این مورد، می‌توانید مقالات مربوط به چندجمله‌ای‌های تطابق را مطالعه کنید. نمودار دایره‌ای
نمودار دایره‌ای یا گراف دایره‌ای، نموداری دایره‌ای است که به بخش‌های گوناگون بخش می‌گردد. جدا کردن بخش‌ها در نمودار دایره‌ای، نسبت و تناسب میان اجزای نموداری را تعیین می‌کند. در نمودار دایره‌ای اندازه طول کمان و به پیروی ار آن زاویه و مساحت قطاع هر بخش، میزان بزرگی مؤلفه نموداری را مشخص می‌کند. گراف (ریاضی)
در نظریه گراف، یک گراف کامل، گرافی‌است که بین هر دو راس آن دقیقاً یک یال وجود داشته باشد. یک گراف کامل از مرتبه n، دارای n راس و formula_9 یال است که آن را با formula_10 نشان می‌دهند. یک گراف کامل یک گراف منتظم از درجه n-۱ است. گراف‌های مسطح با خطوط راست
PSLGها می‌توانند در نمایش انواع نقشه ها بکار گرفته شوند، مانند : نقشه‌های جغرافیایی در سیستم‌های اطلاعاتی جغرافیایی. موارد خاص استفاده ازPSLGها در مثلث بندی ها(مثلث‌بندی چندضلعی‌ها و مجموعه نقاط) می‌باشد. مثلث بندی کاربردهای بسیاری در زمینه‌های گوناگون دارد. درخت (نظریه گراف)
تغییر نام خیابان‌ها و چهارراه‌ها ی عمومی یکی از سرگرمی‌های مطلوب انجمن‌های شهری در سراسر جهان است. فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان‌های خود بسیار اصولی باشند. فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشینگتن بایستی در چهار راه واشینگتن باشد. طبیعتاً می‌خواهیم مسئله خود را در زبان گراف‌ها در حالتی کلی عنوان کنیم. گراف همبندی داده شده‌است. تحت چه شرط‌هایی می‌توان به‌طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد؟ در ابتدا خاطر نشان می‌کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می‌کنیم: پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر به دلخواه انتخاب کردیم، یال a1 a0 را متناظر با رأس a1 می‌گیریم، به همین ترتیب a0 a2 را متناظر با a2 و و a0 a3 را متناظر با a3، سپس a1 a11 را متناظر با a11 قرار می‌دهیم، و الی آخر؛ به‌طور کلی، هر یال را به انتهایی از آن که از a0 دور تر است، متناظر می‌کنیم. اکنون فرض کنید که گراف دارای مداری مثلاً c، باشد (شکل ۲) هر یال c باید متناظر با یکی از دو رأس انتهایی خود باشد، یعنی متناظر با رأسی از c. اگر به عنوان مثال یال a1 a2 متناظر با a2 باشد آنگاه یال a2 a3 بایستی متناظ با a3 باشد، و الی آخر؛ بنابراین هیچ یال نا متعلق به c نمی‌تواند با رأسی از c متناظر باشد. در نتیجه یالی مانند a1 b1 که در a1 مدار c را قطع می‌کند، بایستی با b1 متناظر باشد و یالی مانند b1 b2 با b2 و الی آخر. گراف پدیداری
با استفاده از گراف‌های پدیداری می‌توان کمینه فاصله اقلیدسی بین دو نقطهٔ مورد نظر در فضایی شامل موانع چند ضلعی را پیدا کرد. همیشه کمترین فاصله بین دو نقطه خط راست بین آن دو نقطه هست، مگر آنکه مانعی در میان مسیر مورد نظر باشد. در اینصورت گوشهٔ چند ضلعی مورد نظر باید به عنوان یکی از نقاط میانی(راس‌های گراف پدیداری) انتخاب کرد. به اینصورت می‌توان مسئلهٔ مسیر بهینه در فضای اقلیدسی را به مسئلهٔ کوتاه‌ترین مسیر در یک گراف تبدیل کرد. اکنون در اینجا می‌توان مسئله را به قسمت تقسیم کرد: (۱)ساختن گراف پدیداری از روی مسئلهٔ کوتاه‌ترین مسیر در فضای اقلیدسی (۲) حل مسئلهٔ کوتاه‌ترین مسیر مانند الگوریتم دایکسترا در یک گراف. برای مسیر یابی روباتی که دارای اندازه‌ای قابل توجه است، می‌توان مسئله را تعمیم داد. در واقع در این حالت مسیر بهینه نمی‌تواند کاملاً در لبهٔ موانع عبور کند. چون اگر اینطور باشد، روبات با شعاع غیر جزئی با موانع برخورد می‌کند. مسئله را می‌توان به اینصورت حل کرد که موانع را کمی بزرگتر از آنچه هستند در نظر گرفت و سپس مراحل فوق را در این حالت انجام داد. یکی دیگر از کاربردهای گراف پدیداری در بدست آوردن مکان بهینه برای قرار دادن آنتن‌های رادیویی است. گراف تقاطع
گراف اشتراکی یا گراف تقاطع گرافی‌ست که اشتراک خانواده‌ای از مجموعه‌ها را نشان می‌دهد. به عبارتی دیگر فرض کنیم مجموعه‌ی S و همچنین مجموعهٔ n عضوی از زیر مجموعههای S را در اختیار داریم که نام آن C است. یعنی هر عضو C، زیر مجموعه‌ای از S می‌باشد. به ازای هر عضو C یک رأس رسم می کنیم و در صورتی که دو عضو C اشتراک داشته باشند بین رئوس متناظر با آن‌ها یالی رسم می‌کنیم. شکل حاصل را گراف اشتراکی مجموعهٔ C نامیده و با I(C) نمایش می دهیم. فرض کنید می‌خواهیم برنامه‌ریزی چراغ‌های راهنمای یک تقاطع را برعهده بگیریم. در مدل انتزاعی این مسئله آنچه مهم است گردش‌های مختلف این تقاطع و تلاقی این گردش هاست. بدیهی است که امکان حرکت گردش‌های متلاقی در یک بازهٔ زمانی وجود ندارد. اگر گردش از خیابان X به خیابان Y راXY بنامیم، خود گردش‌ها و تلاقی بین آن‌ها را می‌توان با یک گراف تقاطع نشان داد. در این گراف، هر گردش یک رأس است و بین دو گردش متلاقی یک یال قرار داده‌ایم. ماتریس هموار
ماتریس‌های هموار در جبر خطی کاربرد زیادی دارند. یکی از کاربردهای آن‌ها تبدیلات خطی می‌باشد که توابع را به ابعاد بالاتر می‌برد. همچنین به عنوان ضریب در معادلات خطی به کار می‌آیند. ماتریس‌ها در زمینه‌های فراوانی کاربرد دارند از جمله در فیزیک یا هندسه اپتیک و در ماشین‌های ماتریسی. نظریه گراف‌ها نیز از ماتریس‌ها برای نگاه داشتن فاصله بین رِاس‌ها استفاده می‌کند. در گرافیک کامپیوتری، از ماتریس‌ها برای تبدیل فضای ۳ بعدی به صفحه نمایش دو بعدی استفاده می‌شوند. گراف (ریاضی)
بزرگ ترین و کوچک ترین درجۀ یک گراف: بزرگ ترین عدد در بین درجات رئوس گراف G را با∆ ( G) و کوچک ترینِ آنها را با δ (G) نمایش می دهیم و به ترتیب آنها را ماکزیمم و مینیمم درجهٔ گراف می نامیم. گراف نقشه راه‌ها
نقشه راه‌هایی را که فقط جاده‌های یک طرفه را نمایش داده و هیچ جاده حلقوی نداشته و در آن هیچ دو جاده‌ای که در تقاطع یکسان شروع شده و به تقاطع یکسان ختم شوند وجود ندارد، می‌توان با استفاده از گراف‌های ساده جهت دار مدل کرد. برای نمایش نقشه راه‌هایی که شامل هر دو نوع جاده یک طرفه و دو طرفه هستند، نیاز به گراف‌های مختلط داریم. نشاندن گراف
نوع هر گراف حداقل عدد صحیحی است که گراف می‌تواند درون یک سطح نوع n نشانده شود. به‌طور خاص یک گراف مسطح داری نوع صفر می‌باشد زیرا می‌تواند بر روی یک کره بدون تقاطع کشیده شود. گراف غیر جهت‌دار از نوع حداقل عدد صحیح n می‌باشد که گراف می‌تواند در یک سطح غیر جهت‌دار نوع n نشانده شود. گراف (ریاضی)
گِراف یا نِگار در ریاضیات دست‌کم دارای دو معنی می‌باشد. در ریاضیات پایه گراف اشاره به نمودار تابع دارد، و در اصطلاح ریاضی‌دانان، گراف مجموعه‌ای از نقاط و خطوط به هم پیوسته است. گراف k-مکعب
گراف k- مکعب گرافی است که رئوس آن دنباله‌های غیر تکراری k تایی از 0 و 1 به صورت (a, a, … , a) باشد. و یالهای آن، میان رئوس رسم شوند که دقیقاً در یک جایگاه متفاوت باشند. گراف دوری
در نظریه گراف، گراف دوری به گرافی که متشکل از یک دور باشد گفته می‌شود، یا به عبارت دیگر تعدادی رأس که به صورت زنجیری به یکدیگر متصل شده‌اند. گراف با formula_1 رأس با نماد formula_2 نشان داده می‌شود. گراف دوری گرافی همبند بوده که درجه هر رأس آن دو بوده می‌باشد. تعداد رأس‌ها و یال‌های این گراف نیز برابر می‌باشد. گراف (ریاضی)
گراف مخلوط: گرافی است که در آن ممکن است برخی یال‌ها جهت داشته باشند و برخی بدون جهت باشند. گراف مخلوط G، سه‌تایی مرتب G = (V, E, A) است که در آن V مجموعه‌ی رئوس، E یال‌های بدون جهت و A یال‌های جهت دارمی‌باشند. گراف ساده و گراف جهت‌دار حالت خاصی از گراف جهت دار می باشند. قضیه ویزینگ
ویزینگ (۱۹۶۵) نشان داد که هر گراف مسطح جزو گراف‌های ردهٔ اول است اگر بیشترین درجهٔ رئوس گراف حداقل هشت باشد. در مقابل او مشاهده کرد که به ازاء هر بیشترین درجهٔ بین دو تا پنج، گراف مسطحی وجود دارد که جزو گراف‌های ردهٔ دوم باشد. برای درجهٔ دو، هر دور فردی چنین گراف است و برای درجهٔ سه و چهار و پنج گراف‌های مورد نظر از اجسام افلاطونی با جایگزین کردن یک یال به جای دو یال مجاور می‌توانند ساخته شوند. گراف جهت‌دار و کاربردهای آن
گراف‌های جهت دار هم، مانند گراف‌ها، دارای یک نمایش تصویری ساده هستند. یک گراف جهت دار با نموداری از گراف زمینه آن، به علاوه پیکان‌هایی که سر کمان متناظر با هریال آن را مشخص می‌کنند، نمایش داده می‌شود: هر مفهومی که برای گراف‌ها برقرار باشد به‌طور خودکار برای گراف‌های جهت دار نیز معتبر خواهد بود بنابراین گراف جهت دار شکل (۱) الف همبند است و هیچ دوری به طول ۳ ندارد، زیرا گراف زمینه آن شکل (۱) ب، دارای این ویژگی هاست اما مفاهیم بسیاری وجود دارند که شامل مفهوم جهت می‌باشند تنها برای گراف‌های جهت دار معتبرند. نقشه
نقشه‌های جاده‌ها شاید امروزه پرکاربردترین نوع نقشه باشند و که از زیرمجموعهٔ نقشه‌های ناوبری محسوب می‌شوند؛ که شامل نمودارهای هوایی، دریایی، شبکهٔ ریلی، مسیرهای دوچرخه‌سواری و حتی پیاده‌روی می‌باشند؛ ولی عمده نقشه‌های تولیدی برای کاربردهای دیگر که مورد نیاز شهرداری‌ها، شرکت‌های توزیع آب و برق، واحدهای مالیاتی (البته این مورد در ایران چندان رایج نیست)، سرویس‌های امداد و نجات و خدمات اضطراری و سایر سازمان‌های محلی تولید و مورد استفاده قرار می‌گیرند. یکی از کاربران مهم و تولیدکنندهٔ نقشه‌ها جغرافیایی، سازمان‌های نظامی و انتظامی هر کشوری می‌باشد که معمولاً در سطح ملی اقدام به تولید و گردآوری داده می‌نمایند. گراف جهت‌دار و کاربردهای آن
در ابتدا توجه به این مطلب ضروری است که ابتدا و انتهای هر مسیر جهت داردر َD، رنگ‌های متفاوتی دارند. زیرا فرض کنید که p یک (u,v) مسیر جهت دار با طول مثبت در َD و v€Vi می‌باشد. در این صورت یک مسیر جهت دار (v1,….. , v2 , vi)= Q در َD وجود دارد که در آنv = v1. چون َD شامل هیچ دور جهت داری نیست، PQ یک مسیر با ابتدای u و طول حداقل i می‌باشد. پس داریم: u€Vi. گراف انتساب شغل
فرض کنید در یک گروه ، m کارمند و j شغل مختلف داریم که باید انجام شوند که formula_1. هر کارمند برای انجام یک یا بیشتر از این j شغل، آموزش دیده است. میتوانیم از یک گراف برای مدل کردن تواناییهای کارمندان استفاده کنیم. هر کارمند و هر شغل را با یک رأس نمایش میدهیم. برای هر کارمند، یالی از رأس نمایش دهنده آن، به تمام رئوسی که نمایش دهنده شغلهایی هستند که این کارمند برای آن‌ها آموزش دیده است، رسم میکنیم. توجه کنید که مجموعه رئوس این گراف را می‌توان به دو مجموعه مجزا افراز کرد، مجموعه رئوس نمایش دهنده کارمندان و مجموعه رئوس نمایش دهنده مشاغل و هر یال، رأس نمایش دهنده یک کارمند را به رأس نمایش دهنده یک شغل متصل می‌کند. در نتیجه، این گراف دو قسمتی است. گراف چندگانه
در نظریه گراف گراف چندگانه یا شبه گراف به گرافی گفته می‌شود که مجاز است یالهای چندگانه داشته باشد که به آنها یالهای موازی هم گفته می‌شود. گرافیت هسته‌ای
گرافیت هسته‌ای () به کلیه گریدهای گرافیت که به عنوان آرام کننده نوترون و یا Neutron reflector در راکتورهای هسته ای مورد استفاده قرار می‌گیرند گفته می‌شود. گرافیت به دلیل خلوص بالا و مقاومت خوب در برابر درجه حرارت‌های بالا، کاربرد زیادی در صنایع هسته ای دارد. این نوع خاص گرافیت باید فاقد مواد جاذب نوترون از جمله بور باشد. پایگاه داده‌های گراف
در یک پایگاه داده گراف نمودار خطی
نمودار خطی () دسته‌ای از نمودارها (یا گراف‌ها) هستند، که دو مقیاس اندازه‌گیری را شامل می‌شوند. در این نمودارها یکی از مقیاس‌ها در امتداد قائم و دیگری در امتداد افقی قرار می‌گیرد. این نوع نمودارها، دقیق‌ترین یا صحیح‌ترین نوع نمودارها را تشکیل می‌دهند. از این نظر در نشان دادن رابطه میان دو سری از اطلاعات، بسیار مفید می‌باشند. نمودارهای خطی، نحوه گسترش یا توسعه اطلاعات را در یک مدت زمان معین به‌خوبی نشان می‌دهند، گرچه هنگامی از این نمودارها استفاده می‌گردد که اطلاعات بسیار زیادی در دست باشد. گراف تهی
formula_1 عمل (درستی پوچ) بیشتر گراف‌های پایه با ویژگی‌هایی مشابه با formula_9 (گرافی با یک رأس و بدون یال) را انجام می‌دهد. برای مثال، formula_10 اندازه صفر، برابر با گراف مکمل آن formula_11، یک جنگل و یک گراف مسطح است. شاید یک گراف جهت دار، بی جهت یا هر دوی آنها در نظر گرفته شود. وقتی جهت دار در نظر گرفته شود، یک گراف جهت دار غیرمدور است و در عین حال یک گراف کامل و یک گراف بی یال است. اگر چه تعریف‌ها برای ویژگی‌های این گراف متفاوت خواهد بود و وابسته به متن است که آیا formula_1 را به شمار می‌آورد یا نه. رنگ‌آمیزی گراف
به عنوان نتیجه‌ای از مثال ۴ (د) توجه خود را بر گراف‌های همبند متمرکز می‌کنیم. در بسیاری از موارد در ریاضیات گسسته، برای حلّ مسائل با حالت‌های زیاد روش‌هایی که به کار رفته‌اند، تفکیک این حالت‌ها به دو یا چند حالت کمتر است. ما نیز همین روش را برای حل مسئله به کار می‌بریم. برای انجام این کار به مفاهیم و نمادگذاری زیر نیاز داریم. فرض کنید(G=(V,E گرافی بی سو باشد. برای e=a,b ∈E فرض می‌کنیم G معرف زیر گراف G حاصل از حذف e از G، بدون برداشتن رأس‌های a و b است؛ یعنی به صورت G=G-e می‌باشد. از G، زیرا گراف دوّمی از G با اتصال رأس‌های a و b به دست می‌آید. این زیر گراف دوم را با G نشان می‌دهیم. ابرگراف
از نیم قرن گذشته،نظریه گراف دارای اهمیت بسیاری در زمینه‌های مختلف از جمله هندسه، نظریه اعداد، بهینه‌سازی، توپولوژی، جبرهای میانی و نظیر آن‌ها بوده‌است. برای حل مسایل ترکیبیاتی جدید، لازم بود که مفهوم گراف توسعه داده شود. حدود سال١٩۶٠مفهوم ابرگراف پدیدار شد و یکی از اهداف ابتدایی آن، تعمیم برخی از نتایج کلاسیک نظریه گراف بود. نظریه ابرگراف، ابزاری مفید برای مسایل بهینه‌سازی گسسته است. گراف جهت‌دار
برای هر گره، تعداد رأس‌های ابتدایی مجاور، درجهٔ ورودی و تعداد رأس‌های انتهایی مجاور، درجهٔ خروجی (در درخت‌ها ضریب انشعاب) نامیده می‌شود. درخت (نظریه گراف)
در ختی مانند درخت شکل (۱) یا گرافی مانند گراف شکل (۳)، فقط می‌توانند نقشهٔ خیابان‌های شهرهای خیلی کوچک باشند که فاقد بلوک‌های شهری واقعی اند، یا فقط یک بلوک مرکزی دارند که خیابان‌هایی از حومه به آن‌ها کشیده شده‌است. پس از اندکی تأمل دربارهٔ این موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می‌شوند که شهر آن‌ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت؛ بنابراین قرار می‌گذارند که به جای آن از قاعدهٔ زیر استفاده کنند: خیابان‌ها و چهارراه‌ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان‌ها به نام همان چهارراه باشد؛ یعنی، به عنوان مثال، بایستی یکی از خیابان‌ها به نام همان چهار راه باشد؛ یعنی به عنوان مثال، بایستی یکی از خیابان‌های منتهی به چهارراه واشینگتن به نام واشینگتن باشد. به زبان نظریهٔ گراف‌ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال‌های متصل به آن است. این کار در مواردی عملی نیست؛ به عنوان مثال همان‌طور که گفته شد، تعداد رأس‌های هر درخت از تعداد یال‌های آن یکی بیشتر است. گراف شکل (۱) را در نظر بگیرید. در این گراف می‌توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می‌شود متناظر کرد. به این ترتیب، به جز ریشه، هر رأس با یالی متناظر می‌شود. کنترل‌پذیری شبکه
در نظریه گراف یک تطابق مجموعه‌ای از یال هاست که راس مشترک ندارند. لیو و همکاران این تعریف را به گراف های جهت دار توسعه دادند که در آن یک تطابق، یک مجموعه از یال‌های جهت دار است که در ابتدا و انتها مشترک نیستند. به راحتی قابل بررسی است که یک تطابق از یک گراف جهت دار، یک مجموعه از دور ها و مسیر های ساده ی راس مجزا را تشکیل می دهد. تطابق بیشینه برای یک شبکه جهت دار، می‌تواند به طور کارآمد، با کار کردن درنمایش دو بخشی با استفاده از الگوریتم هاپکرافت-کارپ کلاسیک که در بدترین حالت در زمان O("E") اجرا می‌شود، محاسبه شود. برای گراف های بدون جهت، جواب های تحلیلی برای اندازه و تعداد تطابق های بیشینه با استفاده از روش کاواک که در فیزیک آماری توسعه یافته اند، برسی شده اند. لیو و همکاراناین محاسبات را برای گراف های جهت دار توسعه دادند. برچسب‌گذاری گراف
به بیان رسمی، برای یک گراف "G "، منظور از برچسب‌گذاری شدهٔ راسی، یک تابع است که رأس‌های گراف "G" را به مجموعه‌ای از برچسب‌ها می‌نگارد. به گرافی که برای آن چنین تابعی تعریف شده باشد یک گراف برچسب‌گذاری شدهٔ راسی می‌گویند. به همین ترتیب، یک برچسب‌گذاری ِیالی یک تابع از یال‌های گراف به مجموعه‌ای از برچسب هاست، که در این حالت گراف را برچسب‌گذاری شدهٔ یالی نام‌گذاری کرده‌اند. اگر برچسب‌های نگاشته شده به یال‌های گراف اعضای یه مجموعهٔ مرتب باشند (برای مثال مجموعهٔ اعداد حقیقی)، گراف را یک گراف وزن دار نیز می‌نامند. گراف جهت‌دار غیرمدور
و گراف فاکتور بحرانی
یک گراف critical (بدون قید و شرط) معمولاً این گونه تفسیر می‌شود که حذف هر یک از رأس‌ها تعداد رنگ‌های لازم برای رنگ آمیزی این گراف را کاهش می‌دهد. مفهوم critical بودن به‌طور عمومی در نظریه گراف‌ها اشاره بر این دارد که حذف هر رأسِ ممکن بعضی از ویژگی‌های وابسته به گراف را تغییر می‌دهد و بعضی را تغییر نمی‌دهد. یک matching-critical graph گرافی است که حذف هر رأس اندازه بیشترین تطابق را تغییر نمی‌دهد و طبق تعریف Gallai , گراف‌های matching-critical گراف‌هایی هستند که هر جزء همبند یک factor-critical می‌باشد. گراف مکمل یک گراف critical لزوماً matching-critical می‌باشد، این در واقع اصلی بود که Gallai از آن برای اثبات کران پایین تعداد رأس‌های یک critical graph استفاده کرد. در نظریه گراف پیشرفته، مفهوم factor-criticality با تعریف نوعی از دسته‌های جداشدنی روی matroid و توصیف matroid به عنوان یک factor-critical با این شرط که matroid دسته‌ای جداشدنی داشته باشد که تمام دسته‌ها فرد باشند، به قضیه matroid بسط داده شده‌است. رنگ‌آمیزی گراف
مثال ۱: برای گراف G در شکل ۱، از رأس a شروع می‌کنیم و سپس در هر رأس، عدد فامی لازم برای رنگ آمیزی رأس‌های G را که برای آن‌ها در نظر گرفته‌ایم می‌نویسیم. وقتی به رأس b می‌رویم، عدد ۲ نیاز ما به رنگ دوم است و اگر به صورت الفبایی تا f پیش برویم متوجه می‌شویم که برای رنگ آمیزی خاص a,b،c,d،e,f به دو رنگ نیاز داریم. برای رأُس g، رنگ سومی لازم است؛ این رنگ سوم را می‌توان برای رأس h هم به کار برد، زیرا g , h یالی از G نیست. پس χ(G)=۳. گراف وزن‌دار
گراف وزن‌دار ، گرافی است که به هر یال آن عددی نسبت داده شده‌است که وزن آن یال می‌باشد. یا به راس آن عددی نسبت داده شده. وزن یال می‌تواند نشان دهنده هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسنده‌ها به آن گراف شبکه‌ای می‌گویند. از گراف وزن‌دار برای حل مسائلی چون فروشنده دوره گرد استفاده می‌شود. درگراف وزن‌دار، وزن‌ها را در ماتریس مجاورت ذخیره می‌کنند.وزن هر یال یک گراف موزون می‌تواند نشان دهنده یکی از موارد زیر باشد: گراف (ریاضی)
گراف همپوشانی منابع غذایی در بوم شناسی یکی از کاربردهای گراف در رشته‌های دیگر مانند زیست‌شناسی است، در این گراف منابع غذایی یک اکوسیستم مدل می‌شوند و آگاهی مناسبی از رقابت‌های میان هر گونه ارائه می‌دهند گراف دوبخشی
گراف‌های دوبخشی به طور گسترده‌ای در نظریهٔ کدگذاری مدرن مورد استفاده قرار می‌گیرند، مخصوصاً برای رمزگشایی کدهای (codewords) دریافت‌شده از کانال. گراف‌های Factor و گراف‌های Tanner مثال‌هایی از این مورد هستند. گراف Tanner، یک گراف دوبخشی است که در آن راس‌های یکی از دو بخش نشان‌دهندهٔ ارقام یک کلمه از کد (codeword) هستند و راس‌های بخش دیگر ترکیب‌هایی از ارقام را نشان می‌دهند که انتظار می‌رود در کد (codeword) بدون خطا مجموع آن‌ها صفر شود. گراف تصادفی
در ریاضیات، گراف تصادفی اصطلاحی کلی است که به احتمال پراکندگی روی گراف‌ها اطلاق می‌گردد و نقطه برخورد تئوری گراف و تئوری احتمالات است. از جنبه ریاضیات، گراف تصادفی برای پاسخ به پرسش‌هایی در مورد خواص گراف‌ها بکار گرفته می‌شود، اما برنامه‌های کاربردی آن در تمام حوزه‌هایی که در آن شبکه‌های پیچیده نیاز به مدل‌سازی دارند وجود دارد. در مبحث ریاضی، گراف تصادفی تقریباً به مدل گراف تصادفی Erdös-Renyi منحصر است. در زمینه‌های دیگر، هر مدل گراف دیگر ممکن است به یک گراف تصادفی نسبت داده شود. گراف جهت‌دار و کاربردهای آن
نتیجه بهتری که می‌توان از قضیه (۱) حاصل نمود، این است که هر گراف G، دارای یک جهت دهی است که طول بزرگترین مسیر جهت دار آن x-۱ است. اگر یکx-رنگ آمیزی راسی مجاز ,….(V1, V2, Vx) از G داده شده باشد، Gرا بدین صورت جهت دهی می‌کنیم: u€Vi و v€Vj با شرط i ≤j، یال uv را به کمان (u,v) تبدیل می‌کنیم. واضح است که در این جهت دهی از G، هیچ مسیر جهت داری نمی‌تواند بیش از x راس داشته باشد زیرا هیچ دوراس از مسیر نمی‌توانند همرنگ باشند. گراف (ریاضی)
اندازه گراف تعداد یال‌های یک گراف است و به صورت formula_8 بیان می‌شود. ریاضیات گسسته
لجستیک مطالعه سازماندهی جریان اطلاعات، کالاها و خدمات است. بدون ریاضیات گسسته، تدارکات وجود نخواهد داشت. دلیل این است که تدارکات به‌طور سنگین از نمودارها و نظریه گراف، که یک زیر رشته ریاضی گسسته‌است، استفاده می‌کند. نظریه گراف اجازه می‌دهد تا مشکلات پیچیده تدارکات به‌طور ساده به نمودارهای متشکل از گره‌ها و خطوط نمایش داده شوند. یک ریاضی‌دان می‌تواند این نمودارها را با توجه به روش نظریه گراف به منظور تعیین بهترین راه برای حمل و نقل یا حل دیگر مشکلات لجستیکی تجزیه و تحلیل کند. رنگ‌آمیزی گراف
فرض کنید G گرافی بی سو ست و λ عدد صحیح مثبت معرّف تعداد رنگ‌های است که برای رنگ آمیزی خاص رأس‌های G موجودند. هدف ما یافتن چندجمله‌ای (P(G، λ برحسب متغیر λ است که بیان می‌کند به چند راه مختلف رأس‌های G را، با استفاده از حداکثر λ رنگ، رنگ کنیم. در سراسر این بحث، رأس‌های گراف بی سوی (G=(V,E به وسیله برچسب‌ها از هم متمایزند. در نتیجه دو رنگ آمیزی خاص چنین گرافی به مفهوم زیر متمایز در نطر گرفته می‌شوند: رنگ آمیزی خاص (رأس‌های G) که حداکثر λ رنگ به کار می‌برد تابعی مانند f با حوزهٔ V و حوزهٔ تمام ۳٬۲٬۱، …، λ است، که در آن، برای رأس‌های مجاور f(u)≠f(v),u،v∈V. لذا تفاوت رنگ آمیزی خاص از متفاوت بودن این تابع‌ها معلوم می‌شود. گراف (ساختار داده)
ساختار داده‌های مختلفی برای نمایش گراف‌ها در عمل استفاده می‌شود: گراف (ریاضی)
می‌توان از گراف‌های تماس تلفنی رأی مدل کردن تماس‌های تلفنی برقرار شده در یک شبکه مانند شبکه تلفن راه دور استفاده کرد؛ که در ان رأس‌ها شماره تلفن‌ها و یال‌ها ارتباط‌های برقرار شده بین شماره تلفن‌ها است. گراف دوبخشی
در هندسهٔ تصویری، گراف‌های Levi نوعی گراف دوبخشی هستند که برای مدل‌سازی واقع شدن نقاط و خط‌ها برهم در یک پیکره (configuration) از آن‌ها استفاده می‌شود. بنابر ویژگی هندسی خطوط و نقاط که هر دو خط حداکثر در یک نقطه یکدیگر را قطع می‌کنند و هر دو نقطه را فقط با یک خط می‌توان به هم متصل کرد، گراف‌های Levi شامل هیچ دوری به طول ۴ نیستند، پس طول کوتاهترین دور آن‌ها باید ۶ یا بیشتر باشد. گراف (ریاضی)
مرتبه و اندازۀ یک گراف: تعداد رأس های گراف G یعنی |V(G)| را مرتبهٔ آن گراف می گوییم و باp(G) نمایش می دهیم و تعداد یال های گراف یعنی |E(G)| را اندازهٔ گراف G می گوییم و با q(G) نمایش می دهیم. معمولاً برای راحتی کار به جای p(G) از p و به جای q(G) از q استفاده می کنیم. گراف فاکتور بحرانی
در نظریه گراف‌ها، یک مبحث ریاضی، گراف فاکتور بحرانی یا گراف هایپومچبل یک گراف با n راس می‌باشد به طوری که هر زیر گراف n-1 عضوی دارای خاصیت تطابق کامل می‌باشد.(تطابق کامل در یک گراف به این معنی است که یک زیر مجموعه از یال‌های این گراف هستند که در این زیر مجموعه هر یک از راس‌ها دقیقاً نقطه پایانی یکی از یال‌ها هستند. گراف جهت‌دار و کاربردهای آن
شگفت آور آن که، با نگاه به عدد رنگی یک گراف جهت دار می‌توان اطلاعاتی راجع به طول مسیرهای جهت دار آن به دست آورد. قضیه زیر که متعلق به روی (۱۹۶۷) و گالای (۱۹۶۸) می‌باشد به توضیح این مطلب می‌پردازد. گراف وتری
در ریاضیات، حوزهٔ نظریهٔ گرافها، گراف وتری گرافی است که هر دور به طول چهار یا بیشتر از آن شامل وتر باشد. (وتر: یالی است که دو رأس از دور که در دور شرکت نکرده باشند را به هم وصل می‌کند). به عبارت دیگر، هر دور القایی در گراف می‌بایست حداکثر سه رأس داشته باشد. گراف‌های وتری زیرمجموعه‌ای از گراف‌های آرمانی می‌باشند که در مدت زمانی چندجمله‌ای شناسایی می‌شوند. اگر ورودی مسایلی همچون رنگ‌آمیزی گراف، گرافی وتری باشد در مدت زمانی چندجمله‌ای حل می‌شوند. علوم نظری رایانه
نظریه گراف شاخه‌ای از ریاضیات گسسته است که دربارهٔ گراف‌ها بحث می‌کند. این مبحث به زبان دقیق‌تر شاخه‌ای از توپولوژی است که با جبر و نظریه ماتریس‌ها پیوند مستحکم و تنگاتنگی دارد. نظریهٔ گراف برخلاف شاخه‌های دیگر ریاضیات نقطهٔ آغاز مشخصی دارد و آن انتشار مقاله‌ای از لئونارد اویلر، ریاضیدان سوئیسی است. گراف (ریاضی)
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأس‌های G و اعضای E را یال‌های G می‌نامیم. به بیان ساده‌تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقه‌ای (یعنی یالی که رأس را به خودش وصل می‌کند) نیز وجود نداشته باشد. گراف جهت‌دار و کاربردهای آن
قضیه (۱) گراف جهت دار D شامل مسیر جهت داری به طول۱- x است. رنگ‌آمیزی یالی
در نظریهٔ گراف، یک رنگ‌آمیزی یالی از یک گراف، نسبت دادن "رنگ‌ها" به یال‌های گراف است به نحوی که هیچ دو یال مجاوری رنگ یکسان نداشته باشند. برای مثال، تصویر سمت چپ نمایانگر یک رنگ‌آمیزی یالی از یک گراف با رنگ‌های قرمز، آبی، و سبز است. رنگ‌آمیزی یالی یکی از انواع مختلف رنگ‌آمیزی گراف است. مسئلهٔ رنگ‌آمیزی یالی بررسی می‌کند که آیا ممکن است یال‌های یک گراف داده شده را با حداکثر رنگ متفاوت که داده شده‌است، یا با کمترین تعداد رنگ ممکن، رنگ کرد. کمترین تعداد لازم رنگ برای یال‌های یک گراف داده شده، شاخص رنگی آن گراف نامیده می‌شود. برای مثال، گراف تصویر با سه رنگ، رنگ می‌شود ولی نمی‌توان آن را با دو رنگ رنگ کرد، پس شاخص رنگی آن سه است. گراف (ریاضی)
کاربرد گراف بازه‌ها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد. پهنای مسیر
از جهتی دیگر، اگر G زیرگرافی از گراف بازه‌ای با اندازهٔ کلیک p+1 باشد، در این صورت G دارای تجزیهٔ مسیر با پهنای p است که گره‌های آن توسط ماکزیمم کلیک‌های گراف بازه‌ای داده شده‌است. برای مثال گراف بازه‌ای نشان داده شده در شکل با نمایش بازه‌ای دارای تجزیهٔ مسیر با پنج گره است. با توجه به کلیک‌های ماکزیمال آن ABC، ACD، CDE CDF وFG. ماکزیمم کلیک آن دارای اندازهٔ سه است و پهنای مسیر تجزیهٔ آن دارای اندازهٔ دو است. این هم‌ارزی بین پهنای مسیر و اتصال بازه‌ای بسیار شبیه هم‌ارزی بین پهنای درخت و اندازهٔ مینیمم کلیک (یکی کمتر) از گراف کوردال (chordal) است به‌طوری‌که گراف داده شده زیرگراف آن است. گراف‌های بازه‌ای نوع خاص گراف‌های کوردال هستند و گراف‌های کوردال را می‌توان به صورت گراف‌های اشتراکی از زیردرخت‌های درخت مشترک نمایش داد که روشی است که در آن گراف‌های بازه‌ای، گراف‌های اشتراکی از زیرمسیرهای یک مسیر است را تعمیم می‌دهد. گراف جهت‌دار و کاربردهای آن
گراف جهت داری که دارای هیچ طوقه‌ای نیست و بین هر دو راس آن، هیچ دو کمان هم جهتی قرار ندارد یک گراف جهت دار قوی نامیده می‌شود. گراف (ریاضی)
گراف نقشه راه‌ها از گراف‌ها می‌توان برای مدل کردن نقشه راه‌ها استفاده کرد. در این گونه مدل‌ها، رئوس، نمایش دهنده تقاطع‌ها و یال‌ها، نمایش دهنده جاده‌ها هستند. یال‌های بدون جهت، جاده‌های دو طرفه و یال‌های جهت دار، جاده‌های یک طرفه را نشان می‌دهند. گراف تصادفی
یک گراف تصادفی از یکسری رئوس منفرد به علاوه یال‌های متوالی تصادفی میان آن‌ها بدست می‌آید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحله‌ای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداول‌ترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شده‌است. فهرست برخی گراف‌های خاص
این مقاله به معرفی و بیان خواص برخی گراف‌های خاص می‌پردازد. این گراف‌ها شامل "گراف هی وود"، "گراف پترسن"، "گراف کنزر"، "گراف‌های formula_1-بعدی" و "ماز همپتون" می‌باشند. گراف هی وود یک گراف بدون جهت با14 رأس و 21 یال است . نظریه گراف هندسی
گراف هندسی یک گراف است که در آن رأس‌ و یال‌ها با اشیاء هندسی همراه شده‌اند. ساده‌ترین نمونه آن گراف هندسی تصادفی است.