Folded cube graph
આલેખ સિદ્ધાંતમાં, ફોલ્ડેડ ક્યુબ ગ્રાફ એ એક દિશાહીન ગ્રાફ છે જે હાયપરક્યુબ ગ્રાફમાંથી રચાય છે જેમાં એક સંપૂર્ણ મેળ ખાતો હોય છે જે હાયપરક્યુબ શિરોબિંદુઓની વિરુદ્ધ જોડીને જોડે છે. રચના પરિમાણ k નો ફોલ્ડેડ ક્યુબ ગ્રાફ (2k−1 શિરોબિંદુઓ ધરાવતો) પરિમાણ k−1 ના હાયપરક્યુબ ગ્રાફમાં શિરોબિંદુઓની વિરુદ્ધ જોડી વચ્ચે ધાર ઉમેરીને બનાવી શકાય છે. (2n શિરોબિંદુઓ સાથે હાયપરક્યુબમાં, શિરોબિંદુઓની જોડી વિરુદ્ધ હોય છે જો તેમની વચ્ચેના સૌથી ટૂંકા માર્ગની લંબાઈ n હોય.) તે, સમાનરૂપે, પરિમાણ k ના હાયપરક્યુબ ગ્રાફ (પણ) થી રચાય છે, જે દરેક વિરુદ્ધ શિરોબિંદુઓની જોડીને એકસાથે ઓળખીને (અથવા સંકોચાય છે) બમણી શિરોબિંદુઓ ધરાવે છે. ગુણધર્મો પરિમાણ-k ફોલ્ડેડ ક્યુબ ગ્રાફ એ 2k−1 શિરોબિંદુઓ અને 2k−2k ધાર સાથે k-નિયમિત છે. જ્યારે k સમ હોય ત્યારે પરિમાણ-k ફોલ્ડેડ ક્યુબ ગ્રાફની રંગીન સંખ્યા બે હોય છે (એટલે કે, આ કિસ્સામાં, ગ્રાફ દ્વિપક્ષી હોય છે) અને જ્યારે k વિષમ હોય ત્યારે ચાર હોય છે. વિષમ પરિમાણના ફોલ્ડેડ ક્યુબનો વિષમ ઘેરો k છે, તેથી ત્રણ કરતા મોટા વિષમ k માટે ફોલ્ડેડ ક્યુબ ગ્રાફ રંગીન નંબર ચાર અને મનસ્વી રીતે મોટા વિષમ ઘેરો સાથે ત્રિકોણ-મુક્ત ગ્રાફનો વર્ગ પ્રદાન કરે છે. વિષમ ઘેરાવો k અને વ્યાસ (k−1)/2 સાથે અંતર-નિયમિત આલેખ તરીકે, વિષમ પરિમાણના ફોલ્ડ કરેલા સમઘન સામાન્યીકૃત વિષમ આલેખનના ઉદાહરણો છે. જ્યારે k વિષમ હોય છે, ત્યારે પરિમાણ-k ફોલ્ડેડ ક્યુબનું દ્વિપક્ષી ડબલ કવર એ પરિમાણ-k ક્યુબ છે જેમાંથી તેની રચના થઈ હતી. જો કે, જ્યારે k સરખું હોય, ત્યારે પરિમાણ-k ક્યુબ એ બેવડું આવરણ હોય છે પરંતુ દ્વિપક્ષી બેવડું આવરણ નથી. આ કિસ્સામાં, ફોલ્ડ કરેલ ક્યુબ પોતે પહેલેથી જ દ્વિપક્ષી છે. ફોલ્ડેડ ક્યુબ ગ્રાફ તેમના હાયપરક્યુબ સબગ્રાફ્સમાંથી હેમિલ્ટોનિયન ચક્ર હોવાની મિલકતનો વારસો મેળવે છે, અને હાયપરક્યુબ્સમાંથી જે તેમને અંતર-સંક્રમક ગ્રાફ હોવાના ગુણધર્મને આવરી લે છે. જ્યારે k વિષમ હોય છે, ત્યારે પરિમાણ-k ફોલ્ડેડ ક્યુબ સબગ્રાફ તરીકે 2k−1 નોડ્સ સાથેનું સંપૂર્ણ દ્વિસંગી વૃક્ષ ધરાવે છે. જો કે, જ્યારે k સમ હોય, ત્યારે આ શક્ય નથી, કારણ કે આ કિસ્સામાં ફોલ્ડેડ ક્યુબ એ દ્વિપક્ષી આલેખ છે જેમાં દ્વિપક્ષીકરણની દરેક બાજુએ સમાન સંખ્યામાં શિરોબિંદુઓ હોય છે, જે સંપૂર્ણ દ્વિસંગી વૃક્ષના દ્વિપક્ષીકરણ માટેના લગભગ બે-થી-એક ગુણોત્તરથી ખૂબ જ અલગ હોય છે. ઉદાહરણો પરિમાણ ત્રણનો ફોલ્ડેડ ક્યુબ ગ્રાફ એ સંપૂર્ણ ગ્રાફ K4 છે. પરિમાણ ચારનો ફોલ્ડેડ ક્યુબ ગ્રાફ સંપૂર્ણ દ્વિપક્ષી ગ્રાફ K4,4 છે. પરિમાણ પાંચનો ફોલ્ડેડ ક્યુબ ગ્રાફ ક્લેબ્શ ગ્રાફ છે. છઠ્ઠા પરિમાણનો ફોલ્ડેડ ક્યુબ ગ્રાફ એ કુમેર ગ્રાફ છે, એટલે કે. કુમેર બિંદુ-સમતલ રૂપરેખાંકનનો લેવી આલેખ. સમાંતર કમ્પ્યુટિંગમાં, ફોલ્ડેટેડ ક્યુબ ગ્રાફનો અભ્યાસ હાયપરક્યુબના વિકલ્પ તરીકે સંભવિત નેટવર્ક ટોપોલોજી તરીકે કરવામાં આવ્યો છે. હાયપરક્યુબની સરખામણીમાં, સમાન સંખ્યામાં ગાંઠો ધરાવતા ફોલ્ડેડ ક્યુબમાં લગભગ સમાન શિરોબિંદુ ડિગ્રી હોય છે પરંતુ તેનો વ્યાસ માત્ર અડધો હોય છે. કાર્યક્ષમ વિતરિત અલ્ગોરિધમ્સ (હાયપરક્યુબ માટે સંબંધિત) ફોલ્ડેડ ક્યુબમાં માહિતી પ્રસારિત કરવા માટે જાણીતા છે. અર્ધો સમઘન આલેખ નોંધો સંદર્ભો પણ જુઓ. . . . . . બાહ્ય કડીઓ આલેખના પેરામેટ્રિક પરિવારો નિયમિત આલેખ