Cactus graph
આલેખ સિદ્ધાંતમાં, કેક્ટસ (કેટલીકવાર કેક્ટસ વૃક્ષ તરીકે ઓળખાય છે) એ એક જોડાયેલ આલેખ છે જેમાં કોઈપણ બે સરળ ચક્રમાં મહત્તમ એક શિરોબિંદુ સામાન્ય હોય છે. સમાનરૂપે, તે એક જોડાયેલ આલેખ છે જેમાં દરેક ધાર વધુમાં વધુ એક સરળ ચક્ર સાથે સંબંધિત છે, અથવા (બિન-તુચ્છ કેક્ટી માટે) જેમાં દરેક બ્લોક (કટ-વર્ટેક્સ વિના મહત્તમ સબગ્રાફ) એક ધાર અથવા ચક્ર છે. ગુણધર્મો કેક્ટી બાહ્ય સમતલ આલેખ છે. દરેક સ્યુડોટ્રી એક કેક્ટસ છે. બિન-તુચ્છ આલેખ એ કેક્ટસ છે જો અને માત્ર ત્યારે જ જો દરેક બ્લોક કાં તો એક સરળ ચક્ર અથવા એક જ ધાર હોય. આલેખનો પરિવાર જેમાં દરેક ઘટક કેક્ટસ છે તે આલેખની નાની કામગીરી હેઠળ નીચે તરફ બંધ કરવામાં આવે છે. આ આલેખ કુટુંબને એક પ્રતિબંધિત નાના, સંપૂર્ણ આલેખ K4 માંથી ધારને દૂર કરીને રચાયેલ ચાર-શિરોબિંદુ હીરાના આલેખ દ્વારા વર્ગીકૃત કરી શકાય છે. ત્રિકોણાકાર કેક્ટસ ત્રિકોણાકાર કેક્ટસ એ એક ખાસ પ્રકારનો કેક્ટસ ગ્રાફ છે જેમ કે દરેક ચક્રની લંબાઈ ત્રણ હોય છે અને દરેક ધાર એક ચક્રની હોય છે. દાખલા તરીકે, મિત્રતા આલેખ, ત્રિકોણના સંગ્રહમાંથી રચાયેલા આલેખ, એક વહેંચાયેલ શિરોબિંદુ પર એક સાથે જોડાયેલા, ત્રિકોણાકાર કેક્ટી છે. કેક્ટસ આલેખ હોવા ઉપરાંત ત્રિકોણાકાર કેક્ટી પણ બ્લોક આલેખ અને સ્થાનિક રીતે રેખીય આલેખ છે. ત્રિકોણાકાર કેક્ટસમાં એવો ગુણધર્મ હોય છે કે જો તેમની પાસેથી કોઈ મેળ દૂર કરવામાં આવે તો તેઓ જોડાયેલા રહે છે; શિરોબિંદુઓની આપેલ સંખ્યા માટે, તેમની પાસે આ ગુણધર્મ સાથે શક્ય તેટલી ઓછી ધાર હોય છે. વિચિત્ર સંખ્યામાં શિરોબિંદુઓ ધરાવતા દરેક વૃક્ષને તેની ધાર ઉમેરીને ત્રિકોણાકાર કેક્ટસમાં વધારી શકાય છે, જે બંધબેસતા વૃક્ષને દૂર કર્યા પછી જોડાયેલા રહેવાના ગુણધર્મ સાથે ન્યૂનતમ વૃદ્ધિ આપે છે. કોઈપણ આલેખમાં સૌથી મોટું ત્રિકોણાકાર કેક્ટસ બહુપદી સમયમાં મેટ્રોઇડ પેરિટી સમસ્યા માટે અલ્ગોરિધમનો ઉપયોગ કરીને મળી શકે છે. ત્રિકોણાકાર કેક્ટસ આલેખ સમતલીય આલેખ હોવાથી, સૌથી મોટા ત્રિકોણાકાર કેક્ટસનો ઉપયોગ સૌથી મોટા સમતલીય સબગ્રાફના અંદાજ તરીકે થઈ શકે છે, જે સમતલીકરણમાં એક મહત્વપૂર્ણ પેટા સમસ્યા છે. અંદાજિત અલ્ગોરિધમ તરીકે, આ પદ્ધતિ અંદાજિત ગુણોત્તર 4/9 ધરાવે છે, જે મહત્તમ સમતલીય સબગ્રાફ સમસ્યા માટે જાણીતી છે. સૌથી મોટા ત્રિકોણાકાર કેક્ટસને શોધવા માટેનું અલ્ગોરિધમ લોવેઝ અને પ્લમરના પ્રમેય સાથે સંકળાયેલું છે જે આ સૌથી મોટા કેક્ટસમાં ત્રિકોણની સંખ્યાને દર્શાવે છે. લવાસ્ઝ અને પ્લમર આપેલ આલેખના શિરોબિંદુઓ અને ધારોના પાર્ટીશનોની જોડીને ઉપગણમાં ધ્યાનમાં લે છે, આ ગુણધર્મ સાથે કે આલેખના દરેક ત્રિકોણમાં કાં તો શિરોબિંદુ પાર્ટીશનના એક વર્ગમાં બે શિરોબિંદુઓ હોય છે અથવા ધાર પાર્ટીશનના એક વર્ગમાં ત્રણેય ધાર હોય છે; તેઓ આ ગુણધર્મ સાથે પાર્ટીશનોની જોડીને માન્ય કહે છે. પછી સૌથી મોટા ત્રિકોણાકાર કેક્ટસમાં ત્રિકોણની સંખ્યા મહત્તમ, માન્ય પાર્ટીશનોની જોડીની બરાબર હોય છે અને, જ્યાં આપેલ આલેખમાં શિરોબિંદુઓની સંખ્યા છે અને ધાર વર્ગ દ્વારા મળેલા શિરોબિંદુ વર્ગોની સંખ્યા છે. દરેક સમતલ આલેખમાં કેક્ટસ સબગ્રાફ હોય છે જેમાં કેક્ટસના ત્રિકોણાકાર ચહેરાનો ઓછામાં ઓછો અપૂર્ણાંક હોય છે. આ પરિણામ ઉપરોક્ત લઘુતમ-મહત્તમ સૂત્રનો ઉપયોગ કર્યા વિના મહત્તમ સમતલીય સબગ્રાફ સમસ્યા માટે 4/9-અંદાજિત અલ્ગોરિધમનું સીધું વિશ્લેષણ સૂચવે છે. રોઝાનું અનુમાન ત્રિકોણાકાર કેક્ટસ સાથે સંબંધિત એક મહત્વપૂર્ણ અનુમાન રોઝાનું અનુમાન છે, જેનું નામ એલેક્ઝાન્ડર રોઝાના નામ પરથી રાખવામાં આવ્યું છે, જે કહે છે કે તમામ ત્રિકોણાકાર કેક્ટી આકર્ષક અથવા લગભગ-ઉદાર છે. વધુ સ્પષ્ટ રીતે કહીએ તો t ષ્ણ 0,1 મોડ 4 બ્લોક ધરાવતી તમામ ત્રિકોણાકાર કેક્ટી આકર્ષક હોય છે, અને t ષ્ણ 2,3 મોડ 4 ધરાવતી કેક્ટી આકર્ષક હોય છે. અલ્ગોરિધમ્સ અને એપ્લિકેશન્સ કેટલીક સુવિધા સ્થાન સમસ્યાઓ કે જે સામાન્ય આલેખ માટે એન. પી.-હાર્ડ છે, તેમજ કેટલીક અન્ય આલેખ સમસ્યાઓ, કેક્ટી માટે બહુપદી સમયમાં ઉકેલી શકાય છે. કેક્ટી બાહ્ય સમતલ આલેખના વિશેષ કિસ્સાઓ હોવાથી, આલેખ પરની સંખ્યાબંધ સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓ તેમના માટે બહુપદી સમયમાં ઉકેલી શકાય છે. કેક્ટી વિદ્યુત પરિપથોનું પ્રતિનિધિત્વ કરે છે જે ઉપયોગી ગુણધર્મો ધરાવે છે. કેક્ટીનો પ્રારંભિક ઉપયોગ ઓપ-એમ્પ્સની રજૂઆત સાથે સંકળાયેલો હતો. કેક્ટીનો ઉપયોગ તુલનાત્મક જીનોમિક્સમાં વિવિધ જીનોમ અથવા જીનોમના ભાગો વચ્ચેના સંબંધને રજૂ કરવાની રીત તરીકે પણ કરવામાં આવે છે. જો કેક્ટસ જોડાયેલ હોય અને તેના દરેક શિરોબિંદુ મહત્તમ બે બ્લોકના હોય, તો તેને ક્રિસમસ કેક્ટસ કહેવામાં આવે છે. દરેક પોલિહેડ્રલ ગ્રાફમાં ક્રિસમસ કેક્ટસ સબગ્રાફ હોય છે જેમાં તેના તમામ શિરોબિંદુઓનો સમાવેશ થાય છે, એક હકીકત જે સાબિતીમાં આવશ્યક ભૂમિકા ભજવે છે કે દરેક પોલિહેડ્રલ ગ્રાફમાં યુક્લિડિયન પ્લેનમાં લોભી એમ્બેડિંગ હોય છે, જે શિરોબિંદુઓને કોઓર્ડિનેટ્સની સોંપણી છે, જેના માટે લોભી ફોરવર્ડિંગ શિરોબિંદુઓની તમામ જોડી વચ્ચેના સંદેશાઓને રૂટ કરવામાં સફળ થાય છે. ટોપોલોજિકલ ગ્રાફ થિયરીમાં, જે આલેખના સેલ્યુલર એમ્બેડિંગ્સ બધા સમતલીય હોય છે તે બરાબર કેક્ટસ ગ્રાફના સબફૅમિલી છે, જેમાં દરેક શિરોબિંદુ મહત્તમ એક ચક્ર સાથે સંબંધિત હોય છે. આ આલેખમાં બે પ્રતિબંધિત નાના અક્ષરો છે, હીરાનો આલેખ અને પાંચ-અક્ષતંતુ મિત્રતા આલેખ. ઇતિહાસ કેક્ટીનો સૌપ્રથમ હુસિમી વૃક્ષોના નામ હેઠળ અભ્યાસ કરવામાં આવ્યો હતો, જે તેમને ફ્રેન્ક હરારી અને જ્યોર્જ યુજીન ઉહલેનબેક દ્વારા આ આલેખ પરના અગાઉના કાર્યના માનમાં આપવામાં આવ્યા હતા. એ જ હેરારી-ઉહલેનબેક પેપરમાં આ પ્રકારના આલેખ માટે "કેક્ટસ" નામ અનામત રાખવામાં આવ્યું છે જેમાં દરેક ચક્ર ત્રિકોણ છે, પરંતુ હવે તમામ લંબાઈના ચક્રને મંજૂરી આપવી એ પ્રમાણભૂત છે. દરમિયાન, હુસિમી વૃક્ષ નામ સામાન્ય રીતે એવા આલેખનો સંદર્ભ આપવા માટે આવ્યું છે જેમાં દરેક બ્લોક સંપૂર્ણ આલેખ હોય છે (સમકક્ષ રીતે, અમુક અન્ય આલેખમાં બ્લોકના આંતરછેદના આલેખ). આ ઉપયોગનો હુસિમીના કામ સાથે બહુ ઓછો સંબંધ હતો, અને વધુ સુસંગત શબ્દ બ્લોક ગ્રાફનો ઉપયોગ હવે આ પરિવાર માટે થાય છે; જો કે, આ અસ્પષ્ટતાને કારણે આ શબ્દસમૂહ કેક્ટસ ગ્રાફનો સંદર્ભ આપવા માટે ઓછો વારંવાર ઉપયોગમાં લેવાય છે. સંદર્ભો બાહ્ય કડીઓ ઇલેક્ટ્રોનિક સર્કિટના વિશ્લેષણ અને ડિઝાઇનમાં કેક્ટસ ગ્રાફનો ઉપયોગ ગ્રાફ પરિવારો પ્લાનર ગ્રાફ સંકલિત સર્કિટ