مقاطع تحصیلی
جستجو در منظومه
همبندی و ناهمبندی یک گراف: گراف G را همبند می‌نامیم هرگاه بین هر دو ِ رأس آن حداقل یک مسیر وجود داشتهباشد، در غیر این صورت آن را ناهمبند می‌نامیم. به طور مثال گراف H در شکل 20 همبند و گراف G ناهمبند است زیرا مثال ًبین رئوس v و w هیچ مسیری وجود ندارد.شکل 20فعالیت1 سه گراف دلخواه رسم کنید.٢ مجموع درجات رئوس هر یک از 3 گرافی را که رسم کرده اید محاسبه کنید.٣ تعداد یال های هر یک از 3 گراف را محاسبه نمایید.٤ حدس می‌زنید چه رابطه ای بین تعداد یال ها و مجموع درجات رئوس یک گراف وجود دارد.٥ پاسخ خود را با دوستانتان مطرح کرده و در این باره بحث کنید.فعالیت1 یک گراف دلخواه مانند G با n ِ رأس ..., v 2, v 1 و v n و m یال ..., e 2, e 1 و e m در نظر بگیرید.٢ تمام یال های گراف G را حذف کنید.٣ مجموع درجات تمام رئوس گراف حاصل چند است؟ تعداد یال های گراف حاصل چند است و این دو عدد چه ارتباطیبا هم دارند؟٤ یال e 1 را در جای خود (بین همان دو رأسی که e 1 قبل از حذف شدن بین آنها قرار داشت) قرار دهید و به سؤال 3جواب دهید.٥ تمام یال های ..., e 3, e 2 و e m را یکی یکی در جای خود قرار دهید تا به گراف ٔ اولیه G برسید و پس از اضافه کردن هریال مجدد ً ا برای گراف جدید ساخته شده به سؤال 3 جواب دهید.٦ آیا مجموع درجات رئوس یک گراف می‌تواند عددی فرد باشد؟ چرا؟٧ برای تساوی m 2 + deg(= v n( + n deg =) v i(deg) v 1 (+ deg) v 2) ∑ استدالل خود را بیان نمایید.1 = iبا توجه به آنچه در این فعالیت به دست آوردیم، می‌توان ٔ قضیه زیر را بیان نمود.قضیه: اگر G یک گراف با ٔ مرتبه p و ٔ اندازه q و } v 1, v 2, ..., v p { V = ٔ مجموعه رئوس آن باشند، آنگاه:q 2 = i v deg ∑1 = i39 درس ا ّ و ل: معرفی گراف