زمان کنونی: ۰۲ آذر ۱۴۰۳, ۰۴:۳۱ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

درخواست حل سوال گراف از علوم کامپیوتر ۹۶

ارسال:
  

Sepideh96 پرسیده:

درخواست حل سوال گراف از علوم کامپیوتر ۹۶

سوال مورد نظر پیوست شده است

ممنون از دوستان


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Jooybari پاسخ داده:

RE: درخواست حل سوال گراف از علوم کامپیوتر ۹۶

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

برای رد گزینه ۱ میتونید یه درخت ۴ راسی به شکل Y درنظر بگیرید. حالا سه تا برگ رو به هم وصل کنید. ۷ تا دور داریم.

گزینه ۲ قابل اثباته. درخت یه گراف مسطحه که به ازای n راس، n-1 یال داره. اگه ۳ یال اضافه بشه میشه n+2 یال.
حداقل تعداد یال برای مسطح نبودن تو گرافهای K3,3 و K5 هست که حداقل ۳ یال بیشتر از تعداد رئوسشون دارن. (اولی ۶ راس و ۹ یال و دومی ۵ راس و ۱۰ یال دارن) پس اگه یه گراف همبند باشه و قراره مسطح نباشه، حداقل باید ۳ یال بیشتر از تعداد رئوسش داشته باشه.

گزینه ۳ که با مثال رد میشه. یه گراف به شکل مسیر درنظر بگیرید. (دو راس از درجه ۱ داشته باشیم) حالا چند یال بهش اضافه کنید که باز هم دو راس از درجه ۱ داشته باشیم. تعداد مسیرها بین اون دو راس درجه ۱ میتونه بیشتر از ۴ باشه.

گزینه ۴ هم نادرسته. وقتی به درخت چند یال اضافه کنیم، طول مسیرها زیاد نمیشه و فقط میتونه کمتر بشه
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه برای درس نظریه علوم کامپیوتر matias ۱۳ ۱۵,۰۵۰ ۲۴ شهریور ۱۴۰۳ ۰۸:۳۳ ب.ظ
آخرین ارسال: shabankhah
  گرایش های علوم کامپیوتر alisaaa ۴ ۴,۲۸۰ ۱۳ آذر ۱۴۰۲ ۰۴:۲۷ ب.ظ
آخرین ارسال: hashemhamidi
  علوم کامپیوتر شریف یا نرم افزار تهران؟ ۴L1R3Z4 ۴۴ ۳۲,۶۸۶ ۰۶ شهریور ۱۴۰۲ ۰۸:۱۲ ب.ظ
آخرین ارسال: moeinbahari
  رتبه ۵۴ علوم کامپیوتر و ۷۶ ریاضی ارشد ۱۴۰۰ Computer92 ۰ ۲,۳۵۰ ۰۸ شهریور ۱۴۰۰ ۰۹:۴۶ ب.ظ
آخرین ارسال: Computer92
  درخواست کارنامه معماری کامپیوتر آزمون آزاد ۹۲ sanazp1388 ۱ ۳,۸۸۱ ۱۷ بهمن ۱۳۹۹ ۰۲:۰۰ ق.ظ
آخرین ارسال: hmaryam567
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۳,۴۷۱ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  سوال ۱۴ علوم کامپیوتر ۹۶ ss311 ۴ ۳,۸۱۰ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ب.ظ
آخرین ارسال: ss311
  جایگشت( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۹۰۵ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۵ ب.ظ
آخرین ارسال: ss311
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۲,۱۱۷ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۲,۰۲۲ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close