گراف تهی

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

گراف تهی

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

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

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

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

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

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

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

گراف بی یال

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

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

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

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

• Glossary of graph theory
• Cycle graph
• Path graph