گراف
| شناسنامه | |
|---|---|
| نام‌های دیگر | گراف ریاضی، ساختار گرافی، شبکهٔ ریاضی |
| حوزه | ریاضیات، ریاضیات گسسته، نظریه گراف، علوم رایانه، ساختار داده، نظریه شبکه |
| خاستگاه | مسئلهٔ پل‌های کونیگسبرگ و مطالعات ریاضی روابط و اتصال‌ها |
| اندیشه و تاریخ | |
| مفاهیم کلیدی | رأس، یال، درجه، مسیر، دور، همبندی، گراف جهت‌دار، گراف وزن‌دار، درخت، ماتریس مجاورت، پیمایش گراف، کوتاه‌ترین مسیر و رنگ‌آمیزی گراف |
| جریان‌های مرتبط | نظریهٔ گراف، ترکیبیات، نظریهٔ شبکه، الگوریتم‌های گراف، علوم شبکه و نظریهٔ پیچیدگی محاسباتی |
| تأثیرپذیرفته از | ریاضیات گسسته، ترکیبیات، هندسه، منطق ریاضی و نظریهٔ مجموعه‌ها |
| تأثیرگذار بر | علوم رایانه، الگوریتم‌ها، شبکه‌های رایانه‌ای، پایگاه دادهٔ گرافی، هوش مصنوعی، زیست‌شناسی محاسباتی و تحلیل شبکه‌های اجتماعی |
| نقد و ارزیابی | |
گراف (به انگلیسی: Graph)، در ریاضیات و علوم رایانه، ساختاری انتزاعی است که از مجموعه‌ای از رأس‌ها (Vertices) و یال‌ها (Edges) تشکیل می‌شود. رأس‌ها معمولاً نمایندهٔ اشیا، نقاط یا موجودیت‌ها هستند و یال‌ها رابطه، ارتباط یا اتصال میان آنها را نمایش می‌دهند. گراف یکی از مفاهیم بنیادی ریاضیات گسسته و موضوع اصلی نظریه گراف است و در مدل‌سازی شبکه‌های ارتباطی، مسیرهای حمل‌ونقل، روابط اجتماعی، ساختارهای داده و بسیاری از مسائل محاسباتی کاربرد دارد.
برای مثال، در مدل‌سازی شبکهٔ راه‌های میان شهرها، هر شهر می‌تواند یک رأس و هر راه ارتباطی میان دو شهر یک یال باشد. در یک شبکهٔ اجتماعی، اشخاص می‌توانند رأس و ارتباط میان آنها یال در نظر گرفته شوند. همچنین در شبکهٔ رایانه‌ای، رایانه‌ها و تجهیزات ارتباطی را می‌توان با رأس‌ها و پیوندهای ارتباطی را با یال‌ها نمایش داد.
ویژگی مهم گراف آن است که برای مطالعهٔ بسیاری از روابط، نیازی به دانستن موقعیت هندسی دقیق اشیا نیست. آنچه اهمیت دارد، ساختار اتصال و ارتباط میان رأس‌هاست. ازاین‌رو، دو گراف که در ظاهر شکل متفاوتی دارند، ممکن است از نظر ریاضی ساختار یکسانی داشته باشند.
مطالعات بنیادین نظریهٔ گراف معمولاً به پژوهش لئونارد اویلر دربارهٔ مسئلهٔ مشهور «هفت پل کونیگسبرگ» در سال ۱۷۳۶ میلادی نسبت داده می‌شود. اویلر نشان داد که پاسخ این مسئله را می‌توان بدون بررسی فاصله‌ها و اندازه‌های واقعی پل‌ها، تنها با مطالعهٔ روابط اتصال میان بخش‌های خشکی تعیین کرد.[۱]
گراف در علوم رایانه علاوه بر یک مفهوم ریاضی، نوعی ساختار داده نیز به شمار می‌رود. برنامه‌نویسان می‌توانند گراف را با روش‌هایی مانند فهرست مجاورت یا ماتریس مجاورت در حافظهٔ رایانه نمایش دهند و الگوریتم‌هایی برای پیمایش، جست‌وجو، یافتن مسیر و تحلیل ارتباطات روی آن اجرا کنند.[۲]
گراف‌ها در هوش مصنوعی، یادگیری ماشین، پایگاه داده، تحلیل داده، زیست‌شناسی، اقتصاد، مدیریت و مطالعات اجتماعی نیز کاربرد دارند. بااین‌حال، مدل‌سازی یک پدیده به‌صورت گراف به معنای آن نیست که تمام ویژگی‌های آن پدیده در مدل منعکس شده است؛ زیرا انتخاب رأس‌ها، یال‌ها و نوع رابطه بر نتیجهٔ تحلیل تأثیر می‌گذارد.
تعریف ریاضی گراف
در تعریف متداول، یک گراف بدون جهت با نماد زیر نمایش داده می‌شود:
<math>G=(V,E)</math>
در این رابطه، <math>G</math> نشان‌دهندهٔ گراف، <math>V</math> مجموعهٔ رأس‌ها و <math>E</math> مجموعهٔ یال‌هاست.
در یک گراف سادهٔ بدون جهت، هر یال یک جفت نامرتب از دو رأس متمایز است. بنابراین، مجموعهٔ یال‌ها را می‌توان زیرمجموعه‌ای از مجموعهٔ جفت‌های دوعضوی رأس‌ها در نظر گرفت.
برای مثال، گراف زیر را در نظر می‌گیریم:
<math>V=\{A,B,C,D\}</math>
<math>E=\{\{A,B\},\{A,C\},\{B,C\},\{C,D\}\}</math>
این گراف چهار رأس و چهار یال دارد. رأس A به رأس‌های B و C متصل است؛ رأس B به A و C متصل است؛ و رأس D تنها به C اتصال دارد.
در گراف‌های جهت‌دار، یال‌ها معمولاً به‌صورت زوج‌های مرتب تعریف می‌شوند. همچنین در چندگراف‌ها، برای نمایش چند یال میان دو رأس، تعریف مجموعه‌ای سادهٔ یال‌ها کافی نیست و باید یال‌های متمایز یا تابع وقوع یال‌ها نیز مشخص شوند.
اجزای بنیادی گراف
رأس
رأس (Vertex) که گاهی «گره» (Node) نیز نامیده می‌شود، یکی از عناصر اصلی گراف است.
رأس می‌تواند نمایندهٔ شخص، شهر، رایانه، صفحهٔ وب، ایستگاه حمل‌ونقل یا هر موجودیت دیگری باشد.
در یک گراف ریاضی، رأس‌ها لزوماً دارای مختصات هندسی نیستند و هویت آنها با جایگاهشان در ساختار روابط مشخص می‌شود.
یال
یال (Edge) ارتباط میان دو رأس را نمایش می‌دهد.
در گراف بدون جهت، یال میان A و B با یال میان B و A یکسان است.
اما در گراف جهت‌دار، ارتباط A به B الزاماً به معنای وجود ارتباط B به A نیست.
برای مثال، رابطهٔ دوستی متقابل را می‌توان در یک مدل ساده با یال بدون جهت نمایش داد، درحالی‌که رابطهٔ دنبال‌کردن یک حساب کاربری در شبکهٔ اجتماعی معمولاً جهت‌دار است.
درجهٔ رأس
درجهٔ رأس (Degree) در گراف بدون جهت، تعداد یال‌های متصل به آن رأس است. در محاسبهٔ درجه، هر حلقهٔ خودی دو بار شمرده می‌شود.
در یک گراف ساده، درجهٔ هر رأس برابر تعداد همسایگان آن است.
در گراف جهت‌دار، دو مفهوم درجهٔ ورودی و درجهٔ خروجی اهمیت دارند.
درجهٔ ورودی تعداد یال‌هایی است که به رأس وارد می‌شوند و درجهٔ خروجی تعداد یال‌هایی است که از رأس خارج می‌شوند.
همسایگی
دو رأس زمانی مجاور یا همسایه‌اند که یالی میان آنها وجود داشته باشد.
در گراف جهت‌دار، ممکن است میان همسایگان ورودی و خروجی تفاوت گذاشته شود.
مفهوم همسایگی در بسیاری از الگوریتم‌های گراف نقش بنیادی دارد.
مسیر
مسیر (Path) در تعریف رایج نظریهٔ گراف، دنباله‌ای از رأس‌های متمایز است که هر دو رأس متوالی آن با یال مرتبط‌اند.
در برخی منابع، واژهٔ مسیر با قراردادهای متفاوتی به کار می‌رود؛ بنابراین باید میان «راه‌پیمایی» (Walk)، «رد» (Trail) و مسیر ساده تمایز گذاشت.
در راه‌پیمایی، تکرار رأس‌ها و یال‌ها ممکن است مجاز باشد. در رد، یال تکرار نمی‌شود. در مسیر ساده، رأس‌ها تکرار نمی‌شوند.
دور
دور (Cycle) مسیری بسته است که از یک رأس آغاز می‌شود و به همان رأس بازمی‌گردد و در تعریف متداول، رأس‌های میانی آن متمایزند.
وجود دور در برخی کاربردها مانند شبکه‌های وابستگی، طراحی فرایند و بررسی بن‌بست‌های محاسباتی اهمیت دارد.
همبندی
یک گراف بدون جهت همبند (Connected) است اگر میان هر دو رأس آن مسیری وجود داشته باشد.
اگر گراف همبند نباشد، از چند مؤلفهٔ همبند تشکیل می‌شود.
در گراف‌های جهت‌دار، میان همبندی قوی و همبندی ضعیف تفاوت وجود دارد.
تاریخچهٔ گراف
مسئلهٔ هفت پل کونیگسبرگ
یکی از مشهورترین مسائل آغازین نظریهٔ گراف، مسئلهٔ هفت پل کونیگسبرگ است.
کونیگسبرگ شهری در پروس بود که امروزه با نام کالینینگراد در روسیه شناخته می‌شود. در سدهٔ هجدهم، رودخانهٔ پرگل از این شهر عبور می‌کرد و بخش‌هایی از خشکی با هفت پل به یکدیگر متصل بودند.
مسئله این بود که آیا می‌توان مسیری یافت که از هر هفت پل دقیقاً یک بار عبور کند.
لئونارد اویلر در پژوهش خود نشان داد که پاسخ منفی است.
او به‌جای بررسی شکل دقیق رودخانه و پل‌ها، هر بخش خشکی را به‌صورت یک رأس و هر پل را به‌صورت یک یال در نظر گرفت.
به این ترتیب، مسئلهٔ جغرافیایی به مسئله‌ای دربارهٔ ساختار اتصال تبدیل شد.[۱]
نقش لئونارد اویلر
اویلر نشان داد که وجود مسیر عبور از همهٔ یال‌ها به درجهٔ رأس‌ها وابسته است.
در گراف بدون جهتِ همبند با دست‌کم یک یال، وجود مسیر اویلری باز مستلزم آن است که دقیقاً دو رأس درجهٔ فرد داشته باشند. وجود دور اویلری نیز مستلزم زوج‌بودن درجهٔ همهٔ رأس‌هاست.
در گراف مسئلهٔ کونیگسبرگ، هر چهار رأس درجهٔ فرد داشتند؛ بنابراین عبور از هر هفت پل دقیقاً یک بار، حتی بدون الزام بازگشت به نقطهٔ آغاز، ممکن نبود.
این پژوهش یکی از نقطه‌های آغاز نظریهٔ گراف و مطالعهٔ ریاضی ساختارهای اتصال به شمار می‌رود.
گسترش نظریهٔ گراف در سدهٔ نوزدهم
در سدهٔ نوزدهم، نظریهٔ گراف با مسائل جدیدی در ریاضیات و علوم طبیعی پیوند یافت.
گوستاو کیرشهف از روش‌های مرتبط با ساختار شبکه برای بررسی مدارهای الکتریکی استفاده کرد.
آرتور کیلی نیز در مطالعهٔ درخت‌ها و شمارش ساختارهای ترکیبیاتی نقش داشت.
همچنین پژوهش دربارهٔ مسیرها و دورهایی که از همهٔ رأس‌ها عبور می‌کنند، به توسعهٔ مسائل همیلتونی کمک کرد.
گراف در سدهٔ بیستم
در سدهٔ بیستم، نظریهٔ گراف به یکی از شاخه‌های مهم ریاضیات گسسته تبدیل شد.
مطالعهٔ گراف‌های تصادفی، رنگ‌آمیزی گراف، تطابق، جریان شبکه و الگوریتم‌های مسیریابی گسترش یافت.
پل اردوش و آلفرد رنی از چهره‌های مهم توسعهٔ نظریهٔ گراف تصادفی بودند.
همچنین ادسخر دایکسترا الگوریتمی مشهور برای یافتن کوتاه‌ترین مسیر از یک مبدأ در گراف‌های دارای وزن نامنفی ارائه کرد.
گراف در عصر اینترنت
با گسترش اینترنت و شبکه‌های رایانه‌ای، اهمیت کاربردی گراف افزایش یافت.
ساختار پیوندهای وب، ارتباط میان کاربران شبکه‌های اجتماعی و مسیرهای انتقال اطلاعات را می‌توان با گراف مدل‌سازی کرد.
در دهه‌های اخیر، پایگاه‌های دادهٔ گرافی، شبکه‌های عصبی گرافی و سامانه‌های تحلیل شبکه نیز توسعه یافته‌اند.
انواع گراف
گراف‌ها را می‌توان بر اساس جهت یال‌ها، وزن، تعداد ارتباطات و ویژگی‌های ساختاری طبقه‌بندی کرد.
گراف بدون جهت
گراف بدون جهت (Undirected Graph) گرافی است که یال‌های آن جهت ندارند.
در چنین گرافی، ارتباط میان دو رأس متقارن است.
برای مثال، اگر A به B متصل باشد، B نیز به A متصل است.
شبکهٔ راه‌های دوطرفه را می‌توان در یک مدل ساده با گراف بدون جهت نمایش داد.
گراف جهت‌دار
گراف جهت‌دار (Directed Graph یا Digraph) گرافی است که یال‌های آن جهت مشخص دارند.
در این نوع گراف، یال از رأس A به B با یال از B به A متفاوت است.
ساختار پیوندهای وب و برخی روابط سازمانی را می‌توان با گراف جهت‌دار مدل‌سازی کرد.
گراف وزن‌دار
گراف وزن‌دار (Weighted Graph) گرافی است که به یال‌ها یا در برخی مدل‌ها به رأس‌های آن مقادیر عددی نسبت داده می‌شود.
وزن می‌تواند نشان‌دهندهٔ فاصله، زمان، هزینه، ظرفیت یا شدت رابطه باشد.
برای مثال، در شبکهٔ راه‌ها، وزن یال ممکن است طول مسیر میان دو شهر باشد.
گراف بدون وزن
در گراف بدون وزن، یال‌ها وزن عددی صریح ندارند.
در برخی مسائل مسیریابی، همهٔ یال‌های چنین گرافی دارای هزینهٔ یکسان در نظر گرفته می‌شوند.
گراف ساده
گراف ساده (Simple Graph) در تعریف رایج، گرافی بدون حلقهٔ خودی و بدون یال‌های موازی است.
در این گراف، میان هر دو رأس متمایز حداکثر یک یال وجود دارد.
چندگراف
چندگراف (Multigraph) گرافی است که می‌تواند چند یال متمایز میان یک جفت رأس داشته باشد.
برای مثال، اگر میان دو شهر چند مسیر ریلی مستقل وجود داشته باشد، می‌توان آنها را با یال‌های موازی نمایش داد.
قرارداد مربوط به مجازبودن حلقهٔ خودی در تعریف چندگراف میان منابع مختلف متفاوت است.
کتابخانهٔ NetworkX برای گراف‌های ساده، جهت‌دار و چندگراف‌ها ساختارهای جداگانه‌ای ارائه می‌کند.[۳]
گراف کامل
گراف کامل (Complete Graph) گراف ساده‌ای است که میان هر دو رأس متمایز آن یک یال وجود دارد.
گراف کامل با n رأس معمولاً با نماد <math>K_n</math> نمایش داده می‌شود.
تعداد یال‌های آن برابر است با:
<math>\frac{n(n-1)}{2}</math>
برای مثال، گراف کامل با چهار رأس دارای شش یال است.
گراف دوبخشی
گراف دوبخشی (Bipartite Graph) گرافی است که مجموعهٔ رأس‌های آن را می‌توان به دو مجموعهٔ مجزا تقسیم کرد، به‌گونه‌ای که هیچ یالی دو رأس متعلق به یک مجموعه را به یکدیگر متصل نکند.
برای مثال، می‌توان مجموعه‌ای از دانشجویان و مجموعه‌ای از درس‌ها را در نظر گرفت و ثبت‌نام هر دانشجو در یک درس را با یال نمایش داد.
گراف‌های دوبخشی در مسائل تطابق و تخصیص منابع کاربرد دارند.
گراف مسطح
گراف مسطح (Planar Graph) گرافی است که بتوان آن را روی صفحه به‌گونه‌ای رسم کرد که یال‌ها جز در رأس‌های مشترک یکدیگر را قطع نکنند.
مسطح‌بودن ویژگی ساختاری گراف است و به یک ترسیم خاص محدود نمی‌شود.
ممکن است گرافی در یک رسم دارای تقاطع یال‌ها باشد، اما بتوان آن را بدون تقاطع دوباره ترسیم کرد.
گراف دوردار و بدون دور
گرافی که دارای دست‌کم یک دور باشد، دوردار نامیده می‌شود.
گراف بدون دور فاقد چنین ساختاری است.
در گراف‌های جهت‌دار، مفهوم گراف جهت‌دار بدون دور یا DAG اهمیت ویژه‌ای دارد.
این نوع گراف در نمایش وابستگی وظایف و ترتیب اجرای فعالیت‌ها کاربرد دارد.
گراف تصادفی
گراف تصادفی (Random Graph) گرافی است که ساختار آن بر اساس یک مدل احتمالاتی تولید یا مطالعه می‌شود.
مدل اردوش–رنی از مدل‌های شناخته‌شدهٔ گراف تصادفی است.
گراف‌های تصادفی برای مطالعهٔ ویژگی‌های آماری شبکه‌ها و بررسی رفتار ساختارهای بزرگ کاربرد دارند.
درخت به‌عنوان نوعی گراف
درخت (Tree) در نظریهٔ گراف، گراف بدون جهتِ همبند و بدون دور است.
اگر درخت دارای n رأس باشد، تعداد یال‌های آن برابر n منهای یک است.
درخت‌ها در علوم رایانه برای نمایش ساختارهای سلسله‌مراتبی، جست‌وجو و سازمان‌دهی داده‌ها استفاده می‌شوند.
هر درخت یک گراف است، اما هر گراف لزوماً درخت نیست.
درخت ریشه‌دار دارای رأسی مشخص به نام ریشه است و می‌توان رابطهٔ والد و فرزند را میان رأس‌های آن تعریف کرد.
ویژگی‌های ساختاری گراف
مرتبه و اندازهٔ گراف
مرتبهٔ گراف معمولاً به تعداد رأس‌ها گفته می‌شود.
اندازهٔ گراف در کاربرد متداول به تعداد یال‌ها اشاره دارد.
این دو مقدار از شاخص‌های پایه برای توصیف گراف هستند.
چگالی گراف
چگالی گراف نسبت تعداد یال‌های موجود به حداکثر تعداد یال‌های ممکن در مدل موردنظر است.
برای گراف سادهٔ بدون جهت با n رأس و m یال، در صورتی که n بزرگ‌تر از یک باشد، چگالی از رابطهٔ زیر به دست می‌آید:
<math>D=\frac{2m}{n(n-1)}</math>
چگالی نشان می‌دهد چه نسبتی از ارتباطات ممکن واقعاً وجود دارد.
فاصلهٔ گرافی
فاصلهٔ گرافی میان دو رأس، در گراف بدون وزن، برابر تعداد یال‌های کوتاه‌ترین مسیر میان آنهاست.
در گراف وزن‌دار، فاصله می‌تواند بر اساس مجموع وزن یال‌های مسیر تعریف شود.
اگر میان دو رأس هیچ مسیری وجود نداشته باشد، فاصلهٔ آنها در بسیاری از قراردادها بی‌نهایت در نظر گرفته می‌شود.
قطر گراف
قطر گراف در گراف همبند، بیشترین فاصلهٔ کوتاه‌ترین مسیر میان هر دو رأس است.
قطر می‌تواند برای بررسی گستردگی شبکه و فاصلهٔ ساختاری میان نقاط آن استفاده شود.
مؤلفهٔ همبند
مؤلفهٔ همبند زیرگراف همبند بیشینه‌ای است که نمی‌توان رأس دیگری از گراف را بدون ازدست‌رفتن ویژگی همبندی به آن افزود.
شناسایی مؤلفه‌های همبند در تحلیل شبکه‌های اجتماعی و سامانه‌های ارتباطی کاربرد دارد.
پل و رأس برشی
پل یالی است که حذف آن تعداد مؤلفه‌های همبند گراف بدون جهت را افزایش می‌دهد.
رأس برشی رأسی است که حذف آن، همراه با یال‌های متصل، تعداد مؤلفه‌های همبند را افزایش می‌دهد.
این مفاهیم در بررسی آسیب‌پذیری شبکه‌ها اهمیت دارند.
قضیهٔ دست‌دادن
یکی از قضیه‌های بنیادی نظریهٔ گراف، قضیهٔ دست‌دادن (Handshaking Lemma) است.
این قضیه بیان می‌کند که در هر گراف بدون جهتِ متناهی، مجموع درجهٔ همهٔ رأس‌ها برابر دو برابر تعداد یال‌هاست:
<math>\sum_{v\in V}\deg(v)=2|E|</math>
دلیل آن است که هر یال در مجموع درجه‌ها دو بار شمرده می‌شود.
نتیجهٔ مهم این قضیه آن است که تعداد رأس‌های دارای درجهٔ فرد در هر گراف بدون جهتِ متناهی، زوج است.
نمایش گراف در رایانه
برای ذخیره‌سازی و پردازش گراف در رایانه، باید رأس‌ها و یال‌ها با استفاده از ساختارهای داده نمایش داده شوند.
انتخاب روش نمایش بر مصرف حافظه و سرعت اجرای عملیات تأثیر می‌گذارد.
ماتریس مجاورت
ماتریس مجاورت (Adjacency Matrix) ماتریسی است که ارتباط میان رأس‌ها را نشان می‌دهد.
در گراف سادهٔ بدون جهت، اگر میان رأس i و رأس j یال وجود داشته باشد، مقدار خانهٔ متناظر برابر یک و در غیر این صورت صفر است.
برای مثال، گرافی با رأس‌های A، B و C را در نظر می‌گیریم که یال‌های آن A–B و B–C هستند.
ماتریس مجاورت آن به‌صورت زیر است:
A B C A 0 1 0 B 1 0 1 C 0 1 0
ماتریس مجاورت برای گرافی با n رأس معمولاً به فضای ذخیره‌سازی متناسب با <math>n^2</math> نیاز دارد.
در مقابل، بررسی وجود یال میان دو رأس مشخص در این نمایش معمولاً با دسترسی مستقیم به یک خانهٔ ماتریس انجام می‌شود.[۲]
فهرست مجاورت
فهرست مجاورت (Adjacency List) روشی است که در آن برای هر رأس، مجموعه یا فهرستی از همسایگان آن نگهداری می‌شود.
برای مثال:
A: B B: A, C C: B
در پیاده‌سازی متداول، فهرست مجاورت برای گرافی با n رأس و m یال به فضایی از مرتبهٔ <math>O(n+m)</math> نیاز دارد.
این روش معمولاً برای گراف‌های تنک مناسب است.
فهرست یال‌ها
فهرست یال‌ها (Edge List) شامل مجموعه یا فهرستی از ارتباطات میان رأس‌هاست.
برای مثال:
(A, B) (B, C) (C, D)
این نمایش ساده است و برای انتقال داده یا اجرای برخی الگوریتم‌ها کاربرد دارد.
اما جست‌وجوی همسایگان یک رأس در فهرست خام یال‌ها ممکن است نیازمند بررسی تعداد زیادی از یال‌ها باشد.
الگوریتم‌های گراف
الگوریتم‌های گراف روش‌های محاسباتی برای بررسی و پردازش ساختار گراف هستند.
این الگوریتم‌ها می‌توانند برای پیمایش، جست‌وجو، یافتن مسیر، تشخیص دور، بررسی همبندی و حل مسائل بهینه‌سازی استفاده شوند.
پیمایش سطح‌اول
پیمایش سطح‌اول (Breadth-First Search یا BFS) الگوریتمی برای پیمایش گراف است که رأس‌ها را به‌ترتیب فاصلهٔ تعداد یال از رأس آغاز بررسی می‌کند.
این الگوریتم معمولاً از صف استفاده می‌کند.
در گراف بدون وزن، BFS می‌تواند کوتاه‌ترین مسیر از نظر تعداد یال‌ها را از یک رأس مبدأ به رأس‌های قابل دسترس پیدا کند.
پیچیدگی زمانی آن در نمایش فهرست مجاورت معمولاً از مرتبهٔ <math>O(V+E)</math> است.
پیمایش عمق‌اول
پیمایش عمق‌اول (Depth-First Search یا DFS) الگوریتمی است که تا حد امکان در یک مسیر پیش می‌رود و سپس به نقاط قبلی بازمی‌گردد.
این الگوریتم را می‌توان با پشته یا فراخوانی بازگشتی پیاده‌سازی کرد.
DFS در تشخیص دور، بررسی همبندی، مرتب‌سازی توپولوژیک و برخی مسائل دیگر کاربرد دارد.
پیچیدگی زمانی آن در نمایش فهرست مجاورت معمولاً از مرتبهٔ <math>O(V+E)</math> است.
الگوریتم دایکسترا
الگوریتم دایکسترا (Dijkstra's Algorithm) برای یافتن کوتاه‌ترین مسیرها از یک رأس مبدأ در گراف‌های دارای وزن یال نامنفی استفاده می‌شود.
این الگوریتم در مسیریابی و شبکه‌های ارتباطی کاربرد دارد.
نسخهٔ متداول آن با صف اولویت می‌تواند محاسبات را کارآمدتر انجام دهد.
الگوریتم دایکسترا در حالت عمومی برای گراف‌هایی که دارای یال با وزن منفی هستند، مناسب نیست.
الگوریتم بلمن–فورد
الگوریتم بلمن–فورد (Bellman–Ford Algorithm) برای محاسبهٔ کوتاه‌ترین مسیر از یک مبدأ استفاده می‌شود.
این الگوریتم می‌تواند یال‌های دارای وزن منفی را نیز مدیریت کند، مشروط بر آنکه دور منفیِ قابل دسترس از مبدأ مانع تعریف فاصلهٔ کوتاه‌ترین مسیر نشود.
بلمن–فورد همچنین می‌تواند وجود دور منفی قابل دسترس را تشخیص دهد.
الگوریتم فلوید–وارشال
الگوریتم فلوید–وارشال (Floyd–Warshall Algorithm) برای محاسبهٔ کوتاه‌ترین مسیر میان همهٔ جفت‌رأس‌ها به کار می‌رود.
پیچیدگی زمانی نسخهٔ متداول آن از مرتبهٔ <math>O(V^3)</math> است.
این الگوریتم در گراف‌هایی با وزن منفی نیز قابل استفاده است، اما وجود دور منفی در مسیرهای مربوط می‌تواند مانع تعریف فاصلهٔ کوتاه‌ترین مسیر شود.
درخت پوشای کمینه
درخت پوشای کمینه (Minimum Spanning Tree) در یک گراف بدون جهتِ همبند و وزن‌دار، درختی است که همهٔ رأس‌ها را در بر می‌گیرد و مجموع وزن یال‌های آن کمینه است.
این مفهوم در طراحی شبکه‌های ارتباطی و مسائل بهینه‌سازی کاربرد دارد.
الگوریتم‌های پریم و کروسکال از روش‌های شناخته‌شده برای یافتن درخت پوشای کمینه هستند.
الگوریتم پریم
الگوریتم پریم (Prim's Algorithm) درخت پوشای کمینه را با گسترش تدریجی مجموعه‌ای از رأس‌های متصل ایجاد می‌کند.
در هر مرحله، یالی با کمترین وزن مناسب انتخاب می‌شود که یک رأس جدید را به درخت موجود متصل کند.
الگوریتم کروسکال
الگوریتم کروسکال (Kruskal's Algorithm) یال‌ها را بر اساس وزن بررسی می‌کند و یال‌هایی را برمی‌گزیند که موجب ایجاد دور در مجموعهٔ انتخاب‌شده نشوند.
این الگوریتم از روش‌های متداول حل مسئلهٔ درخت پوشای کمینه است.
مرتب‌سازی توپولوژیک
مرتب‌سازی توپولوژیک (Topological Sorting) ترتیبی از رأس‌های یک گراف جهت‌دار بدون دور است که در آن هر رأس پیش از رأس‌هایی قرار می‌گیرد که یال خروجی به آنها دارد.
این روش در زمان‌بندی فعالیت‌ها و مدیریت وابستگی‌های نرم‌افزاری کاربرد دارد.
اگر گراف جهت‌دار دارای دور باشد، مرتب‌سازی توپولوژیک کامل برای همهٔ رأس‌ها وجود نخواهد داشت.
رنگ‌آمیزی گراف
رنگ‌آمیزی گراف (Graph Coloring) به اختصاص رنگ‌ها یا برچسب‌ها به عناصر گراف تحت شرایط مشخص اشاره دارد.
در رنگ‌آمیزی رأسی، معمولاً هدف آن است که دو رأس مجاور رنگ یکسان نداشته باشند.
کمترین تعداد رنگ موردنیاز برای رنگ‌آمیزی رأسیِ صحیح، عدد رنگی گراف نامیده می‌شود.
این مفهوم در زمان‌بندی، تخصیص منابع و برخی مسائل نقشه‌کشی کاربرد دارد.
مسئلهٔ چهار رنگ
قضیهٔ چهار رنگ بیان می‌کند که برای رنگ‌آمیزی نواحی هر نقشهٔ مسطح، به‌گونه‌ای که نواحی دارای مرز مشترک با طول مثبت رنگ یکسان نداشته باشند، حداکثر چهار رنگ کافی است.
این مسئله را می‌توان با استفاده از گراف‌های مسطح صورت‌بندی کرد.
اثبات این قضیه در سال ۱۹۷۶ توسط کنت اپل و ولفگانگ هاکن، با کمک محاسبات رایانه‌ای، از رویدادهای مهم تاریخ ریاضیات به شمار می‌رود.
مسیر اویلری و دور اویلری
مسیر اویلری مسیری از نوع رد است که از همهٔ یال‌های گراف دقیقاً یک بار عبور می‌کند.
اگر این مسیر از همان رأسی که آغاز شده پایان یابد، دور اویلری نامیده می‌شود.
در گراف بدون جهتِ همبند با دست‌کم یک یال، وجود دور اویلری معادل زوج‌بودن درجهٔ همهٔ رأس‌هاست.
مسئلهٔ پل‌های کونیگسبرگ نمونهٔ تاریخی بررسی چنین مسیری است.
مسیر همیلتونی و دور همیلتونی
مسیر همیلتونی مسیری است که از همهٔ رأس‌های گراف دقیقاً یک بار عبور می‌کند.
دور همیلتونی دوری است که همهٔ رأس‌ها را در بر می‌گیرد.
تفاوت بنیادی آن با مسیر اویلری در این است که مسیر اویلری بر عبور از همهٔ یال‌ها و مسیر همیلتونی بر بازدید از همهٔ رأس‌ها تمرکز دارد.
مسئلهٔ فروشندهٔ دوره‌گرد
مسئلهٔ فروشندهٔ دوره‌گرد (Traveling Salesperson Problem) از مسائل مشهور بهینه‌سازی ترکیبیاتی است.
در صورت‌بندی رایج، هدف یافتن کوتاه‌ترین دوری است که از هر شهر دقیقاً یک بار بازدید کند و به نقطهٔ آغاز بازگردد.
این مسئله با گراف‌های وزن‌دار و دورهای همیلتونی ارتباط دارد.
نسخهٔ عمومی بهینه‌سازی آن از مسائل دشوار محاسباتی است.
گراف و نظریهٔ پیچیدگی
بسیاری از مسائل نظریهٔ گراف از نظر پیچیدگی محاسباتی مطالعه می‌شوند.
برخی مسائل، مانند پیمایش گراف و یافتن مؤلفه‌های همبند، دارای الگوریتم‌های کارآمد هستند.
در مقابل، نسخه‌های عمومی برخی مسائل مانند یافتن دور همیلتونی و رنگ‌آمیزی با تعداد محدود رنگ می‌توانند از مسائل NP-کامل باشند.
این تفاوت نشان می‌دهد که شباهت ظاهری مسائل گرافی لزوماً به معنای یکسان‌بودن دشواری محاسباتی آنها نیست.
گراف و شبکه‌های رایانه‌ای
در شبکه‌های رایانه‌ای، گراف برای نمایش تجهیزات و ارتباطات میان آنها استفاده می‌شود.
رایانه‌ها، مسیریاب‌ها و سوئیچ‌ها می‌توانند به‌صورت رأس و پیوندهای ارتباطی به‌صورت یال مدل‌سازی شوند.
الگوریتم‌های گراف در مسیریابی بسته‌های اطلاعاتی و بررسی قابلیت دسترسی شبکه کاربرد دارند.
گراف و اینترنت
ساختار پیوندهای میان صفحه‌های وب را می‌توان با گراف جهت‌دار نمایش داد.
در این مدل، هر صفحه یک رأس و هر پیوند از یک صفحه به صفحهٔ دیگر یک یال جهت‌دار است.
این مدل در تحلیل ساختار وب و برخی روش‌های رتبه‌بندی صفحات کاربرد دارد.
گراف و شبکه‌های اجتماعی
در شبکه‌های اجتماعی، اشخاص یا حساب‌های کاربری می‌توانند رأس‌های گراف باشند.
روابطی مانند دوستی، دنبال‌کردن یا تبادل پیام ممکن است به‌صورت یال مدل‌سازی شوند.
تحلیل چنین گراف‌هایی می‌تواند به مطالعهٔ ساختار گروه‌ها، الگوهای ارتباطی و انتشار اطلاعات کمک کند.
بااین‌حال، وجود ارتباط در یک شبکه الزاماً نشان‌دهندهٔ اعتماد، موافقت سیاسی یا رابطهٔ اجتماعی عمیق نیست.
مرکزیت در گراف
مرکزیت (Centrality) به مجموعه‌ای از شاخص‌ها گفته می‌شود که اهمیت ساختاری رأس‌ها را بر اساس تعریف‌های مختلف اندازه‌گیری می‌کنند.
مرکزیت درجه بر تعداد ارتباطات مستقیم تأکید دارد.
مرکزیت بینابینی میزان قرارگرفتن رأس در کوتاه‌ترین مسیرهای میان جفت‌رأس‌ها را بررسی می‌کند.
مرکزیت نزدیکی بر فاصلهٔ یک رأس از سایر رأس‌های قابل دسترس تمرکز دارد.
این شاخص‌ها معناهای متفاوتی دارند و نباید آنها را معادل یکدیگر دانست.
اجتماع‌یابی در گراف
اجتماع‌یابی (Community Detection) به شناسایی گروه‌هایی از رأس‌ها اشاره دارد که بر اساس معیارهای مشخص، ارتباط درونی بیشتری نسبت به ارتباطات بیرونی دارند.
این روش در تحلیل شبکه‌های اجتماعی، شبکه‌های علمی و برخی سامانه‌های زیستی کاربرد دارد.
نتیجهٔ اجتماع‌یابی به الگوریتم و تعریف اجتماع وابسته است.
گراف و پایگاه داده
پایگاه دادهٔ گرافی (Graph Database) نوعی سامانهٔ مدیریت داده است که برای نگهداری و پرس‌وجوی اطلاعات دارای روابط گسترده طراحی می‌شود.
در این سامانه‌ها، موجودیت‌ها و روابط آنها ممکن است به‌صورت گره و یال ذخیره شوند.
پایگاه دادهٔ گرافی برای برخی کاربردها مانند تحلیل ارتباطات، سامانه‌های پیشنهادگر و مدیریت دانش مناسب است.
بااین‌حال، همهٔ داده‌ها نیازمند پایگاه دادهٔ گرافی نیستند و پایگاه‌های رابطه‌ای در بسیاری از کاربردها گزینه‌ای کارآمد به شمار می‌روند.
گراف و ساختار داده
در ساختار داده، گراف برای نمایش ارتباطات غیرسلسله‌مراتبی استفاده می‌شود.
برخلاف آرایه یا فهرست پیوندی که ترتیب مشخصی دارند، گراف می‌تواند روابط چندگانه و پیچیده میان عناصر را نمایش دهد.
همچنین برخلاف درخت، گراف ممکن است دارای دور یا چند مسیر میان دو رأس باشد.
انتخاب نمایش مناسب گراف به تعداد رأس‌ها، تعداد یال‌ها و نوع عملیات موردنیاز بستگی دارد.
گراف و فلوچارت
فلوچارت یا نمودار جریان، روشی گرافیکی برای نمایش مراحل یک الگوریتم یا فرایند است.
از نظر ریاضی، ساختار ارتباطی یک فلوچارت را می‌توان با گراف جهت‌دار مدل‌سازی کرد.
در چنین مدلی، مراحل و تصمیم‌ها رأس و پیکان‌های انتقال کنترل یال‌های جهت‌دار هستند.
اما فلوچارت و گراف مفاهیم یکسانی نیستند.
گراف ساختاری ریاضی و عمومی است، درحالی‌که فلوچارت نوعی نمودار کاربردی با نمادهای قراردادی برای نمایش فرایندهاست.
گراف و علم داده
در علم داده، گراف برای نمایش روابط میان داده‌ها استفاده می‌شود.
برخی مجموعه‌های داده به‌طور طبیعی ساختاری شبکه‌ای دارند.
برای مثال، ارتباط میان نویسندگان مقاله‌های علمی، پیوندهای میان وبگاه‌ها یا تعاملات میان کاربران را می‌توان به‌صورت گراف نمایش داد.
تحلیل گراف می‌تواند الگوهایی را آشکار کند که در بررسی جداگانهٔ رکوردها کمتر دیده می‌شوند.
گراف و داده‌کاوی
داده‌کاوی شامل روش‌هایی برای شناسایی الگوها و روابط در مجموعه‌های داده است.
داده‌کاوی گرافی بر استخراج الگو از ساختارهای شبکه‌ای تمرکز دارد.
شناسایی زیرگراف‌های پرتکرار، کشف اجتماع‌ها و پیش‌بینی ارتباطات احتمالی از نمونه‌های این حوزه هستند.
گراف و هوش مصنوعی
در هوش مصنوعی، گراف‌ها برای بازنمایی روابط، جست‌وجوی حالت‌ها، برنامه‌ریزی و مدل‌سازی دانش استفاده می‌شوند.
برای مثال، در یک سامانهٔ برنامه‌ریزی، هر وضعیت ممکن است به‌صورت رأس و هر عمل مجاز به‌صورت یال نمایش داده شود.
الگوریتم‌های جست‌وجو می‌توانند مسیر رسیدن از وضعیت آغازین به وضعیت هدف را بررسی کنند.
شبکه‌های عصبی گرافی
شبکه‌های عصبی گرافی (Graph Neural Networks یا GNN) خانواده‌ای از مدل‌های یادگیری عمیق هستند که برای پردازش داده‌های دارای ساختار گرافی طراحی شده‌اند.
در بسیاری از این مدل‌ها، اطلاعات هر رأس با استفاده از ویژگی‌های خودش و اطلاعات همسایگان آن به‌روزرسانی می‌شود.
شبکه‌های عصبی گرافی در پیش‌بینی ویژگی رأس‌ها، طبقه‌بندی گراف‌ها و پیش‌بینی یال‌ها کاربرد دارند.
گراف دانش
گراف دانش (Knowledge Graph) ساختاری برای بازنمایی موجودیت‌ها و روابط معنایی میان آنهاست.
در این مدل، اشخاص، مکان‌ها، سازمان‌ها و مفاهیم می‌توانند به‌صورت گره و روابط میان آنها به‌صورت یال نمایش داده شوند.
برای مثال، ارتباط میان یک نویسنده، اثر ادبی و تاریخ انتشار را می‌توان در گراف دانش ثبت کرد.
گراف‌های دانش در جست‌وجوی معنایی، یکپارچه‌سازی اطلاعات و برخی سامانه‌های هوش مصنوعی کاربرد دارند.
گراف و پردازش زبان طبیعی
در پردازش زبان طبیعی، گراف می‌تواند برای نمایش روابط نحوی و معنایی میان واژه‌ها یا مفاهیم استفاده شود.
در برخی روش‌های تحلیل نحوی، واژه‌های جمله به‌صورت گره و وابستگی‌های دستوری میان آنها به‌صورت یال نمایش داده می‌شوند.
این ساختارها در تحلیل زبان و استخراج اطلاعات کاربرد دارند.
گراف و زیست‌شناسی
در زیست‌شناسی محاسباتی، گراف برای مدل‌سازی روابط میان ژن‌ها، پروتئین‌ها و فرایندهای زیستی استفاده می‌شود.
شبکه‌های تعامل پروتئینی از نمونه‌های شناخته‌شدهٔ این کاربرد هستند.
تحلیل ساختار شبکه می‌تواند به شناسایی روابط و فرضیه‌های پژوهشی کمک کند.
اما وجود یال در یک مدل زیستی به‌تنهایی اثبات‌کنندهٔ رابطهٔ علّی نیست.
گراف و حمل‌ونقل
در سامانه‌های حمل‌ونقل، ایستگاه‌ها، تقاطع‌ها یا شهرها می‌توانند رأس‌های گراف باشند.
راه‌ها و مسیرهای ارتباطی نیز با یال نمایش داده می‌شوند.
وزن یال ممکن است فاصله، زمان سفر یا هزینهٔ جابه‌جایی باشد.
الگوریتم‌های کوتاه‌ترین مسیر در طراحی مسیرهای حمل‌ونقل کاربرد دارند.
گراف و اقتصاد
در اقتصاد، گراف برای نمایش روابط تجاری، زنجیره‌های تأمین و ارتباط میان بنگاه‌ها استفاده می‌شود.
برای مثال، شرکت‌ها می‌توانند رأس و روابط تأمین کالا میان آنها یال باشند.
تحلیل چنین شبکه‌هایی می‌تواند به بررسی وابستگی‌ها و شناسایی نقاط آسیب‌پذیر کمک کند.
گراف و علوم اجتماعی
در علوم اجتماعی، گراف ابزار مهمی برای تحلیل ساختار روابط است.
شبکه‌های دوستی، همکاری علمی، ارتباطات سازمانی و روابط میان نهادها را می‌توان با مدل‌های گرافی مطالعه کرد.
بااین‌حال، روابط اجتماعی دارای ابعاد تاریخی، فرهنگی و سیاسی هستند که ممکن است در یک مدل سادهٔ رأس و یال منعکس نشوند.
گراف و حریم خصوصی
تحلیل گراف‌های اجتماعی ممکن است اطلاعات حساسی دربارهٔ روابط افراد آشکار کند.
حتی اگر نام اشخاص حذف شده باشد، ساختار ارتباطات گاهی امکان بازشناسایی آنها را فراهم می‌کند.
بنابراین، گردآوری و تحلیل داده‌های شبکه‌ای باید با رعایت حریم خصوصی و محدودیت‌های قانونی انجام شود.
گراف و دانشنامه‌های دیجیتال
در دانشنامه‌های دیجیتال، ارتباط میان مقاله‌ها را می‌توان به‌صورت گراف مدل‌سازی کرد.
در این مدل، هر مقاله یک رأس و هر پیوند داخلی از یک مقاله به مقالهٔ دیگر یک یال جهت‌دار است.
همچنین می‌توان روابط میان مقاله‌ها و رده‌ها را با یک گراف دوبخشی یا ساختارهای گرافی دیگر بررسی کرد.
تحلیل این ساختارها می‌تواند به شناسایی مقاله‌های فاقد پیوند، بخش‌های کم‌ارتباط و موضوعات مرکزی کمک کند.
گراف در مدیاویکی
مدیاویکی نرم‌افزاری برای ایجاد و مدیریت دانشنامه‌ها و وبگاه‌های مشارکتی است.
در مدیاویکی، مقاله‌ها، رده‌ها، الگوها و پیوندهای داخلی روابط گوناگونی با یکدیگر دارند.
این روابط را می‌توان برای تحلیل‌های جداگانه به ساختار گرافی تبدیل کرد.
برای مثال، می‌توان بررسی کرد که یک مقاله به چند مقالهٔ دیگر پیوند دارد یا از چند مقاله پیوند دریافت می‌کند.
بااین‌حال، این نوع تحلیل الزاماً به معنای استفادهٔ مدیاویکی از پایگاه دادهٔ گرافی برای ذخیره‌سازی اصلی اطلاعات نیست.
کاربرد گراف در ایران‌پدیا
در دانشنامهٔ ایران‌پدیا، ساختار پیوندهای داخلی و رده‌بندی مقاله‌ها را می‌توان با روش‌های نظریهٔ گراف بررسی کرد.
برای مثال، هر مقاله می‌تواند به‌صورت یک رأس و هر پیوند داخلی به‌صورت یک یال جهت‌دار مدل‌سازی شود.
با این روش، می‌توان مقاله‌هایی را که پیوند ورودی کمی دارند شناسایی کرد، ارتباط میان موضوعات مختلف را بررسی کرد و بخش‌هایی از دانشنامه را که پیوندهای داخلی ضعیفی دارند مشخص ساخت.
همچنین ساختار رده‌ها می‌تواند برای مطالعهٔ روابط سلسله‌مراتبی و شناسایی رده‌های بدون ارتباط مناسب بررسی شود.
این کاربردها امکان‌های تحلیلی نظریهٔ گراف هستند و به معنای آن نیست که ایران‌پدیا در حال حاضر از سامانهٔ تحلیل گراف استفاده می‌کند.
نرم‌افزارهای تحلیل گراف
ابزارهای مختلفی برای ایجاد، نمایش و تحلیل گراف‌ها توسعه یافته‌اند.
NetworkX
NetworkX کتابخانه‌ای متن‌باز در زبان پایتون است که برای ایجاد، پردازش و تحلیل گراف‌ها استفاده می‌شود.
این کتابخانه از گراف‌های جهت‌دار، بدون جهت و چندگراف‌ها پشتیبانی می‌کند و الگوریتم‌های متنوعی برای تحلیل شبکه‌ها ارائه می‌دهد.[۳]
igraph
igraph کتابخانه‌ای برای تحلیل گراف‌ها و شبکه‌هاست.
این ابزار در محیط‌های برنامه‌نویسی مختلف برای بررسی ویژگی‌های ساختاری شبکه‌ها استفاده می‌شود.
Gephi
Gephi نرم‌افزاری برای مصورسازی و تحلیل شبکه‌هاست.
این ابزار امکان نمایش گراف‌های بزرگ و بررسی برخی شاخص‌های شبکه را فراهم می‌کند.
Graphviz
Graphviz مجموعه‌ای از ابزارهای ترسیم گراف است که از توصیف متنی ساختار گراف برای تولید نمودار استفاده می‌کند.
این ابزار در مستندسازی نرم‌افزار و نمایش ساختارهای ارتباطی کاربرد دارد.
مزایای استفاده از گراف
یکی از مهم‌ترین مزایای گراف، توانایی مدل‌سازی روابط پیچیده میان موجودیت‌هاست.
گراف می‌تواند ساختارهایی را نمایش دهد که در مدل‌های خطی یا سلسله‌مراتبی به‌سادگی قابل بیان نیستند.
همچنین مجموعهٔ گسترده‌ای از الگوریتم‌ها برای بررسی مسیرها، همبندی، مرکزیت و الگوهای ارتباطی در دسترس است.
این ویژگی‌ها موجب شده‌اند گراف در علوم نظری و کاربردی جایگاه مهمی داشته باشد.
محدودیت‌های مدل‌سازی گرافی
گراف‌ها با وجود انعطاف‌پذیری، محدودیت‌هایی دارند.
در برخی مسائل، رابطهٔ میان موجودیت‌ها بسیار پیچیده‌تر از یک یال ساده است.
همچنین داده‌های واقعی ممکن است ناقص، متغیر یا دارای خطا باشند.
در شبکه‌های بزرگ، ذخیره‌سازی و پردازش گراف می‌تواند به منابع محاسباتی قابل توجهی نیاز داشته باشد.
ازاین‌رو، انتخاب مدل گرافی و روش تحلیل باید با توجه به هدف پژوهش انجام شود.
گراف و مسئلهٔ رابطهٔ علّی
وجود ارتباط میان دو رأس الزاماً نشان‌دهندهٔ رابطهٔ علت و معلولی نیست.
برای مثال، اگر دو شخص در یک شبکهٔ اجتماعی با یکدیگر ارتباط داشته باشند، نمی‌توان تنها از وجود این ارتباط نتیجه گرفت که یکی بر رفتار دیگری تأثیر علّی داشته است.
تحلیل علّی به شواهد و روش‌های پژوهشی مستقل نیاز دارد.
آیندهٔ گراف
با گسترش داده‌های شبکه‌ای، اهمیت گراف در علوم رایانه و تحلیل داده افزایش یافته است.
توسعهٔ پایگاه‌های دادهٔ گرافی، شبکه‌های عصبی گرافی و گراف‌های دانش از زمینه‌های مهم پژوهش و کاربرد هستند.
همچنین بررسی شبکه‌های پویا، گراف‌های بسیار بزرگ و روش‌های حفاظت از حریم خصوصی در تحلیل شبکه از موضوعات فعال این حوزه است.
بااین‌حال، اصول ریاضی مربوط به رأس، یال، مسیر، همبندی و ساختار گراف همچنان بنیان این تحولات را تشکیل می‌دهند.
جمع‌بندی
گراف یکی از ساختارهای بنیادی ریاضیات گسسته و علوم رایانه است که از رأس‌ها و یال‌های ارتباط‌دهندهٔ آنها تشکیل می‌شود.
نظریهٔ گراف با پژوهش لئونارد اویلر دربارهٔ مسئلهٔ پل‌های کونیگسبرگ در سدهٔ هجدهم پیوند تاریخی دارد و در سده‌های بعد به شاخه‌ای گسترده از ریاضیات تبدیل شده است.
گراف‌ها انواع مختلفی مانند گراف جهت‌دار، بدون جهت، وزن‌دار، ساده، چندگراف، کامل، دوبخشی و مسطح دارند.
در علوم رایانه، گراف‌ها با ساختارهایی مانند ماتریس مجاورت و فهرست مجاورت نمایش داده می‌شوند و الگوریتم‌هایی مانند BFS، DFS، دایکسترا، بلمن–فورد، پریم و کروسکال برای پردازش آنها به کار می‌روند.
کاربردهای گراف از شبکه‌های رایانه‌ای و حمل‌ونقل تا هوش مصنوعی، زیست‌شناسی، اقتصاد و تحلیل شبکه‌های اجتماعی گسترده است.
در مجموع، اهمیت گراف در توانایی آن برای تبدیل مجموعه‌ای پیچیده از روابط به ساختاری ریاضی است که بتوان ویژگی‌های آن را تعریف، اندازه‌گیری و تحلیل کرد.
جستارهای وابسته
- ریاضیات
- ریاضیات گسسته
- نظریه گراف
- ترکیبیات
- علوم رایانه
- ساختار داده
- الگوریتم
- طراحی الگوریتم
- درخت (ساختار داده)
- فلوچارت
- شبکه‌های رایانه‌ای
- پایگاه داده
- پایگاه دادهٔ گرافی
- علم داده
- تحلیل داده
- داده‌کاوی
- هوش مصنوعی
- یادگیری ماشین
- یادگیری عمیق
- شبکه عصبی مصنوعی
- پردازش زبان طبیعی
- نظریه شبکه
- شبکه‌های اجتماعی
- گراف دانش
- پایتون
- مدیاویکی
منابع
```