આલેખશાસ્ત્ર

આલેખશાસ્ત્ર (graph theory) : આલેખોના અભ્યાસને લગતું ગણિતશાસ્ત્ર. આ શાખાને રેખા-સંકુલ(net-works)નું ગણિત પણ કહે છે. આલેખ એટલે સાંત સંખ્યાનાં બિંદુઓ અને આ બિંદુઓની કેટલીક જોડને જોડતી રેખાઓનો ગણ. આ રેખા સીધી રેખા હોવા ઉપરાંત વક્રરેખા પણ હોઈ શકે. આ વ્યાખ્યા ઉપરથી એક બાબતનો તુરત ખ્યાલ આવશે કે બીજગણિત અને કલનશાસ્ત્ર(calculus)માં આવતા વિધેય અને સમીકરણના આલેખ સાથે પ્રસ્તુત આલેખને કોઈ સંબંધ નથી. બંને ખ્યાલ માટે આલેખ શબ્દ હવે રૂઢ થઈ ગયો છે.

આલેખશાસ્ત્રનો ઉદભવ 18મી સદીમાં થયો ગણાય છે. ગણિતશાસ્ત્રી લીયોનાર્ડ ઑયલર (1707-1782) આ શાસ્ત્રનો પિતા લેખાય છે. ઑયલરે કનીગ્સબર્ગ પુલ કોયડો રજૂ કરેલો. પૂર્વ પ્રશિયાનું કનીગ્સબર્ગ (જે અત્યારે કાલીનીનગ્રાડ તરીકે ઓળખાય છે.) શહેરમાં પ્રેગેલ નદી આવેલી છે. આ નદીના બે ટાપુઓ અને કિનારાઓ સાત પુલોથી જોડાયેલા છે.

પ્રશ્ન એ છે કે કોઈ શહેરી ઘેરથી નીકળી દરેક પુલ પર એક અને એક જ વાર પસાર થઈ ઘેર પાછો ફરે એ રીતે શહેરની લટાર મારી શકે ખરો ? આ પ્રશ્નનો ઉકેલ પણ ઑયલરે જ આપ્યો અને આ ઉકેલની રીતમાંથી આલેખશાસ્ત્રનો જન્મ થયો. પ્રશ્નના ઉકેલ માટે ટાપુઓ અને કિનારાના પ્રદેશને ઑયલરે બિંદુઓ વડે દર્શાવ્યા અને દરેક પુલને સંગતબિંદુઓને જોડતી રેખા (સીધી કે વક્ર) વડે દર્શાવ્યો. હવે ઑયલરની નીચેની આકૃતિ મળી.

આકૃતિના સંદર્ભમાં ઑયલરનો પ્રશ્ન આ રીતે પૂછી શકાય. આકૃતિના કોઈ પણ બિંદુ (A, B, C કે D) થી શરૂ કરી પ્રત્યેક રેખા પર એક અને એક જ વાર પસાર થઈ પ્રારંભબિંદુએ પાછા ફરી શકાય ખરું ? ઑયલરે આવી આકૃતિને આલેખ (graph) કહી અને તેણે તેના 1736 માં પ્રસિદ્ધ થયેલા સંશોધનપત્રમાં વ્યાપક રીતે કયા પ્રકારના આલેખની પ્રત્યેક રેખા એક અને એક જ વાર ઓળંગી આલેખ પર ફરી શકાય એ પ્રશ્નની ચર્ચા કરી.

નીચેની આકૃતિઓમાં ચાર બિંદુઓથી મળતા વિવિધ આલેખો બતાવ્યા છે.

ઑયલરના પ્રશ્ન સાથે સંકળાયેલી આકૃતિમાં પણ ચાર જ બિંદુઓ હોવા છતાં તે આલેખ, ઉપરના બધા જ આલેખોથી જુદો પડે છે. ઑયલરના આલેખમાં A અને Bને જોડતી બે રેખાઓ છે. તેવી જ રીતે A અને Dને જોડતી પણ બે રેખાઓ છે. ઉપરના બધા આલેખોમાં કોઈ બિંદુજોડને બે કે વધુ રેખાઓ જોડતી નથી. જે આલેખમાં કોઈ બિંદુજોડને બે કે વધુ રેખાઓ જોડતી હોય તે આલેખને બહુઆલેખ (multigraph) કહેવામાં આવે છે. ઑયલરનો આલેખ એ બહુઆલેખ છે. જો આલેખમાં કોઈ એક જ બિંદુએ શરૂ થઈ ત્યાં જ પૂરો થતો પાશ (loop) હોય તો તે અર્ધ આલેખ (pseudograph) કહેવાય છે. નીચેની આકૃતિ અર્ધ આલેખ દર્શાવે છે.

માત્ર બિંદુઓ અને રેખાઓ વડે બનતી આકૃતિઓનો ગણિતમાં કે જ્ઞાન-વિજ્ઞાનની અન્ય શાખાઓમાં શો ઉપયોગ હોઈ શકે એવો પ્રશ્ન અસ્થાને નથી. 1736માં ઑયલરનું સંશોધનપત્ર પ્રસિદ્ધ થયા બાદ લાંબા સમય સુધી ગણિતશાસ્ત્રીઓના મનમાં આલેખની સંકલ્પનાની ઉપયોગિતા વિશે સ્પષ્ટતા ન હતી. મનોરંજન માટેના કેટલાક ગાણિતિક કોયડાઓ ઉકેલવા સિવાય આલેખશાસ્ત્રનો કોઈ ઉપયોગ હોઈ શકે કે કેમ એ અંગે તેઓને શંકા હતી. એટલે જ ઑયલરનું વિખ્યાત થઈ ચૂકેલું સંશોધનપત્ર એકાદ સદીના લાંબા ગાળા માટે ખાસ કોઈ ધ્યાન અપાયા વગરનું પડ્યું રહ્યું. પરંતુ ઓગણીસમી સદીની અધવચ્ચે આલેખનો ખ્યાલ કેટલાંક જુદાં જુદાં ક્ષેત્રોના પ્રશ્નોના ઉકેલમાં બિલકુલ અણધારી રીતે ઉપયોગી થતો દેખાયો. 1847 માં ભૌતિકશાસ્ત્રી કિરચોફે વિદ્યુત-નેટવર્કની જુદી જુદી શાખાઓમાં વહેતા વિદ્યુતપ્રવાહની ગણતરી માટે આલેખની પદ્ધતિ સફળતાપૂર્વક અપનાવી. 1857માં કૅલી નામના ગણિતશાસ્ત્રીએ આલેખશાસ્ત્રમાં વૃક્ષનો ખ્યાલ વિકસાવ્યો અને તેનો ઉપયોગ કાર્બન પરમાણુ ધરાવતા સંતૃપ્ત હાઇડ્રોકાર્બન C_nH_2n+2ના સમઘટકો(isomers)ની ગણતરી માટે કર્યો. 1869ની સાલમાં જોર્દાં નામના ફ્રેંચ ગણિતશાસ્ત્રીએ કૅલીથી સ્વતંત્ર રીતે વૃક્ષનો ખ્યાલ શોધ્યો અને તેનો વિગતવાર અભ્યાસ કર્યો. હવે તો આલેખશાસ્ત્રની રીતો મનોવિજ્ઞાન, અર્થશાસ્ત્ર, વિદ્યુતશાસ્ત્ર, રસાયનશાસ્ત્ર, વાહનવ્યવહાર અને સંદેશાવ્યવહારના પ્રશ્નોના ઉકેલ માટે ઉપયોગી સાબિત થઈ છે. 1936માં માનસશાસ્ત્રી લેવિને મનોવૈજ્ઞાનિક પ્રશ્નોના સમજવા માટે સમતલ ભૌમિતિક આકૃતિઓનો ઉપયોગ કર્યો. આના ઉપરથી કેટલાક અન્ય મનોવૈજ્ઞાનિકોએ વ્યક્તિઓને બિંદુઓ અને વ્યક્તિ-વ્યક્તિ વચ્ચે પ્રેમ કે ધિક્કાર જેવી લાગણીઓ અને અન્ય સંબંધોને રેખાઓ વડે દર્શાવી તેનાથી મળતા આલેખોનો મનોવૈજ્ઞાનિક પ્રશ્નોના ઉકેલમાં ઉપયોગ કર્યો.

વીસમી સદીમાં આલેખશાસ્ત્રનો અભ્યાસ પૂર્ણકળાએ પહોંચ્યો. આલેખમાં રેખાઓની લંબાઈનું મહત્વ નથી; માત્ર બિંદુઓ અને રેખાઓની સ્થિતિનું જ મહત્વ છે. આથી આલેખશાસ્ત્ર સંસ્થિતિવિદ્યા(topology)નો એક ભાગ લેખાય છે. બીજી બાજુ આલેખશાસ્ત્રમાં એક બિંદુ અન્ય બિંદુઓ સાથે કેટલી રીતે જોડાયેલું છે વગેરે ગણતરીઓ આવતી હોવાથી તે સંચયવિદ્યા- (combinatorics)નો પણ ભાગ ગણાય છે. ઉપરાંત બીજગણિત (algebra) અને શ્રેણિકશાસ્ત્ર (matrix theory) જોડે પણ આલેખશાસ્ત્રને ઘનિષ્ઠ સંબંધ છે.

આલેખની મદદથી ઉકેલી શકાતો એક રસપ્રદ કોયડો જોઈએ. રામસેના કોયડા તરીકે જાણીતો આ કોયડો નીચે મુજબ છે :

છ વ્યક્તિઓના સમૂહમાં ઓછામાં ઓછી ત્રણ વ્યક્તિઓ પરસ્પર પરિચિત હોય અથવા તો ઓછામાં ઓછી ત્રણ વ્યક્તિઓ એવી હોય જેમાંથી કોઈ પણ બે એકબીજીથી પરિચિત ન હોય એમ સાબિત કરો.

છ વ્યક્તિઓને બિંદુઓ A, B, C, D, E, F વડે દર્શાવીએ. જે બે વ્યક્તિઓ પરસ્પર પરિચિત હોય તે સંગત બિંદુઓને કાળા રંગની રેખા વડે જોડીએ. જો બે વ્યક્તિઓ એકબીજીથી અપરિચિત હોય તો એ બે બિંદુઓને લાલ રંગની રેખા વડે જોડીએ તો છમાંનું પ્રત્યેક બિંદુ બાકીના દરેક બિંદુ જોડે બેમાંથી એક રંગની રેખા વડે જોડાયેલું હશે અને આપણને એક આલેખ મળશે. આપણે એમ બતાવવું જોઈએ કે આ આલેખમાં ઓછામાં ઓછો એક ત્રિકોણ ભૂરા રંગની બાજુઓવાળો મળે અથવા તો ઓછામાં ઓછો એક ત્રિકોણ લાલ રંગની બાજુઓવાળો મળે, Aનો વિચાર કરીએ તો તે બાકીના પાંચ બિંદુઓમાંથી ત્રણની જોડે એક જ રંગની રેખાથી જોડાયું હશે. ચોકસાઈ ખાતર ધારીએ કે A બિંદુ B, C અને F જોડે કાળા રંગની રેખાથી જોડાયું છે.

હવે જો રેખા ખંડો માંથી કોઈ પણ એકનો રંગ કાળો હોય તો આપણને કાળા રંગની બાજુઓવાળો એક ત્રિકોણ મળશે. જો આ ત્રણેય રેખાખંડોનો રંગ લાલ હોય તો ત્રિકોણ BCF ની ત્રણેય બાજુઓ લાલ રંગની હશે.

આમ જોઈ શકાય છે કે આલેખની મદદથી કેટલાક ગૂંચવણભર્યા દેખાતા કોયડા સરળ રીતે ઉકેલી શકાય છે. ઑયલરે એવું સાબિત કર્યું કે આલેખ જો અવિભક્ત હોય (એટલે કે સળંગ હોય, બે કે વધુ ભાગમાં વહેંચાયેલો ન હોય) અને જો આલેખના દરેક બિંદુમાંથી યુગ્મસંખ્યા(even number)માં રેખાઓ નીકળતી હોય તો અને તો જ એ આલેખની પ્રત્યેક રેખાને એક અને એક જ વખત ઓળંગી પ્રારંભબિંદુએ પાછા ફરી શકાય. કનીગ્સબર્ગ પુલના કોયડાનો આલેખ અવિભક્ત તો છે, પરંતુ તેના પ્રત્યેક બિંદુમાંથી અયુગ્મ (odd) સંખ્યામાં રેખાઓ નીકળવાની શરતનું તેમાં પાલન થતું નથી (એથી ઊલટું, પ્રત્યેક બિંદુમાંથી અયુગ્મસંખ્યામાં રેખાઓ નીકળે છે). આથી કનીગ્સબર્ગ પુલના પ્રશ્નનો જવાબ નકારમાં છે.

ગણિતશાસ્ત્રમાં ખૂબ જાણીતો બનેલો અને દીર્ઘકાળ પર્યંત વણઊકલ્યો રહેલો આલેખશાસ્ત્રનો એક કોયડો એ ચાર રંગનો કોયડો (four colour problem) છે. 1850ની સાલથી જાણીતા બનેલા આ કોયડાનો ઉકેલ છેક 1976ની સાલમાં અમેરિકાની ઇલિનૉઈ યુનિવર્સિટીના એપેલ અને હેકિન નામના ગણિત-શાસ્ત્રીઓએ આપ્યો. તેઓએ કમ્પ્યૂટર(ગણકયંત્ર)નો વિપુલ પ્રમાણમાં ઉપયોગ કરીને સિદ્ધ કર્યું કે ચાર રંગ અંગેનું અનુમાન સાચું છે. આ અનુમાન પ્રમાણે ગમે તેટલી સંખ્યાના દેશોવાળા નકશાને માત્ર ચાર જુદા જુદા રંગો વડે કોઈ પણ બંને પડોશી દેશના રંગ સરખા ન હોય તે રીતે રંગી શકાય.

મહાવીરેન્દ્ર હરિપ્રસાદ વસાવડા