مقاطع تحصیلی
جستجو در منظومه
مسئله :1 اگر G یک گراف با n رأس و v یک ِ رأس آن باشد و G d(v) و G d(v) به ترتیب ٔ درجه رأس v در گراف هایG و G باشند، مقدار G d(v(G d +) v) را به دست آورید.مسئله :2 یک گراف n رأسی حداکثر چند یال می‌تواند داشته باشد؟مسئله :3 اگر G یک گراف n رأسی باشد، مقدار q(G(q +) G) را به دست آورید.گراف کامل: گرافی را که هر رأس آن با تمام ِ رئوس ِ دیگر ، مجاور باشد گراف کامل می‌نامیم. گراف ِ کامل n رأسی را باK n نمایش می‌دهیم. می‌توان گفت K n یک گراف n رأسی و n - 1 ــ منتظم است.مسئله :1 یک گراف کامل p رأسی چند یال دارد؟مسئله :2 اگر G یک گراف p رأسی باشد، چه رابطه ای بین تعداد یال های گراف های G ، G و K p وجود دارد؟مسئله :3 مکمل گراف کامل چه نوع گرافی است؟مسیر: اگر u و v دو رأس از گراف G باشند، یک مسیر از u به v(یک v ــ u مسیر) در G دنباله ای از رئوس دوبه دومتمایز در G است که از u شروع و به v ختم می‌شود به طوری که هر دو رأس متوالی این دنباله در G مجاور هم باشند. طولیک مسیر برابر است با تعداد یال های موجود در آن مسیر (یکی کمتر از تعداد رئوس موجود در آن مسیر). قرارداد می‌کنیم کهٔ دنباله متشکل از تنها یک ِ رأس v ، یک مسیر است با طول صفر از رأس v به خودش.مثالuwv یک v ــ u مسیر به طول 2 است.u z y wv یک v ــ u مسیر به طول 4 است.شکل 17گرافی را که تنها از یک مسی ِ ر n رأسی تشکیل شده باشد با P n نمایش می‌دهیم.به طور مثال P 5 در شکل 18 نمایش داده شده است. شکل 18دور: ٔ دنباله v 1 v 2 v 3 ... v n v 1 3 (≥)n از رئوس دو به دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یکدور به طول n می‌نامیم. به طور مثال در گراف شکل u v w u 17 ، y w u z y ، x w v u z y x دورهایی به ترتیب با طول 3 و 4 و 6هستند.گرافی را که تنها از یک دو ِ ر n رأسی تشکیل شده باشد را با C n نمایش می‌دهیم.به طور مثال C 5 در شکل 19 نمایش داده شده است.مسئله: در گراف شکل ،17 دوری به طول 5 بیابید. شکل 19فصل دوم: گراف و مدل سازی 38