نظریه گراف و برخي سؤالات حل شده براي يادگيري بيشتر

[Borna66]

هر گراف مسطح ماکزیمال یک گراف مثلثی است .

************

برهان : (برهان خلف) فرض کنید گرافG مسطح ماکزیمال باشد اما مثلثی نباشد یعنی حداقل یک وجه آن دارای بیشتر از 3 یال باشد، که در این صورت میتوان با رسم یکی از اقطار این وجه گرافی مسطح بدست آورد که این با فرض مسطح ماکزیمال بودن G متناقض است.

[Borna66]

اگر گراف مسطح ماکزیمال باشد در اینصورت که n تعداد رئوس و m تعداد یال های G است .

************

برهان : با توجه به اینکه هر گراف مسطح ماکزیمال ، مثلثی است . داریم :

[Borna66]

عبارتی برای تعداد یالهای بر اساس درجات رئوس G بیابید.

************

با توجه به شکل مشاهده می شود به ازای هر رأس با درجه n تعداد یال درخواهیم داشت .
حال تعداد کل یالها از فرمول زیر بدست می آید که در آن درجه رأس iام است

[ehsan_elf]

سلاام دوستان. شبتون بخیر

چندتا سوال داشتم نمیدونستم باید کجا مطرحشون کنم همینجا میپرسم

1: الگوریتمی بنویسید که یک گراف راگرفته مشخص کند که راس برشی دارد یا خیر.

2: حداکثر تعداد یال های یک گراف ناهمبند چقدر است؟

3: فرمولی که تعداد درخت های فراگیر یک گراف رامحاسبه کند.

ممنون میشم کمکم کنید. البته فقط تا فردا وقت دارم....تشکر

[Borna66]

سلاام دوستان. شبتون بخیر

چندتا سوال داشتم نمیدونستم باید کجا مطرحشون کنم همینجا میپرسم

1: الگوریتمی بنویسید که یک گراف راگرفته مشخص کند که راس برشی دارد یا خیر.

2: حداکثر تعداد یال های یک گراف ناهمبند چقدر است؟

3: فرمولی که تعداد درخت های فراگیر یک گراف رامحاسبه کند.

ممنون میشم کمکم کنید. البته فقط تا فردا وقت دارم....تشکر

با سلام

متاسفانه در اين زمينه اطلاعي ندارم و كمكي از دست ما بر نمي ايد... شرمنده

روزگار خوش