Skip to content

Study Note: Graph Theory and Topology

Note

ग्राफ सिद्धान्त र टोपोलोजी

ग्राफ $G = (V, E)$ शीर्षबिन्दु (vertices) र तिनलाई जोड्ने किनारा (edges) को समूह हो। शीर्षबिन्दुको डिग्री त्यसमा जोडिएका किनाराको सङ्ख्या हो। हातमिलाइ प्रमेय (Handshaking lemma): $\sum \deg(v) = 2|E|$; त्यसैले बिजोर डिग्री भएका शीर्षबिन्दुको सङ्ख्या सधैँ जोर हुन्छ।

ट्री चक्ररहित जोडिएको ग्राफ हो। $n$ शीर्षबिन्दुको ट्रीमा ठिक $n-1$ किनारा हुन्छन् र कुनै दुई शीर्षबिन्दुबिच एउटै मात्र पथ हुन्छ।

कोनिग्सबर्ग पुल समस्या

कोनिग्सबर्ग सहरका चार भूभाग सात पुलले जोडिएका थिए। सबै पुल एकपटक मात्र पार गरेर घुम्न सकिन्छ कि भन्ने प्रश्नलाई लियोनार्ड अयलरले सन् १७३६ मा ग्राफका रूपमा हल गरे; यसैबाट ग्राफ सिद्धान्त र टोपोलोजीको सुरुआत मानिन्छ। नियम: जोडिएको ग्राफमा अयलर पथ हुन बिजोर डिग्रीका शीर्षबिन्दु ० वा २ हुनुपर्छ, र अयलर परिपथ हुन सबै डिग्री जोर हुनुपर्छ। कोनिग्सबर्गका चारै भूभागको डिग्री बिजोर (५, ३, ३, ३) भएकाले यो सम्भव थिएन।

समतलीय ग्राफ र अयलरको सूत्र: $V - E + F = 2$। घन (cube) मा $8 - 12 + 6 = 2$।

टोपोलोजी

टोपोलोजीलाई "रबर पानाको ज्यामिति" भनिन्छ: तन्काउँदा वा बङ्ग्याउँदा (च्यात्ने वा टाँस्ने बिना) नबदलिने गुणको अध्ययन। टोपोलोजीका दृष्टिले कफी कप र डोनट (टोरस) एउटै हुन्, किनकि दुवैमा एउटा प्वाल छ। मोबियस पट्टीमा एउटै सतह र एउटै किनारा हुन्छ।