శాస్త్ర విజ్ఞానము ఇప్పుడు మిగతా భారతీయ భాషల్లో కూడా... ఇక్కడ నొక్కి చూడండి. For Science in other Indian Languages. Please Click here.

కోనిగ్స్ బర్గ్ వంతెనలు

Posted by శ్రీనివాస చక్రవర్తి Sunday, August 2, 2009

అనగనగా కోనిగ్స్ బర్గ్ అనే ఊళ్లో 7 వంతెనలు ఉండేవి (చిత్రం 1). నగరం లోంచి ప్రవహించే కాలువల మీదుగా కట్టబడ్డ ఈ వంతెనలు నగరంలో వివిధ ప్రాంతాలని కలిపేవి. ఈ వంతెనల గురించిన ఓ చక్కని గణిత సమస్య ఒకటుంది.

"ఎక్కిన వంతెన ఎక్కకుండా వంతెనలన్నీ తిరిగి రావాలి. ఎలా?"

ఇంచుమించు ఇలాంటిదే మరో సమస్య కూడా ఉంది. చిన్నప్పుడు అందరూ దాంతో ఆడుకుని ఉంటారు. ఈ కింద కనిపించే చిత్రాన్ని (చిత్రం 2) చెయ్యి ఎత్తకుండా, గీసిన గీత మళ్లీ గియ్యకుండా, పెన్నుతో కాగితం మీద గీయాలి.




అయితే ఈ సమస్యకి పరిష్కారం లేదు. (కొంచెం మోసం చేసి, పేజీ మడిచి, మడత పేచీ పెట్టి పరిష్కరించే పద్ధతులేవో ఉన్నాయి గాని కని ఆవి నిజానికి సమస్య నియమాలని ఉల్లంఘిస్తాయి కనుక పరిష్కారాలు కావు). కాని ఊరికే పరిష్కారం లేదంటే సరిపోదు. దాన్ని నిరూపించాలి.

అదృష్టవశాత్తు ఈ విషయాన్ని నిరూపించడం అంత కష్టం కాదు.

నిరూపణని వివరించే ముందు కొంచెం పరిభాషని పరిచయం చెయ్యాలి. పై చిత్రాలలో పలు గీతలు కలిసే బిందువుని శీర్షం (vertex) అంటారు. శీర్షాలని కలిపే గీతలని అంచులు (edges) అంటారు. ఒక శీర్షం వద్ద కలిసే మొత్తం అంచుల సంఖ్యని సత్తా (degree) అంటారు. అలా శీర్షాలని అంచులతో కలపగా ఏర్పడే జాలాలని graphs అంటారు. అలాంటి గ్రాఫ్ ల అధ్యయనాన్నే జాల సిద్ధాంతం (graph theory) అంటారు.

ఇప్పుడు చిత్రం 2 లోని చిత్రాన్ని పెన్నుతో గీసిన గీత గియ్యకుండా, చెయ్యెత్తకుండా, గీసినప్పుడు ఒక శీర్షం దరిదాపుల్లో పెన్ను కదలికలు ఈ మూడు రకాలుగా ఉంటుంది:

1వ రకం: ఒక అంచు వెంబడి శీర్షాన్ని చేరి, మరో అంచు వెంబడి శీర్షానికి దూరం అవుతుంది.
2 వ రకం: శీర్షం నుండి బయలుదేరి, ఆ శీర్షాన్ని తాకే ఒక అంచు ద్వారా అక్కణ్ణుంచి దూరంగా జరుగుతుంది.
(అలాంటప్పుడు ఆ శీర్షం పెన్ను యొక్క మొత్తం రేఖా పథానికి మొదటి బిందువు అవుతుంది.)
3వ రకం: ఒక అంచు వెంబడి శీర్షాన్ని చేరుకుని ఇక ముందుకి పోకుండా అక్కడే ఆగిపోతుంది. (అంటే ఆ శీర్షం
పెన్ను యొక్క మొత్తం రేఖాపథానికి చివరి బిందువు అన్నమాట.)

ఏదైనా శీర్షం యొక్క సత్తా సరి సంఖ్య అయితే, దాని వద్ద పెన్ను కదలికలు 1 రకం కదలికలు అవుతాయి.
ఏదైనా శీర్షం యొక్క సత్తా బేసి సంఖ్య అయితే, దాని వద్ద పెన్ను కదలికలు పై మూడు రకాలలో ఏ రకమైనవైనా కావచ్చు.

పెన్ను యొక్క రేఖా పథానికి కొసలు రెండే ఉంటాయి కనుక బేసి సంఖ్యలో సత్తా ఉన్న శీర్షాలు రెండే ఉండాలి. అప్పుడు పెన్ను వాటిలో ఒక దాని వద్ద మొదలై, రెండవ శీర్షం వద్ద ఆగుతుంది. లేదా అన్నీ సరి సంఖ్య సత్తా గల శీర్షాలు అయితే పెన్ను ఆరంభం అయిన బిందువు వద్దనే చివరికి ఆగుతుంది.

అంటే పై సమస్యకి పరిష్కారం ఉండాలంటే ఇదీ నియమం:
"బేసి సంఖ్య సత్తా గల శీర్షాలు ఉంటే రెండు గాని, లేకుంటే సున్నాగాని ఉండాలి."

పైన చెప్పుకున్న కోనిగ్స్ బర్గ్ సమస్య కూడా ఇలాంటిదే. వంతెనల అమరికని ఒక గ్రాఫ్ రూపంలో వ్యక్తం చేస్తే ఇలా ఉంటుంది (చిత్రం 3).

ఈ గ్రాఫ్ లో మొత్తం నాలుగు శీర్షాలు, ఏడు అంచులు (వంతెనలు) ఉన్నాయి. నాలుగు శీర్షాల్లోమూడింటి సత్తా మూడు (బేసి సంఖ్య). ఒక దాని సత్తా నాలుగు. బేసి సంఖ్య సత్తా ఉన్న శీర్షాలు రెండు కన్నా ఎక్కువ ఉన్నాయి కనుక సమస్య పరిష్కరించడానికి కావలసిన నియమాలు ఉల్లంఘింపబడ్డాయి. అంటే కోనిగ్స్ బర్గ్ సమస్యకి పరిష్కారం లేదన్నమాట.

ఈ నియమాలని చిత్రం 2 లో ప్రదర్శించిన బొమ్మలకి కూడా వర్తింపజేసి వాటిని చెయ్యెత్తకుండా గియ్యడం అసంభవం అని నిరూపించొచ్చు.

ఈ నియమాలని మొట్టమొదట సూత్రీకరించిన వాడు ప్రఖ్యాత గణితవేత్త ఆయిలర్ (Euler). ఆ నియమాలు ఉల్లంఘించబడితే పరిష్కారం ఉండదన్నది గుర్తించడం సులభమే. అలాంటి నియమాలని అవసరమైన నియమాలు (necessary conditions) అంటారు.

కాని ఆ నియమాలు ఉల్లంఘింపబడకపోతే పరిష్కారం ఉంటుందని నమ్మకం ఏమిటి? అంటే ఆ నియమాలు సంపూరక నియమాలా (sufficient conditions) అన్న ప్రశ్న వస్తుంది. ఇవి సంపూరక నియమాలు కూడా అని నిరూపించినవాడు పందొమ్మిదవ శతాబ్దానికి చెందిన జర్మన్ గణితవేత్త కార్ల్ హీర్ హోల్జర్ (Carl Hierholzer). హీర్ హోల్జర్ తన మరణానికి కొంచెం ముందుగా ఈ సమస్య పరిష్కారాన్ని తన మిత్రుడికి వివరిస్తే, హీర్ హోల్జర్ మరణానంతరం ఆ మిత్రుడు ఆ నిరూపణని ప్రచురించాడట.

కోనిగ్స్ బర్గ్ వంతెనల సమస్య ఒక విధంగా Graph theory కి శ్రీకారం చుట్టింది. అంతే కాదు, ఆ సమస్య టోపాలజీ (Topology) అనే ఓ ముఖ్య గణిత విభాగానికి పునాది రాళ్లలో ఒకటయ్యింది.

మరింత సమాచారం కోసం:
http://en.wikipedia.org/wiki/Seven_Bridges_of_Konigsberg

రచయిత: డాక్టర్ వి.శ్రీనివాస చక్రవర్తి.

0 comments

Post a Comment

postlink

సైన్సు పుస్తకాలు ఇక్కడ నుంచి కొనవచ్చు.. click on image

అంతరిక్షం చూసొద్దాం రండి

"తారావళీ సూపర్ ట్రావెల్స్" తరపున స్వాగతం... సుస్వాగతం!" "తారావళీ సూపర్ ట్రావెల్స్" గురించి ప్రత్యేకించి మీకు చెప్పనవసరం లేదు. తారాంతర యాత్రా సేవలు అందించడంలో మాకు 120 ఏళ్ల అనుభవం ఉంది. మా హెడ్ క్వార్టర్స్ భూమి మీదే ఉన్నా, సౌరమండలం బయట మాకు చాలా బ్రాంచీలు ఉన్నాయని మీకు బాగా తెలుసు. అంతరిక్షానికి వెళ్ళడానికి ఇక్కడ నొక్కండి

Printer-friendly gadget

Print

ఈ బ్లాగులోని పోస్ట్ లు ఆటోమేటిక్ గా మీ మెయిల్ ఇన్బాక్స్ లోకి చేరడానికి మీ ఈ-మెయిల్ ఐడీని ఎంటర్ చేసి చందాదారులు కండి Enter your email address:

Delivered by FeedBurner

Total

Blogumulus by Roy Tanck and Amanda FazaniInstalled by CahayaBiru.com

Label Category

Followers

archive

Total Pageviews

There was an error in this gadget
There was an error in this gadget

విజ్ఞానులు

GuestBooker 2.5

Recent Posts

Popular Posts

Follow by Email