گراف تهی

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

گراف تهی

گراف تهی
راس	0
ضلع	0
پیرامون	${\displaystyle \infty }$
اتومورفیزم‌ها	1
رنگ‌آمیزی گراف	0
رنگ‌آمیزی یالی	0
برازش گراف	0
ویژگی‌های	Integral Symmetric
قراردادهای نوشتاری	${\displaystyle K_{0}}$

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

آیا اعتبار دادن به ${\displaystyle K_{0}}$ به عنوان یک گراف مفید است یا نه که بستگی به متن دارد.

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

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

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

${\displaystyle K_{0}}$ عمل (درستی پوچ) بیشتر گراف‌های پایه با ویژگی‌هایی مشابه با ${\displaystyle K_{1}}$ (گرافی با یک رأس و بدون یال) را انجام می‌دهد. برای مثال، ${\displaystyle {\overline {K}}_{n}}$ اندازه صفر، برابر با گراف مکمل آن ${\displaystyle {\overline {K}}_{0}}$، یک جنگل و یک گراف مسطح است. شاید یک گراف جهت دار، بی جهت یا هر دوی آنها در نظر گرفته شود. وقتی جهت دار در نظر گرفته شود، یک گراف جهت دار غیرمدور است و در عین حال یک گراف کامل و یک گراف بی یال است. اگر چه تعریف‌ها برای ویژگی‌های این گراف متفاوت خواهد بود و وابسته به متن است که آیا ${\displaystyle K_{0}}$ را به شمار می‌آورد یا نه.

گراف بی یال

گراف بی یال (تهی، خالی)
راس	n
ضلع	0
فاصله در گراف	0
فاصله در گراف	0
پیرامون	${\displaystyle \infty }$
اتومورفیزم‌ها	n!
رنگ‌آمیزی گراف	1
رنگ‌آمیزی یالی	0
برازش گراف	0
ویژگی‌های	Integral Symmetric
قراردادهای نوشتاری	${\displaystyle {\overline {K}}_{n}}$

برای هر عدد طبیعی n، گراف بی یال (خالی) ${\displaystyle {\overline {K}}_{n}}$ از مرتبه n، گرافی با n رأس و صفر یال است. یک گراف بی یال بعضی اوقات به عنوان گراف تهی در متن معرفی شده که در آن متن گراف مرتبه صفر دیگر یک گراف به شمار نمی‌آید.

یک گراف ۰-منتظم است. علامت ${\displaystyle {\overline {K}}_{n}}$ از آن ناشی می‌شود که n رأس بی یال، متمم یک گراف کامل ${\displaystyle K_{n}}$ است.

جستارهای وابسته

• Glossary of graph theory
• Cycle graph
• Path graph

یادداشت