Кіріспе
График, басқа графиктің түйіндерінің және олардың жиектерінің ішкі жиынынан құрылған. Графтар теориясының математикалық саласында, графиктің индукцияланған ішкі графигі – бұл берілген графиктің түйіндерінің ішкі жиынынан және бастапқы графикте сол ішкі жиынға кіретін түйіндерді байланыстыратын барлық жиектерінен тұратын жаңа график.
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset.
Анықтама
Формальды түрде, кез келген граф болсын, G графының кез келген төбелерінің жиынтығы болсын. Онда индуцирленген субграф – бұл төбелер жиынтығы және шеттері G графының екі ұшы да сол жиынтықта болатын барлық шеттерден тұратын граф. Яғни, кез келген екі төбе үшін, егер және тек қана олар G-да жанындас болса, олар да жанындас болады. Осы анықтама бағытталған графтар, бағытталмаған графтар және тіпті көп графтар үшін де қолданылады. Индуцирленген субграфты сонымен қатар , немесе (контекст таңдауды нақтылайтын болса) субграф деп те атауға болады.
Мысалдар
Индуцированды субграфтардың маңызды түрлеріне мыналар жатады. Индукцияланған жолдар – жолдар болып табылатын индуцированды субграфтар. Салмағы жоқ графтың кез келген екі төбесі арасындағы ең қысқа жол әрқашан индуцированған жол болады, себебі оны индуцированбауға себеп болатын төбелер жұбы арасындағы кез келген қосымша қабырға оны ең қысқа болмайтындай етеді. Керісінше, арақашықтық мұрагерлік графтарда әрбір индуцированған жол ең қысқа жол болып табылады. Индукцияланған циклдар – циклдар болып табылатын индуцированды субграфтар. Графтың айналымы оның ең қысқа циклының ұзындығымен анықталады, ол әрқашан индуцированған цикл болады. Күшті толыққанды граф теоремасына сәйкес, индуцированған циклдар және олардың толықтырулары толыққанды графтарды сипаттауда маңызды рөл атқарады. Кликелер және тәуелсіз жиынтықтар – тиісінше толық графтар немесе қабырғасыз графтар болып табылатын индуцированды субграфтар. Индукцияланған сәйкестіктер – сәйкестіктер болып табылатын индуцированды субграфтар. Төбеге жақын маң – оған жақын барлық төбелердің индуцированды субграфы.
Есептеу
Индуцированный субграф изоморфизм мәселесі – субграф изоморфизм мәселесінің бір түрі, онда бір графты екінші графтың индуцированный субграфигі ретінде табуға болатынын анықтау қажет. Ол клика мәселесін ерекше жағдай ретінде қамтиды, сондықтан ол NP-толық.