پاورپوینت ساختمان داده ها (گرافها)

پلهای کوینسبرگ
Konigsberg = Graph Problem
مساله ی پلهای کویسنبرگ یک گراف است.
گراف  G شامل دو مجموعه ی V و E است.
V یک مجموعه ی محدود و غیرپوچ از راسها است.
E یک مجموعه از جفت-راس ها است که به هر جفت یک یال می گوییم.
مثال:
تعاریف گراف:
گراف بدون جهت: جفت راس ها که نماینده ی یالها هستند نامرتب هستند.
(u,v) و  (v,u)یکی هستند.
گراف جهتدار: هر یال توسط یک زوج مرتب نمایش داده می شود.
(u,v) و  (v,u)یکی نیستند.
جهتدار و بدون جهت
محدودیتهای گراف
فرض کنید که یالها و راسها مجموعه هستند.
دو راس یال یکسان نیستند.
یال تکراری نداریم.
تعاریف گراف
حداکثر تعداد یالهای غیر تکراری در گراف بدون جهت با n نود برابر است با:  n*(n-1) / 2
به این گراف کامل گفته می شود.
تعاریف گراف
اگر (u, v) یکی از یالهای E(G) باشد:
راسهایu و v مجاور هستند.
یال (u,v) با راسهای u  و  v تلاقی دارد.
مثال:
تعاریف گراف
زیرگراف G’ از گراف G یک گراف است که V(G ’) زیر مجموعه ی V(G) و E(G’)  زیر مجموعه ی E(G) است.
مسیر
از راس u به راس v در گراف G  دنباله ای از راسها مثل u, i1, i2, …, ik, v
است که یالهای (u,i1), (i1,i2)…(ik,v)  در گراف G هستند.
در گراف جهتدار، جهت تمام یالها باید یکسان و درست باشد.
طول مسیر برابر تعداد یالها است.
مسیر ساده مسیری است که تمام راسها به جز اولی و آخری متفاوت هستند.
تعاریف گراف
تعاریف گراف
دور مسیری است که ابتدا و انتهای آن یکی هستند.
تعاریف گراف
اگر مسیری بین راسهای u و v در گراف G برقرار باشد می گوییم این دو گره متصل هستند.
می گوییم گراف بدون جهت G یکپارچه است اگر و فقط اگر برای هر زوج u و v متعلق به گراف یک مسیر از u به v موجود باشد.
یک جزء یکپارچه ی گراف یک زیرگراف یکپارچه ی حداکثر است. هر گراف می تواند یک یا چند جزء یکپارچه داشته باشد.

دانلود فایل”پاورپوینت ساختمان داده ها (گرافها)”