گراف چگال
گراف چگال گرافی است که شمار یالهای آن به بیشینه شمار یالها نزدیک باشد. در برابر گرافی چگال، گراف تنک گرافی است که یالهای اندکی داشته باشد.
شناسایی گرافی چگال از یک گراف تُنُک وابسته به زمینه و گنگ است. چگالی برای گراف باسو با برابری
گراف تنک
گرافی را (k,l)-تنک تعریف می کنیم اگر هر زیرگراف ناتهی آن با n گره حداکثر kn – l یال داشته باشد. بنابراین جنگل، گراف (1,1)-تنک و شبه جنگل گراف (1,0)-تنک می باشد.
بقیهٔ گرافها که بر پایهی چگالی دسته بندی نشدهاند از این روش قابل توصیف هستند. برای نمونه این حقیقت که هر گراف مسطح با n گره، حداکثر ۳n – ۶ یال دارد، و اینکه هر زیر گراف گراف مسطح، خود مسطح است، نشان می دهد که گرافهای مسطح از نوع گراف (۳,۶)-تنک هستند. همچنین، گراف دوبخشی مسطح از نوع گراف (۲,۴)-تنک است.
مقایسه گراف چگال و گراف تنک
گراف تنک
گراف تنک: گرافی است
نمونه
گراف
گراف چگال
برای گراف چگال
نمونه
گراف
چگالی بالا
چگالی بالا، گسترش مفهوم چگالی گراف (که در بالا توضیح داده شد) از گرافهای متناهی به گرافهای نامتناهی است. گراف نامتناهی به طور قرار دادی، دارای شمار زیادی زیر گراف است که چگالی آنها کمتر از چگالی بالا میباشد و شامل زیرگرافی نیست که دارای چگالیی بیش از چگالی بالا باشد. با توجه به نظریه اردوس-استون چگالی بالا میتواند تنها ۱ یا یکی از اندازههای کسری ۰، ۱/۲، ۲/۳، ۳/۴، ۴/۵، ...، (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