Partial cube
આલેખ સિદ્ધાંતમાં, આંશિક સમઘન એ એક આલેખ છે જે હાયપરક્યુબના સબગ્રાફ માટે સમમિતિય છે. બીજા શબ્દોમાં કહીએ તો, આંશિક સમઘનને હાયપરક્યુબના સબગ્રાફથી એવી રીતે ઓળખી શકાય છે કે આંશિક સમઘનમાં કોઈપણ બે શિરોબિંદુઓ વચ્ચેનું અંતર હાયપરક્યુબના તે શિરોબિંદુઓ વચ્ચેનું અંતર જેટલું જ હોય. સમાનરૂપે, આંશિક સમઘન એ એક આલેખ છે જેના શિરોબિંદુઓને સમાન લંબાઈના બીટ શબ્દમાળાઓ સાથે એવી રીતે લેબલ કરી શકાય છે કે આલેખમાં બે શિરોબિંદુઓ વચ્ચેનું અંતર તેમના લેબલ વચ્ચેના હેમિંગ અંતર જેટલું હોય. આવા લેબલિંગને હેમિંગ લેબલિંગ કહેવામાં આવે છે; તે હાયપરક્યુબમાં આંશિક સમઘનના આઇસોમેટ્રિક એમ્બેડિંગને રજૂ કરે છે. હાયપરક્યુબ્સમાં ગ્રાફના આઇસોમેટ્રિક એમ્બેડિંગનો અભ્યાસ કરનાર ઇતિહાસ સૌપ્રથમ હતો. આલેખ કે જે આવા એમ્બેડિંગ્સને સ્વીકારે છે તે અને દ્વારા વર્ગીકૃત કરવામાં આવ્યા હતા, અને પછીથી તેને આંશિક સમઘનનું નામ આપવામાં આવ્યું હતું. ગ્રાફના હાયપરક્યુબ લેબલિંગને બદલે સમૂહોના પરિવારોની પરિભાષામાં સમાન માળખાઓ પર સંશોધનની એક અલગ લાઇન, અને, અન્ય લોકો વચ્ચે અનુસરવામાં આવી હતી. ઉદાહરણો દરેક વૃક્ષ આંશિક સમઘન છે. કારણ કે, ધારો કે વૃક્ષની ધાર હોય છે, અને આ ધારને (મનસ્વી રીતે) થી સુધી ક્રમાંકિત કરો. વૃક્ષ માટે એક મૂળ શિરોબિંદુ પસંદ કરો, અને દરેક શિરોબિંદુને બિટ્સની સ્ટ્રિંગ સાથે લેબલ કરો કે જે 1 ની સ્થિતિમાં હોય જ્યારે પણ ધાર એકથી અંદરના માર્ગ પર હોય. દાખલા તરીકે, પોતે એક લેબલ હશે જે બધા શૂન્ય બિટ્સ હશે, તેના પડોશીઓ પાસે એક જ 1-બીટ સાથે લેબલ હશે, વગેરે. પછી કોઈપણ બે લેબલ વચ્ચેનું હેમિંગ અંતર એ વૃક્ષમાં બે શિરોબિંદુઓ વચ્ચેનું અંતર છે, તેથી આ લેબલિંગ બતાવે છે કે તે આંશિક સમઘન છે. દરેક હાયપરક્યુબ આલેખ પોતે આંશિક સમઘન છે, જેને હાયપરક્યુબના પરિમાણની સમાન લંબાઈના તમામ વિવિધ બિટસ્ટ્રિંગ્સ સાથે લેબલ કરી શકાય છે. વધુ જટિલ ઉદાહરણોમાં નીચેનાનો સમાવેશ થાય છેઃ આલેખનો વિચાર કરો કે જેના શિરોબિંદુ લેબલોમાં તમામ સંભવિત-અંકના બિટસ્ટ્રિંગ્સ હોય છે જેમાં કાં તો અથવા બિન-શૂન્ય બિટ્સ હોય છે, જ્યાં જ્યારે પણ તેમના લેબલ્સ એક બીટથી અલગ હોય ત્યારે બે શિરોબિંદુઓ અડીને હોય છે. આ લેબલિંગ આ આલેખના હાયપરક્યુબ (આપેલ લંબાઈના તમામ બિટસ્ટ્રિંગ્સનો ગ્રાફ, સમાન નિકટતા-સ્થિતિ સાથે) માં એમ્બેડિંગને વ્યાખ્યાયિત કરે છે જે અંતર-જાળવણી હોવાનું બહાર આવે છે. પરિણામી આલેખ એ દ્વિપક્ષી નેસર આલેખ છે; આ રીતે રચાયેલા આલેખમાં 20 શિરોબિંદુઓ અને 30 ધાર હોય છે, અને તેને ડેસારગ્યુસ આલેખ કહેવામાં આવે છે. બધા મધ્યસ્થ આલેખ આંશિક સમઘન છે. વૃક્ષો અને હાયપરક્યુબ આલેખ મધ્યમ આલેખના ઉદાહરણો છે. મધ્યસ્થ આલેખમાં ચોરસ આલેખ, સિમ્પ્લેક્સ આલેખ અને ફિબોનાકી સમઘનનો સમાવેશ થાય છે, તેમજ મર્યાદિત વિતરણ જાળીઓના આવરણ આલેખનો સમાવેશ થાય છે, આ બધા આંશિક સમઘન છે. યુક્લિડિયન સમતલમાં રેખાઓની ગોઠવણીનો સમતલીય બેવડો આલેખ આંશિક સમઘન છે. વધુ સામાન્ય રીતે, યુક્લિડિયન અવકાશમાં કોઈપણ સંખ્યામાં પરિમાણોની કોઈપણ હાયપરપ્લેન ગોઠવણી માટે, ગોઠવણીના દરેક કોષ માટે શિરોબિંદુ અને દરેક બે અડીને આવેલા કોષો માટે ધાર ધરાવતો આલેખ આંશિક સમઘન છે. એક આંશિક સમઘન જેમાં દરેક શિરોબિંદુ બરાબર ત્રણ પડોશીઓ ધરાવે છે તેને સમઘન આંશિક સમઘન તરીકે ઓળખવામાં આવે છે. ક્યુબિક આંશિક સમઘનના ઘણા અનંત પરિવારો જાણીતા હોવા છતાં, અન્ય ઘણા છૂટાછવાયા ઉદાહરણો સાથે, એકમાત્ર જાણીતા ક્યુબિક આંશિક સમઘન કે જે સમતલીય આલેખ નથી તે ડેસારગ્યુસ આલેખ છે. કોઈપણ એન્ટિમેટ્રોઇડનો અંતર્ગત આલેખ, જેમાં એન્ટિમેટ્રોઇડમાં દરેક સમૂહ માટે શિરોબિંદુ હોય છે અને દરેક બે સમૂહ માટે એક ધાર હોય છે જે એક તત્વ દ્વારા અલગ પડે છે, તે હંમેશા આંશિક સમઘન હોય છે. આંશિક સમઘનના કોઈપણ મર્યાદિત સમૂહનું કાર્ટેશિયન ઉત્પાદન અન્ય આંશિક સમઘન છે. સંપૂર્ણ આલેખનો પેટા વિભાગ આંશિક સમઘન છે જો અને માત્ર ત્યારે જ જો દરેક સંપૂર્ણ આલેખ ધારને બે ધારવાળા માર્ગમાં વિભાજિત કરવામાં આવે, અથવા એક સંપૂર્ણ આલેખ શિરોબિંદુ હોય જેની ઘટના ધાર બધી અવિભાજિત હોય અને તમામ બિન-ઘટના ધારને સમ-લંબાઈના માર્ગમાં વિભાજિત કરવામાં આવી હોય. જોકોવિક-વિંકલર સંબંધ આંશિક સમઘન વિશેના ઘણા પ્રમેયો ગ્રાફની ધાર પર વ્યાખ્યાયિત ચોક્કસ દ્વિસંગી સંબંધ પર પ્રત્યક્ષ અથવા પરોક્ષ રીતે આધારિત છે. આ સંબંધ, પ્રથમ દ્વારા વર્ણવવામાં આવે છે અને દ્વારા અંતરની દ્રષ્ટિએ સમકક્ષ વ્યાખ્યા આપવામાં આવે છે, દ્વારા સૂચવવામાં આવે છે. બે ધાર અને સંબંધમાં વ્યાખ્યાયિત કરવામાં આવે છે, લેખિત, જો. આ સંબંધ પ્રતિબિંબીત અને સપ્રમાણ છે, પરંતુ સામાન્ય રીતે તે સંક્રમક નથી. વિંકલરે દર્શાવ્યું હતું કે જોડાયેલ આલેખ આંશિક સમઘન છે જો અને માત્ર ત્યારે જ જો તે દ્વિપક્ષી હોય અને સંબંધ સંક્રમક હોય. આ કિસ્સામાં, તે એક સમાનતા સંબંધ બનાવે છે અને દરેક સમાનતા વર્ગ આલેખના બે જોડાયેલા પેટા આલેખને એકબીજાથી અલગ કરે છે. જેકોવિક-વિંકલર સંબંધના દરેક સમકક્ષ વર્ગને દરેક લેબલનો એક બીટ સોંપીને હેમિંગ લેબલિંગ મેળવી શકાય છે; સમકક્ષ વર્ગની ધાર દ્વારા અલગ કરાયેલા બે જોડાયેલા સબગ્રાફ્સમાંથી એકમાં, તમામ શિરોબિંદુઓ તેમના લેબલની તે સ્થિતિમાં 0 ધરાવે છે, અને અન્ય જોડાયેલા સબગ્રાફમાં તમામ શિરોબિંદુઓ સમાન સ્થિતિમાં 1 ધરાવે છે. ઓળખ આંશિક સમઘનને ઓળખી શકાય છે, અને સમયસર હેમિંગ લેબલિંગનું નિર્માણ કરવામાં આવે છે, ગ્રાફમાં શિરોબિંદુઓની સંખ્યા ક્યાં છે. આંશિક સમઘનને જોતાં, કુલ સમયમાં, દરેક શિરોબિંદુમાંથી પહોળાઈ પ્રથમ શોધ કરીને, જાકોવિક-વિંકલર સંબંધના સમાનતા વર્ગોનું નિર્માણ કરવું સરળ છે;-સમય ઓળખ અલ્ગોરિધમ બીટ-સ્તરની સમાંતરતાનો ઉપયોગ કરીને ગ્રાફમાંથી એક જ પાસમાં બહુવિધ પહોળાઈ પ્રથમ શોધ કરવા માટે આને ઝડપી બનાવે છે, અને પછી આ ગણતરીનું પરિણામ માન્ય આંશિક સમઘન લેબલિંગ છે તે ચકાસવા માટે એક અલગ અલ્ગોરિધમ લાગુ કરે છે. આંશિક સમઘનનું સમમિતિય પરિમાણ એ હાયપરક્યુબનું લઘુતમ પરિમાણ છે જેના પર તે સમમિતિય રીતે જડિત થઈ શકે છે, અને તે જેકોવિક-વિંકલર સંબંધના સમતુલ્ય વર્ગોની સંખ્યાની બરાબર છે. દાખલા તરીકે,-વર્ટેક્સ વૃક્ષનું સમમિતીય પરિમાણ તેની ધારની સંખ્યા છે. આ પરિમાણના હાયપરક્યુબ પર આંશિક સમઘનનું એમ્બેડિંગ અનન્ય છે, હાયપરક્યુબની સમપ્રમાણતા સુધી. દરેક હાયપરક્યુબ અને તેથી દરેક આંશિક ક્યુબને પૂર્ણાંક જાળીમાં સમમિતિની રીતે જડિત કરી શકાય છે. આલેખનું જાળીનું પરિમાણ એ પૂર્ણાંક જાળીનું લઘુતમ પરિમાણ છે જેમાં આલેખ સમમિતિય રીતે જડિત કરી શકાય છે. જાળીનું પરિમાણ સમમિતિય પરિમાણ કરતાં નોંધપાત્ર રીતે નાનું હોઈ શકે છે; દાખલા તરીકે, વૃક્ષ માટે તે વૃક્ષના પાંદડાઓની સંખ્યાનો અડધો ભાગ છે (નજીકના પૂર્ણાંક સુધી ગોળાકાર). કોઈપણ આલેખનું જાળીનું પરિમાણ, અને લઘુત્તમ પરિમાણનું જાળી એમ્બેડિંગ, સહાયક આલેખમાં મહત્તમ મેળ ખાતા પર આધારિત અલ્ગોરિધમ દ્વારા બહુપદી સમયમાં મળી શકે છે. વધુ વિશિષ્ટ માળખામાં એમ્બેડિંગના આધારે આંશિક સમઘનના અન્ય પ્રકારનાં પરિમાણોને પણ વ્યાખ્યાયિત કરવામાં આવ્યા છે. રાસાયણિક આલેખ સિદ્ધાંતનો ઉપયોગ હાયપરક્યુબ્સમાં આલેખના આઇસોમેટ્રિક એમ્બેડિંગનો રાસાયણિક આલેખ સિદ્ધાંતમાં મહત્વપૂર્ણ ઉપયોગ થાય છે. બેન્ઝેનોઇડ આલેખ એ ષટ્કોણ જાળીમાં ચક્રની અંદર અને અંદર આવેલા તમામ શિરોબિંદુઓ અને ધારોનો બનેલો આલેખ છે. આવા આલેખ એ બેન્ઝેનોઇડ હાઇડ્રોકાર્બનનો પરમાણુ આલેખ છે, જે કાર્બનિક અણુઓનો મોટો વર્ગ છે. આવા દરેક આલેખ આંશિક સમઘન છે. આવા આલેખના હેમિંગ લેબલિંગનો ઉપયોગ અનુરૂપ અણુના વીનર અનુક્રમણિકાની ગણતરી કરવા માટે થઈ શકે છે, જેનો ઉપયોગ પછી તેના ચોક્કસ રાસાયણિક ગુણધર્મોની આગાહી કરવા માટે થઈ શકે છે. કાર્બનમાંથી રચાયેલ એક અલગ પરમાણુ માળખું, ડાયમંડ ક્યુબિક પણ આંશિક ક્યુબ ગ્રાફ બનાવે છે. નોંધો સંદર્ભો. . . . . . . . જેમ ટાંકવામાં આવ્યું છે. . જેમ ટાંકવામાં આવ્યું છે. . . . જેમ ટાંકવામાં આવ્યું છે. . ખાસ કરીને પ્રકરણ 5, "આંશિક સમઘન", પૃષ્ઠો જુઓ. 127-181. . આલેખ પરિવારો ગાણિતિક રસાયણશાસ્ત્ર દ્વિપક્ષી આલેખ