Ore's theorem
ઓરેનો પ્રમેય એ 1960માં નોર્વેના ગણિતશાસ્ત્રી ઓસ્ટીન ઓરે દ્વારા સાબિત કરવામાં આવેલા આલેખ સિદ્ધાંતનું પરિણામ છે. તે આલેખ હેમિલ્ટોનિયન હોવા માટે પૂરતી શરત આપે છે, અનિવાર્યપણે જણાવે છે કે પૂરતી ધારવાળા આલેખમાં હેમિલ્ટન ચક્ર હોવું આવશ્યક છે. ખાસ કરીને, આ પ્રમેય અ-અડીને આવેલા શિરોબિંદુઓની જોડીની ડિગ્રીના સરવાળાને ધ્યાનમાં લે છેઃ જો આવી દરેક જોડીનો સરવાળો ઓછામાં ઓછો આલેખમાં શિરોબિંદુઓની કુલ સંખ્યા જેટલો હોય, તો આલેખ હેમિલ્ટોનિયન છે. ઔપચારિક નિવેદન ચાલો શિરોબિંદુઓ સાથે (મર્યાદિત અને સરળ) આલેખ હોઈએ. આપણે શિરોબિંદુની ડિગ્રી દ્વારા સૂચવીએ છીએ, એટલે કે. ઘટના ધારની સંખ્યા. પછી, ઓરેનો પ્રમેય જણાવે છે કે જો તે હેમિલ્ટોનિયન છે. પુરાવો તે બતાવવા સમાન છે કે દરેક બિન-હેમિલ્ટોનિયન આલેખ શરત (઱્઱ં) નું પાલન કરતું નથી. તદનુસાર, ચાલો શિરોબિંદુઓ પર આલેખ બનાવીએ જે હેમિલ્ટોનિયન નથી, અને જ્યાં સુધી કોઈ વધુ ધાર ઉમેરી શકાતી નથી ત્યાં સુધી હેમિલ્ટોનિયન ચક્ર ન બનાવે ત્યાં સુધી એક સમયે એક ધાર ઉમેરીને રચાય છે. કોઈપણ બે બિન-અડીને આવેલા શિરોબિંદુઓને અંદર આવવા દો. પછી તેમાં ધાર ઉમેરવાથી ઓછામાં ઓછું એક નવું હેમિલ્ટોનિયન ચક્ર બનશે, અને આવા ચક્ર સિવાયની કિનારીઓએ અને સાથે હેમિલ્ટોનિયન માર્ગ બનાવવો આવશ્યક છે. શ્રેણીમાં દરેક અનુક્રમણિકા માટે, બે સંભવિત ધારને થી અને થી માં ધ્યાનમાં લો. આ બે ધારમાંથી વધુમાં વધુ એક ધાર હાજર હોઈ શકે છે, અન્યથા ચક્ર હેમિલ્ટોનિયન ચક્ર હશે. આમ, ધારની કુલ સંખ્યા ક્યાં તો અથવા મહત્તમ પસંદગીઓની સંખ્યા જેટલી હોય છે, જે છે. તેથી, ગુણધર્મ (઱્઱ં) નું પાલન કરતું નથી, જેના માટે જરૂરી છે કે ધારની આ કુલ સંખ્યા () કરતા વધારે અથવા તેની બરાબર હોય. કારણ કે શિરોબિંદુની ડિગ્રી સૌથી વધુ ડિગ્રીની બરાબર હોય છે, તે અનુસરે છે કે તે પણ ગુણધર્મ (ir) નું પાલન કરતું નથી. અલ્ગોરિધમ ઓરેની સ્થિતિને મળતા ગ્રાફમાં હેમિલ્ટોનિયન ચક્રના નિર્માણ માટે નીચેના સરળ અલ્ગોરિધમનું વર્ણન કરે છે. આલેખમાં નિકટતાઓને અવગણીને શિરોબિંદુઓને મનસ્વી રીતે ચક્રમાં ગોઠવો. જ્યારે ચક્રમાં બે સળંગ શિરોબિંદુઓ vi અને vi + 1 હોય છે જે આલેખમાં સંલગ્ન નથી, ત્યારે નીચેના બે પગલાંઓ અનુસરોઃ અનુક્રમણિકા j માટે એવી રીતે શોધો કે જેમાં ચાર શિરોબિંદુઓ vi, vi + 1, vj અને vj + 1 બધા અલગ હોય અને જેમ કે આલેખમાં vi થી vj અને vj + 1 થી vi + 1 સુધીની ધાર હોય અને vi + 1 અને vj (સમાવિષ્ટ) વચ્ચેના ચક્રના ભાગને ઉલટાવી દો. દરેક પગલું ગ્રાફમાં અડીને આવેલા ચક્રમાં સતત જોડીઓની સંખ્યામાં એક કે બે જોડીઓ દ્વારા વધારો કરે છે (vj અને vj + 1 પહેલેથી જ અડીને આવેલા છે કે કેમ તેના આધારે), તેથી બાહ્ય લૂપ અલ્ગોરિધમ સમાપ્ત થાય તે પહેલાં મહત્તમ n સમયે જ થઈ શકે છે, જ્યાં n એ આપેલ ગ્રાફમાં શિરોબિંદુઓની સંખ્યા છે. પ્રમેયના પુરાવા જેવી જ દલીલ દ્વારા, ઇચ્છિત અનુક્રમણિકા જે અસ્તિત્વમાં હોવી જોઈએ, નહીં તો બિન-અડીને આવેલા શિરોબિંદુઓ vi અને vi + 1 ની કુલ ડિગ્રી ખૂબ ઓછી હશે. i અને j શોધવું, અને ચક્રના ભાગને ઉલટાવવું, આ બધું સમય O (n) માં પૂર્ણ કરી શકાય છે. તેથી, અલ્ગોરિધમનો કુલ સમય O (n2) છે, જે ઇનપુટ ગ્રાફમાં ધારની સંખ્યા સાથે મેળ ખાય છે. સંબંધિત પરિણામો ઓરેનો પ્રમેય એ ડીરાકના પ્રમેયનું સામાન્યીકરણ છે કે, જ્યારે દરેક શિરોબિંદુ ઓછામાં ઓછી ડિગ્રી ધરાવે છે, ત્યારે આલેખ હેમિલ્ટોનિયન હોય છે. કારણ કે, જો આલેખ ડીરાકની સ્થિતિને પૂર્ણ કરે છે, તો સ્પષ્ટ રીતે શિરોબિંદુઓની દરેક જોડીમાં ઓછામાં ઓછી ડિગ્રી ઉમેરવામાં આવે છે. બદલામાં ઓરેના પ્રમેયને બોન્ડી-ચ્વાટલ પ્રમેય દ્વારા સામાન્યીકૃત કરવામાં આવે છે. ગ્રાફ પર ક્લોઝર ઓપરેશનને વ્યાખ્યાયિત કરી શકાય છે, જેમાં જ્યારે પણ બે બિન-અડીને આવેલા શિરોબિંદુઓમાં ઓછામાં ઓછી ડિગ્રી ઉમેરવામાં આવે છે, ત્યારે એક તેમને જોડતી ધાર ઉમેરે છે; જો ગ્રાફ ઓરેના પ્રમેયની શરતોને પૂર્ણ કરે છે, તો તેનું ક્લોઝર એ સંપૂર્ણ ગ્રાફ છે. બોન્ડી-ચ્વાટલ પ્રમેય જણાવે છે કે આલેખ હેમિલ્ટોનિયન છે જો અને માત્ર ત્યારે જ જો તેનો બંધ હેમિલ્ટોનિયન હોય; કારણ કે સંપૂર્ણ આલેખ હેમિલ્ટોનિયન છે, ઓરેનો પ્રમેય તાત્કાલિક પરિણામ છે. ઓરેના પ્રમેયની એક આવૃત્તિ મળી જે નિર્દેશિત આલેખ પર લાગુ થાય છે. ધારો કે ડિગ્રાફ G પાસે એવો ગુણધર્મ છે કે, દરેક બે શિરોબિંદુઓ u અને v માટે, ક્યાં તો u થી v સુધીની ધાર હોય અથવા u ની આઉટ ડિગ્રી વત્તા v ની ઇન્ડીગ્રી G માં શિરોબિંદુઓની સંખ્યાની બરાબર અથવા તેનાથી વધી જાય. પછી, વુડલના પ્રમેય અનુસાર, G એ નિર્દેશિત હેમિલ્ટોનિયન ચક્ર ધરાવે છે. ઓરેનો પ્રમેય વુડલ પાસેથી આપેલ દિશાહીન આલેખમાં દરેક ધારને નિર્દેશિત ધારની જોડી દ્વારા બદલીને મેળવી શકાય છે. એક નજીકથી સંબંધિત પ્રમેય જણાવે છે કે એન-વર્ટેક્સ એ ગુણધર્મ સાથે ડિગ્રાફને મજબૂત રીતે જોડે છે કે, દરેક બે બિન-અડીને આવેલા શિરોબિંદુઓ u અને v માટે, u અથવા v સાથે સંકળાયેલી કિનારીઓની કુલ સંખ્યા ઓછામાં ઓછી 2n−1 હોવી જોઈએ. પ્રમેયમાં ડિગ્રીની સ્થિતિના પરિણામે હેમિલ્ટોનિસિટી કરતાં વધુ મજબૂત નિષ્કર્ષ આપવા માટે ઓરેના પ્રમેયને પણ મજબૂત કરી શકાય છે. ખાસ કરીને, ઓરેના પ્રમેયની શરતોને સંતોષતો દરેક આલેખ કાં તો નિયમિત સંપૂર્ણ દ્વિપક્ષી આલેખ હોય છે અથવા પેન્સીક્લિક હોય છે. સંદર્ભો. . . . . ગ્રાફ થિયરીમાં એક્સ્ટ્રીમ ગ્રાફ થિયરી પ્રમેયો હેમિલ્ટોનિયન પાથ અને ચક્રના પુરાવા ધરાવતા લેખો