Halin graph
આલેખ સિદ્ધાંતમાં, હેલિન આલેખ એ સમતલ આલેખનો એક પ્રકાર છે, જે વૃક્ષના પાંદડાઓને ચક્રમાં જોડીને બનાવવામાં આવે છે. વૃક્ષમાં ઓછામાં ઓછા ચાર શિરોબિંદુઓ હોવા જોઈએ, જેમાંથી કોઈ પણ બરાબર બે પડોશીઓ ન હોય; તેને સમતલમાં દોરવું જોઈએ જેથી તેની કોઈ પણ ધાર પાર ન થાય (આને સમતલીય એમ્બેડિંગ કહેવામાં આવે છે), અને ચક્ર આ એમ્બેડિંગમાં તેમના ઘડિયાળની દિશામાં ક્રમમાં પાંદડાઓને જોડે છે. આમ, ચક્ર હેલિન આલેખનો બાહ્ય ચહેરો બનાવે છે, જેની અંદર વૃક્ષ હોય છે. હેલિન આલેખ જર્મન ગણિતશાસ્ત્રી રુડોલ્ફ હેલિનના નામ પરથી રાખવામાં આવ્યા છે, જેમણે 1971માં તેનો અભ્યાસ કર્યો હતો. ક્યુબિક હેલિન આલેખ-જેમાં દરેક શિરોબિંદુ બરાબર ત્રણ ધારને સ્પર્શે છે-કિર્કમેન દ્વારા એક સદી અગાઉ અભ્યાસ કરવામાં આવ્યો હતો. હેલિન આલેખ પોલિહેડ્રલ આલેખ છે, જેનો અર્થ થાય છે કે દરેક હેલિન આલેખનો ઉપયોગ બહિર્મુખ પોલિહેડ્રોનના શિરોબિંદુઓ અને ધાર બનાવવા માટે થઈ શકે છે, અને તેમાંથી બનેલા પોલિહેડ્રાને છત વિનાના પોલિહેડ્રા અથવા ગુંબજો કહેવામાં આવે છે. દરેક હેલિન આલેખમાં તેના તમામ શિરોબિંદુઓમાંથી હેમિલ્ટોનિયન ચક્ર હોય છે, તેમજ આલેખના શિરોબિંદુઓની સંખ્યા સુધી લગભગ તમામ લંબાઈના ચક્ર હોય છે. હેલિન આલેખ રેખીય સમયમાં ઓળખી શકાય છે. કારણ કે હેલિન આલેખમાં ત્રણ પહોળાઈ ઓછી હોય છે, ઘણી કોમ્પ્યુટેશનલ સમસ્યાઓ કે જે અન્ય પ્રકારના સમતલીય આલેખ પર સખત હોય છે, જેમ કે હેમિલ્ટોનિયન ચક્ર શોધવા, હેલિન આલેખ પર ઝડપથી ઉકેલી શકાય છે. ઉદાહરણો તારો એ બરાબર એક આંતરિક શિરોબિંદુ ધરાવતું વૃક્ષ છે. તારામાં હેલિન આલેખની રચનાને લાગુ કરવાથી ચક્ર આલેખ ઉત્પન્ન થાય છે, જે પિરામિડની (ધાર) આલેખ છે. ત્રિકોણાકાર પ્રિઝમનો આલેખ પણ હેલિન આલેખ છેઃ તેને દોરવામાં આવે છે જેથી તેનો એક લંબચોરસ ચહેરો બાહ્ય ચક્ર હોય અને બાકીની ધાર ચાર પાંદડાં, બે આંતરિક શિરોબિંદુઓ અને પાંચ ધારવાળા વૃક્ષની રચના કરે. ફ્રુક્ટ આલેખ, જે પાંચ સૌથી નાના ઘન આલેખમાંથી એક છે, જેમાં કોઈ બિન-તુચ્છ આલેખ ઓટોમોર્ફિઝમ નથી, તે પણ હેલિન આલેખ છે. ગુણધર્મો દરેક હેલિન આલેખ 3-જોડાયેલ છે, એટલે કે તેમાંથી બે શિરોબિંદુઓ કાઢી નાખવા અને બાકીના શિરોબિંદુઓને ડિસ્કનેક્ટ કરવું શક્ય નથી. તે ધાર-લઘુત્તમ 3-જોડાયેલ છે, એટલે કે જો તેની કોઈ એક ધાર દૂર કરવામાં આવે, તો બાકીનો આલેખ હવે 3-જોડાયેલ રહેશે નહીં. સ્ટેનિટ્ઝના પ્રમેય દ્વારા, 3-જોડાયેલા સમતલીય આલેખ તરીકે, તેને બહિર્મુખ પોલિહેડ્રોનના શિરોબિંદુઓ અને ધારોના સમૂહ તરીકે રજૂ કરી શકાય છે; એટલે કે, તે એક પોલિહેડ્રલ આલેખ છે. પોલિહેડ્રોન કે જે આલેખની અનુભૂતિ કરે છે તે પસંદ કરી શકાય છે જેથી વૃક્ષના તમામ પાંદડાઓ ધરાવતો ચહેરો આડી હોય અને અન્ય તમામ ચહેરાઓ તેની ઉપર સમાન ઢોળાવ સાથે હોય. દરેક પોલિહેડ્રલ ગ્રાફની જેમ, હેલિન ગ્રાફમાં એક અનન્ય સમતલીય એમ્બેડિંગ હોય છે, જે તેના કયા ચહેરાની પસંદગી બાહ્ય ચહેરો છે તેની પસંદગી કરે છે. દરેક હેલિન આલેખ હેમિલ્ટોનિયન આલેખ છે, અને આલેખની દરેક ધાર હેમિલ્ટોનિયન ચક્રની છે. વધુમાં, કોઈપણ શિરોબિંદુને દૂર કર્યા પછી કોઈપણ હેલિન આલેખ હેમિલ્ટોનિયન રહે છે. કારણ કે ડિગ્રી 2 ના શિરોબિંદુ વિનાના દરેક વૃક્ષમાં બે પાંદડા હોય છે જે સમાન મૂળ ધરાવે છે, દરેક હેલિન આલેખમાં ત્રિકોણ હોય છે. ખાસ કરીને, હેલિન આલેખ ત્રિકોણ-મુક્ત આલેખ અથવા દ્વિપક્ષી આલેખ હોવો શક્ય નથી. વધુ મજબૂત રીતે, દરેક હેલિન આલેખ લગભગ પેન્સીક્લિક હોય છે, એ અર્થમાં કે તેમાં એક સરખી લંબાઈના સંભવિત અપવાદ સાથે 3 થી n સુધીની તમામ લંબાઈના ચક્ર હોય છે. વધુમાં, જો એક ધાર સંકોચાય છે તો કોઈપણ હેલિન ગ્રાફ લગભગ પેન્સીક્લિક રહે છે, અને ડિગ્રી ત્રણના આંતરિક શિરોબિંદુઓ વિનાનો દરેક હેલિન ગ્રાફ પેન્સીક્લિક છે. હેલિન આલેખની મહત્તમ ડિગ્રી ચાર કરતા વધારે હોય તેવી ઘટના રંગીન સંખ્યા છે. આ તમામ જોડીઓ (v, e) ને રંગવા માટે જરૂરી રંગોની સંખ્યા છે જ્યાં v એ આલેખનો શિરોબિંદુ છે, અને e એ v માટે એક ધાર ઘટના છે, જે રંગ પરની ચોક્કસ મર્યાદાઓનું પાલન કરે છે. જે જોડી શિરોબિંદુ વહેંચે છે અથવા જે ધાર વહેંચે છે તેને સમાન રંગની મંજૂરી નથી. વધુમાં, જોડી (v, e) અન્ય જોડી જેવો જ રંગ ધરાવી શકતી નથી જે e ના અન્ય અંતિમ બિંદુનો ઉપયોગ કરે છે. અથવા સાથે હેલિન આલેખ માટે, ઘટના રંગીન સંખ્યા અનુક્રમે અથવા તેટલી મોટી હોઈ શકે છે. કોમ્પ્યુટેશનલ જટિલતા આપેલ-વર્ટેક્સ ગ્રાફ રેખીય સમયમાં હેલિન ગ્રાફ છે કે કેમ તે ચકાસવું શક્ય છે, ગ્રાફનું સમતલીય એમ્બેડિંગ શોધીને (જો કોઈ અસ્તિત્વમાં હોય તો), અને પછી પરીક્ષણ કરવું શક્ય છે કે ત્યાં કોઈ ચહેરો અસ્તિત્વમાં છે કે કેમ જેમાં ઓછામાં ઓછા શિરોબિંદુઓ છે, બધા ડિગ્રી ત્રણ. જો એમ હોય તો, આવા વધુમાં વધુ ચાર મુખ હોઈ શકે છે, અને તેમાંથી દરેક માટે રેખીય સમયમાં તપાસવું શક્ય છે કે બાકીનો આલેખ આ મુખના શિરોબિંદુઓને તેના પાંદડા તરીકે રાખીને વૃક્ષ બનાવે છે કે કેમ. બીજી બાજુ, જો આવો કોઈ ચહેરો અસ્તિત્વમાં નથી, તો ગ્રાફ હેલિન નથી. વૈકલ્પિક રીતે, શિરોબિંદુઓ અને ધાર સાથેનો આલેખ હેલિન હોય છે જો અને માત્ર ત્યારે જ જો તે સમતલીય હોય, 3-જોડાયેલ હોય અને તેનો ચહેરો હોય કે જેના શિરોબિંદુઓની સંખ્યા આલેખના સર્કિટ ક્રમની બરાબર હોય, જે તમામને રેખીય સમયમાં ચકાસી શકાય છે. રેખીય સમયમાં હેલિન આલેખને ઓળખવા માટેની અન્ય પદ્ધતિઓમાં કોર્સેલના પ્રમેયનો ઉપયોગ અથવા આલેખ પુનર્લેખન પર આધારિત પદ્ધતિનો સમાવેશ થાય છે, જેમાંથી કોઈ પણ આલેખના સમતલીય એમ્બેડિંગને જાણવા પર આધાર રાખતું નથી. દરેક હેલિન આલેખમાં ત્રિ-પહોળાઈ = 3 હોય છે. તેથી, ગ્રાફ ઓપ્ટિમાઇઝેશનની ઘણી સમસ્યાઓ કે જે મનસ્વી સમતલીય આલેખ માટે એન. પી.-પૂર્ણ હોય છે, જેમ કે મહત્તમ સ્વતંત્ર સમૂહ શોધવો, તેને ગતિશીલ પ્રોગ્રામિંગ અથવા કોર્સેલના પ્રમેયનો ઉપયોગ કરીને હેલિન આલેખ પર રેખીય સમયમાં અથવા કેટલાક કિસ્સાઓમાં (જેમ કે હેમિલ્ટોનિયન ચક્રોનું નિર્માણ) સીધા અલ્ગોરિધમ્સ દ્વારા ઉકેલી શકાય છે. જો કે, આપેલ ગ્રાફનો સૌથી મોટો હેલિન સબગ્રાફ શોધવો, આપેલ ગ્રાફના તમામ શિરોબિંદુઓનો સમાવેશ કરતો હેલિન સબગ્રાફ અસ્તિત્વમાં છે કે કેમ તે ચકાસવા અથવા આપેલ ગ્રાફ મોટા હેલિન ગ્રાફનો સબગ્રાફ છે કે કેમ તે ચકાસવા માટે એન. પી.-પૂર્ણ છે. 1971માં, હેલિને હેલિન આલેખને લઘુત્તમ 3-વર્ટેક્સ-જોડાયેલા આલેખના વર્ગ તરીકે રજૂ કર્યો હતોઃ આલેખની દરેક ધાર માટે, તે ધારને દૂર કરવાથી આલેખની કનેક્ટિવિટીમાં ઘટાડો થાય છે. આ આલેખને એ શોધ સાથે મહત્વ મળ્યું કે ઘણી અલ્ગોરિધમિક સમસ્યાઓ કે જે મનસ્વી સમતલીય આલેખ માટે ગણતરીની દૃષ્ટિએ અવ્યવહારુ હતી, તેમના પર અસરકારક રીતે ઉકેલી શકાય છે. આ હકીકત પાછળથી તેમની ઓછી ત્રિ-પહોળાઈ અને કોર્સેલના પ્રમેય જેવા અલ્ગોરિધમિક મેટા-થીર્મ્સનું પરિણામ હોવાનું સમજાવવામાં આવ્યું હતું, જે ઓછી ત્રિ-પહોળાઈના કોઈપણ આલેખ પર આ સમસ્યાઓના કાર્યક્ષમ ઉકેલો પૂરા પાડે છે. આ આલેખ પર હેલિનના કામ પહેલાં, ક્યુબિક (અથવા 3-નિયમિત) હેલિન આલેખ સંબંધિત આલેખ ગણતરી સમસ્યાઓનો અભ્યાસ 1856માં થોમસ કિર્કમેન દ્વારા અને 1965માં હંસ રેડેમાકર દ્વારા કરવામાં આવ્યો હતો. રેડેમાકર આ આલેખને પોલિહેડ્રા આધારિત કહે છે. તેઓ તેમને ક્યુબિક પોલિહેડ્રલ આલેખ તરીકે વ્યાખ્યાયિત કરે છે જેમાં ચહેરાઓ હોય છે જેમાં એક બાજુ હોય છે. આ વ્યાખ્યાને અનુરૂપ આલેખ બરાબર ક્યુબિક હેલિન આલેખ છે. હેલિન આલેખ અને 4-વર્ટેક્સ સાથે જોડાયેલા સમતલીય આલેખ બંને હેમિલ્ટોનિયન ચક્ર ધરાવે છે તે હકીકતથી પ્રેરિત છે, એવું અનુમાન કરવામાં આવે છે કે દરેક 4-વર્ટેક્સ સાથે જોડાયેલા સમતલીય આલેખમાં ફેલાયેલો હેલિન સબગ્રાફ હોય છે; અહીં "સ્પૅનિંગ" નો અર્થ એ છે કે સબગ્રાફમાં મોટા આલેખના તમામ શિરોબિંદુઓનો સમાવેશ થાય છે. લોવાસ-પ્લમર અનુમાન 2015 સુધી ખુલ્લું રહ્યું, જ્યારે અનંત ઘણા પ્રતિકૂળ ઉદાહરણો માટેનું બાંધકામ પ્રકાશિત કરવામાં આવ્યું હતું. હેલિન આલેખને કેટલીકવાર સ્કર્ટેડ વૃક્ષો અથવા છત વિનાના પોલિહેડ્રા પણ કહેવામાં આવે છે. જોકે, આ નામો અસ્પષ્ટ છે. કેટલાક લેખકો વૃક્ષોના પાંદડાઓને ચક્રમાં જોડીને વૃક્ષોમાંથી રચાયેલા સમતલીય આલેખનો સંદર્ભ આપવા માટે "સ્કર્ટેડ વૃક્ષો" નામનો ઉપયોગ કરે છે, પરંતુ વૃક્ષના આંતરિક શિરોબિંદુઓ ડિગ્રી ત્રણ કે તેથી વધુ હોય તે જરૂરી નથી. અને "આધારિત પોલિહેડ્રા" ની જેમ, "છત વિનાનું પોલિહેડ્રા" નામ પણ ઘન હેલિન આલેખનો સંદર્ભ આપી શકે છે. બહિર્મુખ પોલિહેડ્રા કે જેના આલેખ હેલિન આલેખ છે તેને પણ ગુંબજ કહેવામાં આવે છે. સંદર્ભો બાહ્ય લિંક્સ હેલિન આલેખ, આલેખ વર્ગ સમાવેશ પર માહિતી પ્રણાલી. આલેખ પરિવારો પ્લાનર આલેખ