پیش‌نویس:گراف رادو

گراف رادو که توسط آکرمن(1937) و رادو(1964) شماره گذاری شده است.

در حوزه نظریه گراف، گراف رادو یا گراف Erdős–Rényi یا گراف تصادفی یک گراف با ابعاد نامحدود است و به این صورت ایجاد می‌شود که برای هر زوج از رئوس، به صورت مستقل از بقیه، تصمیم بگیریم که آیا یالی بین آن دو قرار دهیم یا خیر. این گراف به افتخار ریچارد رادو، پاول اردوش، و آلفرد رنی نامگذاری شده است، البته قبل از آنها هم کسانی در اوایل دهه ۱۹۶۰ این گراف را مورد مطالعه قرار دادند، و حتی در آثار ویلیام آکرمن نیز به آن اشاره شده است. چندین روش برای ساخت گراف رادو وجود دارد از جمله روش های غیر تصادفی که در آنها از طریق هم‌تراز کردن رابطه‌ی عضویت مجموعه‌های محدود به وراثت، با استفاده از گزاره BIT برای نمایش دودویی اعداد طبیعی، یا به عنوان یک گراف نامحدود پالی که گرافی هست به هر راس آن یک عدد اول به فرم 4k+1 نسبت می‌دهیم و یال‌های آن جفت اعداد اول به فرم 4k+1 را طبق قوانین تقابل مربعی به یکدیگر وصل می‌کنند.

هر گراف که تعداد راس‌های آن شمارا یا منتاهی باشد را میتوان به چشم یک زیرگراف القایی از گراف رادو دید، و میتوان آن را با الگوریتم حریصانه پیدا کرد. کلیات روش کار الگوریتم اینگونه است که راس‌های متناظر با گراف اول را یکی یکی در گراف رادو پیدا می‌کند و آنها را اضافه می‌کند. گراف رادو درمیان گراف‌های شمارا که "ویژگی گسترش" را دارد به طور یکتا تعریف می‌شود. یعنی هر گراف شمارا با خاصیت گسترش با گراف رادو یک‌ریخت است. این خاصیت صحت الگوریتم حریصانه را تضمین می‌کند: اهمیتی ندارد که چه رئوسی تا این مرحله انتخاب شده‌اند همواره می‌توانیم راسی جدید با هر الگوی مجاورتی با رئوس قبلی پیدا کینم و بخش بزرگتری از زیرگراف القایی را تولید کنیم.

گراف رادو بسیار متقارن هست: هر یکریختی بین دو زیرگراف القایی آن را میتوان به یک خودریختی از کل گراف گسترش داد. جمله های منطق مرتبه اولی که در مورد گراف رادو صدق میکنند برای تقریبا همه گراف های متناهی صدق میکنند، و جمله هایی که برای گراف رادو صادق نیستند نیز برای تقریبا همه گراف های متناهی صدق نمی‌کنند. در نظریه مدل، گراف رادو مصداقی از مدل شمارای نامتناهی ω-categorical theory است.

تاریخچه

گراف رادو برای اولین بار توسط آکرمن به دو روش ساخته شد. در روش اول هر راس نماینده یک عضو از مجموعه‌های متناهی موروثی و در روش دوم هر راس نماینده یک عدد حسابی است.( به بیان دقیق‌تر، آکرمن یک گراف جهت دار را توصیف می‌کرد و گراف رادو در حقیقت گراف زمینه گراف آکرمن است) اردوش و رینی گراف رادو را به عنوان گراف تصادفی روی شمارا راس ساختند، و ثابت شده که این گراف دارای نامتناهی خودریختی است که با آن می‌توان یکتایی این گراف را نشان داد ولی در اثباتشان به صورت مستقیم به این موضوع اشاره این نکردند. در ادامه ریچارد رادو متوجه شد که گراف رادو یک گراف مرجع است و یک ساختار صریح از آن با مجموعه راس های اعداد طبیعی ارائه کردند که این ساختار عملا با ساختاری که آکرمن ارائه داد معادل است.

روش‌های ساخت

اعداد باینری

اکرمن(1937) و رادو(1964) گراف رادو را با استفاده از گزاره BIT به روش زیر ساختند: آنها راس‌های گراف را با اعداد حسابی شماره گذاری کردند و بین راس $y$ , $x$ (که $x$<$y$) یک یال قرار می‌دهند هرگاه بیت $x$ ام نمایش باینری $y$ یک باشد. پس برای مثال راس متناظر با عدد صفر به همه راس های منتاظر با اعداد فرد وصل می‌شود، همچنین راس منتاظر با عدد 1 از بین اعداد کوچکترش به صفر وصل است، چون صفر به همه اعداد فرد وصل است و از بین اعداد بزرگتر از خودش به همه راس‌های متناظر با اعدادی که به پیمانه چهار ، 2 یا 3 هستند وصل است چون این‌ها دقیقا اعدادی هستند که بیت اولشان یک است.

گراف تصادفی

مدل اردوش-رینی بر روی یک مجموعه نامتناهی از رئوس با احتمال یک با گراف رادو یک‌ریخت می‌شود. به طور خاص، این مدل را می‌توان به این صورت ساخت که بین هر زوج از رئوس، با احتمال 1/2 یال قرار دهیم، و گراف حاصل از این عمل با احتمال یک با گراف رادو یک‌ریخت می‌شود. اگر جای 1/2 هر عدد $p$ دیگر که $0<p<1$ است بگذاریم هم گراف حاصل با احتمال یک با گراف رادو یک‌ریخت می‌شود.

حکم بالا که توسط پال اردوش و آلفرد رینی ثابت شده است اسم جایگزین رایج دیگر این گراف را که "گراف تصادفی" است را توجیه میکند. اگر از مدل اردوش-رینی روی متناهی راس چندین بار نمونه گیری انجام دهیم به گراف های مختلفی دست پیدا میکنیم امّا روی نامتناهی شمارا راس تقریبا همیشه به یک گراف نامتناهی خاص (گراف رادو) میرسیم.

برای هر گراف تصادفی‌ای که به این روش تولید می‌شود گراف مکمل را می‌توان همزمان با معکوس کردن انتخاب‌های قبلی بدست آورد به اینگونه که هر یال را که در گراف اولیه باشد را در گرافمان نمی‌گذاریم و هر یالی که در گراف اولی نباشد را در گرافمان قرار می‌دهیم، در این فرآیند که گراف مکمل را می‌سازیم هر یال را مستقل از بقیه انتخاب می‌کنیم پس این گراف هم با احتمال یک با گراف رادو یک‌ریخت است پس گراف تصادفی یک گراف خودمکمل است

ویژگی ها

گسترش

ویژگی گسترش گراف رادو: برای هر دو مجموعه متناهی از رئوس$U$ و $V$، راس دیگری مانند $x$ وجود دارد که به همه رئوس $U$ متصل است و به هیچ راس در $V$ متصل نیست.

گراف رادو دارای ویژگی گسترش است به این معنا که برای هر دو مجموعه متناهی از رئوس $U$ و $V$، یک راس $x$ خارج از دو مجموعه وجود دارد که به تمام راس‌های $U$ متصل است و به هیچ کدام از راس‌های $V$ یال ندارد با توجه به تعریف باینری گراف رادو عدد $x$ می‌شود:

$$x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}.$$

با توجه به مقداری دهی بالا بیت‌های یک در نمایش باینری $x$ باعث می‌شود که به همه رئوس$U$ یال داشته باشد و از طرفی $x$ هیچ بیت غیرصفری در نمایش باینری خود ندارد که متناظر با رئوس $V$ باشد و همچنین $x$ آنقدر بزرگ است که بیت $x$ ام هر عنصر از $V$ صفر نیست در نتیجه $x$ مجاور هیچ کدام از رئوس $V$ نیست.

از طرفی دیگر با تعبیر گراف تصادفی که از گراف رادو داشتیم هر راس خارج از اجتماع $V$ و $U$ با احتمال $({\frac {1}{2}})^{|V|+|U|}$ ویژگی گسترش را برآورده می‌کند، و چن ناشمارا راس برای انتخاب وجود دارد به احتمال یک راسی وجود دارد که ویژگی گسترش را برآورده کند. همچنین با تعریف گراف پالی، برای هر محموعه $U$ و $V$ طبق قضیه باقیمانده چینی دنباله‌ای حسابی از اعدادی که به هنگ هر عدد اول در $U$ مانده مربعی هستند و به هنگ هر عدد اول در $V$ نامانده مربعی هستند وجود دارد و طبق قضیه دیریکله خاصیت گسترش برای این گراف برقرار می‌شود و در نتیجه با گراف رادو یک‌ریخت می‌شود.

از گراف $G$ که یک گراف رادو است اگر به تعداد متنهاهی از یال‌ها و راس‌هایش حذف کنیم یا تعداد متناهی یال به آن اضافه کنیم ویژگی گسترش گراف تغییری نمی‌کند. پس در گراف جدید همچنان برای هر مجموعه $V$ و $U$ از راس‌ها می‌توان یک راسی پیدا کرد که به همه راس‌های موجود در $U$ وصل باشد و به هیچ کدام از راس‌های $V$ یال نداشته باشد. پس هر تغییر متناهی روی گراف به گرافی می‌رشد که به گراف رادو یک‌ریخت است