Core (graph theory)
ગ્રાફ થિયરીના ગાણિતિક ક્ષેત્રમાં, કોર એ એક કલ્પના છે જે ગ્રાફ હોમોમોર્ફિઝમ્સના સંદર્ભમાં ગ્રાફના વર્તનનું વર્ણન કરે છે. વ્યાખ્યા ગ્રાફ એ એક કોર છે જો દરેક હોમોમોર્ફિઝમ એક આઇસોમોર્ફિઝમ છે, એટલે કે તે તેના શિરોબિંદુઓનું દ્વિભાજન છે. આલેખનો મુખ્ય ભાગ એ આલેખ છે કે જ્યાં થી થી હોમોમોર્ફિઝમ અસ્તિત્વમાં છે, ત્યાં થી થી હોમોમોર્ફિઝમ અસ્તિત્વમાં છે, અને આ ગુણધર્મ સાથે ન્યૂનતમ છે. જો બે આલેખમાં સમરૂપતા કોર હોય તો તેને સમરૂપતા સમકક્ષ અથવા સમતુલ્ય કહેવામાં આવે છે. ઉદાહરણો કોઈપણ સંપૂર્ણ આલેખ એક કોર છે. વિષમ લંબાઈનું ચક્ર એ કોર છે. ગ્રાફ એ કોર છે જો અને માત્ર ત્યારે જ જ્યારે તેનો કોર સમાન હોય. સમ લંબાઈના દરેક બે ચક્ર, અને વધુ સામાન્ય રીતે દરેક બે દ્વિપક્ષી આલેખ સમ-સમકક્ષ હોય છે. આ દરેક આલેખનો મુખ્ય ભાગ બે-શિરોબિંદુ સંપૂર્ણ આલેખ K2 છે. બેકમેન-ક્વેર્લ્સ પ્રમેય અનુસાર, યુક્લિડિયન સમતલના તમામ બિંદુઓ પર અથવા કોઈપણ ઉચ્ચ-પરિમાણીય યુક્લિડિયન અવકાશનો અનંત એકમ અંતર આલેખ એક કોર છે. ગુણધર્મો દરેક મર્યાદિત આલેખમાં એક કોર હોય છે, જે આઇસોમોર્ફિઝમ સુધી અનન્ય રીતે નક્કી થાય છે. ગ્રાફ G નો મુખ્ય ભાગ હંમેશા G નો પ્રેરિત સબગ્રાફ હોય છે. જો અને પછી ગ્રાફ અને આવશ્યકપણે હોમોમોર્ફિકલી સમકક્ષ હોય. કોમ્પ્યુટેશનલ જટિલતા એ ચકાસવા માટે એન. પી.-પૂર્ણ છે કે શું ગ્રાફમાં યોગ્ય સબગ્રાફ માટે હોમોમોર્ફિઝમ છે, અને સહ-એન. પી.-પૂર્ણ છે કે કેમ તે ચકાસવા માટે કે શું ગ્રાફ તેનો પોતાનો મુખ્ય ભાગ છે (એટલે કે. શું આવું કોઈ હોમોમોર્ફિઝમ અસ્તિત્વમાં નથી). સંદર્ભો ગોડસિલ, ક્રિસ અને રોયલે, ગોર્ડન. બીજગણિત આલેખ સિદ્ધાંત. ગણિતમાં ગ્રેજ્યુએટ ટેક્સ્ટ્સ, વોલ્યુમ. 207. સ્પ્રિંગર-વેરલેગ, ન્યૂયોર્ક, 2001. પ્રકરણ 6 વિભાગ 2. . આલેખ સિદ્ધાંત પદાર્થો