گراف تهی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات رشته نظریه گراف اصطلاح "گراف تهی" ممکن است اشاره به گرافی از مرتبه صفر داشته باشد یا معادل گرافی بی یال باشد. (دومی که گاهی اوقات به "گراف خالی" نام برده می‌شود).

گراف تهی[ویرایش]

گراف تهی
Vertices 0
Edges 0
Girth
Automorphisms 1
Chromatic number 0
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation

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

آیا اعتبار دادن به به عنوان یک گراف مفید است یا نه که بستگی به متن دارد.

از دیدگاه مثبت، وجود برای تعریف گراف مجموعه به طریق نظریه مجموعه‌ها لازم است (که در آن زوج مرتبی از (V,E)هستند که برای مجموعه یال‌ها و رأس‌ها، (V,E)، هر دو خالی (تهی) هستند) در اثباتها، برای حالت پایه طبیعی در استقرای ریاضی و به طور مشابه، در تعریف بازگشتی ساختمان داده‌ها برای حالت پایه بازگشت، مفید واقع می‌شود (به صورتی که با درخت تهی به عنوان یک برگ بدون در همه درخت‌های دوتایی غیر تهی رفتار شود که همه درخت‌های دوتایی غیر تهی دقیقاً دو برگ دارند).

از دیدگاه منفی، قبول کردن به عنوان یک گراف باعث می‌شود که برای خیلی از فرمول‌های خوش تعریف را استثنا بگیریم. برای اجتناب از همیچن استثناهایی، معمولاً در نوشتارها مفروض است که عبارت گراف دلالت دارد بر «گرافی حداقل با یک رأس».

در نظریه دسته‌ها، گراف تهی، بنابر برخی از تعاریف «دسته گراف‌ها» عضوی اولیه در دسته است.

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

گراف بی یال[ویرایش]

== گراف بی یال (تهی، خالی) ==
Vertices n
Edges 0
Radius 0
Diameter 0
Girth
Automorphisms n!
Chromatic number 1
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation

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

یک گراف ۰-منتظم است. علامت از آن ناشی می‌شود که n رأس بی یال، متمم یک گراف کامل است.

جستارهای وابسته[ویرایش]

یادداشت[ویرایش]