از ویکیپدیا، دانشنامه آزاد

 

در نظریه گراف ، یک نمودار بسیار نامنظم است گراف که در آن، برای هر راس به همه راسهای همسایه از همان راس  درجه متمایز دارند  .

 

فهرست

تاریخچه [ ویرایش ]

نمودارهای نامنظم در ابتدا توسط یوسف علوی ، گری چارتراند ، فن چونگ ، پل اردوس ، رونالد گراهام و اورتود اولرمن مشخص می شدند . [1] انگیزه آنها این بود که "عکس" گراف منظم را تعریف کنند ، مفهومی که کاملاً مورد مطالعه و درک قرار گرفته است.

مکان و نظم [ ویرایش ]

تعریف "نمودار نامنظم" بلافاصله آشکار نبود. در یک نمودار- k منظم ، همه رئوس درجه  k دارند . در هر نمودار G با بیش از یک راس ، دو راس در G باید یک درجه داشته باشند ، بنابراین یک نمودار نامنظم را نمی توان به عنوان یک نمودار با تمام رئوس درجات مختلف تعریف کرد. ممکن است وسوسه شود که یک نمودار نامنظم را تعریف کنیم که دارای همه رئوس درجات مشخص است به جز دو ، اما این نوع نمودارها نیز به خوبی درک شده اند و بنابراین جالب نیستند. [2]

بنابراین نظریه پردازان گراف به مسئله نظم محلی روی آوردند. نمودار به صورت محلی در راس به طور منظم است V اگر همه رئوس مجاور به V دارای درجه R . نمودار نتیجه به صورت محلی نامنظم اگر برای هر رأس V از G همسایگان V درجه متمایز، و این نمودار به این ترتیب نمودار بسیار نامنظم نامیده می شوند. [1]

خصوصیات نمودارهای نامنظم [ ویرایش ]

برخی از حقایق در مورد نمودارهای بسیار نامنظم که توسط علوی و همکاران شرح داده شده است. : [3]

  • اگر v یک راس حداکثر درجه d در یک نمودار بسیار نامنظم H باشد ، پس v دقیقاً مجاور یک راس درجه 1 ، 2 ، ... ،  d است . [3]
  • بیشترین درجه در نمودار بسیار نامنظم حداکثر نیمی از راس است. [3]
  • اگر H یک نمودار بسیار نامنظم با حداکثر درجه d باشد ، می توان با گرفتن دو نسخه از H و افزودن لبه بین دو راس درجه  d یک نمودار بسیار نامنظم از درجه d + 1 ساخت . [3]
  • H ( n ) / G ( n ) به 0 می رود زیرا n به سرعت به بی نهایت می رود ، جایی که H ( n ) تعداد نمودارهای (غیر ایزومورف) بسیار نامنظم با n راس است و G ( n ) تعداد کل از نمودارها با n راس. [3]
  • برای هر نمودار G ، یک نمودار بسیار نامنظم H وجود دارد که حاوی G به عنوان یک زیرگراف القا شده است . [3]

این آخرین مشاهده را می توان با نتیجه Dénes Kőnig ، که می گوید اگر H یک نمودار با بیشترین درجه  r باشد ، در نظر گرفت ، یک نمودار G وجود دارد که r- منظم است و حاوی H به عنوان یک زیرگراف القا شده است. [3]

کاربردهای بی نظمی [ ویرایش ]

تعاریف بی نظمی در مطالعه ناهمگنی شبکه مهم بوده است ، که پیامدهایی را در شبکه های زیست شناسی ، زیست محیطی ، فناوری و اقتصاد دارد. [4] چندین گراف وجود دارد که پیشنهاد شده است ، که بسیاری از آنها براساس تعداد رئوس یک نمودار و درجه آنها است. خصوصیات گراف های بسیار نامنظم نیز در مورد مسئله ناهمگنی به کار رفته است ، اما همه اینها نتوانند به اندازه کافی شرایط دنیای واقعی را روشن کنند. تلاشها برای یافتن راههای مناسب برای تعیین کمیت ناهمگنی شبکه ادامه دارد. [4]

منبع 

https://en.wikipedia.org/wiki/Highly_irregular_graph