مقاطع تحصیلی
جستجو در منظومه
توجه: برای رسم نمودار یک گراف (شکل گراف) روش یکتایی مدنظر نیست. آنچه مهم است این است که باید مشخصباشد که گراف مورد نظر چند رأس و چند یال دارد و کدام یال به کدام رئوس متصل است. به طور مثال با نوشتن مجموعه هایV(G) و E(G) برای هر یک از شکل های زیر، نشان دهید هر دو یک گراف را نمایش می‌دهند.شکل 7} { = V(G 1 (= { } V) G 2)} { = E(G 1 (= { } E) G 2)مرتبه و اندازۀ یک گراف: تعداد رأس های گراف G یعنی V(G) را ٔ مرتبه آن گراف می‌گوییم و با p(G) نمایشمی‌دهیم و تعداد یال های گراف یعنی E(G) را ٔ اندازه گراف G می‌گوییم و با q(G) نمایش می‌دهیم. معموال ً برای راحتی کاربه جای p(G) از p و به جای q(G) از q استفاده می‌کنیم. به طور مثال گراف های نمایش داده شده در شکل 7 از ٔ مرتبه 5 ؤ اندازه 6 هستند. بنابراین p = 5 و . q = 6درجۀ یک رأس: ٔ درجه رأس v در گراف G برابر است با تعداد یال هایی ازگراف G که به رأس v متصل اند و آن را با G deg(v) یا به طور ساده تر با deg(v) یاd(v) نمایش می‌دهیم. اگر ٔ درجه یک رأس فرد باشد آن را رأس فرد و اگر زوج باشدآن را رأس زوج می‌نامیم. به طور مثال در شکل مقابل داریم:4 = deg(v 1 (= 3, deg) v 5)شکل 8گراف K ـ منتظم: گرافی را که ٔ درجه تمام رئوس آن با هم مساوی و برابر با عدد k باشند،گراف - k منتظم می‌نامیم. مثال ً گراف شکل 9 یک گراف 6 ِ رأسی - 3 منتظم است.رأس تنها: به رأسی که ٔ درجه آن صفر باشد؛ یعنی هیچ یالی به آن متصل نباشد، رأس تنها (یا شکل 9ایزوله) می‌گوییم.گرافی را که تمام رئوس آن رأس تنها باشند، یعنی هیچ یالی نداشته باشد، گراف تهی می‌نامیم. بنابراین منظور از گرافِ تهی n رأسی، گرافی شامل n ِ رأس تنها و بدون یال است.35 درس ا ّ و ل: معرفی گراف