Tutte theorem
આલેખ સિદ્ધાંતની ગાણિતિક શાખામાં વિલિયમ થોમસ ટુટ્ટેના નામ પરથી નામ આપવામાં આવેલ ટુટ્ટે પ્રમેય એ સંપૂર્ણ મેળ ખાતા મર્યાદિત દિશાહીન આલેખની લાક્ષણિકતા છે. તે દ્વિદલીયથી મનસ્વી આલેખ સુધીના હોલના લગ્ન પ્રમેયનું સામાન્યીકરણ છે. તે ટુટ્ટે-બર્જ સૂત્રનો એક ખાસ કેસ છે. અંતઃપ્રેરણા ધ્યેય એ છે કે એવા તમામ આલેખની લાક્ષણિકતા દર્શાવવી કે જે સંપૂર્ણ રીતે મેળ ખાતા નથી. સંપૂર્ણ મેળ ખાતા વગર ગ્રાફના સૌથી સ્પષ્ટ કેસથી પ્રારંભ કરોઃ શિરોબિંદુઓની વિચિત્ર સંખ્યા સાથેનો ગ્રાફ. આવા આલેખમાં, કોઈપણ મેળ ખાતી ટોચ ઓછામાં ઓછી એક મેળ ન ખાતી ટોચ છોડી દે છે, તેથી તે સંપૂર્ણ ન હોઈ શકે. સહેજ વધુ સામાન્ય કેસ એ ડિસ્કનેક્ટેડ ગ્રાફ છે જેમાં એક અથવા વધુ ઘટકોમાં શિરોબિંદુઓની વિચિત્ર સંખ્યા હોય છે (ભલે શિરોબિંદુઓની કુલ સંખ્યા સરખી હોય). ચાલો આપણે આવા ઘટકોને વિચિત્ર ઘટકો કહીએ. કોઈપણ મેળમાં, દરેક શિરોબિંદુને માત્ર સમાન ઘટકમાં શિરોબિંદુઓ સાથે સરખાવી શકાય છે. તેથી, કોઈપણ મેળ ખાતી દરેક વિચિત્ર ઘટકમાં ઓછામાં ઓછી એક મેળ ન ખાતી શિરોબિંદુ છોડી દે છે, તેથી તે સંપૂર્ણ ન હોઈ શકે. આગળ, ગ્રાફ G ને શિરોબિંદુ u સાથે એવી રીતે ધ્યાનમાં લો કે, જો આપણે G માંથી શિરોબિંદુ u અને તેની અડીને આવેલી ધારને દૂર કરીએ, તો બાકીના ગ્રાફ (સૂચિત) માં બે અથવા વધુ વિચિત્ર ઘટકો હોય. ઉપરની જેમ, કોઈપણ મેળ ખાતા પાંદડા, દરેક વિચિત્ર ઘટકમાં, ઓછામાં ઓછું એક શિરોબિંદુ જે સમાન ઘટકમાં અન્ય શિરોબિંદુઓ સાથે મેળ ખાતું નથી. આવા શિરોબિંદુને ફક્ત યુ સાથે સરખાવી શકાય છે. પરંતુ ત્યાં બે અથવા વધુ મેળ ન ખાતા શિરોબિંદુઓ હોવાથી, અને તેમાંથી માત્ર એક જ યુ સાથે મેળ ખાઈ શકાય છે, ઓછામાં ઓછું એક અન્ય શિરોબિંદુ મેળ ખાતું નથી, તેથી મેળ ખાતું સંપૂર્ણ નથી. છેવટે, શિરોબિંદુઓના સમૂહ સાથે ગ્રાફ G ને ધ્યાનમાં લો કે, જો આપણે G માંથી શિરોબિંદુઓને અંદર અને તેમની બાજુમાં આવેલી તમામ ધારને દૂર કરીએ, તો બાકીના ગ્રાફ (સૂચિત) માં વિચિત્ર ઘટકો કરતાં વધુ હોય છે. ઉપર વર્ણવ્યા મુજબ, કોઈપણ મેળ ખાતા દરેક વિચિત્ર ઘટકમાં ઓછામાં ઓછા એક મેળ ન ખાતા શિરોબિંદુને છોડી દે છે, અને આ ફક્ત તેના શિરોબિંદુઓ સાથે મેળ ખાઈ શકાય છે-પરંતુ આ તમામ મેળ ન ખાતા શિરોબિંદુઓ માટે પૂરતા શિરોબિંદુઓ નથી, તેથી મેળ ખાતું સંપૂર્ણ નથી. આપણે એક આવશ્યક શરત પર પહોંચ્યા છીએઃ જો G સંપૂર્ણ મેળ ખાતો હોય, તો G માં દરેક શિરોબિંદુ ઉપગણ માટે, આલેખમાં સૌથી વધુ વિચિત્ર ઘટકો હોય છે. ટુટ્ટેનો પ્રમેય કહે છે કે આ શરત સંપૂર્ણ મેળના અસ્તિત્વ માટે જરૂરી અને પૂરતી બંને છે. ટુટ્ટેનો પ્રમેય એ આલેખ, સંપૂર્ણ મેળ ખાતો હોય છે જો અને માત્ર ત્યારે જ જો દરેક સબસેટ માટે, સબગ્રાફમાં સૌથી વધુ વિચિત્ર ઘટકો હોય (જોડાયેલા ઘટકોમાં શિરોબિંદુઓની વિષમ સંખ્યા હોય). પુરાવો પ્રથમ આપણે શરત લખીએ છીએઃ જ્યાં દ્વારા પ્રેરિત સબગ્રાફના વિચિત્ર ઘટકોની સંખ્યા સૂચવે છે. ની આવશ્યકતાઃ આ દિશાની ચર્ચા નીચે અંતર્જ્ઞાન વિભાગમાં પહેલેથી જ કરવામાં આવી હતી, પરંતુ ચાલો આપણે અહીં સાબિતીનો સારાંશ આપીએ. સંપૂર્ણ મેળ ખાતા આલેખનો વિચાર કરો. ચાલો એક આર્બિટરી સબસેટ હોઈએ. કાઢી નાંખો. ચાલો એક મનસ્વી વિચિત્ર ઘટક હોઈએ. સંપૂર્ણ મેળ ખાતું હોવાથી, ઓછામાં ઓછું એક શિરોબિંદુ શિરોબિંદુ સાથે મેળ ખાતું હોવું જોઈએ. તેથી, દરેક વિષમ ઘટકમાં ઓછામાં ઓછું એક શિરોબિંદુ હોય છે જે શિરોબિંદુ સાથે મેળ ખાય છે. કારણ કે દરેક શિરોબિંદુ વધુમાં વધુ એક જોડાયેલા ઘટક સાથે આ સંબંધમાં હોઈ શકે છે (કારણ કે તે સંપૂર્ણ મેળમાં વધુમાં વધુ એક વાર મેળ ખાય છે). (઱્઱ં) ની પર્યાપ્તતાઃ ચાલો કોઈ સંપૂર્ણ મેળ ખાતા વગરનો મનસ્વી આલેખ બનીએ. આપણને એક કહેવાતા ટુટ્ટે ઉલ્લંઘનકર્તા મળશે, એટલે કે, તેનો એક ઉપસમૂહ. આપણે ધારી શકીએ કે તે ધાર-મહત્તમ છે, એટલે કે, પહેલેથી હાજર ન હોય તેવી દરેક ધાર માટે સંપૂર્ણ મેળ ખાય છે. ખરેખર, જો આપણને ધાર-મહત્તમ આલેખમાં તુટ્ટે ઉલ્લંઘનકર્તા મળે, તો તે દરેક વિસ્તૃત સબગ્રાફમાં તુટ્ટે ઉલ્લંઘનકર્તા પણ છે, કારણ કે દરેક વિચિત્ર ઘટકને સંભવતઃ વધુ ઘટકોમાં વહેંચવામાં આવશે, જેમાંથી ઓછામાં ઓછો એક ફરીથી વિચિત્ર હશે. આપણે ડિગ્રી સાથે શિરોબિંદુઓના સમૂહ તરીકે વ્યાખ્યાયિત કરીએ છીએ. પહેલા આપણે એવા કેસને ધ્યાનમાં લઈએ છીએ જ્યાં તેના તમામ ઘટકો સંપૂર્ણ આલેખ છે. પછી ટુટ્ટે ઉલ્લંઘનકર્તા હોવું જોઈએ, કારણ કે જો, તો આપણે દરેક વિચિત્ર ઘટકમાંથી એક શિરોબિંદુને શિરોબિંદુ સાથે સરખાવીને અને અન્ય તમામ શિરોબિંદુઓને જોડી બનાવીને એક સંપૂર્ણ મેળ શોધી શકીએ છીએ (આ ત્યાં સુધી કામ કરશે જ્યાં સુધી તે વિચિત્ર ન હોય, પરંતુ પછી તે ટુટ્ટે ઉલ્લંઘનકર્તા છે). હવે ધારો કે તે એક ઘટક છે અને તેના જેવા શિરોબિંદુઓ છે. ચાલો સૌથી ટૂંકા પાથ પર પ્રથમ શિરોબિંદુઓ હોઈએ. આ સુનિશ્ચિત કરે છે કે અને. કારણ કે, ત્યાં એક શિરોબિંદુ અસ્તિત્વમાં છે. ની ધાર-મહત્તમતાથી, અમે એક સંપૂર્ણ મેળ તરીકે અને એક સંપૂર્ણ મેળ તરીકે વ્યાખ્યાયિત કરીએ છીએ. તેનું ચોક્કસપણે અવલોકન કરો. ચાલો મહત્તમ માર્ગ હોવો જોઈએ જે એક ધારથી શરૂ થાય છે અને જેની ધાર અને વચ્ચે વૈકલ્પિક હોય છે. અંત કેવી રીતે આવી શકે? જ્યાં સુધી આપણે 'વિશેષ' શિરોબિંદુ પર ન પહોંચીએ જેમ કે અથવા, આપણે હંમેશા ચાલુ રાખી શકીએ છીએઃ દ્વારા મેળ ખાય છે, તેથી પ્રથમ ધાર અંદર નથી, તેથી બીજી શિરોબિંદુ એક અલગ ધાર દ્વારા મેળ ખાય છે અને આપણે આ રીતે ચાલુ રાખીએ છીએ. ચાલો તેના છેલ્લા શિરોબિંદુને દર્શાવીએ. જો છેલ્લી ધાર અંદર હોય, તો પછી હોવી જોઈએ, કારણ કે અન્યથા આપણે એક ધાર સાથે ચાલુ રાખી શકીએ છીએ (અથવા સુધી પહોંચવા માટે પણ). આ કિસ્સામાં આપણે વ્યાખ્યાયિત કરીએ છીએ. જો તેની છેલ્લી ધાર અંદર હોય, તો ચોક્કસપણે સમાન કારણોસર અને આપણે વ્યાખ્યાયિત કરીએ છીએ. હવે દરેક અન્ય ધાર સાથે સમ લંબાઈનું ચક્ર છે. હવે આપણે વ્યાખ્યાયિત કરી શકીએ છીએ (જ્યાં સપ્રમાણ તફાવત છે) અને આપણે એક વિરોધાભાસમાં સંપૂર્ણ મેળ મેળવીએ છીએ. ટુટ્ટે-બર્જ સૂત્રની સમાનતા ટુટ્ટે-બર્જ સૂત્ર કહે છે કે આલેખના મહત્તમ મેળનું કદ સમાન છે. સમાનરૂપે, મહત્તમ મેળ ખાતા શિરોબિંદુઓમાં મેળ ન ખાતા શિરોબિંદુઓની સંખ્યા સમાન હોય છે. આ સૂત્ર ટુટ્ટેના પ્રમેયને અનુસરે છે, જે અવલોકન સાથે કદની મેળ ખાતી હોય છે જો અને માત્ર ત્યારે જ જો નવા શિરોબિંદુઓ ઉમેરીને મેળવેલ આલેખ, દરેક મૂળ શિરોબિંદુ સાથે જોડાયેલો હોય, તો તે સંપૂર્ણ મેળ ખાતો હોય. કારણ કે કોઈપણ સમૂહ કે જે એક કરતાં વધુ ઘટકોમાં વિભાજિત થાય છે તેમાં તમામ નવા શિરોબિંદુઓ હોવા આવશ્યક છે, (*) જો અને માત્ર જો માટે સંતુષ્ટ છે. અનંત આલેખમાં જોડાયેલા અનંત આલેખ માટે કે જે સ્થાનિક રીતે મર્યાદિત હોય (દરેક શિરોબિંદુ મર્યાદિત ડિગ્રી ધરાવે છે), ટુટ્ટેની સ્થિતિનું સામાન્યીકરણ ધરાવે છેઃ આવા આલેખ સંપૂર્ણ મેળ ખાતા હોય છે જો અને માત્ર ત્યારે જ જો કોઈ મર્યાદિત સબસેટ ન હોય, જેને દૂર કરવાથી સંખ્યાબંધ મર્યાદિત વિચિત્ર ઘટકો બને છે જે સબસેટના કદ કરતા મોટા હોય. બાયપાર્ટાઇટ મેચિંગ હોલના મેરેજ થીયરમ પીટરસનના થીયરમ નોટ્સ રેફરન્સ મેચિંગ (ગ્રાફ થિયરી) ગ્રાફ થિયરીમાં થીયરમ્સ પણ જુઓ.