درس یازدهم: زير گراف یا Subgraph

گراف  G را در نظر می گيريم. هر گرافی که مجموعه رئوسش زير مجموعه ای ناتهی از V(G) و مجموعه يالهايش زير مجموعه ای (نه لزوماً ناتهی) از  E(G) باشد را زير گرافی از گراف  G می ناميم. زير گراف فراگير گراف  G، گرافی است که مجموعه رئوسش دقيقاً مساوی با  V(G) باشد. و زيرگراف القايي گراف  G، زير گرافی است که به ازای هر يال موجود در G اگر دو انتهای يال عضو مجموعه رئوس زيرگراف مزبور باشند، آنگاه آن يال حتماً در زيرگراف موجود باشد.

مسئله : تعدادی کامپيوتر در يک مکان موجود است. هر کامپيوتر با يک يا چند کابل رابط به کامپيوترهای ديگر متصل است و بين هر دو کامپيوتر بيش از يک سيم وجود ندارد. در بين اين کامپيوترها هيچ کامپيوتری پيدا نمی شود که به آن هيچ کابل رابطی متصل نباشد. همچنين اگر هر دسته سه تايی از اين کامپيوترها را در نظر بگيريم هيچ گاه دقيقا دو کابل رابط بين آنها وجود ندارد.آيا می توان گفت هر کامپيوتر به همه کامپيوترهای ديگر متصل است؟