Induced subgraph
આલેખ સિદ્ધાંતના ગાણિતિક ક્ષેત્રમાં, આલેખનો પ્રેરિત પેટા આલેખ એ બીજો આલેખ છે, જે આલેખના શિરોબિંદુઓના સબસેટ અને તે સબસેટમાં શિરોબિંદુઓની જોડીને જોડતી તમામ ધાર (મૂળ ગ્રાફમાંથી) માંથી બનેલો છે. વ્યાખ્યા ઔપચારિક રીતે, કોઈપણ આલેખ હોવો જોઈએ, અને તેના શિરોબિંદુઓનો કોઈપણ સબસેટ હોવો જોઈએ. પછી પ્રેરિત સબગ્રાફ એ આલેખ છે જેનો શિરોબિંદુ સમૂહ છે અને જેની ધાર સમૂહમાં તમામ ધારોનો સમાવેશ થાય છે જેમાં બંને અંતિમ બિંદુઓ હોય છે. એટલે કે, કોઈપણ બે શિરોબિંદુઓ માટે, અને જો અને માત્ર જો તેઓ અડીને હોય તો જ અડીને આવે છે. આ જ વ્યાખ્યા દિશાહીન આલેખ, નિર્દેશિત આલેખ અને બહુલેખન માટે પણ કામ કરે છે. પ્રેરિત સબગ્રાફને પ્રેરિત સબગ્રાફ પણ કહી શકાય, અથવા (જો સંદર્ભ અસંદિગ્ધની પસંદગી કરે છે) પ્રેરિત સબગ્રાફ. ઉદાહરણો પ્રેરિત સબગ્રાફ્સના મહત્વપૂર્ણ પ્રકારોમાં નીચેનાનો સમાવેશ થાય છે. પ્રેરિત માર્ગો પ્રેરિત સબગ્રાફ્સ છે જે પાથ છે. ભાર વગરના આલેખમાં કોઈપણ બે શિરોબિંદુઓ વચ્ચેનો સૌથી ટૂંકો માર્ગ હંમેશા પ્રેરિત માર્ગ હોય છે, કારણ કે શિરોબિંદુઓની જોડી વચ્ચેની કોઈપણ વધારાની ધાર જે તેને પ્રેરિત ન કરી શકે તે પણ તેને ટૂંકો નહીં કરે. તેનાથી વિપરીત, અંતર-વંશપરંપરાગત આલેખમાં, દરેક પ્રેરિત માર્ગ ટૂંકો માર્ગ છે. પ્રેરિત ચક્ર એ પ્રેરિત સબગ્રાફ છે જે ચક્ર છે. આલેખનો ઘેરો તેના સૌથી ટૂંકા ચક્રની લંબાઈ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે, જે હંમેશા પ્રેરિત ચક્ર હોય છે. મજબૂત સંપૂર્ણ આલેખ પ્રમેય અનુસાર, પ્રેરિત ચક્ર અને તેમના પૂરક સંપૂર્ણ આલેખની લાક્ષણિકતામાં નિર્ણાયક ભૂમિકા ભજવે છે. ક્લીક અને સ્વતંત્ર સમૂહો પ્રેરિત સબગ્રાફ છે જે અનુક્રમે સંપૂર્ણ ગ્રાફ અથવા ધાર વિનાના ગ્રાફ છે. પ્રેરિત મેચિંગ એ પ્રેરિત સબગ્રાફ છે જે મેચિંગ છે. શિરોબિંદુની પડોશ એ તેની નજીકના તમામ શિરોબિંદુઓનો પ્રેરિત સબગ્રાફ છે. ગણતરી પ્રેરિત સબગ્રાફ આઇસોમોર્ફિઝમ સમસ્યા એ સબગ્રાફ આઇસોમોર્ફિઝમ સમસ્યાનું એક સ્વરૂપ છે જેમાં ધ્યેય એ ચકાસવાનું છે કે શું એક આલેખ બીજાના પ્રેરિત સબગ્રાફ તરીકે મળી શકે છે કે કેમ. કારણ કે તેમાં ખાસ કેસ તરીકે જૂથની સમસ્યાનો સમાવેશ થાય છે, તે એન. પી.-પૂર્ણ છે. સંદર્ભો આલેખ કામગીરી આલેખ સિદ્ધાંત પદાર્થો