مقایسه گراف اسپارس و چگال

در ریاضیات، یک گراف چگال گرافی است که تعداد یال‌های آن نزدیک به بیشینه تعداد یال‌ها باشد. درمقابل یک گراف با کمینه تعداد یال‌ها یک گراف اسپارس است. تمایز بین گراف اسپارس و چگال مبهم است و بستگی به محتوای آن‌ها دارد. برای گراف بدون جهت ساده، گراف چگال به صورت روبرو تعریف می‌شود: $D={\frac {2|E|}{|V|\,(|V|-1)}}$ بیشینه تعداد یال ها${\frac {|V|(|V|-1)}{2}}$است بنابراین چگالی ماکسیمال آن ۱ می‌باشد . اما برای گراف جهتدار چگالی به صورت زیر تعریف می‌شود:

$D={\frac {|E|}{|V|\,(|V|-1)}}$

تعریف

اگر گراف $G=(V,E)$ را در نظر بگیریم:

در گراف اسپارس $|E|=O(|V|)$.
و در گراف چگال $|E|$ = Θ$(|V|^{2})$.

گراف $G=(V,E)$، با n راس را در نظر بگیرید. فرض کنید درجهٔ خروجی هر رأس در گراف G، مقدار ثابت K باشد. می گوییم گراف G اسپارس است زیرا $|E|=k|V|=O(|V|)$.

اگر فرض کنیم که درجهٔ خروجی هر رأس در گراف G، مقدار اعشاری f بین ۰ و ۱ باشد. مثلا اگر n = ۱۶ و f = ۰٫۲۵، درجهٔ خروجی هر رأس ۴است.آن گاه گراف G چگال است زیرا $|E|=f|V|^{2}$ = Θ$(|V|^{2})$.

انواع گراف های اسپارس و چگال

شکل ۱

شکل ۱: یک گراف خطی که هر راس دارای دو لبهٔ متقاطع است.

شکل ۲

شکل ۲:یک گراف شبکه در آن هر راس دارای چهار لبهٔ متقاطع است.

شکل ۳

شکل ۳:یک گراف تصادفی اسپارس

شناسایی گراف ها

طبق تعریف استرینو و تران [۲۰۰۸]:

• یک گراف (k,I) – اسپارس است اگر تمام زیرگراف‌های غیرتهی با n راس آن دارای حداکثر kn-I یال باشند.
• یک گراف (k,I)- متراکم است اگر (k,I)- اسپارس باشد و دقیقا kn-I یال داشته باشد.

مثال

نوع گراف	معادل
درخت	(۱و۱)- چگال
جنگل	(۱و۱)- اسپارس
شبه جنگل	(۰و۱)- اسپارس
لامان	(۳و۲)- چگال

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

به عنوان مثال هر گراف مسطح با n راس دارای حداکثر ۳n-۶ یال است. هر زیرگراف گراف مسطح، مسطح است. بنابراین گراف‌های مسطح (۶و۳)- اسپارس هستند اما هر گراف (۶و۳)- اسپارس، لزوما مسطح نیست. به‌طور مشابه گراف‌های مسطح بیرونی (۳و۲)- اسپارس و گراف‌های مسطح دوبخشی (۴و۲)-اسپارس هستند. استرینو و تران نشان داد که امتحان کردن پراکندگی (K,I)ممکن است در زمان چندجمله ای اجرا شود.

فراچگالی

فراچگالی گسترش یافتهٔ مفهوم چگالی گراف بر روی گراف‌های متناهی تا گراف‌های نامتناهی می‌باشد . به‌طور مستقیم، یک گراف متناهی ذاتا دارای زیرگراف‌های محدود بزرگ با چگالی کم تر از فراچگالی خود هستند، و ذاتا فاقد زیرگراف‌های محدود بزرگتر از فراچگالی خود می‌باشند. به عبارت دیگر، فراچگالی گراف G، بزرگترین کرانه پایین (Infimum) مقادیر a ای است که زیرگراف‌های متناهی G با چگالی a دارای تعداد رئوس متناهی باشند. با استفاده از قضیهٔ اردوس-استون می‌توان نشان داد که فراچگالی می‌تواند تنها ۱و یا یکی از نسبت‌های ویژه ی۰، ۱/۲، ۲/۳، ۳/۴، ۴/۵، ...، (n/(n+1، .... باشد.

الگوریتم ها

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

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

در شکل زیر با استفاده از ماتریس مجاورت نیاز به فضای V| ² | است درحالی با لیست مجاورت فضای مورد نیاز E| ² | می‌شود.

شکل ۴

به عنوان مثال در الگوریتم پریم با استفاده از داده ساختار هیپ دودوئی ساده و لیست مجاورت می‌توان زمان اجرا را به (O(E log V رساند.

اطلاعات ساختاری این گراف‌ها در الگوریتم‌های موازی کاربرد دارد.

منابع

• en:Dense graph Dense Graph

• http://www.brpreiss.com/books/opus4/html/page534.html

• http://www.brpreiss.com/books/opus4/html/page534.html