گراف متراکم

گراف متراکم گرافی است که تعداد یال‌های آن به بیشینه تعداد یال ممکن نزدیک باشد و در مقابل گرافی که تعداد یال‌های آن به نسبت کم باشد، گراف پراکنده (کم پشت) نامیده می‌شود.
توجه:
تمایز محکمی میان گراف متراکم و گراف پراکنده وجود ندارد. یک امکان برای تشخیص، انتخاب عددی مثلا k است که $\{1\le k<2\}$ و تعریف گرافی پراکنده با $|E| = O(|V|k)$. در اینجا V تعداد رأس‌ها و E تعداد یال‌ها می‌باشد.
گراف جهت دار حداکثر (n(n-۱ یال دارد، که در آن n تعداد رأس هاست. گراف غیرجهت‌دار دارای حداکثر ۲/(n(n-۱ یال است.
برای گراف‌های غیرجهت‌دار ساده، تراکم گراف بدین گونه تعریف می شود:
$D = 2|E|/(|V|(|V|- 1)$
بیشترین تراکم برابر با ۱ (برای گراف کامل)، و کمترین برابر با صفر است.

گراف پراکنده

گرافی را (k,l)-پراکنده تعریف می کنیم اگر هر زیرگراف ناتهی آن با n رأس حداکثر kn – l یال داشته باشد. بنابراین جنگل، گراف (1,1)-پراکنده و شبه جنگل گراف (1,0)-پراکنده می باشد.
بقیهٔ گراف‌ها که براساس تراکم دسته بندی نشده‌اند از این روش قابل توصیف هستند. برای مثال این حقیقت که هر گراف مسطح با n رأس، حداکثر ۳n – ۶ یال دارد، و اینکه هر زیر گراف گراف مسطح، خود مسطح است، نشان می دهد که گراف‌های مسطح از نوع گراف (۳,۶)-پراکنده هستند. همچنین، گراف دوبخشی مسطح از نوع گراف (۲,۴)-پراکنده است.

مقایسه گراف متراکم و گراف پراکنده

گراف پراکنده

گراف پراکنده: گرافی است $G = (V,E)$ که در آن $(|E| = O(|V|)$.

مثال

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

گراف متراکم

برای گراف متراکم $G = (V,E)$ داریم: (E| = Θ(|V|۲|.

مثال

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

تراکم بالا

تراکم بالا، گسترش مفهوم تراکم گراف (که در بالا توضیح داده شد) از گراف‌های متناهی به گراف‌های نامتناهی است. گراف نامتناهی به طور قرار دادی، دارای تعداد زیادی زیر گراف است که تراکم آنها کمتر از تراکم بالا می‌باشد و شامل زیرگرافی نیست که دارای تراکمی بیش از تراکم بالا باشد. با توجه به نظریه اردوس-استون تراکم بالا می تواند تنها ۱ یا یکی از مقادیر کسری ۰، ۱/۲، ۲/۳، ۳/۴، ۴/۵، ...، (n/(n+1، ....

منابع

۱-صفحه انگیسی ویکی‌پدیا .
۲-Paul E. Black, "dense graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008.
۳-Bruno R. Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, Waterloo, Canada, November 11-12, 1999