کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875705 1441981 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An iteration method for computing the total number of spanning trees and its applications in graph theory
ترجمه فارسی عنوان
یک روش تکرار برای محاسبه تعداد کل درختان درختکاری و کاربرد آن در نظریه گراف
کلمات کلیدی
ترجمه چکیده
محاسبه و تجزیه و تحلیل تعدادی از درختان پوشش گراف (مدل های شبکه) یک پروژه تحقیقاتی مهم و جالب در زمینه های مختلفی از قبیل ریاضیات، فیزیک، علوم رایانه ای نظری، شیمی و غیره است. تعداد درختان درختی از نمودار ها (مدل ها) مقدار اطلاعاتی را در مورد ویژگی های ساختاری آن و نیز برخی از ویژگی های دینامیکی مربوطه، به ویژه امنیت شبکه، راه های تصادفی و نفوذ نشان می دهد. در این مقاله ابتدا با توجه به تعداد زیادی از نمودار ها (مدل ها) بر اساس عناصر ساده و کوچک مختلف (اجزای سازنده) ساخته شده است، در ابتدا برخی از عملیات مفید شبکه مانند عملیات پیوند و ادغام عملیات، برای تولید گرافهای واقع گرایانه و پیچیده تر (مدل ها). در مرحله دوم، با توجه به قابلیت اطمینان از خطا به گسل های تصادفی و تحمل به نفوذ برای حذف انتخابی حملات، قابلیت هماهنگ سازی و ویژگی های انتشار در شبکه ها، ما یک روش تکراری (الگوریتم) برای محاسبه تعداد کل درختان پشته داریم. به عنوان مثال، به روش ما به فضای درخت و فضای چرخه اعمال می شود، متوجه می شویم که ثابت شده است که در واقع یک ابزار بهتر است. به منظور مفهوم بیشتر معنای عمیق، کاربرد آن را در نظریه گراف، از جمله گراف نردر با ضریب خوشه بندی صفر، نمودار چرخ با داشتن ضریب خوشه بندی غیر صفر به عنوان مواد تشکیل دهنده حداکثر نمودارهای مسطح مطالعه می کنیم. در بقیه این مقاله، خلاصه ای مختصری ارائه می دهیم که روش توصیف شده توسط ما می تواند یک برنامه (الگوریتم) برای به دست آوردن تعداد دقیق درختان درخت در برخی از مدل ها باشد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Calculating and analyzing the number of spanning trees of graphs (network models) is an important and interesting research project in wide variety of fields, such as mathematics, physics, theoretical computer science, chemistry and so on. The number of spanning trees of graphs (models) displays amounts of information on its structural features and also on some relevant dynamical properties, in particular network security, random walks and percolation. In this paper, firstly, due to lots of graphs (models) are built on the basis of various simple and small elements (components), we provide primarily some helpful network-operation, such as link-operation and merge-operation, to generate more realistic and complicated graphs (models). Secondly, considering reliability of fault-tolerance to random faults and of intrusion-tolerance to selectively remove attacks, synchronization capability and diffusion properties of networks, we present an iterative method (algorithm) for computing the total number of spanning trees. As a pellucid example, we apply our method to tree space and cycle space, notice that it is proved to be indeed a better tool. In order to reflect more widely practical meanings, we study its applications in graph theory, including ladder-graph with zero clustering coefficient, wheel-graph having nonzero clustering coefficient as constituent ingredients of maximal planar graphs. In the rest of this paper, we make a brief summary that the method described by us can be designed a program (algorithm) for obtaining easily the exact number of spanning trees of some models.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 708, 17 January 2018, Pages 46-57
نویسندگان
, ,