گراف چگال

گراف چگال گرافی است که شمار یال‌های آن به بیشینه شمار یال‌ها نزدیک باشد. در برابر گرافی چگال، گراف تنک گرافی است که یال‌های اندکی داشته باشد. شناسایی گرافی چگال از یک گراف تُنُک وابسته به زمینه و گنگ است. چگالی برای گراف باسو با برابری ${\displaystyle {\frac {2|E|}{|V|(|V|-1)}}}$ و برای گراف بی‌سو با${\displaystyle {\frac {|E|}{|V|(|V|-1)}}}$ تعریف می‌شود. در این برابری‌ها، ${\displaystyle |E|}$ شمار یال‌های گراف و ${\displaystyle |V|}$ شمار گره‌های گراف است. شمار بیشینه‌ی یال‌ها در گراف‌های باسو برابر است با ${\displaystyle |V|(|V|-1)}$ و در گراف‌های بی‌سو ${\displaystyle {\frac {1}{2}}|V|(|V|-1)}$ است. از این روی، بیشینه‌ی چگالی یک و کمینه‌ی آن صفر است.

گراف تنک

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

مقایسه گراف چگال و گراف تنک

گراف تنک

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

نمونه

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

گراف چگال

برای گراف چگال ${\displaystyle G=(V,E)}$ داریم: (E| = Θ(|V|۲|.

نمونه

گراف ${\displaystyle 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