Frucht's theorem
ફ્રુક્ટનો પ્રમેય એ 1936માં ડેન્સ કોનિગ દ્વારા અનુમાનિત અને 1939માં રોબર્ટ ફ્રુક્ટ દ્વારા સાબિત બીજગણિત આલેખ સિદ્ધાંતમાં એક પ્રમેય છે. તે જણાવે છે કે દરેક મર્યાદિત જૂથ એ મર્યાદિત દિશાહીન આલેખની સમપ્રમાણતાનું જૂથ છે. વધુ મજબૂત રીતે, કોઈપણ મર્યાદિત જૂથ G માટે અનંત રીતે ઘણા બિન-આઇસોમોર્ફિક સરળ જોડાયેલા આલેખ અસ્તિત્વમાં છે જેમ કે તેમાંના દરેકનું ઓટોમોર્ફિઝમ જૂથ G માટે આઇસોમોર્ફિક છે. પુરાવો વિચાર સાબિતીનો મુખ્ય વિચાર એ અવલોકન કરવાનો છે કે G નો કેલે ગ્રાફ, એકબીજાથી G ના જનરેટરને અલગ પાડવા માટે તેની ધાર પર રંગો અને દિશાઓના ઉમેરા સાથે, ઇચ્છિત ઓટોમોર્ફિઝમ જૂથ ધરાવે છે. તેથી, જો આ દરેક ધારને યોગ્ય સબગ્રાફ દ્વારા બદલવામાં આવે, જેમ કે દરેક રિપ્લેસમેન્ટ સબગ્રાફ પોતે અસમપ્રમાણ હોય અને બે રિપ્લેસમેન્ટ આઇસોમોર્ફિક હોય જો અને માત્ર જો તેઓ સમાન રંગની ધારને બદલે, તો પછી આ રિપ્લેસમેન્ટ કરીને બનાવેલ દિશાહીન ગ્રાફમાં પણ તેના સમપ્રમાણતા જૂથ તરીકે G હશે. આલેખનું કદ ત્રણ અપવાદો સાથે-3,4 અને 5 ક્રમના ચક્રીય જૂથો-દરેક જૂથને આલેખની સમપ્રમાણતા તરીકે રજૂ કરી શકાય છે, જેના શિરોબિંદુઓમાં માત્ર બે ભ્રમણકક્ષાઓ હોય છે. તેથી, આલેખમાં શિરોબિંદુઓની સંખ્યા જૂથના ક્રમ કરતાં બમણી હોય છે. અપવાદોના મોટા સમૂહ સાથે, મોટાભાગના મર્યાદિત જૂથોને શિરોબિંદુ-સંક્રમક આલેખની સમપ્રમાણતા તરીકે રજૂ કરી શકાય છે, જેમાં જૂથના ક્રમની સમાન સંખ્યાબંધ શિરોબિંદુઓ હોય છે. આલેખના વિશેષ પરિવારો ફ્રુક્ટના પ્રમેયની મજબૂત આવૃત્તિઓ છે જે દર્શાવે છે કે આલેખના અમુક પ્રતિબંધિત પરિવારો હજુ પણ કોઈપણ સમપ્રમાણતા જૂથને સાકાર કરવા માટે પૂરતા આલેખ ધરાવે છે. ફ્રુચે સાબિત કર્યું કે હકીકતમાં ઇચ્છિત ગુણધર્મ સાથે સંખ્યાબંધ 3-નિયમિત આલેખ અસ્તિત્વમાં છે; દાખલા તરીકે, ફ્રુક્ટ આલેખ, 12 શિરોબિંદુઓ અને 18 ધાર સાથેનો 3-નિયમિત આલેખ, કોઈ બિન-તુચ્છ સમપ્રમાણતા ધરાવતો નથી, જે તુચ્છ જૂથ માટે આ પ્રકારની અનુભૂતિ પ્રદાન કરે છે. ગેર્ટ સબિડુસીએ દર્શાવ્યું હતું કે કોઈપણ જૂથને તમામ હકારાત્મક પૂર્ણાંક મૂલ્યો k (નિયમિત આલેખ માટે અને k-રંગીન આલેખ માટે) માટે સંખ્યાબંધ ઘણા અલગ k-નિયમિત આલેખ, k-વર્ટેક્સ-જોડાયેલા આલેખ અથવા k-રંગીન આલેખના સમપ્રમાણતા જૂથો તરીકે અનુભવી શકાય છે. દરેક આલેખને તેની ધાર અને શિરોબિંદુઓના આંશિક નિયંત્રણ ક્રમમાંથી પુનઃનિર્માણ કરી શકાય છે, કે દરેક મર્યાદિત આંશિક ક્રમ બર્ખોફના પ્રતિનિધિત્વ પ્રમેય દ્વારા મર્યાદિત વિતરણ જાળીની સમકક્ષ છે, તે હકીકતો પરથી, તે અનુસરે છે કે દરેક મર્યાદિત જૂથને વિતરણ જાળીની સમપ્રમાણતા તરીકે અને જાળીના આલેખની, મધ્ય ગ્રાફ તરીકે અનુભવી શકાય છે. દરેક મર્યાદિત જૂથને મજબૂત નિયમિત આલેખની સમપ્રમાણતાના જૂથ તરીકે સમજવું શક્ય છે. દરેક મર્યાદિત જૂથને બે નંબરને અલગ પાડતા આલેખની સમપ્રમાણતા તરીકે પણ અનુભવી શકાય છેઃ એક વ્યક્તિ (અયોગ્ય રીતે) આલેખને બે રંગોથી રંગાવી શકે છે જેથી આલેખની કોઈ પણ સમપ્રમાણતા રંગને જાળવી ન શકે. જો કે, આલેખના કેટલાક મહત્વપૂર્ણ વર્ગો તમામ જૂથોને તેમની સમપ્રમાણતા તરીકે સમજવામાં અસમર્થ છે. કેમિલી જોર્ડને વૃક્ષોના સમપ્રમાણતા જૂથોને તુચ્છ જૂથ ધરાવતા મર્યાદિત જૂથોના સૌથી નાના સમૂહ તરીકે વર્ણવ્યા હતા અને એકબીજા સાથે સીધા ઉત્પાદનો અને સમપ્રમાણ જૂથો સાથે પુષ્પગુચ્છ ઉત્પાદનો હેઠળ બંધ કર્યા હતા; ખાસ કરીને, ક્રમ ત્રણનું ચક્રીય જૂથ વૃક્ષનું સમપ્રમાણતા જૂથ નથી. સમતલીય આલેખ પણ તમામ જૂથોને તેમની સમપ્રમાણતા તરીકે સમજવામાં સક્ષમ નથી; દાખલા તરીકે, એકમાત્ર મર્યાદિત સરળ જૂથો કે જે સમતલીય આલેખની સમપ્રમાણતા છે તે ચક્રીય જૂથો અને વૈકલ્પિક જૂથ છે. વધુ સામાન્ય રીતે, દરેક નાના બંધ આલેખ પરિવાર તેના આલેખની સમપ્રમાણતા દ્વારા તમામ મર્યાદિત જૂથોનું પ્રતિનિધિત્વ કરવામાં અસમર્થ હોય છે. લેઝલો બાબાઇ વધુ મજબૂત રીતે અનુમાન કરે છે કે દરેક નાના-બંધ કુટુંબ માત્ર મર્યાદિત રીતે ઘણા બિન-ચક્રીય મર્યાદિત સરળ જૂથોનું પ્રતિનિધિત્વ કરી શકે છે. અનંત આલેખ અને જૂથો ઇઝબિકીએ 1959માં આ પરિણામોને વિસ્તૃત કર્યા અને દર્શાવ્યું કે કોઈપણ મર્યાદિત સમપ્રમાણતા જૂથને સાકાર કરતા અસંખ્ય અનંત આલેખ હતા. છેવટે, જોહાન્સ ડી ગ્રૂટ અને સબિડુસીએ 1959/1960 માં સ્વતંત્ર રીતે સાબિત કર્યું કે કોઈપણ જૂથ (જૂથ મર્યાદિત હોવાની ધારણાને છોડીને, પરંતુ પસંદગીના સ્વયંસિદ્ધની ધારણા સાથે) અનંત આલેખની સમપ્રમાણતાના જૂથ તરીકે અનુભવી શકાય છે. સંદર્ભો સ્ત્રોતો. . . . . . જેમ ટાંકવામાં આવ્યું છે. . . ગ્રાફ સિદ્ધાંતમાં બીજગણિત ગ્રાફ સિદ્ધાંત પ્રમેયો