payamvha/North_RAG huggingface dataset:
می‌یابد که رأس هدف پیدا شود یا احتمالاً همهٔ گراف پیمایش شود. براساس آنچه گفته شد پیاده‌سازی هوشمندانهٔ الگوریتم آنقدر مؤثر نخواهد بود. از دیدگاه عملی، برای پیاده‌سازی این الگوریتم از صف استفاده می‌شود. بدین ترتیب که در ابتدا ریشه در صف قرار می‌گیرد. سپس هر دفعه عنصر ابتدای صف بیرون کشیده شده، همسایگانش بررسی شده و هر همسایه‌ای که تا به حال دیده نشده باشد به انتهای صف اضافه می‌شود. جزئیات پیاده‌سازی در ادامه خواهد آمد. الگوریتم. پیاده‌سازی این الگوریتم مشابه پیاده‌سازی جستجوی عمق اول است با این تفاوت که به
پیاده‌سازی جستجوی عمق اول است با این تفاوت که به جای پشته از صف استفاده می‌شود. در این‌جا نیز مانند جستجوی عمق اول، preWORK را برای انعطاف بیشتر الگوریتم در نظر می‌گیریم که در زمان بررسی کردن هر رأس خارج شده از صف انجام می‌شود. الگوریتم جستجوی اول سطح به صورت زیر است. آرایه Visited برای تعیین رئوس ملاقات شده بکار می‌رود. از یک صف برای نگهداشتن رئوس مجاور استفاده می‌شود. هر بار که راسی ملاقات می‌شود کلیه رئوس مجاور آن در صف اضافه می‌شود. پیمایش از راسی که از صف برداشته می‌شود ادامه پیدا می‌کند. الگوریتم:
از صف برداشته می‌شود ادامه پیدا می‌کند. الگوریتم: BFS (int v){ int w Queue q Visited[v]:=1 CreateQueue(q) AddQueue(q, v) While (not EmptyQueue(q)) DeleteQueue(q,v) For (all vertex w adjacent to v) If (not visited[w]) then AddQueue(q,w) Visited[w]:=1 End if End For End while پیاده‌سازی. 1 Algorithm BFS(G,v) 2 Input: G=(V,E), v(a vertex of G) 3 Output: depends on the application 4 begin 5 mark v 6 put v in the queue 7 while the queue is not empty do 8 remove first vertex w from the queue 9 perform preWORK on
vertex w from the queue 9 perform preWORK on w 10 for all edge (w,x) such that x is unmarked do 11 mark k 12 put x in the queue 13 end پیاده‌سازی با متلب. در این الگوریتم اگر تعداد درایه‌های بردار خروجی برابر تعداد رئوس گراف ورودی باشد نشان می‌دهد که گراف همبند می‌باشد در غیر اینصورت گراف ناهمبند می‌باشد. 1 function B=BFS(A) 2 [r,c]=size(A); 3 B=[1]; 4 z=[1]; 5 s=[1]; 6 while (~isempty(s)) 7 b=z(length(z)); 8 adj=find(A(b,:)==1); 9 for t=1:length(adj) 10 if ~ismember(adj(t),B) 11 B=[B adj(t)]; 12 end 13
if ~ismember(adj(t),B) 11 B=[B adj(t)]; 12 end 13 end 14 s=setdiff(B,z); 15 if ~isempty(s) 16 z=[z s(1)]; 17 end 18 end 19 end پیچیدگی زمانی. هر رأس در صورتی وارد صف می‌شود که تا به حال دیده نشده باشد و بنابراین هر رأس قابل دسترسی از ریشه دقیقاً یک بار وارد صف خواهد شد. هر بار عمل ورود یک رأس به صف در formula_1 انجام می‌شود و لذا با فرض همبند بودن گراف اعمال مربوط به صف formula_2 از زمان صرف را صرف خواهند کرد. همچنین هر یال در گراف بدون جهت دقیقاً دو بار و هر یال در گراف جهت‌دار دقیقاً یک بار پیمایش خواهند
یال در گراف جهت‌دار دقیقاً یک بار پیمایش خواهند شد. بدین ترتیب با فرض formula_1 بودن اعمال preWORK و همبندی گراف، پیچیدگی زمانی جستجوی سطح اول formula_4 خواهد بود.
در علم ترکیبیات قضیهٔ رمزی بیان می‌کند که در رنگ آمیزی یال‌های هر گراف کامل (گراف ساده‌ای که در آن هر رأس به تمامی رئوس دیگر به وسیلهٔ یک یال متصل است) به اندازهٔ کافی بزرگی می‌توان زیر گراف‌های کامل تک رنگ یافت. در رنگ آمیزی با دو رنگ قضیهٔ رمزی بیان می‌کند که برای هر جفت از اعداد صحیح و مثبت formula_1 کوچکترین عدد مثبت formula_2 وجود دارد به گونه‌ای که برای هر گراف کامل با formula_2 راس که یال‌های آن با دو رنگ قرمز و آبی رنگ آمیزی شده باشند، زیرگراف کاملی با formula_4 راس وجود دارد که کاملاً آبی شده باشد
با formula_4 راس وجود دارد که کاملاً آبی شده باشد یا زیر گراف کاملی با formula_5 راس وجود دارد که کاملاً قرمز شده باشد. در این جا formula_2 به عدد صحیحی دلالت می‌کند که به formula_4 و formula_5 وابسته‌است. قضیهٔ رمزی یک دست‌آورد بنیادین در علم ترکیبیات است. F. P. Ramsey اولین نسخهٔ این دست‌آورد را به اثبات رساند. این مسئله قضیهٔ ترکیبیاتی را بنیان نهاد که امروزه آن را قضیهٔ رمزی می‌نامند. در این کاربرد سؤال این است که آیا زیرمجموعه‌های تک رنگی یافت می‌شوند که در این زیرمجموعه‌ها تمام یال‌های متصل به هم از
که در این زیرمجموعه‌ها تمام یال‌های متصل به هم از یک رنگ باشند. بسطی از این قضیه برای هر تعداد رنگ متناهی به جای دو رنگ به کار می‌رود. به‌طور دقیق تر این قضیه بیان می‌کند که برای هر تعداد رنگ داده شدهٔ c وهر مجموعه از اعداد صحیح داده شدهٔ formula_9 عدد formula_10 به گونه‌ای وجود دارد که اگر یال‌های گراف کاملی از مرتبه formula_10 با c رنگ متفاوت، رنگ آمیزی شود آن گاه برای مقادیری از i بین ۱ تا c گراف مورد نظر باید شامل زیرگراف کاملی از مرتبهformula_12باشد که تمام یال‌های آن به رنگ i هستند. مورد خاصی که در
تمام یال‌های آن به رنگ i هستند. مورد خاصی که در بالا به آن اشاره شد برای c=۲ اتفاق می‌افتد. (formula_13، formula_14) مثال:R(۳٬۳)=۶. تصور کنید که یال‌های یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ آمیزی شده باشد. حال یک راس مثلاً راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آن‌ها باید همرنگ باشند. بدون کاسته شدن از کلیت مسئله می‌توان فرض کرد که حداقل ۳ یال که از راس v به راس‌های r,s،t متصل اند آبی هستند (در غیر این صورت جای رنگ‌های قرمز و آبی عوض می‌شود)
غیر این صورت جای رنگ‌های قرمز و آبی عوض می‌شود) اگر هر یک از یال‌های (r, s), (r, t), (s, t) نیز آبی باشد آن گاه ما یک مثلث از یال‌های آبی داریم. در غیر این صورت یعنی اگر هیچ‌یک از یال‌های ذکر شده آبی نباشند هر سهٔ این یال‌ها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت. از آن جایی که این استدلال را برای هر رنگ آمیزی می‌توان به کار برد، هر گراف کامل formula_15 شامل یک formula_16 تک رنگ است و از این رو R(۳٬۳) ≤ ۶. نسخهٔ عمومی این قضیه، قضیهٔ آشنایان وغریبه‌ها نامیده می‌شود. یک اثبات جایگزین با
وغریبه‌ها نامیده می‌شود. یک اثبات جایگزین با استفاده از روش دوگونه شماری بدست می‌آید. این روش بدین صورت پیش می‌رود: تعداد سه تایی‌های مرتب از راس‌های x,y،z را که در آن یال (x,y) قرمز و (y,z) آبی هستند، بشمارید. اولاً هر راس داده شده در میان ۰×۵=۰ یا ۱×۴=۴ یا ۲ × ۳ = ۶ تا از سه تایی‌های مرتب خواهد بود؛ بنابراین حداکثر ۶×۶=۳۶ تا از این سه تایی‌ها وجود دارد. دوما برای هر مثلث (x,y،z) غیر تک رنگ دقیقاً ۲ تا از این سه تایی‌ها وجود دارد؛ بنابراین حداکثر ۱۸ تا مثلث غیر تک رنگ وجود دارد؛ بنابراین حداقل ۲ تا از ۲۰
غیر تک رنگ وجود دارد؛ بنابراین حداقل ۲ تا از ۲۰ مثلث موجود در formula_15 تک رنگند. برعکس، می‌توان یک formula_18 را با دو رنگ، رنگ آمیزی کرد بدون این که هیچ formula_16 تک رنگی ایجاد شود که نشان می‌دهد R(۳٬۳)&gt; ۵. اثبات قضیه. ابتدا قضیه را برای حالت رنگ آمیزی با دو رنگ با استفاده از استقرا روی r+s اثبات می‌کنیم. از روی تعریف واضح است که برای هر n ای R(n, ۱) = R(1, n) = ۱. این پایهٔ استقراست. ما اثبات خواهیم کرد که formula_20 وجود دارد و این کار را با یافتن یک محدودهٔ صریح برای آن انجام خواهیم داد. فرض
یک محدودهٔ صریح برای آن انجام خواهیم داد. فرض استقرای ما این است که formula_21،formula_22 وجود دارد. ادعا: formula_23. یک گراف کامل با formula_24 راس را در نظر بگیرید. راس v از گراف داده شده را انتخاب کنید و راس‌های باقی‌مانده را به دو مجموعهٔ M و N تفکیک کنید به گونه‌ای که هر راسی همانند w در مجموعهٔ M باشد اگر یال (v, w) آبی باشد و w در N باشد اگر که یال (v, w) قرمز باشد. حال با استفاده از اصل لانه کبوتری داریم: formula_25 یا formula_26اگر M دارای زیرگراف کامل formula_27 به رنگ قرمز باشد آن گاه گراف
کامل formula_27 به رنگ قرمز باشد آن گاه گراف اولیه نیز شامل این بخش می‌شود و مسئله حل شده‌است. در غیر این صورت M دارای زیرگراف کامل formula_28 است و بنابراین بنا بر تعریف M, M اجتماع {v} دارای زیرگراف کامل formula_29 به رنگ آبی است. برای حالت دیگر نیز استدلال مشابه‌است. پس ادعای ما درست است و ما اثبات را برای رنگ آمیزی با دو رنگ کامل کردیم. اکنون می‌خواهیم نتایج حالت کلی در رنگ آمیزی با c رنگ را به اثبات برسانیم. از استقرا استفاده می‌کنیم. ما نتایج مورد نظرمان را برای c=۱(بدیهی) و c=۲ (طبق مطالب گفته شده
را برای c=۱(بدیهی) و c=۲ (طبق مطالب گفته شده در بالا) داریم. حال c&gt;۲ را در نظر می‌گیریم. ادعا:formula_30 توجه کنید که عبارت سمت راست تنها دارای عدد رمزی برای c-۱ رنگ و ۲ رنگ است و از این رو طبق فرض استقرا عددی متناهی مانند t وجود دارد. پس اثبات ادعایمان برای اثبات قضیه کافی است. اثبات ادعا. گرافی با t راس را در نظر بگیرید و یال‌های آن را با c رنگ، رنگ آمیزی کنید. حال خود را به کور رنگی بزنید و وانمود کنید که رنگ c-1 و رنگ c رنگ‌های یکسانی هستند. پس در این وضعیت گراف با c-1 رنگ، رنگ آمیزی شده‌است. بنابر
وضعیت گراف با c-1 رنگ، رنگ آمیزی شده‌است. بنابر فرض استقرا این گراف شامل formula_31 تک رنگ است که رنگ i در بازهٔ formula_32 قرار دارد یا شامل یک formula_33 رنگ شده با رنگ‌های تیره‌است. در حالت اول کار ما به پایان رسیده‌است. در حالت دوم دیدگاه خود را مورد بازبینی قرار می‌دهیم و می‌بینیم که بنا بر تعریف formula_34 ما باید یا یک گراف formula_35 که به تمامی با تک رنگ (c-1) رنگ شده داشته باشیم یا یک گراف formula_36 که با تک رنگ c رنگ شده باشد. در هر دو حالت اثبات کامل است. اعداد رمزی. اعداد formula_20 در قضیهٔ
کامل است. اعداد رمزی. اعداد formula_20 در قضیهٔ رمزی (و بسط یافتهٔ آن‌ها در موارد با بیش از دو رنگ) تحت عنوان اعداد رمزی شناخته می‌شوند. یک حد بالا برای formula_38 را، می‌توان از اثبات قضیه استخراج کرد و سایر استدلال‌ها نیز حد پایین برای آن ارائه می‌کنند. (نخستین حد پایین توسط Paul Erdős با استفاده از روش احتمالاتی به دست آمد) هر چند شکاف بزرگی میان مقادیر حد پایین و حد بالا وجود دارد. من تبع آن تعداد بسیار اندکی از r وsها هستند که ما برای آن‌ها مقدار دقیق formula_20 را می‌دانیم. محاسبهٔ حد پایین L برای
formula_20 را می‌دانیم. محاسبهٔ حد پایین L برای formula_20 معمولاً نیازمند ارائهٔ یک رنگ آمیزی گراف formula_41 با دو رنگ قرمز و آبی است به‌طوری‌که هیچ زیرگراف آبی formula_29 و هیچ زیرگراف قرمز formula_27 در آن یافت نشود. هر چند که بررسی حالت‌های مختلف رنگ آمیزی گراف formula_44 با افزایش مقدار n از نظر محاسباتی بسیار پیچیده خواهد شد. تعداد حالت‌های رنگ آمیزی رشدی بالاتر از رشد نمایی(exponentially) دارد. در حال حاضر حتی مقدار دقیق formula_45 شناخته شده‌است هر چند که از قبل می‌دانستیم که مقدار آن بین ۴۳(توسط
چند که از قبل می‌دانستیم که مقدار آن بین ۴۳(توسط Geoffrey Exoo) و 49 (Brendan McKay، وStanisław Radziszowski) قرار دارد. احتمال داده می‌شود که مقدار دقیق formula_46 برای همیشه مجهول بماند. Paul Erdős می‌گوید: " بیگانگانی (نیروهای خارجی) را تصور کنید که بسیار نیرومندتر از ما بر روی زمین هستند و از ما خواسته‌اند که مقدار formula_47 را محاسبه کنیم و در غیر این صورت سیارهٔ ما را نابود خواهند کرد. در این حالت ما باید تمام کامپیوترها و ریاضی دان هایمان را به کار بگیریم و برای یافتن مقدار مورد نظر به شدت تلاش
بگیریم و برای یافتن مقدار مورد نظر به شدت تلاش کنیم. حال به جای این تصور کنید که از ما خواسته شده تا مقدار formula_48 را محاسبه نماییم، در این وضعیت ما باید تمام تلاشمان را برای نابود کردن بیگانگان به کار ببریم!" مقدار formula_20 برای مقادیر r و s تا ۱۰ در جدول زیر نشان داده شده‌است. از آن جایی که در بسیاری از موارد مقدار دقیق را نمی‌دانیم، بهترین حدود یافت شده در جدول به نماش گذاشته شده‌است. formula_20 برای مقادیر r و s کوچک‌تر از ۳ به صورت R(1,s) = ۱و R(2,s) = s برای تمام مقادیرs داده شده‌است. در جدول یک
= s برای تمام مقادیرs داده شده‌است. در جدول یک تقارن ناچیز در میان قطر نیز وجود دارد. جدول فوق از جدول بزرگ‌تری که توسط Stanisław Radziszowski تألیف شده، اقتباس شده‌است. در سال ۲۰۱۲ قضیه formula_51 را Geoffrey Exoo اثبات کرد. یک مثال از چندین رنگ: R(3,3،3) = ۱۷. یک عدد رمزی رنگارنگ یک عدد رمزی است که در آن برای رنگ آمیزی از ۳ رنگ یا بیشتر استفاده می‌شود. فقط یک عدد رمزی رنگارنگ وجود دارد که مقدار دقیق آن شناخته شده‌است و آن R(3,3،3) = ۱۷ است. برای اثبات این مسئله، یالی از یک گراف کامل را در نظر بگیرید که
مسئله، یالی از یک گراف کامل را در نظر بگیرید که با ۳ رنگ قرمز، سبز و زرد رنگ آمیزی شده‌است. حال می‌خواهیم ببینیم این گراف باید حداقل چند راس داشته باشد که شرایط قضیهٔ رمزی برایش بر قرار باشند. پس معادلاً می‌توانیم ببینیم حداکثر تعداد رئوس باید چند باشد که شرایط قضیهٔ رمزی بر قرار نشود. پس فرض کنید که یال مورد نظر هیچ مثلث هم رنگی را تشکیل نمی‌دهد. یک راس دلخواه v را انتخاب کنید. مجموعهٔ رئوسی که یک یال سبز به v داده‌اند را در نظر بگیرید. این مجموعه همسایگی سبز راس v نامیده می‌شود. همسایگی سبز v نمی‌تواند
سبز راس v نامیده می‌شود. همسایگی سبز v نمی‌تواند شامل هیچ یال سبزی باشد، زیرا در غیر این صورت مثلث سبزی وجود خواهد داشت که متشکل از دو نقطهٔ انتهایی آن یال سبز و راس v خواهد بود. پس یال‌های رنگ آمیزی شده در همسایگی سبز v تنها با دو رنگ قرمز و زرد رنگ آمیزی شده‌اند. از آن جایی که R(3,3) = 6است همسایگی سبز v می‌تواند حداکثر شامل ۵ راس باشد. به‌طور مشابه همسایگی‌های قرمز و زرد v نیز هر کدام حداکثر می‌توانند ۵ راس داشته باشند. از آن جایی که هر راس به جز خود v در یکی از همسایگی‌های سبز، قرمز یا زرد v قرار
v در یکی از همسایگی‌های سبز، قرمز یا زرد v قرار گرفته، گراف کامل حداکثر می‌تواند ۱ + ۵ + ۵ + ۵ = ۱۶ راس داشته باشد. در نتیجه داریم: R(3,3،3) ≤ 17 برای این که ببینیم R(3,3،3) ≥ 17کافی است یال‌های یک گراف کامل با ۱۶ راس را با سه رنگ متفاوت رنگ آمیزی کنیم و در عین حال از ایجاد مثلث‌های تک رنگ بپرهیزیم. به این نتیجه خواهیم رسید که دقیقاً دو روش برای رنگ آمیزی K16 با این شرایط وجود دارد که آن‌ها را رنگ آمیزی تابیده (معوج) و ناتابیده می‌نامیم. هر دو روش رنگ آمیزی در شکل سمت چپ در بالا نشان داده شده‌است. شکل
در شکل سمت چپ در بالا نشان داده شده‌است. شکل بالایی رنگ آمیزی ناتابیده و شکل پایینی رنگ آمیزی تابیده را نشان می‌دهد. بدین ترتیب، مشخص می‌شود که گراف K16 را می‌توان طوری با ۳ رنگ رنگ آمیزی کرد که هیچ k3 تک رنگی ایجاد نشود. پس R(3,3،3)=17. اگر شما هر رنگی از رنگ‌های تابیده یا ناتابیدهٔ گراف formula_52 را انتخاب کنید و گرافی را در نظر بگیرید که یال‌هایش دقیقاً یال‌هایی با همان رنگ ویژه باشد آن گاه به گراف Clebsch دست خواهیم یافت. دقیقاً دو روش برای رنگ آمیزی یال‌های گراف formula_53 با سه رنگ وجود دارد به
یال‌های گراف formula_53 با سه رنگ وجود دارد به گونه‌ای که از ایجاد مثلث‌های تک رنگ پرهیز کنیم. این گراف را می‌توان با حذف کردن هر راس دلخواه از گراف تابیده یا ناتابیدهٔ K16 که به‌طور مطلوب رنگ آمیزی شده، به دست آورد. علاوه بر این دقیقاً ۱۱۵ یال برای رنگ آمیزی formula_54 با سه رنگ وجود دارد به گونه‌ای که در آن از ایجاد مثلث‌های تک رنگ جلوگیری شود. منابع. ویکی‌پدیای انگلیسی
گراف کامل گراف ساده‌ای است که در آن هر رأس به تمامی راس‌های دیگر به وسیلهٔ یک یال متصل است. معمولاً گراف کاملِ formula_1 راسی را با formula_2 نمایش میدهند. آغاز نظریه گراف‌ها معمولاً با کار اویلر بر روی هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است. با این حال، تاریخچه گرافهای کامل به رسم‌های رامون یوی در قرن سیزدهم بازمی‌گردد، که رئوس گراف را در گوشه‌های چندضلعی منتظم قرار میداد. این رسم‌ها با عنوان گل رز عرفانی نیز شناخته می‌شوند. مثال. شکل پایین شامل گرافهای کامل که دارای یک تا هشت رأس هستند می‌باشد:
کامل که دارای یک تا هشت رأس هستند می‌باشد: ماتریس مجاورت گراف کامل. تمامی درایه‌های گراف کامل ۱ هستند به جز درایه‌های روی قطر اصلی که صفر هستند چون گراف کامل طوقه وجود ندارد. formula_7
الگوریتم بلمن-فورد الگوریتم پیمایش گراف است که مسئلهٔ کوتاهترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که وزن یال‌ها ممکن است منفی باشد حل می‌کند. الگوریتم دَیکسترا مسئلهٔ مشابهی را در زمان اجرای کمتر حل می‌کند، اما در آن الگوریتم می‌بایست وزن یال‌ها اعداد نامنفی باشند. بنابراین در عمل الگوریتم بلمن-فورد فقط برای گراف‌هایی که یال با وزن منفی دارند استفاده می‌شود. قبل از توضیح الگوریتم لازم به ذکر است که اگر گراف دوری با مجموع وزن منفی داشته باشد که از مبدأ قابل دست‌یابی باشد، مسئلهٔ کوتاهترین مسیر
از مبدأ قابل دست‌یابی باشد، مسئلهٔ کوتاهترین مسیر جوابی نخواهد داشت، چراکه با پیمایش آن دور به هر تعداد بار دلخواه، مسیرهایی با وزن کمتر و کمتر حاصل خواهد شد. چگونه کار می‌کند؟. ساختار اصلی الگوریتم بلمن-فورد مشابه الگوریتم دایکسترا است. اجرای الگوریتم 1-|V| دنبالهٔ formula_1 چنان تعریف می‌شود که برای هر رأس formula_2، مقدار formula_3 در پایان مرحلهٔ formula_4ام برابر وزن کوتاهترین گذر از مبدأ به formula_2 است با این شرط اضافه که تعداد یال‌های این گذر حداکثر formula_4 باشد. بنابراین در پایان مرحلهٔ
حداکثر formula_4 باشد. بنابراین در پایان مرحلهٔ (1-|V|)ام formula_3 برابر وزن کوتاهترین مسیر از مبدأ به formula_2 خواهد بود (در واقع چون دور با مجموع وزن منفی نداریم، کوتاهترین گذر با حداکثر 1-|V| یال از مبدأ به formula_2، همان کوتاهترین مسیر از مبدأ به formula_2 در گراف خواهد بود). اساس کار الگوریتم آزادسازی (Relaxation) همهٔ یال‌های گراف در هر مرحله‌است. آزادسازی یال formula_11 به این معناست که اگر formula_12 آنگاه قرار می‌دهیم formula_13. با این اوصاف اگر آزادسازی همهٔ یال‌ها را برای بار |V|ام هم تکرار
آزادسازی همهٔ یال‌ها را برای بار |V|ام هم تکرار کنیم و بعد از این مرحله هم دنبالهٔ formula_1 تغییر کند، آنگاه می‌توان نتیجه گرفت که گراف دور منفی‌ای دارد که از مبدأ قابل دست‌یابی است. بنابراین الگوریتم بلمن-فورد توانایی تشخیص دور منفی را نیز دارد. الگوریتم. همانطور که گفته شد الگوریتم بلمن-فورد توانایی تشخیص دور منفی را نیز دارد. بنابراین الگوریتم را به گونه‌ای پیاده‌سازی می‌کنند که در صورت تشخیص دور منفی مثلاً مقدار بولی True برگرداند. پیاده‌سازی. یک پیاده‌سازی نوعی به این شرح است: 1 Algorithm
یک پیاده‌سازی نوعی به این شرح است: 1 Algorithm Bellman-Ford(G,s) 2 Input : G=(V,E), s(the source vertex) 3 Output : Sequence d and a boolean return value 4 begin 5 for all vertices w do 6 formula_15 = formula_16 8 formula_17 = 0 9 for i = 1 to |V|-1 do 10 for all edge (u,v) in E do 11 if formula_12 then 12 formula_3 = formula_20 13 for all edge (u,v) in E do 14 if formula_12 then 15 return False 16 return True 17 end اثبات درستی. می توان درستی را با استفاده از استقرای ریاضی نشان داد. لم. بعد از "i" بار
از استقرای ریاضی نشان داد. لم. بعد از "i" بار تکرار حلقه: اثبات. ابتدا حالت پایه استقرا را در نظر بگیریم که در آن codice_1. در این حالت codice_2 که درست است. به ازای تمامی گره‌های غیر از مبنا "u" داریم codice_3 که درست است؛ چون که هیچ مسیری از مبنا به این گره‌ها با طول مسیر صفر وجود ندارد. ابتدا قسمت اول را اثبات می کنیم. با فرض استقرا فرض کنیم codice_4 طول مسیری از مبنا به "u" باشد. در اینصورت codice_5 طول مسیری از مبنا به "v" است. برای قسمت دوم، طول کوتاه‌ترین مسیر از مبنا به "u" با حداکثر تعداد i یال را
مسیر از مبنا به "u" با حداکثر تعداد i یال را در نظر بگیریم. فرض کنیم "v" گرهی قبل از "u" در طول این مسیر باشد، در اینصورت کوتاه‌ترین مسیر به "v" با تعداد i-1 یال است. بنابه فرض استقرا بعد از i-1 تکرار حلقه، کوتاه‌ترین مسیر تا "v" حداکثر به طول همین مسیر است(با i-1 یال). در اینصورت چون در "i"-امین تکرار حلقه codice_6 با codice_4 مقایسه می‌شود حتماً کوتاه‌ترین مسیر با تعداد i یال در i امین تکرار پیدا خواهد شد. توجه کنید که در چنین درختی که مسیر شامل حلقه نداریم، حداکثر طول مسیر برابر با formula_22 است. لذا
حداکثر طول مسیر برابر با formula_22 است. لذا الگوریتم مورد نظر بعد از اتمام جواب بهینه را به‌دست خواهد داد. پیچیدگی زمانی. مشخص است که در formula_22 مرحله، در هر مرحله formula_24 عملیات بر روی یال‌ها انجام می‌شود. پس formula_25 پیچیدگی زمانی الگوریتم بلمن-فورد خواهد بود. برنامه‌های مورد استفاده در مسیر یابی. انتشارات مختلفی از الگوریتم بل من فورد در پروتکل Distance vector routing مورد استفاده قرار گرفته بود. برای مثال پروتکل RIP یکی از الگوریتم‌هایی است که انتشار یافته‌است چون تعدادی از گره‌ها (مسیر یاب
انتشار یافته‌است چون تعدادی از گره‌ها (مسیر یاب ها) را با یک سیستم خود مختار درگیر می‌کند. یک مجموعه شبکه IP که معمولاً به وسیلهٔ یک ISP مالکیت می‌شود شامل این گام‌ها می‌شود: ۱- هر گره مسافت بین خودش و تمام گره‌هایی که در داخل AS اند را محاسبه می‌کند و در جدولی اطلاعات را ذخیره می‌کند . ۲- هر گره جدول اش را به تمام نودهای مجاورش ارسال می‌کند. ۳- وقتی یک گره جدول مسافت را از گره مجاور خودش دریافت می‌کند، کوتاهترین مسیرها را به تمام بقیه گره‌ها محاسبه می‌کند و جدول خودش را برای بازتاب تغییرات بروز می‌کند.
و جدول خودش را برای بازتاب تغییرات بروز می‌کند. اشکال اصلی الگوریتم بل من فورد در این تنظیمات عبارتست از : - به‌خوبی مقیاس (نسبت) نمی‌کند. - تغییر در توپولوژی شبکه به سرعت انعکاس داده نمی‌شود چون آپدیت شدن گره به گره منتشر می‌شود. - محاسبه تا بی‌نهایت ( اگر لینک یا گره در انتقال به یک گره غیرقابل دسترس از بعضی از مجموعه دیگر گره‌ها شکست بخورد، آن گره‌ها ممکن است برای همیشه به تدریج تخمین مسافتشان به آن گره افزایش پیدا کند و در ضمن ممکن است مسیر loop باشد.) توسعه YEN. در انتشار سال ۱۹۷۰، Jin.Y.Yen یک توسعه
توسعه YEN. در انتشار سال ۱۹۷۰، Jin.Y.Yen یک توسعه از الگوریتم بل من فورد را برای گراف بدون حلقه با وزن منفی تشریح کرد. توسعه Yen ابتدا کمی نوبت خطی انحصاری بر روی تمام رئوس و بعد تمام قسمت‌های مجموعه تمام یال‌ها در یکی از ۲ زیر مجموعه نشان داد. اولین زیر مجموعه Ef۱ شامل تمام رئوس (Vi،Vj) که i&lt;j و دومین مجموعه، Eb شامل یال‌های (Vi،Vj) که i&lt;j است. هر راس که در ترتیب v۱، v۲، ...، v|V|، ملاقات می‌شود را کم می‌کند . هر خروجی یال از آن راس در Ef ثبت می‌شود. هر راس بعدی که در ترتیب v|V|، v|V|−۱، ...، v۱
هر راس بعدی که در ترتیب v|V|، v|V|−۱، ...، v۱ ملاقات می‌شود، هر خروجی از آن راس را در Eb کم می‌کند . توسعه Yen، تأثیرگذاری بسزایی در نصف کردن تعداد مسیرهای طی شده مورد نیاز برای مسئله کوتاهترین مسیر ممکن تک منبعی داشت.
نحله مکتب فلسفی است. یک نحله زمانی مورد تایید فیلسوفان است که نوآوری در آن وجود داشته باشد. برای گسترش یک نحله فلسفی باید آن نحله مورد نقد و بررسی قرار گیرد و بر دیدگاه‌های دیگر فیلسوفان تاثیر کند. منبع. The Philosophical Theory of the State and Related Essays- by Bernard Bosanquet, Gerald F. Gaus, and William Sweet- UK: Thoemmes Press/South Bend, IN: St Augustine's Press, 2001 Science and Philosophy and Other Essays by the Late Bernard Bosanquet, (ed. J.H. Muirhead and R.C. Bosanquet), London, Allen and
Muirhead and R.C. Bosanquet), London, Allen and Unwin, 1927
رابطهٔ بازگشتی (به انگلیسی: Recurrence relation) در ریاضیات، دنباله‌ای است که به‌صورت بازگشتی تعریف می‌شود. واژه معادلهٔ تفاضلی (difference equation) مربوط به حالت خاصی از رابطۀ بازگشتی می‌باشد. به هر حال، «مدل تفاضلی» برای اشاره به هر گونه رابطۀ بازگشتی به کار می‌رود. نمونه‌ای از یک رابطۀ بازگشتی، نقشه لجستیک (منطقی) با ثابت داده شدۀ formula_1 می‌باشد که با در نظر گرفتن formula_2 به عنوان مقدار اولیه، تمام مقادیر بعدی با این رابطه به‌دست می‌آید. بسیاری از روابط بازگشتی ممکن است رفتارهای پیچیده‌ای از خودشان
بازگشتی ممکن است رفتارهای پیچیده‌ای از خودشان نشان دهند. این نوع روابط توسط فیزیک‌دانان و ریاضی‌دانان در شاخه‌ای از ریاضیات به نام تحلیل غیر خطی مطالعه می‌شوند. حل یک معادلۀ بازگشتی یعنی به‌دست آوردن یک فرم بسته برای آن (یک تابع غیر بازگشتی از formula_3). فیبوناچی. اعداد فیبوناچی نمونه اولیه‌ای از یک رابطۀ بازگشتی همگن با ضرائب ثابت می‌باشد. این اعداد با رابطۀ خطی بازگشتی زیر: با مقادیر اولیه: تعریف می‌شوند. مشخصاً رابطۀ بازگشتی معادله‌های زیر را ایجاد می‌کند: به توالی اعداد فیبوناچی می‌رسیم که به شکل: ۰،
به توالی اعداد فیبوناچی می‌رسیم که به شکل: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳، ۲۱، ۳۴، ۵۵، ۸۹ و … است. آن را می‌توان با روش‌هایی که در ادامه توضیح داده می‌شوند، حل کرد؛ روش‌هایی که عبارتی بسته (closed-form expression) شامل توان‌های دو ریشه چندجمله‌ای مشخصه formula_10 دارند. تابع ایجادکنندۀ توالی، تابع گویای زیر است: ساختار. رابطۀ بازگشتی خطی همگن با ضرایب ثابت. رابطۀ بازگشتی خطی همگن با ضرایب ثابت از مرتبۀ formula_12، معادله‌ای به شکل زیر است: که در آن formula_12 ضرایب formula_15 (برای تمام formula_16ها) ثابت است.
formula_15 (برای تمام formula_16ها) ثابت است. می‌توان گفت، فهرست معادلات خطی هم‌زمان نامتناهی است که برای هر formula_17 می‌باشد. یک توالی که رابطه‌ای چنینی داشته باشد، توالی بازگشتی خطی یا LRS نامیده می‌شود. formula_12 درجۀ آزادی برای LRS وجود دارد بدین معنا که مقادیر اولیۀ formula_19 هر مقداری را می‌توانند بگیرند ولی رابطۀ بازگشتی خطی توالی یکتایی را مشخص می‌کند. ضرایب یکسان چندجمله‌ای مشخصه را ایجاد می‌کنند: که ریشه‌های formula_12 نقش مهمی در یافتن و فهمیدن توالی‌های درست از لحاظ تابع بازگشتی دارند. اگر
توالی‌های درست از لحاظ تابع بازگشتی دارند. اگر ریشه‌های معادلۀ مشخصه تماماً مشخص باشند، حال راه‌حل بازگشتی به شکل زیر خواهد بود: که در آن ضرایب formula_23 برای متناسب کردن شرایط اولیۀ رابطۀ بازگشتی مشخص می‌شوند. وقتی که ریشه‌های یکسان برای چندین بار اتفاق می‌افتند، قسمت‌هایی از این فرمول که مربوط به موارد دوم و بیشتر از یک ریشه است در توان‌های افزایشی از formula_3 ضرب می‌شوند. برای مثال، اگر چندجمله‌ای مشخصه فاکتوری از formula_25 با ریشۀ تکراری سه بارۀ formula_1 باشد، راه‌حل به شکل زیر خواهد بود: در کنار
باشد، راه‌حل به شکل زیر خواهد بود: در کنار اعداد فیبوناچی، دیگر توالی‌های ایجاد شده توسط روابط بازگشتی خطی همگن شامل اعداد لوکاس و توالی لوکاس، اعداد یاکوبسال، اعداد پل و معادلۀ پل می‌باشد. تابع مولد گویا. توالی‌های بازگشتی خطی دقیقاً توالی‌هایی هستند که تابع مولدشان یک تابع گویا است. مخرج چندجمله‌ای به‌دست آمده از چندجمله‌ای مشخصه با معکوس کردن ترتیب ضرائب است و صورت با مقادیر اولیه توالی مشخص می‌شود. ساده‌ترین حالت‌ها توالی‌های دوره‌ای formula_28هستند که توالی formula_29 و تابع مولدی مجموع سری هندسی زیر
توالی formula_29 و تابع مولدی مجموع سری هندسی زیر دارند: عموماً در مورد رابطه بازگشتی زیر: با تابع مولد: سری‌ها در "ad" و بالاتر به وسیله چندجمله‌ای زیر متوقف می‌شوند: که این یعنی ضرب تابع مولد در چندجمله‌ای، در پی خواهد داشت: به‌طوری‌که ضرایب formula_35 برای "n" ≥ "d" حذف می‌شوند. پس: و با تقسیم خواهیم داشت: که نشان دهنده تابع مولد به عنوان تابع گویا است. مخرج formula_38 است که تبدیلی از چندجمله‌ای مشخصه است. می‌توان هر مضربی از آن را استفاده کرد، ولی این نرمال سازی هر دو را انتخاب کرده تا رابطه ساده‌تری
نرمال سازی هر دو را انتخاب کرده تا رابطه ساده‌تری برای چندجمله‌ای مشخصه داشته باشد و همچنین داشته باشد formula_39. روابط تفاضلی به دقت تعریف شده. دنباله اعداد حقیقی formula_40 را در نظر بگیرید. اولین دنباله تفاضلی برابر است. دومین دنباله به صورت تعریف می‌شود که می‌تواند به صورت ساده‌سازی شود. به صورت کلی دنباله تفاضلی k ام به صورت زیر تعریف می‌شود: تعریف محدودتری از معادله تفاضلی معادله‌ای است بر حسب "an" و k امین تفاضل. در واقع معادله زیر را داریم: formula_45 بنابراین معادله تفاضلی می‌تواند معادله‌ای بر