گراف چگال

گراف چگال گرافی است که شمار یال های آن به بیشینه شمار یال ها نزدیک باشد. در برابر گرافی چگال، گراف تنک گرافی است که یال های اندکی داشته باشد.شناسایی گرافی چگال از یک گراف تُنُک وابسته به زمینه و گنگ است. چگالی برای گراف باسو با برابری 2 | E | | V | ( | V | − 1 ) {\displaystyle {\frac {2|E|}{|V|(|V|-1)}}} و برای گراف بی سو با | E | | V | ( | V | − 1 ) {\displaystyle {\frac {|E|}{|V|(|V|-1)}}} تعریف می شود. در این برابری ها، | E | {\displaystyle |E|} شمار یال های گراف و | V | {\displaystyle |V|} شمار گره های گراف است. شمار بیشینه ی یال ها در گراف های باسو برابر است با | V | ( | V | − 1 ) {\displaystyle |V|(|V|-1)} و در گراف های بی سو 1 2 | V | ( | V | − 1 ) {\displaystyle {\frac {1}{2}}|V|(|V|-1)} است. از این روی، بیشینه ی چگالی یک و کمینه ی آن صفر است.
گرافی را (k,l)-تنک تعریف می کنیم اگر هر زیرگراف ناتهی آن با n گره حداکثر kn – l یال داشته باشد. بنابراین جنگل، گراف (1,1)-تنک و شبه جنگل گراف (1,0)-تنک می باشد.بقیهٔ گراف ها که بر پایه ی چگالی دسته بندی نشده اند از این روش قابل توصیف هستند. برای نمونه این حقیقت که هر گراف مسطح با n گره، حداکثر ۳n – ۶ یال دارد، و اینکه هر زیر گراف گراف مسطح، خود مسطح است، نشان می دهد که گراف های مسطح از نوع گراف (۳,۶)-تنک هستند. همچنین، گراف دوبخشی مسطح از نوع گراف (۲,۴)-تنک است.
گراف تنک: گرافی است G = ( V , E ) {\displaystyle G=(V,E)}   که در آن ( | E | = O ( | V | ) {\displaystyle (|E|=O(|V|)}  .
گراف G = ( V , E ) {\displaystyle G=(V,E)}  ، با n گره را در نظر بگیرید. فرض کنید درجهٔ خروجی هر گره در گراف G، مقدار ثابت K باشد. می گوییم گراف G تنک است زیرا ( | E | = k | V | = O ( | V | ) {\displaystyle (|E|=k|V|=O(|V|)}  .