صفحه نخست --> تحلیل شبکه های اجتماعی --> تئوری گراف به صورت خلاصه

تئوری گراف به صورت خلاصه

  • تئوری گراف به صورت خلاصه:

در این مبحث به شرح تعاریف اولیه از نظریه گراف (Graph Theory) پرداخته می‌شود. مطالب این بخش برگرفته از کتاب تئوری گراف نوشته گروس (Gross) می‌باشد. گراف هر شیء ریاضی شامل یک سری نقاط و اتصالات میان آن‌ها، گراف نامیده می‌شود. گراف‌ها در طیف وسیعی از مسائل کاربرد دارند. یک گراف می‌تواند نماینده یک شبکه فیزیکی مثل مدار الکتریکی، شبکه ریلی و یا مدلی از مولکول‌های عضوی (Organic Molecules) از بدن باشد. یک اکوسیستم، روابط اجتماعی (Sociological Relationships) ، پایگاه‌داده و شبکه‌های اجتماعی را نیز با گراف‌ها نشان می‌دهند. برای یک گراف تعاریف زیر وجود دارد:

  •  اگر تمامی اتصالات در یک گراف بدون جهت باشد، به آن گراف بدون جهت (graph) گفته می‌شود.
  •  یک گراف را (G=(V,E با  نشان می‌دهند. عناصر مجموعه V رأس‌ یا گره یا vertex نام دارد. عناصر مجموعه  یال E نامیده می‌شود.
  •  هر یال شامل مجموعه‌ای از یک یا دو رأس است که نقاط انتهایی (Endpoints) آن نامیده می‌شوند.
  •  اگر رأس v نقطه انتهایی یال e باشد، آنگاه v برخورد (Incident) یال e می‌باشد.
  •  دو رأس مجاور (Adjacent) همسایه یا مجاور نامیده می‌شوند.
  • گره منزوی یا Isolated Node گره ای هست که با هیچ گره دیگری مجاور نباشد.
  •  دو یالی که دارای نقطه انتهایی مشترک می‌باشند، همسایه یکدیگر خوانده می‌شوند.
  •  یالی که دارای نقاط انتهایی یکسانی است را حلقه (Self-loop) می‌نامند.

 

تئوری گراف
تئوری گراف

 

گراف ساده: اکثر تئوری‌های نظریه گراف برای گراف ساده (Simple Graph) بیان شده است. علت این موضوع این است که خیلی از مسائل گراف‌های عمومی را می‌توان به یک گراف ساده کاهش داد. بنابراین تعاریف زیر را داریم:

  • گراف ساده، گرافی است که دارای حلقه نبوده و مابین تمامی رأس‌های آن حداکثر یک یال وجود داشته باشد.
  • گراف بی‌اهمیت (Trivial Graph): گرافی است که تنها از یک رأس و هیچ یالی تشکیل شده است.
  • گراف پوچ(Null Graph): گرافی است که هیچ یال و گره‌ای نداشته باشد.

گراف کامل : گرافی که بین تمام راس ها دقیقا یک یال وجود داشته باشد.

تئوری گراف
گراف کامل

Cycle: گرافی که هر راس به همسایه قبلی و بعدی متصل است.(شبیه linkedlist)

Wheel: گرافی که به cycle یک راس اضافه میکند و آن راس را به تمام رئوس دیگر متصل میکند .

 

گراف چندگانه: اگر میان دو گره بیش از یک یال وجود داشته باشد، به این یال‌ها، یال‌های چندگانه گفته می‌شود. اگر یک گراف دارای یال‌های چندگانه باشد، به آن گراف چندگانه می‌گویند.

گراف جهت‌دار: گراف‌هایی که در آن‌ها تمامی یال‌ها دارای جهت می‌باشند را گراف جهت‌دار(Digraph) می‌نامند. برای گراف جهت‌دار تعاریف در ادامه وجود دارد:

  • یال جهت‌دار یا پیکان(Arc)، یالی است که یکی از نقاط انتهایی آن دم (Tail) و انتهای دیگر سر نامیده می‌شود.
  • گراف ساده جهت‌دار گرافی است که هیچ یال حلقه‌ای نداشته و مابین تمامی رأس‌های آن حداکثر یک یال جهت‌دار وجود داشته باشد.

گراف مخلوط Mixed Graph: گرافی است که در آن برخی لبه ها جهت دار و برخی بدون جهت است.

گراف دوبخشی: اگر بتوان تمامی گره‌های موجود در گراف را به دو دسته تقسیم‌بندی نمود، به طوری که یک نقطه پایانی یال‌ها در یک دسته و نقطه پایانی دیگر در دسته دیگر قرار گیرد، به آن گراف دو بخشی (Bipartite Graph) گفته می‌شود.

 

گراف دوبخشی
گراف دوبخشی
گراف دوبخشی
گراف دوبخشی

روش تشخیص گراف دوبخشی

برای تست این شرط و افراز به دو مجموعه، میتوانیم از هر دو الگوریتم جست‌و‌جوی عمق‌اول و جست‌و‌جوی سطح‌اول استفاده کنیم. کافیست نحوه علامت گذاری مزاعفی در این دو الگوریتم را به گونه ای اضافه کنیم که از رأس‌های با رنگ ۰ به رأس‌های با رنگ ۱ برویم و برعکس. حال اگر به رأسی با علامت ۱ رسیدیم که همسایه‌ای از آن از قبل رنگ ۱ را داشت، پس در نتیجه دور فرد پیدا شده است و نمیتوان این کار را کرد؛ برای علامت ۰ نیز به همین ترتیب است. حال اگر هیچ یک از این دو حالت اتفاق نیافتد، در نتیجه میتوان این کار را کرد و رأس‌هایی که علامت ۱ را دارند در یک دسته و بقیه را در دسته مقابل قرار می‌دهیم.
دقت کنید که ممکن است گراف نا‌همبند باشد در نتیجه برای تمام رأس‌های دیده نشده این الگوریتم را تکرار میکنیم.

پیچیدگی‌ الگوریتم

از آنجا که از الگوریتم های پیمایش استفاده میکنیم، مرتبه زمانی برابر مرتبه زمانی جست‌و‌جو ها است که برابر (O(n+e است. n تعداد رأس‌ها و e تعداد یال‌ها است.

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

  • دنباله درجه یک گراف، شامل دنباله درجه‌های گراف به صورت صعودی می‌باشد.
  • درجه داخلی (Indegree) یک گره در گراف جهت‌دار عبارت است از تعداد پیکان‌هایی که به سمت آن گره اشاره می‌کنند.
  • درجه خارجی (Outdegree) یک گره عبارت است از تعداد پیکان‌هایی که از آن گره خارج می‌شوند. یال‌های از نوع طوقه شامل یک درجه داخلی و یک درجه خارجی می‌باشند.
  • رأس منزوی (Isolated) رأسی است که دارای درجه صفر باشد.

 

گام: گام  w در گراف G دنباله‌ای از یال‌ها و گره‌ها می‌باشد.

  • در یک گام اگر یال‌ها دارای جهت باشند، به آن گام جهت‌دار می‌گویند.
  • طول یک گام برابر با تعداد یال‌های آن است (یال‌های تکراری نیز شمارش می‌شوند)
  • اگر در یک گام، گره‌ی آغازی و پایانی یکی باشند، به آن گام بسته (Closed Walk) گفته می‌شود.

دنباله: یک دنباله (Trail) در گراف، گامی است که هیچ یالی بیشتر از یک بار در آن مشاهده نشود.

  • اگر در یک دنباله، تمامی یال‌های یک گراف برای یک بار پیمایش شود، به آن دنباله اویلری (Eulerian Trail) می‌گویند.
دنباله اویلری (Eulerian Trail)
دنباله اویلری (Eulerian Trail)

 

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

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

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

گراف همبند یا connected و گراف ناهمبند: گرافی که بین دو راس آن حداقل یک مسیر وجود داشته باشد.

مولفه: گرافی که ناهمبند است هر قسمت از گراف یک مولفه است.

گراف ترانهاده یا Gt: گراف جهت داری است که جهت یال های آن برعکس شده باشد. یکی از استفاده های گراف ترانهاده در پیدا کردن مولفه های متصل قوی است.

یک مسیر در یک گراف
یک مسیر در یک گراف

فاصله و اتصال: فاصله میان دو گره در یک گراف، طول کوتاه‌ترین گام Geodestic میان آن دو است.

  • در گراف جهت‌دار، فاصله میان دو گره برابر با طول کوتاه‌ترین گام جهت‌دار میان آن‌هاست.
  • گراف را متصل یا همبند (Connected) می‌نامند، اگر میان هر دو گره‌ای یک گام وجود داشته باشد.
  • گراف جهت‌دار را به طور ضعیف همبند (Weakly Connected) است، اگر گراف بدون جهت متناظر با آن متصل باشد.
  • گراف جهت‌دار قویاً همبند (Srtongly Connected) می‌باشد اگر میان هر دو گره‌ای در آن، حداقل یک گام جهت‌دار وجود داشته باشد.
  • گریز از مرکز (Eccentricity) یک گره در گراف همبند برابر با فاصله دورترین گره نسبت به آن در گراف می‌باشد.
  • شعاع (Radius) یک گراف همبند برابر با طول کمترین مقدار گریز از مرکز آن است.
  • قطر (Diameter) یک گراف همبند، برابر با بزرگ‌ترین مقدار گریز از مرکز آن است.

روش محاسبه قطر گراف

توجه کنید که قطر همیشه برابر طولانی‌ترین مسیر نیست، برای مثال در گراف متشکل از یک دور، طولانی‌ترین مسیر برابر n۱ است، ولی قطر n/است.

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

همریختی ایزومورفیک: دو گراف هم‌ریخت (Isomorphism) یکدیگر می‌باشند اگر از لحاظ ساختاری (Structrual) شبیه به هم باشند؛ به طوری که تناظر یک به یک میان یال‌ها و گره‌های آن دو بر قرار باشد.

زیر‌گراف: زیرگراف (Subgraph) گراف G را H می‌نامند.

  • گراف همریخت گراف G  را می‌توان یک زیرگراف آن در نظر گرفت.
  • موءلفه (Component) گراف، بزرگ‌ترین زیرگراف متصل آن می‌باشد.

انواع نمایش گراف

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

  1. ماتریس مجاورت
  2. ماتریس برخورد

ماتریس مجاورت

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

  • دو گراف همریخت دارای ماتریس مجاورت یکسانی هستند.

برای بهتر متوجه شدن این ماتریس، سطر و ستون های ماتریس مجاورت هر دو شامل نام راس های ما هستند.به صورت زیر:

 

ماتریس مجاورتی
ماتریس مجاورتی

 

 

ماتریس برخورد

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

ماتریس برخورد
ماتریس برخورد

 

پیمایش گراف

پیمایش گراف (Graph traversal) در حالت کلی به معنی گذشتن و دیدن تمام راس‌های گراف است و معمولا پیمایش از طریق یال‌های موجود در گراف انجام می‌شود. معمولا پیمایش گراف به تنهایی ارزش خاصی ندارد و هدف از پیمایش، محاسبه یا پیدا کردن چیز دیگری است. برای مثال شاید با نگاه کردن به یک گراف بتوانید خواص آن را پیدا کنید و مسئله را حل کنید؛ اما در کامپیوتر به دلیل محدودیت‌هابه همین راحتی نمی‌توان این کار را کرد. الگوریتم‌های پیمایش در حرکت روی گراف و پیدا کردن خواص آن به ما کمک می‌کنند.

اول سطح

اول سطح
اول سطح

اول عمق

اول عمق
اول عمق

 

رنگ آمیزی یا علامت گذاری

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

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

معمولا در بدنه‌ی الگوریتم‌ها از این مطلب به اسم رأس دیده شده (visited) یا علامت زده شده (marked) یاد می‌شود و لیست یا آرایه‌ای برای نگه‌داری علامت‌ها اختصاص می‌دهند.

گراف دوبخشی و چند بخشی
Bipartite and k-partite graphs

کاربردهای الگوریتم جستجوی اول عمق

الگوریتم DFS و روش پیمایش آن کاربردهای فراوانی دارد که در ادامه به چند مورد مهم اشاره می‌شود.

۱تشخیص وجود مسیر: با استفاده از الگوریتم dfs می‌توان وجود مسیر از گره مبدأ به گره دیگر را بررسی کرد.

نکته: اگر گراف همبند و بدون جهت باشد همواره مسیر بین هر دو گره دلخواه وجود دارد و نیاز به استفاده از این الگوریتم نیست. تذکر: در الگوریتم BFS اگر گراف بدون وزن باشد، مسیر مشخص شده توسط الگوریتم به طور حتم کوتاهترین مسیر از گره مبدأ به مقصد است؛ اما در مورد الگوریتم DFS این خاصیت لزوما برقرار نیست.

۲تولید درخت پوشا: درخت پوشا یعنی همه نود های گراف روئیت شوند. خروجی الگوریتم DFS روی یک گراف بدون جهت و همبند یک درخت پوشا است. در مورد گراف‌های جهت‌دار ممکن است متناسب با گره مبدأ چنین درختی ساخته شود یا نشود.

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

نکته: اگر در یک گراف بدون جهت بیش از|V|۱ یال وجود داشته باشد، گراف به طور حتم دور دارد (چرا؟).

۴ تشخیص دو بخشی بودن گراف: یک گراف دوبخشی است اگر و فقط اگر بتوان گره‌های آن را با استفاده از دو رنگ به نحوی نشانه‌گذاری کرد که هیچ دو گره مجاوری همرنگ نباشند. برای تشخیص دوبخشی بودن گراف با استفاده از الگوریتم DFS، هر گره در پیمایش با رنگ مخالف گره پیشین نشانه‌گذاری شده و بررسی می‌گردد که آیا از گره‌های پیمایش‌شده‌ی مجاورش گرهی با همین رنگ نشانه‌گذاری شده است یا نه. اگر چنین گرهی یافت شود به معنی عدم امکان رنگ شدن گراف با دو رنگ و در نتیجه دو بخشی نبودن گراف است. یافت نشدن چنین گرهی در هر مرحله تا انتهای اجرای الگوریتم به معنی دو بخشی بودن آن است که این دو بخش توسط رنگ‌ها متمایز شده‌اند.

۵حل مارپیج‌های تک‌مسیر: الگوریتم BFS راهکاری است که در یافتن کوتاهترین مسیر در مسیرهای مارپیچ (Maze) کاربرد دارد. اگر مسیر رسیدن به هر نقطه از مارپیچ یکی باشد (دوری در مارپیچ نباشد یا گراف معادل مارپیچ یک درخت باشد) می‌توان از الگوریتم DFS نیز استفاده کرد. چرا که در چنین حالتی تنها یک مسیر به مقصد وجود داشته و کوتاه بودن آن مطرح نیست.

۶- تشخیص اینکه گراف هم بند است یا خیر: و اگر نا همبند است، چند مولفه دارد. اگر همه رئوس گراف با یک فراخوانی تابع DFS-VISIT ملاقات شوند همبند است و در غیر این صورت به تعداد فراخوانی های این تابع مولفه دارد.

۷- یافتن ترتیب توپولوژیک: یعنی هر راسی که ملاقات میشود یا درجه ورودی اش صفر باشد یا اگر صفر نیست رئوس وارد شده قبلا ملاقات شده باشند. فقط گراف بدون سیکل جهت دار یا dag دارای ترتیب توپولوزیک است.

۸- یافتن مولفه های متصل قوی در گراف جهت دار

۹- یافتن نقاط انفصال یا راس برشی در پراف غیر جهت دار:

۱۰- یافتن پل: پل یالی است که اگر حذ شود تعداد مولفه های گراف بیشتر می شوند. در واقع پل یالی است که عضو هیچ سیکلی نباشد که به کمک کمک پیمایش اول عمق میتوان پلها را پیدا کرد.

 

مرتبه زمانی یک الگوریتم

برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشود. این نمادها عباتند از: O ، Ω، Θ و o، ω که هر کدام طبق روش خاصی محاسبه میشوند و در تحلیل الگوریتم کاربرد فراوانی دارند.

رشد توابع

گوییم رشد تابع f(n) از تابع g(n) بیشتر است اگر n به بینهایت میل کند (n \to \infty) آنگاه f(n) زودتر به ∞ میل میکند. ترتیب رشد زیر برای توابع نام برده قابل اثبات است:

Asymptotic Notation
Asymptotic Notation

۱ یعنی بدون رشد، یعنی به n وابسته نیست. مثلا حلقه ای که ۱۰۰۰ بار اجرا میشود رشدش ۱ است.

  • اگر جواب برابر ∞ باشد، رشد f از g بیشتر است.
  • اگر برابر k ۰  باشد، f و g رشد یکسان دارند.

وقتی اندازه ورودی (n) بزرگ باشد، بیان دقیق زمان اجرا برحسب n ضروری نیست زیرا جمله با بزرگترین درجه در زمان موثر است. مثلا اگر زمان اجرای الگوریتمی 2n^3 + n^2 + n باشدف به ازای nهای بزرگ فقط n^3 مهم است. میتوان با نمادهای مجانبی این تفسیر را بهتر نشان داد. در بیان نمادها فرض میشود که دامنه اعداد طبیعی N={0, 1, 2, …} است.

نماد O بزرگ

در نظریهٔ پیچیدگی محاسباتی، نماد O بزرگ (به انگلیسی: Big O notation) برای نشان دادن رابطه میان تعداد داده‌ها و منابع محاسباتی مورد نیاز برای حل یک مسأله با استفاده از یک الگوریتم استفاده می‌شود. استفاده از این نماد معمولاً برای بررسی زمان و یا حافظه مورد نیاز برای حل مسأله‌ای با تعداد زیادی ورودی می‌باشد.

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

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

این به طراحان الگوریتم اجازه می‌دهد که رفتار الگوریتم‌هایشان را پیش‌بینی کنند و تصمیم بگیرند که کدام الگوریتم را استفاده کنند (بدون توجه به معماری رایانه یا میزان آهنگ ساعت آن).

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

بنابراین O یک کران بالا برای تابع مشخص میکند. ما مینویسیم f(n) = O(g(n)) اگر f(n) عضوی از O(g(n)) باشد.

نکته : وقتی گفته می­شود زمان اجرای الگوریتم O(n^2)است یعنی الگوریتم هر جوری اجرا شود، مرتبه­ ی زمانی اجرای آن یا n2 است و یا از n2 کمتر است.

فواید

علامت O بزرگ دو دامنه کاربرد دارد:

  • در ریاضیات معمولاً برای نشان دادن این که یک سری هندسی متناهی تا چه اندازه به تابع مورد نظر نزدیک است، خصوصاً در مورد سری تیلور ناقص از این علامت استفاده می‌شود.
  • در علوم کامپیوتر این علامت در تحلیل الگوریتم‌ها کاربرد دارد.

در هر دو کاربرد تابع g(x) که در O(...) به گونه‌ای انتخاب می‌شود که تا حد امکان ساده باشد.

نماد امگا Ω

نماد Ω یک کران پایین حدی برای تابع مشخص میکند

نماد تتا Θ

تتا(جی(ان)) برابر است با اف(ان) به طوری که وجود دارد سی۱، سی۲ و ان۰ی بزرگتر از ۰ که به ازای هر ان بزرگتر مساوی ‘ان۰’ داریم: ۰ کوچکتر مساوی سی۱ جی(ان) کوچکتر مساوی اف(ان) کوچکتر مساوی سی۲ جی(ان)

 

منبع:

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

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

http://opedia.ir

http://notif.ir/asymptotic-notations-in-algorithm-design-2386.html.

کارگاه شبکه های اجتماعی تئوری گراف

آدرس کانال تلگرام سایت بیگ دیتا:

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

جهت دیدن سرفصل های دوره های آموزشی بر روی اینجا کلیک کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *