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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

 

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

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

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

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

t.me/bigdata_channel
برای ورود به کانال بر روی اینجا کلیک کنید.

منبع:

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

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

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