ग्राफ़ सिद्धान्त बाहरी कड़ियाँ दिक्चालन सूचीबढ़ाने मेंसंGraph Theory with ApplicationsDigraphs: Theory Algorithms and ApplicationsGraph Theory, by Reinhard DiestelGraph theory tutorialA searchable database of small connected graphsConcise, annotated list of graph theory resources for researchersrocsGraph Theory Software
ग्राफ़ सिद्धान्तसैद्धांतिक कम्प्यूटर विज्ञान
गणितसंगणक विज्ञानमॉडलविविक्त गणितफलनों
ग्राफ़ सिद्धान्त
Jump to navigation
Jump to search
 | यह लेख एक आधार है। जानकारी जोड़कर इसे बढ़ाने में विकिपीडिया की मदद करें। |
एक ग्राफ जिसमें छः नोड और सात कोर हैं।
गणित तथा संगणक विज्ञान में ग्राफ सिद्धांत (graph theory) में वस्तुओं से जुड़ी वस्तुओं और उनकी आपसी दूरी का अध्ययन किया जाता है। इस संदर्भ में ग्राफ उन गणितीय संरचनाओं को कहते हैं जो वस्तुओं के बीच जुड़े या युग्मित संबन्धों (pairwise relations) को मॉडल करने के काम आती हैं। इसकी तुलना किसी मानचित्र में शहरों के बीच बने सड़कों के जाल से कर सकते हैं। दो शहरों के बीच की दूरी उनके बीच बनी सड़क की लंबाई बताती है। यदि उन शहरों से बीच सीधी सड़क न हो, तो किसी अन्य शहर द्वारा वहाँ तक पहुँचने की दूरी निकाली जा सकती है।
इसके आरेखों और चित्रों में दर्शाने के लिए वस्तुओं को बिन्दु या गोले (node, vertex) से दर्शाया जाता है। इनके बीच के जुड़ाव को एक रेख द्वारा जिसे कोर (edges) कहते हैं। अतः ग्राफ शीर्षों (vertices or nodes) तथा उनको जोड़ने वाली कोरों (edges) का समुच्चय है। विविक्त गणित (discrete mathematics) में ग्राफ का अध्ययन एक महत्वपूर्ण विषय है।
ध्यान रहे कि 'ग्राफ सिद्धान्त' का 'ग्राफ', फलनों के आलेख (ग्राफ) यानि वक्र रेखा द्वारा किसी संबंध को दिखाने से बिलकुल भिन्न चीज है।
ग्राफ़ सिद्धांत का प्रयोग वस्तुओं के विशाल समूह में एक दूसरे से दूरी (या अन्तर) निकालने के लिए किया जाता है। ग्राफ़ सिद्धांत के अनुसार, इसी प्रकार आकड़ों के पुंजीकरण, वस्तुओं की समरूपता इत्यादि जैसे कार्यों का हल निकाला जा सकता है।
सामान्यतया ग्राफ़ को G=(V,E) से व्यक्त किया जाता है। यहाँ V बिन्दुओ यानि वस्तुओं का संग्रह है और E उनके बीच बने जोड़ों (कोर) का। ध्यान दीजिये कि एक ग्राफ़ में सभी बिन्दु एक दूसरे से जुड़े नहीं होते। केवल कुछ ही एक दूसरे से सीधे तौर पर जुड़े होते हैं। जैसे उपर दिये गए आरेख में बिन्दु २ और बिन्दु ६ के बीच कोई सीधा संबंध नहीं है।
बाहरी कड़ियाँ
आनलाइन पुस्तकें
Graph Theory with Applications (1976) by Bondy and Murty
Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin- Graph Theory, by Reinhard Diestel
अन्य स्रोत
- Graph theory tutorial
- A searchable database of small connected graphs
- Concise, annotated list of graph theory resources for researchers
rocs - a graph theory IDE- Graph Theory Software
श्रेणियाँ:
- ग्राफ़ सिद्धान्त
- सैद्धांतिक कम्प्यूटर विज्ञान
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.032","walltime":"0.046","ppvisitednodes":"value":46,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":4077,"limit":2097152,"templateargumentsize":"value":0,"limit":2097152,"expansiondepth":"value":3,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":0,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 30.051 1 साँचा:आधार","100.00% 30.051 1 -total"," 92.50% 27.798 1 साँचा:Asbox"],"scribunto":"limitreport-timeusage":"value":"0.009","limit":"10.000","limitreport-memusage":"value":787302,"limit":52428800,"cachereport":"origin":"mw1275","timestamp":"20190414014336","ttl":2592000,"transientcontent":false);mw.config.set("wgBackendResponseTime":108,"wgHostname":"mw1245"););
