समतल आलेख: Difference between revisions

Revision as of 03:15, 10 July 2023

उदाहरण आलेख
तलीय	नॉनयोजना
File:Butterfly graph.svg तितली आलेख	File:Complete graph K5.svg संपूर्ण आलेख K₅
File:CGK4PLN.svg संपूर्ण आलेख K₄	File:Biclique K 3 3.svg उपयोगिता आलेख K_3,3

आलेख सिद्धांत में, एक समतल आलेख एक असतत आलेख होता है जिसे समतल (ज्यामिति) में आलेख अंतर्निहित किया जा सकता है, अर्थात, इसे समतल पर इस तरह से खींचा जा सकता है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद करते है। दूसरे शब्दों में, इसे इस तरह से खींचा जा सकता है कि कोई भी किनारा एक-दूसरे को पार न कर सके।^[1]^[2] इस तरह के आलेख को समतल आलेख अंतर्निहित कहा जाता है। एक समतल आलेख को एक समतल आलेख अंतर्निहित के रूप में परिभाषित किया जा सकता है, जिसमें एक समतल पर प्रत्येक नोड से एक बिंदु तक और प्रत्येक किनारे से उस समतल पर एक समतल वक्र तक मैपिंग की जाती है, जैसे कि प्रत्येक वक्र के उच्चतम बिंदु उसके अंत से मैप किए गए बिंदु होते है। नोड्स, और सभी वक्र अपने उच्चतम बिंदुओं को छोड़कर असंयुक्त होते है।ka

प्रत्येक आलेख जो एक समतल पर खींचा जा सकता है, उसे त्रिविम प्रक्षेपण के माध्यम से गोले पर भी खींचा जा सकता है।

समतल आलेख संयोजक मानचित्रों या घुमाव प्रणाली द्वारा एन्कोड किया जा सकता है।

गोले पर संस्थानिक रूप से समतुल्य आलेखों का एक समतुल्य वर्ग, सामान्यतः आलेख सिद्धांत की अनुपस्थिति जैसी अतिरिक्त मान्यताओं के साथ, एक समतल मानचित्र कहलाता है। चूँकि समतल आलेख का एक बाहरी या असीमित फलन होता है (आलेख सिद्धांत), समतल मानचित्र के किसी भी फलन की कोई विशेष स्थिति नहीं होती है।

समतलीय आलेख किसी दिए गए जीनस (गणित) की सतह पर खींचे जाने योग्य आलेख के लिए सामान्यीकृत होते है। इस वाक्यांश में, समतलीय आलेख में आलेख जीनस 0 होता है, क्योंकि समतल (और गोला) जीनस 0 होती है। अन्य संबंधित विषयों के लिए आलेख अंतर्निहित देखें।

समतलीयता मानदंड

कुराटोव्स्की और वैगनर के प्रमेय

File:Tesseract graph nonplanar visual proof.svg

Proof without words that a hypercube graph is non-planar using Kuratowski's or Wagner's theorems and finding either K₅ (top) or K_3,3 (bottom) subgraphs

पोलैंड के गणितज्ञ काज़िमिर्ज़ कुराटोव्स्की ने निषिद्ध आलेख वर्णन के संदर्भ में समतल आलेख का एक वर्णन प्रदान किया था, जिसे अब कुराटोव्स्की के प्रमेय के रूप में जाना जाता है:

एक आलेख (असतत गणित) परिमित और अनंत आलेख समतल होते है यदि इसमें आलेख सिद्धांत की वाक्यांश सम्मलित नहीं होती है आलेख जो संपूर्ण आलेख का एक उपवर्ग (आलेख सिद्धांत) होता है

K 5

या संपूर्ण आलेख

K 3,3

(उपयोगिता आलेख)।

आलेख का एक उपवर्ग (आलेख सिद्धांत) किनारों में से उत्पन्न होता है (उदाहरण के लिए, एक किनारे को बदलना)। • —— • to • — • — • ) शून्य या अधिक होता है

File:Nonplanar no subgraph K 3 3.svg

संख्या वाले आलेख का एक उदाहरण

K 5

या

K 3,3

उपआलेख. चूँकि, इसमें एक उपवर्ग सम्मलित है

K 3,3

और इसलिए गैर-तलीय है।

उपवर्गों पर विचार करने के अतिरिक्त, वैगनर का प्रमेय लघु (आलेख सिद्धांत) से संबंधित होता है:

एक परिमित आलेख समतलीय होता है

K 5

या

K 3,3

एक लघु (आलेख सिद्धांत) होता है।

आलेख का एक लघु (आलेख सिद्धांत) एक उपआलेख एक किनारे को बार-बार एक शीर्ष में अनुबंधित करने से उत्पन्न होता है, जिसमें मूल अंत-शीर्ष का प्रत्येक गुण नए शीर्ष का गुण बन जाता है।

File:Kuratowski.gif

एक एनीमेशन जो दर्शाता है कि पीटरसन आलेख में मामूली समरूपी सम्मलित है

K 3,3

आलेख, और इसलिए गैर-तलीय है

क्लॉस वैगनर (गणितज्ञ) ने पूछा कि क्या आलेख का कोई लघु-बंद वर्ग निषिद्ध लघु के एक सीमित समूह द्वारा निर्धारित किया जा सकता है। यह अब रॉबर्टसन-सेमुर प्रमेय के एक लंबी श्रृंखला में सिद्ध हुआ है। इस प्रमेय की भाषा में, $K 5$ और $K 3,3$ परिमित समतलीय आलेख के वर्ग के लिए निषिद्ध अवयस्क होते है।

अन्य मानदंड

व्यवहार में, यह तय करने के लिए कि कोई दिया गया आलेख समतल है या नहीं, यह पता करने के लिए कुराटोस्की का उपयोग किया जाता है। चूँकि, इस समस्या के लिए तेज़ कलन विधि उपस्थित है: एक आलेख के लिए $n$ शीर्ष, समय पर निर्धारित करना संभव है $O (n)$ (रैखिक समय) आलेख समतलीय हो सकता है (तलीयता परीक्षण देखें)।

एक सरल, संपर्क, समतलीय आलेख के लिए $v$ शीर्ष और $e$ किनारे और $f$ चेहरों के लिए निम्नलिखित सरल स्थितियाँ लागू होती है $v \geq 3$ :

प्रमेय 1. $e \leq 3 v - 6$ ,
प्रमेय 2. यदि लंबाई 3 का कोई चक्र नहीं है, तो $e \leq 2 v - 4$ .
प्रमेय 3. $f \leq 2 v - 4$ .

इस अर्थ में, समतलीय आलेख विरल आलेख होते है, इसमें $O (v)$ किनारे, अधिकतम से बिल्कुल छोटे $O (v 2)$ लेखाचित्र {{गणित|K_3,3}उदाहरण के लिए,} में 6 शीर्ष, 9 किनारे और लंबाई 3 का कोई चक्र नहीं है। इसलिए, प्रमेय 2 के अनुसार, यह समतल नहीं हो सकता है। यह प्रमेय समतलता के लिए आवश्यक स्थितिें प्रदान करते है, और इसलिए इसका उपयोग केवल यह सिद्ध करने के लिए किया जा सकता है कि आलेख समतल नहीं है। यदि प्रमेय 1 और 2 दोनों विफल हो जाते है, तो अन्य विधियों का उपयोग किया जा सकता है।

व्हिटनी का समतलीय मानदंड एक बीजगणितीय दोहरे के अस्तित्व के आधार पर एक वर्णन प्रदान करता है,
मैक लेन का समतलीय मानदंड, उनके चक्र स्थानों के माध्यम से, परिमित समतलीय आलेख का बीजगणितीय वर्णन प्रदान करता है,
फ्रैसेसिक्स-रोसेनस्टीहल प्लैनरिटी मानदंड गहराई-प्रथम किनारों के द्विविभाजन के अस्तित्व के आधार पर एक वर्णन प्रदान करता है। यह बाएँ-दाएँ समतलता परीक्षण कलन विधि का केंद्र होता है,
श्नाइडर का प्रमेय क्रम आयाम के संदर्भ में समतलता का वर्णन प्रदान करता है,
कॉलिन डी वेरडीयर का प्लानेरिटी मानदंड आलेख द्वारा परिभाषित कुछ श्रोडिंगर परिचलनों के दूसरे संख्या की अधिकतम बहुलता के आधार पर एक वर्णन प्रदान करता है।
हनानी-टुट्टे प्रमेय में कहा गया है कि एक आलेख समतल होता है यदि और केवल तभी जब इसमें एक आलेख होता है जिसमें किनारों का प्रत्येक स्वतंत्र जोड़ उप संख्या को पार करता है, इसका उपयोग समीकरण मॉड्यूलो 2 की प्रणाली के माध्यम से समतलीय आलेख को चित्रित करने के लिए किया जा सकता है।

गुण

यूलर का सूत्र

यूलर के सूत्र में कहा गया है कि यदि एक परिमित, (आलेख सिद्धांत), समतलीय आलेख बिना किसी किनारे के समतल में खींचा जाता है, और $v$ शीर्ष की संख्या है, $e$ किनारों की संख्या है और $f$ तो फलनों की संख्या है।

v-e+f=2.

उदाहरण के रूप में, ऊपर दिए गए तितली आलेख में, $v = 5$ , $e = 6$ और $f = 3$ .

सामान्यतः, यदि गुण सभी समतलीय आलेखों के लिए मान्य है $f$ , आलेख में कोई भी परिवर्तन जो आलेख को समतल रखते हुए एक अतिरिक्त संकया प्राप्त होती है, $v - e + f$ एक अपरिवर्तनीय. चूंकि गुण सभी आलेख के लिए मान्य है $f = 2$ , गणितीय प्रेरण द्वारा यह सभी स्थितियों के लिए लागू होता है। यूलर के सूत्र को इस प्रकार भी सिद्ध किया जा सकता है: यदि आलेख एक ट्री नहीं है, $v - e + f$ । यह तब तक दोहराएँ जब तक शेष आलेख एक ट्री न बन जाए, ट्री के पास है $v = e + 1$ और $f = 1$ , और $v - e + f = 2$ । ई., यूलर विशेषता 2 है।

एक परिमित में, आलेख सिद्धांत, सरल आलेख, समतल आलेख, (संभवतः बाहरी को छोड़कर) कम से कम तीन किनारों से घिरा होता है और प्रत्येक किनारा अधिकतम दो संख्याओ के पास होता है, यूलर के सूत्र का उपयोग करके, यह दिखाया जा सकता है कि ये आलेख इस अर्थ में विरल है यदि $v \geq 3$ :

e\leq 3v-6.

File:Dodecahedron schlegel.svg

एक नियमित द्वादशफ़लक का श्लेगल आरेख, एक उत्तल पॉलीहेड्रॉन से एक समतल आलेख बनाता है।

यूलर का सूत्र उत्तल बहुफलन के लिए भी मान्य होता है। यह कोई संयोग नहीं है: प्रत्येक उत्तल पॉलीहेड्रॉन को पॉलीहेड्रॉन के श्लेगल आरेख का उपयोग करके एक संपर्क, सरल, योजना आलेख में बदल दिया जा सकता है, एक विमान पर पॉलीहेड्रॉन का एक परिप्रेक्ष्य प्रक्षेपण जिसमें से किसी एक के केंद्र के पास चुने गए परिप्रेक्ष्य का केंद्र होता है बहुफलन के फलन. प्रत्येक समतलीय आलेख इस तरह से उत्तल बहुफलन से मेल नहीं खाता है। स्टीनिट्ज़ के प्रमेय का कहना है कि उत्तल पॉलीहेड्रा से बने बहुफलनीय आलेख त्रुटिहीन रूप से परिमित संपर्क (आलेख सिद्धांत) 3-जुड़े हुए सरल योजना आलेख होते है। अधिक सामान्यतः, यूलर का सूत्र किसी भी बहुफलन पर लागू होता है जिसके संख्या सरल बहुभुज होते है।

औसत डिग्री

एक से अधिक किनारों वाले जुड़े समतलीय आलेख असमानता का पालन करते है $2 e \geq 3 f$ , क्योंकि प्रत्येक संख्या में कम से कम तीन संख्या-किनारे की होती है। यह यूलर के सूत्र के साथ इस असमानता के बीजगणितीय परिवर्तनों का अनुसरण करता है $v - e + f = 2$ कि परिमित समतलीय आलेख के लिए औसत डिग्री 6 से बिल्कुल कम होती है। उच्चतर औसत डिग्री वाले आलेख समतलीय नहीं हो सकते है।

मुद्रण आलेख

File:Circle packing theorem K5 minus edge example.svg

वृत्त पैकिंग प्रमेय का उदाहरण

K - 5

, पांच शीर्ष पर पूरा आलेख।

हम कहते है कि समतल में खींचे गए दो वृत्त जब भी बिल्कुल एक बिंदु पर प्रतिच्छेद करते है तो चुंबन (या ऑस्कुलेटिंग वृत्त) करते है। एक मुद्रण आलेख एक ऐसा आलेख होता है जो वृत्तों के एक समूह द्वारा बनाया जाता है, जिनमें से, प्रत्येक वृत्त के लिए एक शीर्ष बनाते है और वृत्त की प्रत्येक जोड़ के लिए एक किनारा बनाते है जो चुंबन करते है। वृत्त पैकिंग प्रमेय, जिसे पहली बार 1936 में पॉल कोबे द्वारा सिद्ध किया गया था, बताता है कि एक आलेख समतल है यदि और केवल यह एक मुद्रण आलेख होता है।

यह परिणाम फ़ेरी के प्रमेय का एक आसान प्रमाण प्रदान करता है, कि प्रत्येक सरल समतलीय आलेख को समतल में इस तरह से अंतर्निहित किया जा सकता है कि उसके किनारे सीधी रेखा वर्ग एक दूसरे को पार न कर सके। यदि कोई मुद्रण आलेख प्रतिनिधित्व में आलेख के प्रत्येक शीर्ष को संबंधित वृत्त के केंद्र में रखता है, तो चुंबन वृत्त के केंद्रों के बीच की रेखा वर्ग किसी भी अन्य किनारों को पार नहीं करती है।

समतलीय आलेख घनत्व

घनत्व गुणांक $D$ एक समतलीय आलेख या, संख्या का अनुपात होता है $f - 1$ इसके अधिकतम संभव मानों द्वारा परिबद्ध फलन है $2 v - 5$ इसके लिए एक आलेख के लिए $v$ शीर्ष:

D={\frac {f-1}{2v-5}}

घनत्व पालन करता है $0 \leq D \leq 1$ , साथ $D = 0$ के लिए पूरी तरह से विरल समतलीय आलेख, और $D = 1$ पूरी तरह से सघन (अधिकतम) समतलीय आलेख के लिए होता है।^[3]

दोहरा आलेख

एक समतलीय आलेख और उसका दोहरा आलेख

एक अंतर्निहित दिया गया $G$ किनारों के प्रतिच्छेदन के बिना समतल में (आवश्यक रूप से सरल नहीं) जुड़े हुए आलेख का, हम दोहरे आलेख का निर्माण करते है $G*$ इस प्रकार है: हम प्रत्येक फलन में एक शीर्ष चुनते है $G$ (बाहरी संख्या सहित) और प्रत्येक किनारे के लिए $e$ में $G$ हम एक नई बढ़त का परिचय देते है $G*$ दो शीर्ष को अंदर जोड़ना $G*$ दो संख्याओ के अनुरूप $G$ यहां मिलते है $e$ . इसके अतिरिक्त, यह किनारा खींचा जाता है जिससे कि यह पार हो जाता है $e$ और उसका कोई दूसरा किनारा नहीं होता है $G$ या $G*$ प्रतिच्छेदित होता है. तब $G*$ फिर से एक (आवश्यक नहीं कि सरल) समतलीय आलेख का अंतर्निहित होता है, इसके उतने ही किनारे है $G$ , जितने शीर्ष $G$ के संख्या और उतने ही संख्या है जितनी $G$ शीर्ष की होती है $G ** = G$ , यहां समानता अंतर्निहित की तुल्यता होती है। यदि $G$ तो उत्तल बहुफलन के अनुरूप समतलीय आलेख होता है $G*$ दोहरे बहुफलन के अनुरूप समतलीय आलेख होता है।

यह दोहरे उपयोगी होते है क्योंकि दोहरे आलेख के कई गुण मूल आलेख के गुणों से सरल विधियों से संबंधित होते है, जिससे उनके दोहरे आलेख की जांच करके आलेख के बारे में परिणामों को सिद्ध किया जा सकता है।

जबकि किसी विशेष अंतर्निहित के लिए निर्मित दोहरा अद्वितीय होता है (समाकृतिकता तक), आलेख में अलग-अलग (अर्थात गैर-समरूपी) दोहरा हो सकते है, जो अलग-अलग (अर्थात समरूपी) अंतर्निहित से प्राप्त होते है।

तलीय रेखांकन के वर्ग

अधिकतम समतलीय आलेख

File:Goldner-Harary graph.svg

गोल्डनर-हैरी आलेख अधिकतम समतलीय है। इसके सभी मुख तीन किनारों से घिरे हुए है।

एक साधारण आलेख को अधिकतम तलीय कहा जाता है यदि यह समतल होता है, लेकिन कोई भी किनारा जोड़ने (दिए गए शीर्ष समूह पर) उस गुण को नष्ट कर देता है। फिर सभी फलनों (बाहरी फलन सहित) को तीन किनारों से घेर दिया जाता है, जो वैकल्पिक शब्द समतल त्रिभुज की व्याख्या करता है। वैकल्पिक त्रिकोणीय आलेख^[4]^[5] का उपयोग किया जाता है, लेकिन वे अस्पष्ट होते है, क्योंकि वे सामान्यतः क्रमशः पूर्ण आलेख के रेखा आलेख और कॉर्डल आलेख को संदर्भित करते है। प्रत्येक अधिकतम तलीय आलेख कम से कम 3- से जुड़ा हुआ होता है।

यदि एक अधिकतम समतलीय आलेख है $v$ शीर्ष के साथ $v > 2$ , तो यह बिल्कुल ठीक है $3 v - 6$ किनारे और $2 v - 4$ ।

अपोलोनियन संजाल त्रिकोणीय को बार-बार छोटे त्रिकोणों के त्रिगुणों में विभाजित करके बनाए गए अधिकतम समतलीय आलेख होता है। सामान्यतः, वे समतलीय k-ट्री होते है।

स्ट्रेंग्युलेटेड आलेख वे आलेख होते है जिनमें प्रत्येक परिधीय चक्र एक त्रिभुज होता है। अधिकतम समतलीय आलेख (या अधिक सामान्यतः एक बहुफलनीय आलेख) में परिधीय चक्र फलन होते है। इस आलेख में कॉर्डल आलेख भी सम्मलित होते है, और ये बिल्कुल ऐसे आलेख होते है जो पूर्ण आलेख और अधिकतम योजना आलेख के योग किनारों को हटाए बिना बनाए जा सकते है।^[6]

आउटरयोजना आलेख

आउटरयोजना आलेख समतल में अंतर्निहित वाले आलेख होते है, जैसे कि सभी कोने अंतर्निहित के असीमित संख्या से संबंधित होते है। प्रत्येक बाहरी तलीय आलेख समतलीय होते है, लेकिन इसका विपरीत सत्य नहीं है: $K 4$ समतलीय है लेकिन बाह्यतलीय नहीं है। कुराटोस्की के समान एक प्रमेय में कहा गया है कि एक परिमित आलेख बाहरी तलीय होता है यदि और केवल तभी जब इसमें उपविभाजन न हो $K 4$ या का $K 2,3$ . उपरोक्त इस तथ्य का प्रत्यक्ष परिणाम है कि एक आलेख {{mvar|G}यदि आलेख से बना है तो } आउटरयोजना है $G$ एक नया शीर्ष जोड़कर, किनारों के साथ इसे अन्य सभी शीर्ष से जोड़कर, एक समतल आलेख बनता है।^[7]

आलेख का 1-आउटरयोजना अंतर्निहित आउटरयोजना अंतर्निहित के समान होता है। इसके लिए $k > 1$ एक समतल अंतर्निहित होता है $k$ -आउटरयोजना यदि बाहरी फलन पर शीर्ष को हटाने पर परिणाम मिलता है $(k - 1)$ ।

हैलिन आलेख

हैलिन आलेख एक अप्रत्यक्ष समतल ट्री (बिना डिग्री-दो नोड्स के) से बना एक आलेख होता है, जो ट्री के समतल अंतर्निहित द्वारा दिए गए क्रम में, इसकी पत्तियों को एक चक्र में जोड़ता है। समान रूप से, यह एक बहुफलनीय आलेख होता है जिसमें एक फलन अन्य सभी फलनों से जुड़ा हुआ होता है। प्रत्येक हेलिन आलेख समतलीय होते है। आउटरयोजना आलेख की तरह, हेलिन आलेख में कम ट्री चौड़ाई होती है, जिससे उन पर कई कलन विधि समस्याएं अप्रतिबंधित योजना आलेख की तुलना में अधिक आसानी से हल हो जाती है।^[8]

समतलीय आलेख

एक उर्ध्व तलीय आलेख एक निर्देशित चक्रीय आलेख होता है जिसे समतल में इसके किनारों के साथ गैर-क्रॉसिंग वक्र के रूप में खींचा जा सकता है जो लगातार ऊपर की दिशा में उन्मुख होते है। प्रत्येक तलीय निर्देशित अचक्रीय आलेख उर्ध्व तलीय नहीं होता है, और यह परीक्षण करने के लिए एनपी-पूर्ण है कि कोई दिया गया आलेख उर्ध्व तलीय है या नहीं है।

उत्तल तलीय आलेख

एक समतल आलेख को उत्तलतब तब कहा जाता है यदि उसके सभी फलन उत्तल बहुभुज होते है। सभी समतलीय आलेख में उत्तल अंतर्निहित नहीं होते है। $K 2,4$ ) एक पर्याप्त स्थिति यह है कि एक आलेख को उत्तल रूप से खींचा जा सकता है कि यह एक 3-शीर्ष-संपर्क योजना आलेख का एक उपवर्ग (आलेख सिद्धांत) होता है। टुट्टे अंतर्निहित प्रमेय कहता है कि सरल 3-शीर्ष-संपर्क योजना आलेख के लिए आंतरिक शीर्ष की स्थिति को उसके वर्गों के औसत के रूप में चुना जा सकता है।

शब्द-प्रतिनिधित्व योग्य समतलीय आलेख

शब्द-प्रतिनिधित्व योग्य समतलीय आलेख में त्रिभुज-मुक्त समतलीय आलेख और, अधिक सामान्यतः, 3-रंगीय समतलीय आलेख सम्मलित होते है।^[9]

प्रमेय

समतलीय आलेख की गणना

समतल आलेख की संख्या के लिए स्पर्शोन्मुख विश्लेषण $n$ शीर्ष है $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$ , जहाँ $\gamma \approx 27.22687$ और $g\approx 0.43\times 10^{-5}$ .^[10]

लगभग सभी समतलीय आलेखों में ऑटोमोर्फिज्म की घातीय संख्या होती है।^[11]

गैर-समरूपी समतल आलेख की संख्या $n$ शीर्ष के बीच है $27.2^{n}$ और $30.06^{n}$ .^[12]

अन्य परिणाम

चार रंग प्रमेय में कहा गया है कि प्रत्येक समतलीय आलेख आलेख रंग (अर्थात, 4-बिंदु) होते है।

फेरी के प्रमेय में कहा गया है कि प्रत्येक सरल समतलीय आलेख एक समतलीय सीधी-रेखा आलेख के रूप में प्रतिनिधित्व स्वीकार करता है। एक सार्वभौमिक बिंदु समूह बिंदुओं का एक समूह होता है जैसे कि एन कोने वाले प्रत्येक समतल आलेख में बिंदु समूह में सभी शीर्ष के साथ ऐसा अंतर्निहित होता है, द्विघात आकार के सार्वभौमिक बिंदु समूह उपस्थित होते है, जो पूर्णांक के आयताकार उपसमुच्चय को लेकर बनते है। प्रत्येक सरल आउटरयोजना आलेख समतल में एक अंतर्निहित को स्वीकार करते है जैसे कि सभी शीर्ष एक निश्चित वृत्त पर स्थित होते है और सभी किनारे सीधी रेखा वर्ग में होते है जो चक्र के अंदर स्थित होते है और प्रतिच्छेद नहीं करते है, इसलिए एन-शीर्ष नियमित बहुभुज आउटरयोजना आलेख के लिए सार्वभौमिक होते है।

शीनरमैन का प्रमेय बताता है कि प्रत्येक समतल आलेख को समतल में रेखा वर्गों के प्रतिच्छेदन आलेख के रूप में दर्शाया जा सकता है।

समतल विभाजक प्रमेय में कहा गया है कि प्रत्येक एन-शीर्ष समतल आलेख को आलेख सिद्धांत की दो वाक्यांश में विभाजित किया जा सकता है O को हटाकर अधिकतम 2n/3 आकार के उपआलेख√n) शीर्ष. परिणामस्वरूप, समतलीय आलेख में ट्री-चौड़ाई होती है O(√n).

समतलीय उत्पाद संरचना प्रमेय में कहा गया है कि प्रत्येक समतलीय आलेख अधिकतम 8 और एक पथ पर ट्री चौड़ाई वाले आलेख के मजबूत आलेख उत्पाद का एक उपआलेख होता है।^[13]

इस परिणाम का उपयोग यह दिखाने के लिए किया जाता है कि समतल आलेख में परिबद्ध संख्या, रंगीन संख्या और निकट-रेखीय आकार के सार्वभौमिक आलेख होते है। इसमें शीर्ष वर्गों के लिए भी उपकरण होते है^[14] पी-केंद्रित रंग^[15] समतलीय रेखांकन का V शीर्ष वाले दो समतलीय आलेखों के लिए, O(v) में यह निर्धारित करना संभव होता है कि वह आलेख सिद्धांत है या नहीं है (आलेख समरूपता समस्या भी देखें)।^[16]

सामान्यीकरण

शीर्ष आलेख एक ऐसा आलेख होता है जिसे एक शीर्ष को हटाकर समतल बनाया जा सकता है, और के-एपेक्स आलेख एक ऐसा आलेख होता है जिसे अधिकतम k शीर्ष को हटाकर समतल बनाया जा सकता है।

1-तलीय आलेख एक ऐसा आलेख होता है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ समतल में खींचा जा सकता है, और के-योजना आलेख एक ऐसा आलेख होता है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ खींचा जा सकता है।

मानचित्र आलेख एक ऐसा आलेख होता है जो दो क्षेत्रों को जोड़कर समतल में बहुत सारे सरलता से जुड़े हुए आंतरिक-विच्छेदित क्षेत्रों के एक समूह से बनता है। जब अधिकतम तीन क्षेत्र एक बिंदु पर मिलते है, तो परिणाम एक समतलीय आलेख होता है, लेकिन जब चार या अधिक क्षेत्र एक बिंदु पर मिलते है, तो परिणाम गैर-तलीय हो सकता है।

टॉरॉइडल आलेख एक ऐसा आलेख होता है जिसे टोरस्र्स पर क्रॉसिंग के बिना अंतर्निहित किया जा सकता है। अधिक सामान्यतः, आलेख का जीनस (गणित) एक द्वि-आयामी सतह का न्यूनतम जीनस होता है जिसमें आलेख को अंतर्निहित किया जा सकता है, समतलीय आलेख में जीनस शून्य होता है और नॉनयोजना टोरॉयडल आलेख में जीनस एक होता है। प्रत्येक आलेख को किसी बंद द्वि-आयामी सतह में क्रॉस किए बिना अंतर्निहित किया जा सकता है और इस प्रकार आलेख का जीनस अच्छी तरह से परिभाषित होता है। यदि आलेख को जीनस जी के साथ एक सतह में क्रॉसिंग के बिना अंतर्निहित किया जा सकता है, तो इसे अधिक या समान जीनस के साथ सभी सतहों में क्रॉसिंग के बिना अंतर्निहित किया जा सकता है। आलेख सिद्धांत में अन्य अवधारणाएँ भी होती है जिन्हें एक्स क्वालीफायर के साथ एक्स जीनस कहा जाता है, सामान्यतः ये बिना किसी योग्यता के जीनस की उपरोक्त परिभाषित अवधारणा से भिन्न होते है। विशेष रूप से एक आलेख का गैर-उन्मुखी जीनस (इसकी परिभाषा में गैर-उन्मुखी सतहों का उपयोग करके) उस आलेख के जीनस (इसकी परिभाषा में उन्मुखी सतहों का उपयोग करके) से एक सामान्य आलेख से भिन्न होता है।

किसी भी आलेख को बिना क्रॉसिंग के त्रि-आयामी स्थान में अंतर्निहित किया जा सकता है। वास्तव में, किसी भी आलेख को दो समतल उपसमूह में क्रॉसिंग के बिना खींचा जा सकता है। इसकी व्याख्या इस प्रकार की जा सकती है कि किसी भी विद्युत संकलक संजाल को दो-तरफा परिपथ बोर्ड के साथ बनाना संभव होता है जहां बोर्ड के किनारों के बीच विद्युत संपर्क बनाया जा सकता है (जैसा कि सामान्य वास्तविक जीवन परिपथ बोर्डों के साथ संभव होता है, विद्युत संपर्क के साथ) बोर्ड के ऊपरी हिस्से में तार के टुकड़ों के माध्यम से और नीचे की तरफ बोर्ड पर बने तांबे के ट्रैक के माध्यम से प्राप्त किया जाता है और बोर्ड के किनारों के बीच ड्रिलिंग छेद के माध्यम से विद्युत संपर्क प्राप्त किया जाता है, इसकी व्याख्या इस तरह भी की जा सकती है कि किसी भी संजाल को बनाने के लिए केवल सुरंगों की जरूरत होती है। चूँकि, योजना आलेख का एक त्रि-आयामी अनुरूप संपर्क रहित अंतर्निहित द्वारा प्रदान किया जाता है, इस आलेख को त्रि-आयामी स्थान में अंतर्निहित तब किया जा सकता है जब कोई भी दो चक्र एक दूसरे के साथ संख्या को नहीं जोड़ते है। कुराटोस्की और वैगनर के समतलीय आलेख के वर्णन के अनुरूप, ऐसे आलेख जिनमें K₅ सम्मलित नहीं है या K₃ के रूप में, संपर्क अंतर्निहित आलेख को उन आलेख के रूप में चित्रित किया जा सकता है जिनमें पीटरसन वर्ग के सात आलेखों में से कोई भी संख्या के रूप में सम्मलित नहीं होते है। आउटरयोजना और योजना आलेख के वर्णन के अनुरूप, कॉलिन डी वेरडीयर आलेख अधिकतम दो या तीन में अपरिवर्तनीय होते है, संपर्क अंतर्निहित आलेख वह आलेख होते है जिनमें कॉलिन डी वेरडीयर अधिकतम चार में अपरिवर्तनीय होते है।

यह भी देखें

कॉम्बिनेटरियल मैप एक कॉम्बिनेटरियल ऑब्जेक्ट है जो प्लेन आलेख को एनकोड कर सकता है
समतलीकरण, प्रत्येक क्रॉसिंग बिंदु को एक नए शीर्ष द्वारा प्रतिस्थापित करके क्रॉसिंग के साथ एक आलेख से बनाया गया एक समतल आलेख
मोटाई (आलेख सिद्धांत), समतलीय आलेख की सबसे छोटी संख्या जिसमें किसी दिए गए आलेख के किनारों को विभाजित किया जा सकता है
समतलता, एक पहेली कंप्यूटर गेम जिसमें उद्देश्य एक समतल आलेख को एक समतल पर अंतर्निहित करना है
अंकुर (खेल) , एक पेंसिल-और-पेपर गेम जहां गेम खेलने के हिस्से के रूप में कुछ बाधाओं के अधीन एक योजना आलेख का निर्माण किया जाता है
तीन उपयोगिताएँ समस्या, एक लोकप्रिय पहेली

↑ Trudeau, Richard J. (1993). ग्राफ सिद्धांत का परिचय (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Retrieved 8 August 2012. Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.
↑ Barthelemy, M. (2017). "1.5 Planar Graphs". स्थानिक नेटवर्क की आकृति विज्ञान. Springer. p. 6. ISBN 978-3-319-20565-6.
↑ Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004), "Efficiency and robustness in ant networks of galleries", European Physical Journal B, 42 (1): 123–129, Bibcode:2004EPJB...42..123B, doi:10.1140/epjb/e2004-00364-9, S2CID 14975826.
↑ Schnyder, W. (1989), "Planar graphs and poset dimension", Order, 5 (4): 323–343, doi:10.1007/BF00353652, MR 1010382, S2CID 122785359.
↑ Bhasker, Jayaram; Sahni, Sartaj (1988), "A linear algorithm to find a rectangular dual of a planar triangulated graph", Algorithmica, 3 (1–4): 247–278, doi:10.1007/BF01762117, S2CID 2709057.
↑ Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
↑ Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Geometric graphs and arrangements, Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, pp. 6–7, doi:10.1007/978-3-322-80303-0_1, ISBN 3-528-06972-4, MR 2061507
↑ Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
↑ Halldórsson, M.; Kitaev, S.; Pyatkin., A. (2016). "अर्ध-संक्रमणीय अभिविन्यास और शब्द-प्रतिनिधित्व योग्य ग्राफ़". Discr. Appl. Math. 201: 164–171. doi:10.1016/j.dam.2015.07.033. S2CID 26796091.
↑ Giménez, Omer; Noy, Marc (2009). "समतलीय ग्राफ़ के स्पर्शोन्मुख गणना और सीमा नियम". Journal of the American Mathematical Society. 22 (2): 309–329. arXiv:math/0501269. Bibcode:2009JAMS...22..309G. doi:10.1090/s0894-0347-08-00624-3. S2CID 3353537.
↑ McDiarmid, Colin; Steger, Angelika; Welsh, Dominic J.A. (2005). "यादृच्छिक समतलीय रेखांकन". Journal of Combinatorial Theory, Series B. 93 (2): 187–205. CiteSeerX 10.1.1.572.857. doi:10.1016/j.jctb.2004.09.007.
↑ Bonichon, N.; Gavoille, C.; Hanusse, N.; Poulalhon, D.; Schaeffer, G. (2006). "सुव्यवस्थित मानचित्रों और पेड़ों के माध्यम से समतलीय रेखांकन". Graphs and Combinatorics. 22 (2): 185–202. CiteSeerX 10.1.1.106.7456. doi:10.1007/s00373-006-0647-2. S2CID 22639942.
↑ Dujmović, Vida; Joret, Gwenäel; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R. (2020), "Planar graphs have bounded queue number", Journal of the ACM, 67 (4): 22:1–22:38, arXiv:1904.04791, doi:10.1145/3385731
↑ Bose, Prosenjit; Dujmović, Vida; Javarsineh, Mehrnoosh; Morin, Pat (2020), Asymptotically optimal vertex ranking of planar graphs, arXiv:2007.06455
↑ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved Bounds for Centered Colorings", Advances in Combinatorics, arXiv:1907.04586, doi:10.19086/aic.27351, S2CID 195874032
↑ Filotti, I. S.; Mayer, Jack N. (1980). "A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus". Proceedings of the 12th Annual ACM Symposium on Theory of Computing (PDF). pp. 236–243. doi:10.1145/800141.804671. ISBN 978-0-89791-017-0. S2CID 16345164.

संदर्भ

Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fundamenta Mathematicae (in français), 15: 271–283, doi:10.4064/fm-15-1-271-283.
Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (in Deutsch), 114: 570–590, doi:10.1007/BF01594196, S2CID 123534907.
Boyer, John M.; Myrvold, Wendy J. (2005), "On the cutting edge: Simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10.7155/jgaa.00091.
McKay, Brendan; Brinkmann, Gunnar, A useful planar graph generator.
de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1029, arXiv:math/0610935, doi:10.1142/S0129054106004248, S2CID 40107560. Special Issue on Graph Drawing.
Bader, D.A.; Sreshta, S. (October 1, 2003). A New Parallel Algorithm for Planarity Testing (Technical report). UNM-ECE Technical Report 03-002. Archived from the original on 2016-03-16.
Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X.

बाहरी संबंध

Edge Addition Planarity Algorithm Source Code, version 1.0 — Free C source code for reference implementation of Boyer–Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator. An open source project with free licensing provides the Edge Addition Planarity Algorithms, current version.
Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
Boost Graph Library tools for planar graphs, including linear time planarity testing, embedding, Kuratowski subgraph isolation, and straight-line drawing.
3 Utilities Puzzle and Planar Graphs
NetLogo Planarity model — NetLogo version of John Tantalo's game

[1] Trudeau, Richard J. (1993). ग्राफ सिद्धांत का परिचय (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Retrieved 8 August 2012. Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.

[2] Barthelemy, M. (2017). "1.5 Planar Graphs". स्थानिक नेटवर्क की आकृति विज्ञान. Springer. p. 6. ISBN 978-3-319-20565-6.

[3] Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004), "Efficiency and robustness in ant networks of galleries", European Physical Journal B, 42 (1): 123–129, Bibcode:2004EPJB...42..123B, doi:10.1140/epjb/e2004-00364-9, S2CID 14975826.

[4] Schnyder, W. (1989), "Planar graphs and poset dimension", Order, 5 (4): 323–343, doi:10.1007/BF00353652, MR 1010382, S2CID 122785359.

[5] Bhasker, Jayaram; Sahni, Sartaj (1988), "A linear algorithm to find a rectangular dual of a planar triangulated graph", Algorithmica, 3 (1–4): 247–278, doi:10.1007/BF01762117, S2CID 2709057.

[6] Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.

[7] Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Geometric graphs and arrangements, Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, pp. 6–7, doi:10.1007/978-3-322-80303-0_1, ISBN 3-528-06972-4, MR 2061507

[8] Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.

[HK|last=P16-9] Halldórsson, M.; Kitaev, S.; Pyatkin., A. (2016). "अर्ध-संक्रमणीय अभिविन्यास और शब्द-प्रतिनिधित्व योग्य ग्राफ़". Discr. Appl. Math. 201: 164–171. doi:10.1016/j.dam.2015.07.033. S2CID 26796091.

[10] Giménez, Omer; Noy, Marc (2009). "समतलीय ग्राफ़ के स्पर्शोन्मुख गणना और सीमा नियम". Journal of the American Mathematical Society. 22 (2): 309–329. arXiv:math/0501269. Bibcode:2009JAMS...22..309G. doi:10.1090/s0894-0347-08-00624-3. S2CID 3353537.

[11] McDiarmid, Colin; Steger, Angelika; Welsh, Dominic J.A. (2005). "यादृच्छिक समतलीय रेखांकन". Journal of Combinatorial Theory, Series B. 93 (2): 187–205. CiteSeerX 10.1.1.572.857. doi:10.1016/j.jctb.2004.09.007.

[12] Bonichon, N.; Gavoille, C.; Hanusse, N.; Poulalhon, D.; Schaeffer, G. (2006). "सुव्यवस्थित मानचित्रों और पेड़ों के माध्यम से समतलीय रेखांकन". Graphs and Combinatorics. 22 (2): 185–202. CiteSeerX 10.1.1.106.7456. doi:10.1007/s00373-006-0647-2. S2CID 22639942.

[13] Dujmović, Vida; Joret, Gwenäel; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R. (2020), "Planar graphs have bounded queue number", Journal of the ACM, 67 (4): 22:1–22:38, arXiv:1904.04791, doi:10.1145/3385731

[14] Bose, Prosenjit; Dujmović, Vida; Javarsineh, Mehrnoosh; Morin, Pat (2020), Asymptotically optimal vertex ranking of planar graphs, arXiv:2007.06455

[15] Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved Bounds for Centered Colorings", Advances in Combinatorics, arXiv:1907.04586, doi:10.19086/aic.27351, S2CID 195874032

[16] Filotti, I. S.; Mayer, Jack N. (1980). "A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus". Proceedings of the 12th Annual ACM Symposium on Theory of Computing (PDF). pp. 236–243. doi:10.1145/800141.804671. ISBN 978-0-89791-017-0. S2CID 16345164.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 6: / Line 6: @@
 |-
 ! तलीय
-! नॉनप्लानर
+! नॉनयोजना
 |-
 | align="center" | [[Image:Butterfly graph.svg|100px]] <br> [[Butterfly graph|तितली आलेख]]
@@ Line 14: / Line 14: @@
 | align="center" | [[Image:Biclique K 3 3.svg|100px]] <br>[[Utility graph|उपयोगिता आलेख]] ''K''<sub>3,3</sub>
 |}
-आलेख सिद्धांत में, एक '''समतल आलेख''' एक असतत आलेख होता है जिसे समतल (ज्यामिति) में [[ग्राफ एम्बेडिंग|आलेख अंतर्निहित]] किया जा सकता है, अर्थात, इसे समतल पर इस तरह से खींचा जा सकता है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद करते है। दूसरे शब्दों में, इसे इस तरह से खींचा जा सकता है कि कोई भी किनारा एक-दूसरे को पार न कर सके।<ref>{{cite book|last=Trudeau|first=Richard J.|title=ग्राफ सिद्धांत का परिचय|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=64|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012|quote=Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.}}</ref><ref>{{cite book |last1=Barthelemy |first1=M. |chapter=1.5 Planar Graphs |chapter-url={{GBurl|9-hEDwAAQBAJ|p=6}}  |title=स्थानिक नेटवर्क की आकृति विज्ञान|date=2017 |isbn=978-3-319-20565-6 |publisher=Springer |page=6}}</ref> इस तरह के आलेख को समतल आलेख अंतर्निहित कहा जाता है। एक समतल आलेख को एक समतल आलेख अंतर्निहित के रूप में परिभाषित किया जा सकता है, जिसमें एक समतल पर प्रत्येक नोड से एक बिंदु तक और प्रत्येक किनारे से उस समतल पर एक [[समतल वक्र]] तक मैपिंग की जाती है, जैसे कि प्रत्येक वक्र के उच्चतम बिंदु उसके अंत से मैप किए गए बिंदु होते है। नोड्स, और सभी वक्र अपने उच्चतम बिंदुओं को छोड़कर असंयुक्त होते है।
+आलेख सिद्धांत में, एक '''समतल आलेख''' एक असतत आलेख होता है जिसे समतल (ज्यामिति) में [[ग्राफ एम्बेडिंग|आलेख अंतर्निहित]] किया जा सकता है, अर्थात, इसे समतल पर इस तरह से खींचा जा सकता है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद करते है। दूसरे शब्दों में, इसे इस तरह से खींचा जा सकता है कि कोई भी किनारा एक-दूसरे को पार न कर सके।<ref>{{cite book|last=Trudeau|first=Richard J.|title=ग्राफ सिद्धांत का परिचय|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=64|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012|quote=Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.}}</ref><ref>{{cite book |last1=Barthelemy |first1=M. |chapter=1.5 Planar Graphs |chapter-url={{GBurl|9-hEDwAAQBAJ|p=6}}  |title=स्थानिक नेटवर्क की आकृति विज्ञान|date=2017 |isbn=978-3-319-20565-6 |publisher=Springer |page=6}}</ref> इस तरह के आलेख को समतल आलेख अंतर्निहित कहा जाता है। एक समतल आलेख को एक समतल आलेख अंतर्निहित के रूप में परिभाषित किया जा सकता है, जिसमें एक समतल पर प्रत्येक नोड से एक बिंदु तक और प्रत्येक किनारे से उस समतल पर एक [[समतल वक्र]] तक मैपिंग की जाती है, जैसे कि प्रत्येक वक्र के उच्चतम बिंदु उसके अंत से मैप किए गए बिंदु होते है। नोड्स, और सभी वक्र अपने उच्चतम बिंदुओं को छोड़कर असंयुक्त होते है।ka
 प्रत्येक आलेख जो एक समतल पर खींचा जा सकता है, उसे [[त्रिविम प्रक्षेपण]] के माध्यम से गोले पर भी खींचा जा सकता है।
-समतल आलेख [[संयोजक मानचित्र]] मानचित्रों या [[ रोटेशन प्रणाली |घुमाव प्रणाली]] द्वारा एन्कोड किया जा सकता है।
+समतल आलेख [[संयोजक मानचित्र|संयोजक मानचित्रों]] या [[ रोटेशन प्रणाली |घुमाव प्रणाली]] द्वारा एन्कोड किया जा सकता है।
-गोले पर संस्थानिक रूप से समतुल्य आलेखों का एक समतुल्य वर्ग, सामान्यतः पुल (आलेख सिद्धांत) की अनुपस्थिति जैसी अतिरिक्त मान्यताओं के साथ, एक समतल मानचित्र कहलाता है। चूँकि समतल आलेख का एक बाहरी या असीमित फलक होता है (आलेख सिद्धांत), समतल मानचित्र के किसी भी फलक की कोई विशेष स्थिति नहीं होती है।
+गोले पर संस्थानिक रूप से समतुल्य आलेखों का एक समतुल्य वर्ग, सामान्यतः आलेख सिद्धांत की अनुपस्थिति जैसी अतिरिक्त मान्यताओं के साथ, एक समतल मानचित्र कहलाता है। चूँकि समतल आलेख का एक बाहरी या असीमित फलन होता है (आलेख सिद्धांत), समतल मानचित्र के किसी भी फलन की कोई विशेष स्थिति नहीं होती है।
-समतलीय आलेख किसी दिए गए [[जीनस (गणित)]] की सतह पर खींचे जाने योग्य आलेख के लिए सामान्यीकृत होते है। इस वाक्यांश में, समतलीय आलेख में [[ग्राफ जीनस|आलेख जीनस]] 0 होता है, क्योंकि समतल (और गोला) जीनस 0 की सतहें होती है। अन्य संबंधित विषयों के लिए आलेख अंतर्निहित देखें।
+समतलीय आलेख किसी दिए गए [[जीनस (गणित)]] की सतह पर खींचे जाने योग्य आलेख के लिए सामान्यीकृत होते है। इस वाक्यांश में, समतलीय आलेख में [[ग्राफ जीनस|आलेख जीनस]] 0 होता है, क्योंकि समतल (और गोला) जीनस 0 होती है। अन्य संबंधित विषयों के लिए आलेख अंतर्निहित देखें।
 == समतलीयता मानदंड ==
@@ Line 28: / Line 28: @@
 === कुराटोव्स्की और वैगनर के प्रमेय ===
 {{tesseract_graph_nonplanar_visual_proof.svg}}
-[[पोलैंड]] के गणितज्ञ [[काज़िमिर्ज़ कुराटोव्स्की]] ने निषिद्ध आलेख लक्षण वर्णन के संदर्भ में समतल आलेख का एक लक्षण वर्णन प्रदान किया, जिसे अब कुराटोव्स्की के प्रमेय के रूप में जाना जाता है:
+[[पोलैंड]] के गणितज्ञ [[काज़िमिर्ज़ कुराटोव्स्की]] ने निषिद्ध आलेख वर्णन के संदर्भ में समतल आलेख का एक वर्णन प्रदान किया था, जिसे अब कुराटोव्स्की के प्रमेय के रूप में जाना जाता है:
-:एक आलेख (असतत गणित)#परिमित और अनंत आलेख समतल है यदि और केवल यदि इसमें आलेख सिद्धांत की वाक्यांश सम्मलित नहीं होता है आलेख जो संपूर्ण आलेख का एक [[उपखंड (ग्राफ़ सिद्धांत)|उपवर्ग (आलेख सिद्धांत)]] है {{math|''K''{{sub|5}}}} या सं[[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विदलीय]] आलेख {{math|''K''{{sub|3,3}}}} ([[उपयोगिता ग्राफ|उपयोगिता आलेख]])।
+:एक आलेख (असतत गणित) परिमित और अनंत आलेख समतल होते है यदि इसमें आलेख सिद्धांत की वाक्यांश सम्मलित नहीं होती है आलेख जो संपूर्ण आलेख का एक [[उपखंड (ग्राफ़ सिद्धांत)|उपवर्ग (आलेख सिद्धांत)]] होता है {{math|''K''{{sub|5}}}} या [[पूर्ण द्विदलीय ग्राफ|संपूर्ण आलेख]] {{math|''K''{{sub|3,3}}}} ([[उपयोगिता ग्राफ|उपयोगिता आलेख]])।
-आलेख का एक उपवर्ग (आलेख सिद्धांत) किनारों में शीर्ष डालने से उत्पन्न होता है (उदाहरण के लिए, एक किनारे को बदलना)। {{nowrap|• —— • to • — • — • )}} शून्य या अधिक होता है
+आलेख का एक उपवर्ग (आलेख सिद्धांत) किनारों में से उत्पन्न होता है (उदाहरण के लिए, एक किनारे को बदलना)। {{nowrap|• —— • to • — • — • )}} शून्य या अधिक होता है
-[[Image:Nonplanar no subgraph K 3 3.svg|thumb|संख्या वाले आलेख का एक उदाहरण {{math|''K''{{sub|5}}}} या {{math|''K''{{sub|3,3}}}} सबआलेख. चूँकि, इसमें एक उपवर्ग सम्मलित है {{math|''K''{{sub|3,3}}}} और इसलिए गैर-तलीय है।]]उपवर्गों पर विचार करने के अतिरिक्त, वैगनर का प्रमेय [[लघु (ग्राफ़ सिद्धांत)|लघु (आलेख सिद्धांत)]] से संबंधित है:
+[[Image:Nonplanar no subgraph K 3 3.svg|thumb|संख्या वाले आलेख का एक उदाहरण {{math|''K''{{sub|5}}}} या {{math|''K''{{sub|3,3}}}} उपआलेख. चूँकि, इसमें एक उपवर्ग सम्मलित है {{math|''K''{{sub|3,3}}}} और इसलिए गैर-तलीय है।]]उपवर्गों पर विचार करने के अतिरिक्त, वैगनर का प्रमेय [[लघु (ग्राफ़ सिद्धांत)|लघु (आलेख सिद्धांत)]] से संबंधित होता है:
-:एक परिमित आलेख समतलीय होता है यदि और केवल तभी जब उसमें ऐसा न हो {{math|''K''{{sub|5}}}} या {{math|''K''{{sub|3,3}}}} एक लघु (आलेख सिद्धांत) होता है।
+:एक परिमित आलेख समतलीय होता है {{math|''K''{{sub|5}}}} या {{math|''K''{{sub|3,3}}}} एक लघु (आलेख सिद्धांत) होता है।
-आलेख का एक लघु (आलेख सिद्धांत) एक सबआलेख लेने और एक किनारे को बार-बार एक शीर्ष में अनुबंधित करने से उत्पन्न होता है, जिसमें मूल अंत-शीर्ष का प्रत्येक पड़ोसी नए शीर्ष का पड़ोसी बन जाता है।
+आलेख का एक लघु (आलेख सिद्धांत) एक उपआलेख एक किनारे को बार-बार एक शीर्ष में अनुबंधित करने से उत्पन्न होता है, जिसमें मूल अंत-शीर्ष का प्रत्येक गुण नए शीर्ष का गुण बन जाता है।
-[[File:Kuratowski.gif|thumb|484px|एक एनीमेशन जो दर्शाता है कि [[पीटरसन ग्राफ|पीटरसन]] आलेख में मामूली समरूपी सम्मलित है {{math|''K''{{sub|3,3}}}} आलेख, और इसलिए गैर-तलीय है]][[क्लॉस वैगनर (गणितज्ञ)]] ने अधिक सामान्यतः पूछा कि क्या आलेख का कोई लघु-बंद वर्ग निषिद्ध लघु के एक सीमित समूह द्वारा निर्धारित किया जाता है। यह अब रॉबर्टसन-सेमुर प्रमेय है, जो कागजात की एक लंबी श्रृंखला में सिद्ध हुआ है। इस प्रमेय की भाषा में, {{math|''K''{{sub|5}}}} और {{math|''K''{{sub|3,3}}}}परिमित समतलीय आलेख के वर्ग के लिए निषिद्ध अवयस्क है।
+[[File:Kuratowski.gif|thumb|484px|एक एनीमेशन जो दर्शाता है कि [[पीटरसन ग्राफ|पीटरसन]] आलेख में मामूली समरूपी सम्मलित है {{math|''K''{{sub|3,3}}}} आलेख, और इसलिए गैर-तलीय है]][[क्लॉस वैगनर (गणितज्ञ)]] ने पूछा कि क्या आलेख का कोई लघु-बंद वर्ग निषिद्ध लघु के एक सीमित समूह द्वारा निर्धारित किया जा सकता है। यह अब रॉबर्टसन-सेमुर प्रमेय के एक लंबी श्रृंखला में सिद्ध हुआ है। इस प्रमेय की भाषा में, {{math|''K''{{sub|5}}}} और {{math|''K''{{sub|3,3}}}}परिमित समतलीय आलेख के वर्ग के लिए निषिद्ध अवयस्क होते है।
 === अन्य मानदंड ===
-व्यवहार में, यह तय करने के लिए कि कोई दिया गया आलेख समतल है या नहीं, कुराटोस्की की कसौटी का उपयोग करना कठिन होता है। चूँकि, इस समस्या के लिए तेज़ [[कलन विधि]] उपस्थित है: एक आलेख के लिए {{mvar|n}} शीर्ष, समय पर निर्धारित करना संभव है {{math|[[Big O notation|''O'']](''n'')}} (रैखिक समय) आलेख समतलीय हो सकता है या नहीं (तलीयता परीक्षण देखें)।
+व्यवहार में, यह तय करने के लिए कि कोई दिया गया आलेख समतल है या नहीं, यह पता करने के लिए कुराटोस्की का उपयोग किया जाता है। चूँकि, इस समस्या के लिए तेज़ [[कलन विधि]] उपस्थित है: एक आलेख के लिए {{mvar|n}} शीर्ष, समय पर निर्धारित करना संभव है {{math|[[Big O notation|''O'']](''n'')}} (रैखिक समय) आलेख समतलीय हो सकता है (तलीयता परीक्षण देखें)।
-एक सरल, संपर्क, समतलीय आलेख के लिए {{mvar|v}} शीर्ष और {{mvar|e}}किनारे और {{mvar|f}} चेहरों के लिए निम्नलिखित सरल स्थितियाँ लागू होती है {{math|''v'' ≥ 3}}:
+एक सरल, संपर्क, समतलीय आलेख के लिए {{mvar|v}} शीर्ष और {{mvar|e}} किनारे और {{mvar|f}} चेहरों के लिए निम्नलिखित सरल स्थितियाँ लागू होती है {{math|''v'' ≥ 3}}:
 *प्रमेय 1. {{math|''e'' ≤ 3''v'' – 6}},
@@ Line 51: / Line 51: @@
 *प्रमेय 3. {{math|''f'' ≤ 2''v'' – 4}}.
-इस अर्थ में, समतलीय आलेख [[विरल ग्राफ|विरल]] आलेख होते है, इसमें केवल यही होता है {{math|''O''(''v'')}} किनारे, अधिकतम से बिल्कुल छोटे {{math|''O''(''v''{{sup|2}})}}. लेखाचित्र {{math|''K''{{sub|3,3}}}उदाहरण के लिए, } में 6 शीर्ष, 9 किनारे और लंबाई 3 का कोई चक्र नहीं है। इसलिए, प्रमेय 2 के अनुसार, यह समतल नहीं हो सकता। ये प्रमेय समतलता के लिए आवश्यक स्थितिें प्रदान करते है जो पर्याप्त स्थितियाँ नहीं है, और इसलिए इसका उपयोग केवल यह सिद्ध करने के लिए किया जा सकता है कि आलेख समतल नहीं है, न कि यह समतल है। यदि प्रमेय 1 और 2 दोनों विफल हो जाते है, तो अन्य विधियों का उपयोग किया जा सकता है।
+इस अर्थ में, समतलीय आलेख [[विरल ग्राफ|विरल]] आलेख होते है, इसमें {{math|''O''(''v'')}} किनारे, अधिकतम से बिल्कुल छोटे {{math|''O''(''v''{{sup|2}})}}<nowiki> लेखाचित्र {{गणित|</nowiki>''K''{{sub|3,3}}}उदाहरण के लिए,} में 6 शीर्ष, 9 किनारे और लंबाई 3 का कोई चक्र नहीं है। इसलिए, प्रमेय 2 के अनुसार, यह समतल नहीं हो सकता है। यह प्रमेय समतलता के लिए आवश्यक स्थितिें प्रदान करते है, और इसलिए इसका उपयोग केवल यह सिद्ध करने के लिए किया जा सकता है कि आलेख समतल नहीं है। यदि प्रमेय 1 और 2 दोनों विफल हो जाते है, तो अन्य विधियों का उपयोग किया जा सकता है।
-* व्हिटनी का समतलीय मानदंड एक बीजगणितीय दोहरे के अस्तित्व के आधार पर एक लक्षण वर्णन देता है,
+* व्हिटनी का समतलीय मानदंड एक बीजगणितीय दोहरे के अस्तित्व के आधार पर एक वर्णन प्रदान करता है,
-* मैक लेन का समतलीय मानदंड, उनके [[चक्र स्थान]]ों के माध्यम से, परिमित समतलीय आलेख का बीजगणितीय लक्षण वर्णन देता है,
+* मैक लेन का समतलीय मानदंड, उनके [[चक्र स्थान|चक्र स्थानों]] के माध्यम से, परिमित समतलीय आलेख का बीजगणितीय वर्णन प्रदान करता है,
-* फ्रैसेसिक्स-रोसेनस्टीहल प्लैनरिटी मानदंड गहराई-प्रथम खोज ट्री के कोट्री किनारों के द्विविभाजन के अस्तित्व के आधार पर एक लक्षण वर्णन देता है। यह बाएँ-दाएँ समतलता परीक्षण कलन विधि का केंद्र होता है,
+* फ्रैसेसिक्स-रोसेनस्टीहल प्लैनरिटी मानदंड गहराई-प्रथम किनारों के द्विविभाजन के अस्तित्व के आधार पर एक वर्णन प्रदान करता है। यह बाएँ-दाएँ समतलता परीक्षण कलन विधि का केंद्र होता है,
-* श्नाइडर का प्रमेय क्रम आयाम के संदर्भ में समतलता का लक्षण वर्णन देता है,
+* श्नाइडर का प्रमेय क्रम आयाम के संदर्भ में समतलता का वर्णन प्रदान करता है,
-* कॉलिन डी वेरडीयर आलेख इनवेरिएंट कॉलिन डी वेरडीयर का प्लानेरिटी मानदंड आलेख द्वारा परिभाषित कुछ श्रोडिंगर परिचलनों के दूसरे आइगेनवैल्यू की अधिकतम बहुलता के आधार पर एक लक्षण वर्णन देता है।
+* कॉलिन डी वेरडीयर का प्लानेरिटी मानदंड आलेख द्वारा परिभाषित कुछ श्रोडिंगर परिचलनों के दूसरे संख्या की अधिकतम बहुलता के आधार पर एक वर्णन प्रदान करता है।
-* हनानी-टुट्टे प्रमेय में कहा गया है कि एक आलेख समतल होता है यदि और केवल तभी जब इसमें एक आलेख हो जिसमें किनारों का प्रत्येक स्वतंत्र जोड़ा सम संख्या में बार पार करता हो, इसका उपयोग समीकरण मॉड्यूलो 2 की प्रणाली के माध्यम से समतलीय आलेख को चित्रित करने के लिए किया जा सकता है।
+* हनानी-टुट्टे प्रमेय में कहा गया है कि एक आलेख समतल होता है यदि और केवल तभी जब इसमें एक आलेख होता है जिसमें किनारों का प्रत्येक स्वतंत्र जोड़ उप संख्या को पार करता है, इसका उपयोग समीकरण मॉड्यूलो 2 की प्रणाली के माध्यम से समतलीय आलेख को चित्रित करने के लिए किया जा सकता है।
 == गुण ==
@@ Line 65: / Line 65: @@
 {{main|यूलर विशेषता#समतल रेखांकन}}
-यूलर के सूत्र में कहा गया है कि यदि एक परिमित, कनेक्टिविटी (आलेख सिद्धांत), समतलीय आलेख बिना किसी किनारे के चौराहे के समतल में खींचा जाता है, और {{mvar|v}} शीर्ष की संख्या है, {{mvar|e}} किनारों की संख्या है और {{mvar|f}} तो फलकों की संख्या है (किनारों से घिरा क्षेत्र, जिसमें बाहरी, असीम रूप से बड़ा क्षेत्र भी सम्मलित है)।
+यूलर के सूत्र में कहा गया है कि यदि एक परिमित, (आलेख सिद्धांत), समतलीय आलेख बिना किसी किनारे के समतल में खींचा जाता है, और {{mvar|v}} शीर्ष की संख्या है, {{mvar|e}} किनारों की संख्या है और {{mvar|f}} तो फलनों की संख्या है।
 :<math>v-e+f=2.</math>
 उदाहरण के रूप में, ऊपर दिए गए [[तितली ग्राफ|तितली आलेख]] में, {{math|1=''v'' = 5}}, {{math|1=''e'' = 6}} और {{math|1=''f'' = 3}}.
-सामान्यतः, यदि गुण सभी समतलीय आलेखों के लिए मान्य है {{mvar|f}} चेहरे, आलेख में कोई भी परिवर्तन जो आलेख को समतल रखते हुए एक अतिरिक्त चेहरा बनाता है, रखा जाएगा {{math|''v'' – ''e'' + ''f''}} एक अपरिवर्तनीय. चूंकि गुण सभी आलेख के लिए मान्य है {{math|1=''f'' = 2}}, [[गणितीय प्रेरण]] द्वारा यह सभी स्थितियों के लिए लागू होता है। यूलर के सूत्र को इस प्रकार भी सिद्ध किया जा सकता है: यदि आलेख एक पेड़ नहीं है (आलेख सिद्धांत), तो एक किनारे को हटा दें जो एक चक्र (आलेख सिद्धांत) को पूरा करता है। इससे दोनों कम हो जाते है {{mvar|e}} और {{mvar|f}} एक करके, जा रहा हूँ {{math|''v'' – ''e'' + ''f''}} नियत। तब तक दोहराएँ जब तक शेष आलेख एक पेड़ न बन जाए, पेड़ों के पास है {{math|1=''v'' = ''e'' + 1}} और {{math|1=''f'' = 1}}, उपज {{math|1=''v'' – ''e'' + ''f'' = 2}}, मैं। ई., [[यूलर विशेषता]] 2 है।
+सामान्यतः, यदि गुण सभी समतलीय आलेखों के लिए मान्य है {{mvar|f}} , आलेख में कोई भी परिवर्तन जो आलेख को समतल रखते हुए एक अतिरिक्त संकया प्राप्त होती है, {{math|''v'' – ''e'' + ''f''}} एक अपरिवर्तनीय. चूंकि गुण सभी आलेख के लिए मान्य है {{math|1=''f'' = 2}}, [[गणितीय प्रेरण]] द्वारा यह सभी स्थितियों के लिए लागू होता है। यूलर के सूत्र को इस प्रकार भी सिद्ध किया जा सकता है: यदि आलेख एक ट्री नहीं है, {{math|''v'' – ''e'' + ''f''}} । यह तब तक दोहराएँ जब तक शेष आलेख एक ट्री न बन जाए, ट्री के पास है {{math|1=''v'' = ''e'' + 1}} और {{math|1=''f'' = 1}}, और {{math|1=''v'' – ''e'' + ''f'' = 2}}। ई., [[यूलर विशेषता]] 2 है।
-एक परिमित में, कनेक्टिविटी (आलेख सिद्धांत), [[सरल ग्राफ|सरल आलेख]], समतल आलेख, कोई भी चेहरा (संभवतः बाहरी को छोड़कर) कम से कम तीन किनारों से घिरा होता है और प्रत्येक किनारा अधिकतम दो चेहरों को छूता है, यूलर के सूत्र का उपयोग करके, कोई यह दिखा सकता है कि ये आलेख इस अर्थ में विरल है कि यदि {{math|''v'' ≥ 3}}:
+एक परिमित में, आलेख सिद्धांत, [[सरल ग्राफ|सरल आलेख]], समतल आलेख, (संभवतः बाहरी को छोड़कर) कम से कम तीन किनारों से घिरा होता है और प्रत्येक किनारा अधिकतम दो संख्याओ के पास होता है, यूलर के सूत्र का उपयोग करके, यह दिखाया जा सकता है कि ये आलेख इस अर्थ में विरल है यदि {{math|''v'' ≥ 3}}:
 :<math>e\leq 3v-6.</math>
-[[File:Dodecahedron schlegel.svg|thumb|एक नियमित [[द्वादशफ़लक]] का [[श्लेगल आरेख]], एक उत्तल पॉलीहेड्रॉन से एक समतल आलेख बनाता है।]]यूलर का सूत्र [[उत्तल बहुफलक]] के लिए भी मान्य है। यह कोई संयोग नहीं है: प्रत्येक उत्तल पॉलीहेड्रॉन को पॉलीहेड्रॉन के श्लेगल आरेख का उपयोग करके एक संपर्क, सरल, प्लेनर आलेख में बदल दिया जा सकता है, एक विमान पर पॉलीहेड्रॉन का एक [[परिप्रेक्ष्य प्रक्षेपण]] जिसमें से किसी एक के केंद्र के पास चुने गए परिप्रेक्ष्य का केंद्र होता है बहुफलक के फलक. प्रत्येक समतलीय आलेख इस तरह से उत्तल बहुफलक से मेल नहीं खाता: उदाहरण के लिए, पेड़ ऐसा नहीं करते। स्टीनिट्ज़ के प्रमेय का कहना है कि उत्तल पॉलीहेड्रा से बने [[ बहुफलकीय ग्राफ |बहुफलकीय आलेख]] त्रुटिहीन रूप से परिमित संपर्क (आलेख सिद्धांत) 3-जुड़े हुए सरल प्लानर आलेख होते है। अधिक सामान्यतः, यूलर का सूत्र किसी भी बहुफलक पर लागू होता है जिसके चेहरे [[सरल बहुभुज]] होते है जो एक गोले की सतह समरूपता बनाते है।
+[[File:Dodecahedron schlegel.svg|thumb|एक नियमित [[द्वादशफ़लक]] का [[श्लेगल आरेख]], एक उत्तल पॉलीहेड्रॉन से एक समतल आलेख बनाता है।]]यूलर का सूत्र [[उत्तल बहुफलक|उत्तल बहुफलन]] के लिए भी मान्य होता है। यह कोई संयोग नहीं है: प्रत्येक उत्तल पॉलीहेड्रॉन को पॉलीहेड्रॉन के श्लेगल आरेख का उपयोग करके एक संपर्क, सरल, योजना आलेख में बदल दिया जा सकता है, एक विमान पर पॉलीहेड्रॉन का एक [[परिप्रेक्ष्य प्रक्षेपण]] जिसमें से किसी एक के केंद्र के पास चुने गए परिप्रेक्ष्य का केंद्र होता है बहुफलन के फलन. प्रत्येक समतलीय आलेख इस तरह से उत्तल बहुफलन से मेल नहीं खाता है। स्टीनिट्ज़ के प्रमेय का कहना है कि उत्तल पॉलीहेड्रा से बने [[ बहुफलकीय ग्राफ |बहुफलनीय आलेख]] त्रुटिहीन रूप से परिमित संपर्क (आलेख सिद्धांत) 3-जुड़े हुए सरल योजना आलेख होते है। अधिक सामान्यतः, यूलर का सूत्र किसी भी बहुफलन पर लागू होता है जिसके संख्या [[सरल बहुभुज]] होते है।
 === औसत डिग्री ===
-एक से अधिक किनारों वाले जुड़े समतलीय आलेख असमानता का पालन करते है {{math|2''e'' ≥ 3''f''}}, क्योंकि प्रत्येक चेहरे में कम से कम तीन चेहरे-किनारे की घटनाएं होती है और प्रत्येक किनारे ठीक दो घटनाओं में योगदान देता है। यह यूलर के सूत्र के साथ इस असमानता के बीजगणितीय परिवर्तनों का अनुसरण करता है {{math|1=''v'' – ''e'' + ''f'' = 2}}कि परिमित समतलीय आलेख के लिए औसत डिग्री 6 से बिल्कुल कम होती है। उच्चतर औसत डिग्री वाले आलेख समतलीय नहीं हो सकते है।
+एक से अधिक किनारों वाले जुड़े समतलीय आलेख असमानता का पालन करते है {{math|2''e'' ≥ 3''f''}}, क्योंकि प्रत्येक संख्या में कम से कम तीन संख्या-किनारे की होती है। यह यूलर के सूत्र के साथ इस असमानता के बीजगणितीय परिवर्तनों का अनुसरण करता है {{math|1=''v'' – ''e'' + ''f'' = 2}} कि परिमित समतलीय आलेख के लिए औसत डिग्री 6 से बिल्कुल कम होती है। उच्चतर औसत डिग्री वाले आलेख समतलीय नहीं हो सकते है।
-=== सिक्का आलेख ===
+=== मुद्रण आलेख ===
 {{main|वृत्त पैकिंग प्रमेय}}
-[[File:Circle packing theorem K5 minus edge example.svg|thumb|वृत्त पैकिंग प्रमेय का उदाहरण {{math|''K''{{sup| −}}{{sub|5}}}}, पांच शीर्ष पर पूरा आलेख।]]हम कहते है कि समतल में खींचे गए दो वृत्त जब भी बिल्कुल एक बिंदु पर प्रतिच्छेद करते है तो चुंबन (या ऑस्कुलेटिंग वृत्त) करते है। एक सिक्का आलेख एक ऐसा आलेख है जो वृत्तों के एक समूह द्वारा बनाया जाता है, जिनमें से किसी भी दो में ओवरलैपिंग भीतरी भाग नहीं होते है, प्रत्येक सर्कल के लिए एक शीर्ष बनाते है और सर्कल की प्रत्येक जोड़ी के लिए एक किनारा बनाते है जो चुंबन करते है। [[सर्कल पैकिंग प्रमेय]], जिसे पहली बार 1936 में [[पॉल कोबे]] द्वारा सिद्ध किया गया था, बताता है कि एक आलेख समतल है यदि और केवल यदि यह एक सिक्का आलेख है।
+[[File:Circle packing theorem K5 minus edge example.svg|thumb|वृत्त पैकिंग प्रमेय का उदाहरण {{math|''K''{{sup| −}}{{sub|5}}}}, पांच शीर्ष पर पूरा आलेख।]]हम कहते है कि समतल में खींचे गए दो वृत्त जब भी बिल्कुल एक बिंदु पर प्रतिच्छेद करते है तो चुंबन (या ऑस्कुलेटिंग वृत्त) करते है। एक मुद्रण आलेख एक ऐसा आलेख होता है जो वृत्तों के एक समूह द्वारा बनाया जाता है, जिनमें से, प्रत्येक वृत्त के लिए एक शीर्ष बनाते है और वृत्त की प्रत्येक जोड़ के लिए एक किनारा बनाते है जो चुंबन करते है। [[सर्कल पैकिंग प्रमेय|वृत्त पैकिंग प्रमेय]], जिसे पहली बार 1936 में [[पॉल कोबे]] द्वारा सिद्ध किया गया था, बताता है कि एक आलेख समतल है यदि और केवल यह एक मुद्रण आलेख होता है।
-यह परिणाम फ़ेरी के प्रमेय का एक आसान प्रमाण प्रदान करता है, कि प्रत्येक सरल समतलीय आलेख को समतल में इस तरह से अंतर्निहित किया जा सकता है कि उसके किनारे सीधी [[रेखा खंड|रेखा वर्ग]] हों जो एक दूसरे को पार न करें। यदि कोई सिक्का आलेख प्रतिनिधित्व में आलेख के प्रत्येक शीर्ष को संबंधित सर्कल के केंद्र में रखता है, तो चुंबन सर्कल के केंद्रों के बीच की रेखा वर्ग किसी भी अन्य किनारों को पार नहीं करती है।
+यह परिणाम फ़ेरी के प्रमेय का एक आसान प्रमाण प्रदान करता है, कि प्रत्येक सरल समतलीय आलेख को समतल में इस तरह से अंतर्निहित किया जा सकता है कि उसके किनारे सीधी [[रेखा खंड|रेखा वर्ग]] एक दूसरे को पार न कर सके। यदि कोई मुद्रण आलेख प्रतिनिधित्व में आलेख के प्रत्येक शीर्ष को संबंधित वृत्त के केंद्र में रखता है, तो चुंबन वृत्त के केंद्रों के बीच की रेखा वर्ग किसी भी अन्य किनारों को पार नहीं करती है।
 === समतलीय आलेख घनत्व ===
-[[जालीपन गुणांक]] या घनत्व {{mvar|D}} एक समतलीय आलेख या संजाल का, संख्या का अनुपात है {{math|''f'' – 1}} इसके अधिकतम संभव मानों द्वारा परिबद्ध फलकों का (मैक लेन के समतलीय मानदंड के अनुसार, आलेख के [[सर्किट रैंक|परिपथ रैंक]] के समान) {{math|2''v'' – 5}} के साथ एक आलेख के लिए {{mvar|v}} शीर्ष:
+[[जालीपन गुणांक|घनत्व गुणांक]] {{mvar|D}} एक समतलीय आलेख या, संख्या का अनुपात होता है {{math|''f'' – 1}} इसके अधिकतम संभव मानों द्वारा परिबद्ध फलन है {{math|2''v'' – 5}} इसके लिए एक आलेख के लिए {{mvar|v}} शीर्ष:
 :<math>D = \frac{f-1}{2v-5}</math>
-घनत्व पालन करता है {{math|0 ≤ ''D'' ≤ 1}}, साथ {{math|1=''D'' = 0}} के लिए
+घनत्व पालन करता है {{math|0 ≤ ''D'' ≤ 1}}, साथ {{math|1=''D'' = 0}} के लिए पूरी तरह से विरल समतलीय आलेख, और {{math|1=''D'' = 1}} पूरी तरह से सघन (अधिकतम) समतलीय आलेख के लिए होता है।<ref>{{citation
-एक पूरी तरह से विरल समतलीय आलेख (एक पेड़), और {{math|1=''D'' = 1}} पूरी तरह से सघन (अधिकतम) समतलीय आलेख के लिए है।<ref>{{citation
   | last1 = Buhl | first1 = J.
   | last2 = Gautrais | first2 = J.
@@ Line 109: / Line 108: @@
   }}.</ref>
 ===दोहरा आलेख===
-[[Image:dual graphs.svg|thumb|100px|एक समतलीय आलेख और उसका [[दोहरा ग्राफ|दोहरा आलेख]]]]एक अंतर्निहित दिया गया {{mvar|G}} किनारों के प्रतिच्छेदन के बिना समतल में (आवश्यक रूप से सरल नहीं) जुड़े हुए आलेख का, हम दोहरे आलेख का निर्माण करते है {{mvar|G*}} इस प्रकार है: हम प्रत्येक फलक में एक शीर्ष चुनते है {{mvar|G}} (बाहरी चेहरे सहित) और प्रत्येक किनारे के लिए {{mvar|e}} में {{mvar|G}} हम एक नई बढ़त का परिचय देते है {{mvar|G*}} दो शीर्ष को अंदर जोड़ना {{mvar|G*}} दो चेहरों के अनुरूप {{mvar|G}} जो यहां मिलते है {{mvar|e}}. इसके अतिरिक्त, यह किनारा खींचा जाता है जिससे कि यह पार हो जाए {{mvar|e}} बिल्कुल एक बार और उसका कोई दूसरा किनारा नहीं {{mvar|G}} या {{mvar|G*}} प्रतिच्छेदित है. तब {{mvar|G*}} फिर से एक (आवश्यक नहीं कि सरल) समतलीय आलेख का अंतर्निहित है, इसके उतने ही किनारे है {{mvar|G}}, जितने शीर्ष {{mvar|G}} के चेहरे और उतने ही चेहरे है {{mvar|G}} शीर्ष है. द्वैत शब्द इस तथ्य से उचित है {{math|1=''G''** = ''G''}}, यहां समानता गोले पर अंतर्निहित की तुल्यता है। यदि {{mvar|G}} तो उत्तल बहुफलक के अनुरूप समतलीय आलेख है {{mvar|G*}} दोहरे बहुफलक के अनुरूप समतलीय आलेख है।
+[[Image:dual graphs.svg|thumb|100px|एक समतलीय आलेख और उसका [[दोहरा ग्राफ|दोहरा आलेख]]]]एक अंतर्निहित दिया गया {{mvar|G}} किनारों के प्रतिच्छेदन के बिना समतल में (आवश्यक रूप से सरल नहीं) जुड़े हुए आलेख का, हम दोहरे आलेख का निर्माण करते है {{mvar|G*}} इस प्रकार है: हम प्रत्येक फलन में एक शीर्ष चुनते है {{mvar|G}} (बाहरी संख्या सहित) और प्रत्येक किनारे के लिए {{mvar|e}} में {{mvar|G}} हम एक नई बढ़त का परिचय देते है {{mvar|G*}} दो शीर्ष को अंदर जोड़ना {{mvar|G*}} दो संख्याओ के अनुरूप {{mvar|G}} यहां मिलते है {{mvar|e}}. इसके अतिरिक्त, यह किनारा खींचा जाता है जिससे कि यह पार हो जाता है {{mvar|e}} और उसका कोई दूसरा किनारा नहीं होता है {{mvar|G}} या {{mvar|G*}} प्रतिच्छेदित होता है. तब {{mvar|G*}} फिर से एक (आवश्यक नहीं कि सरल) समतलीय आलेख का अंतर्निहित होता है, इसके उतने ही किनारे है {{mvar|G}}, जितने शीर्ष {{mvar|G}} के संख्या और उतने ही संख्या है जितनी {{mvar|G}} शीर्ष की होती है {{math|1=''G''** = ''G''}}, यहां समानता अंतर्निहित की तुल्यता होती है। यदि {{mvar|G}} तो उत्तल बहुफलन के अनुरूप समतलीय आलेख होता है {{mvar|G*}} दोहरे बहुफलन के अनुरूप समतलीय आलेख होता है।
-दोहरे उपयोगी होते है क्योंकि दोहरे आलेख के कई गुण मूल आलेख के गुणों से सरल विधियों से संबंधित होते है, जिससे उनके दोहरे आलेख की जांच करके आलेख के बारे में परिणामों को सिद्ध किया जा सकता है।
+यह दोहरे उपयोगी होते है क्योंकि दोहरे आलेख के कई गुण मूल आलेख के गुणों से सरल विधियों से संबंधित होते है, जिससे उनके दोहरे आलेख की जांच करके आलेख के बारे में परिणामों को सिद्ध किया जा सकता है।
-जबकि किसी विशेष अंतर्निहित के लिए निर्मित दोहरा अद्वितीय है ([[ समाकृतिकता |समाकृतिकता]] तक), आलेख में अलग-अलग (अर्थात गैर-समरूपी) दोहरे हो सकते है, जो अलग-अलग (अर्थात [[होम्योमॉर्फिक|समरूपी]]) अंतर्निहित से प्राप्त होते है।
+जबकि किसी विशेष अंतर्निहित के लिए निर्मित दोहरा अद्वितीय होता है ([[ समाकृतिकता |समाकृतिकता]] तक), आलेख में अलग-अलग (अर्थात गैर-समरूपी) दोहरा हो सकते है, जो अलग-अलग (अर्थात [[होम्योमॉर्फिक|समरूपी]]) अंतर्निहित से प्राप्त होते है।
 ==तलीय रेखांकन के वर्ग==
 ===अधिकतम समतलीय आलेख===
-[[File:Goldner-Harary graph.svg|thumb|240px|गोल्डनर-हैरी आलेख अधिकतम समतलीय है। इसके सभी मुख तीन किनारों से घिरे हुए है।]]एक साधारण आलेख को अधिकतम तलीय कहा जाता है यदि यह समतल है, लेकिन कोई भी किनारा जोड़ने (दिए गए शीर्ष समूह पर) उस गुण को नष्ट कर देता है। फिर सभी फलकों (बाहरी फलक सहित) को तीन किनारों से घेर दिया जाता है, जो वैकल्पिक शब्द समतल त्रिभुज की व्याख्या करता है। वैकल्पिक नाम त्रिकोणीय आलेख<ref>{{citation|first=W.|last=Schnyder|title=Planar graphs and poset dimension|journal=[[Order (journal)|Order]]|volume=5|year=1989|issue=4|pages=323–343|doi=10.1007/BF00353652|mr=1010382|s2cid=122785359}}.</ref> या त्रिकोणीय आलेख<ref>{{citation|journal=Algorithmica|volume=3|issue=1–4|year=1988|pages=247–278|doi= 10.1007/BF01762117|title=A linear algorithm to find a rectangular dual of a planar triangulated graph|first1=Jayaram|last1=Bhasker|first2=Sartaj|last2=Sahni|s2cid=2709057}}.</ref> का भी उपयोग किया गया है, लेकिन वे अस्पष्ट है, क्योंकि वे सामान्यतः क्रमशः पूर्ण आलेख के [[लाइन ग्राफ|रेखा]] आलेख और [[कॉर्डल ग्राफ|कॉर्डल]] आलेख को संदर्भित करते है। प्रत्येक अधिकतम तलीय आलेख कम से कम 3-जुड़ा हुआ होता है।
+[[File:Goldner-Harary graph.svg|thumb|240px|गोल्डनर-हैरी आलेख अधिकतम समतलीय है। इसके सभी मुख तीन किनारों से घिरे हुए है।]]एक साधारण आलेख को अधिकतम तलीय कहा जाता है यदि यह समतल होता है, लेकिन कोई भी किनारा जोड़ने (दिए गए शीर्ष समूह पर) उस गुण को नष्ट कर देता है। फिर सभी फलनों (बाहरी फलन सहित) को तीन किनारों से घेर दिया जाता है, जो वैकल्पिक शब्द समतल त्रिभुज की व्याख्या करता है। वैकल्पिक त्रिकोणीय आलेख<ref>{{citation|first=W.|last=Schnyder|title=Planar graphs and poset dimension|journal=[[Order (journal)|Order]]|volume=5|year=1989|issue=4|pages=323–343|doi=10.1007/BF00353652|mr=1010382|s2cid=122785359}}.</ref><ref>{{citation|journal=Algorithmica|volume=3|issue=1–4|year=1988|pages=247–278|doi= 10.1007/BF01762117|title=A linear algorithm to find a rectangular dual of a planar triangulated graph|first1=Jayaram|last1=Bhasker|first2=Sartaj|last2=Sahni|s2cid=2709057}}.</ref> का उपयोग किया जाता है, लेकिन वे अस्पष्ट होते है, क्योंकि वे सामान्यतः क्रमशः पूर्ण आलेख के [[लाइन ग्राफ|रेखा]] आलेख और [[कॉर्डल ग्राफ|कॉर्डल]] आलेख को संदर्भित करते है। प्रत्येक अधिकतम तलीय आलेख कम से कम 3- से जुड़ा हुआ होता है।
-यदि एक अधिकतम समतलीय आलेख है {{mvar|v}} शीर्ष के साथ {{math|''v'' > 2}}, तो यह बिल्कुल ठीक है {{math|3''v'' – 6}}किनारे और {{math|2''v'' – 4}} चेहरे के।
+यदि एक अधिकतम समतलीय आलेख है {{mvar|v}} शीर्ष के साथ {{math|''v'' > 2}}, तो यह बिल्कुल ठीक है {{math|3''v'' – 6}} किनारे और {{math|2''v'' – 4}}।
-[[अपोलोनियन नेटवर्क|अपोलोनियन संजाल]] त्रिकोणीय चेहरों को बार-बार छोटे त्रिकोणों के त्रिगुणों में विभाजित करके बनाए गए अधिकतम समतलीय आलेख है। समान रूप से, वे समतलीय [[k-वृक्ष|k-ट्री]] है।
+[[अपोलोनियन नेटवर्क|अपोलोनियन संजाल]] त्रिकोणीय को बार-बार छोटे त्रिकोणों के त्रिगुणों में विभाजित करके बनाए गए अधिकतम समतलीय आलेख होता है। सामान्यतः, वे समतलीय [[k-वृक्ष|k-ट्री]] होते है।
-स्ट्रेंग्युलेटेड आलेख वे आलेख होते है जिनमें प्रत्येक [[परिधीय चक्र]] एक त्रिभुज होता है। अधिकतम समतलीय आलेख (या अधिक सामान्यतः एक बहुफलकीय आलेख) में परिधीय चक्र फलक होते है, इसलिए अधिकतम समतलीय आलेख का गला घोंट दिया जाता है। [[गला घोंट दिया गया ग्राफ|गला घोंट दिया गया आलेख]] में कॉर्डल आलेख भी सम्मलित है, और ये बिल्कुल ऐसे आलेख है जो पूर्ण आलेख और अधिकतम प्लानर आलेख के क्लिक-योग (किनारों को हटाए बिना) द्वारा बनाए जा सकते है।<ref>{{citation
+स्ट्रेंग्युलेटेड आलेख वे आलेख होते है जिनमें प्रत्येक [[परिधीय चक्र]] एक त्रिभुज होता है। अधिकतम समतलीय आलेख (या अधिक सामान्यतः एक बहुफलनीय आलेख) में परिधीय चक्र फलन होते है। इस [[गला घोंट दिया गया ग्राफ|आलेख]] में कॉर्डल आलेख भी सम्मलित होते है, और ये बिल्कुल ऐसे आलेख होते है जो पूर्ण आलेख और अधिकतम योजना आलेख के योग किनारों को हटाए बिना बनाए जा सकते है।<ref>{{citation
   | last1 = Seymour | first1 = P. D.
   | last2 = Weaver | first2 = R. W.
@@ Line 135: / Line 134: @@
   | volume = 8
   | year = 1984}}.</ref>
-===[[आउटरप्लानर ग्राफ|आउटरप्लानर]] आलेख===
+===[[आउटरप्लानर ग्राफ|आउटरयोजना]] आलेख===
-आउटरप्लानर आलेख समतल में अंतर्निहित वाले आलेख होते है, जैसे कि सभी कोने अंतर्निहित के असीमित चेहरे से संबंधित होते है। प्रत्येक बाहरी तलीय आलेख समतलीय होता है, लेकिन इसका विपरीत सत्य नहीं है: {{math|''K''<sub>4</sub>}} समतलीय है लेकिन बाह्यतलीय नहीं है। कुराटोस्की के समान एक प्रमेय में कहा गया है कि एक परिमित आलेख बाहरी तलीय होता है यदि और केवल तभी जब इसमें उपविभाजन न हो {{math|''K''<sub>4</sub>}} या का {{math|''K''<sub>2,3</sub>}}<nowiki>. उपरोक्त इस तथ्य का प्रत्यक्ष परिणाम है कि एक आलेख {{mvar|G}यदि आलेख से बना है तो } आउटरप्लानर है </nowiki>{{mvar|G}} एक नया शीर्ष जोड़कर, किनारों के साथ इसे अन्य सभी शीर्ष से जोड़कर, एक समतल आलेख बनता है।<ref>{{citation
+आउटरयोजना आलेख समतल में अंतर्निहित वाले आलेख होते है, जैसे कि सभी कोने अंतर्निहित के असीमित संख्या से संबंधित होते है। प्रत्येक बाहरी तलीय आलेख समतलीय होते है, लेकिन इसका विपरीत सत्य नहीं है: {{math|''K''<sub>4</sub>}} समतलीय है लेकिन बाह्यतलीय नहीं है। कुराटोस्की के समान एक प्रमेय में कहा गया है कि एक परिमित आलेख बाहरी तलीय होता है यदि और केवल तभी जब इसमें उपविभाजन न हो {{math|''K''<sub>4</sub>}} या का {{math|''K''<sub>2,3</sub>}}<nowiki>. उपरोक्त इस तथ्य का प्रत्यक्ष परिणाम है कि एक आलेख {{mvar|G}यदि आलेख से बना है तो } आउटरयोजना है </nowiki>{{mvar|G}} एक नया शीर्ष जोड़कर, किनारों के साथ इसे अन्य सभी शीर्ष से जोड़कर, एक समतल आलेख बनता है।<ref>{{citation
   | last = Felsner | first = Stefan
   | contribution = 1.4 Outerplanar Graphs and Convex Geometric Graphs
@@ Line 148: / Line 147: @@
   | year = 2004}}</ref>
-आलेख का 1-आउटरप्लानर अंतर्निहित आउटरप्लानर अंतर्निहित के समान है। के लिए {{math|''k'' > 1}} एक समतल अंतर्निहित है {{mvar|k}}-आउटरप्लानर यदि बाहरी फलक पर शीर्ष को हटाने पर परिणाम मिलता है {{math|(''k'' – 1)}}-आउटरप्लानर अंतर्निहित। एक आलेख है {{mvar|k}}-आउटरप्लानर यदि इसमें एक है {{mvar|k}}-आउटरप्लानर अंतर्निहित।
+आलेख का 1-आउटरयोजना अंतर्निहित आउटरयोजना अंतर्निहित के समान होता है। इसके लिए {{math|''k'' > 1}} एक समतल अंतर्निहित होता है {{mvar|k}}-आउटरयोजना यदि बाहरी फलन पर शीर्ष को हटाने पर परिणाम मिलता है {{math|(''k'' – 1)}}।
 ===हैलिन आलेख===
-[[ हालीन ग्राफ |हालीन आलेख]] एक अप्रत्यक्ष समतल ट्री (बिना डिग्री-दो नोड्स के) से बना एक आलेख है, जो पेड़ के समतल अंतर्निहित द्वारा दिए गए क्रम में, इसकी पत्तियों को एक चक्र में जोड़ता है। समान रूप से, यह एक बहुफलकीय आलेख है जिसमें एक फलक अन्य सभी फलकों से सटा हुआ होता है। प्रत्येक हेलिन आलेख समतलीय है। आउटरप्लानर आलेख की तरह, हेलिन आलेख में कम [[ वृक्ष चौड़ाई |ट्री चौड़ाई]] होती है, जिससे उन पर कई एल्गोरिथम समस्याएं अप्रतिबंधित प्लेनर आलेख की तुलना में अधिक आसानी से हल हो जाती है।<ref>{{citation
+[[ हालीन ग्राफ |हैलिन आलेख]] एक अप्रत्यक्ष समतल ट्री (बिना डिग्री-दो नोड्स के) से बना एक आलेख होता है, जो ट्री के समतल अंतर्निहित द्वारा दिए गए क्रम में, इसकी पत्तियों को एक चक्र में जोड़ता है। समान रूप से, यह एक बहुफलनीय आलेख होता है जिसमें एक फलन अन्य सभी फलनों से जुड़ा हुआ होता है। प्रत्येक हेलिन आलेख समतलीय होते है। आउटरयोजना आलेख की तरह, हेलिन आलेख में कम [[ वृक्ष चौड़ाई |ट्री चौड़ाई]] होती है, जिससे उन पर कई कलन विधि समस्याएं अप्रतिबंधित योजना आलेख की तुलना में अधिक आसानी से हल हो जाती है।<ref>{{citation
   | last1 = Sysło | first1 = Maciej M.
   | last2 = Proskurowski | first2 = Andrzej
@@ Line 163: / Line 162: @@
   | year = 1983}}.</ref>
 ===समतलीय आलेख===
-एक उर्ध्व तलीय आलेख एक निर्देशित चक्रीय आलेख है जिसे समतल में इसके किनारों के साथ गैर-क्रॉसिंग वक्र के रूप में खींचा जा सकता है जो लगातार ऊपर की दिशा में उन्मुख होते है। प्रत्येक तलीय [[निर्देशित अचक्रीय ग्राफ|निर्देशित अचक्रीय आलेख]] उर्ध्व तलीय नहीं है, और यह परीक्षण करने के लिए एनपी-पूर्ण है कि कोई दिया गया आलेख उर्ध्व तलीय है या नहीं है।
+एक उर्ध्व तलीय आलेख एक निर्देशित चक्रीय आलेख होता है जिसे समतल में इसके किनारों के साथ गैर-क्रॉसिंग वक्र के रूप में खींचा जा सकता है जो लगातार ऊपर की दिशा में उन्मुख होते है। प्रत्येक तलीय [[निर्देशित अचक्रीय ग्राफ|निर्देशित अचक्रीय आलेख]] उर्ध्व तलीय नहीं होता है, और यह परीक्षण करने के लिए एनपी-पूर्ण है कि कोई दिया गया आलेख उर्ध्व तलीय है या नहीं है।
 ===उत्तल तलीय आलेख===
-एक समतल आलेख को उत्तल कहा जाता है यदि उसके सभी फलक [[उत्तल बहुभुज]] होते है। सभी समतलीय आलेख में उत्तल अंतर्निहित नहीं होती है। {{math|K{{sub|2,4}}}}). एक पर्याप्त स्थिति यह है कि एक आलेख को उत्तल रूप से खींचा जा सकता है कि यह एक 3-शीर्ष-संपर्क प्लेनर आलेख का एक उपवर्ग (आलेख सिद्धांत) है। टुट्टे अंतर्निहित प्रमेय कहता है कि सरल 3-शीर्ष-संपर्क प्लेनर आलेख के लिए आंतरिक शीर्ष की स्थिति को उसके वर्गों के औसत के रूप में चुना जा सकता है।
+एक समतल आलेख को उत्तलतब तब कहा जाता है यदि उसके सभी फलन [[उत्तल बहुभुज]] होते है। सभी समतलीय आलेख में उत्तल अंतर्निहित नहीं होते है। {{math|K{{sub|2,4}}}}) एक पर्याप्त स्थिति यह है कि एक आलेख को उत्तल रूप से खींचा जा सकता है कि यह एक 3-शीर्ष-संपर्क योजना आलेख का एक उपवर्ग (आलेख सिद्धांत) होता है। टुट्टे अंतर्निहित प्रमेय कहता है कि सरल 3-शीर्ष-संपर्क योजना आलेख के लिए आंतरिक शीर्ष की स्थिति को उसके वर्गों के औसत के रूप में चुना जा सकता है।
 ===शब्द-प्रतिनिधित्व योग्य समतलीय आलेख===
-[[शब्द-प्रतिनिधित्व योग्य ग्राफ़|शब्द-प्रतिनिधित्व योग्य समतलीय आलेख]] में त्रिभुज-मुक्त समतलीय आलेख और, अधिक सामान्यतः, 3-रंगीय समतलीय आलेख सम्मलित है।<ref name="HK|last=P16">{{cite journal |first1=M. |last1=Halldórsson |first2=S. |last2=Kitaev |first3=A. |last3=Pyatkin. |title=अर्ध-संक्रमणीय अभिविन्यास और शब्द-प्रतिनिधित्व योग्य ग्राफ़|journal=Discr. Appl. Math.  |volume=201  |issue= |pages=164–171  |doi= 10.1016/j.dam.2015.07.033|date=2016 |s2cid=26796091 |doi-access=free }}</ref>
+[[शब्द-प्रतिनिधित्व योग्य ग्राफ़|शब्द-प्रतिनिधित्व योग्य समतलीय आलेख]] में त्रिभुज-मुक्त समतलीय आलेख और, अधिक सामान्यतः, 3-रंगीय समतलीय आलेख सम्मलित होते है।<ref name="HK|last=P16">{{cite journal |first1=M. |last1=Halldórsson |first2=S. |last2=Kitaev |first3=A. |last3=Pyatkin. |title=अर्ध-संक्रमणीय अभिविन्यास और शब्द-प्रतिनिधित्व योग्य ग्राफ़|journal=Discr. Appl. Math.  |volume=201  |issue= |pages=164–171  |doi= 10.1016/j.dam.2015.07.033|date=2016 |s2cid=26796091 |doi-access=free }}</ref>
 ==प्रमेय==
@@ Line 181: / Line 180: @@
 === अन्य परिणाम ===
-[[चार रंग प्रमेय]] में कहा गया है कि प्रत्येक समतलीय आलेख [[ग्राफ़ रंग|आलेख रंग]] (अर्थात, 4-पार्टाइट) है।
+[[चार रंग प्रमेय]] में कहा गया है कि प्रत्येक समतलीय आलेख [[ग्राफ़ रंग|आलेख रंग]] (अर्थात, 4-बिंदु) होते है।
-फ़ेरी के प्रमेय में कहा गया है कि प्रत्येक सरल समतलीय आलेख एक समतलीय सीधी-रेखा आलेख के रूप में प्रतिनिधित्व स्वीकार करता है। एक [[सार्वभौमिक बिंदु सेट|सार्वभौमिक बिंदु समूह]] बिंदुओं का एक समूह है जैसे कि एन कोने वाले प्रत्येक समतल आलेख में बिंदु समूह में सभी शीर्ष के साथ ऐसा अंतर्निहित होता है, द्विघात आकार के सार्वभौमिक बिंदु समूह उपस्थित है, जो [[पूर्णांक जाली]] के आयताकार उपसमुच्चय को लेकर बनते है। प्रत्येक सरल आउटरप्लानर आलेख समतल में एक अंतर्निहित को स्वीकार करता है जैसे कि सभी शीर्ष एक निश्चित वृत्त पर स्थित होते है और सभी किनारे सीधी रेखा वर्ग होते है जो डिस्क के अंदर स्थित होते है और प्रतिच्छेद नहीं करते है, इसलिए एन-शीर्ष [[नियमित बहुभुज]] आउटरप्लानर आलेख के लिए सार्वभौमिक होते है।
+फेरी के प्रमेय में कहा गया है कि प्रत्येक सरल समतलीय आलेख एक समतलीय सीधी-रेखा आलेख के रूप में प्रतिनिधित्व स्वीकार करता है। एक [[सार्वभौमिक बिंदु सेट|सार्वभौमिक बिंदु समूह]] बिंदुओं का एक समूह होता है जैसे कि एन कोने वाले प्रत्येक समतल आलेख में बिंदु समूह में सभी शीर्ष के साथ ऐसा अंतर्निहित होता है, द्विघात आकार के सार्वभौमिक बिंदु समूह उपस्थित होते है, जो [[पूर्णांक जाली|पूर्णांक]] के आयताकार उपसमुच्चय को लेकर बनते है। प्रत्येक सरल आउटरयोजना आलेख समतल में एक अंतर्निहित को स्वीकार करते है जैसे कि सभी शीर्ष एक निश्चित वृत्त पर स्थित होते है और सभी किनारे सीधी रेखा वर्ग में होते है जो चक्र के अंदर स्थित होते है और प्रतिच्छेद नहीं करते है, इसलिए एन-शीर्ष [[नियमित बहुभुज]] आउटरयोजना आलेख के लिए सार्वभौमिक होते है।
-शीनरमैन का अनुमान (अब एक प्रमेय) बताता है कि प्रत्येक समतल आलेख को समतल में रेखा वर्गों के [[प्रतिच्छेदन ग्राफ|प्रतिच्छेदन आलेख]] के रूप में दर्शाया जा सकता है।
+शीनरमैन का प्रमेय बताता है कि प्रत्येक समतल आलेख को समतल में रेखा वर्गों के [[प्रतिच्छेदन ग्राफ|प्रतिच्छेदन आलेख]] के रूप में दर्शाया जा सकता है।
-समतल विभाजक प्रमेय में कहा गया है कि प्रत्येक एन-शीर्ष समतल आलेख को आलेख सिद्धांत की दो वाक्यांश में विभाजित किया जा सकता है O को हटाकर अधिकतम 2n/3 आकार के सबआलेख{{radic|''n''}}) शीर्ष. परिणामस्वरूप, समतलीय आलेख में ट्री-चौड़ाई और [[शाखा-चौड़ाई]] O({{radic|''n''}}).
+समतल विभाजक प्रमेय में कहा गया है कि प्रत्येक एन-शीर्ष समतल आलेख को आलेख सिद्धांत की दो वाक्यांश में विभाजित किया जा सकता है O को हटाकर अधिकतम 2n/3 आकार के उपआलेख{{radic|''n''}}) शीर्ष. परिणामस्वरूप, समतलीय आलेख में ट्री-चौड़ाई होती है O({{radic|''n''}}).
-समतलीय उत्पाद संरचना प्रमेय में कहा गया है कि प्रत्येक समतलीय आलेख अधिकतम 8 और एक पथ पर ट्री चौड़ाई वाले आलेख के मजबूत आलेख उत्पाद का एक उपआलेख है।<ref>{{citation
+समतलीय उत्पाद संरचना प्रमेय में कहा गया है कि प्रत्येक समतलीय आलेख अधिकतम 8 और एक पथ पर ट्री चौड़ाई वाले आलेख के मजबूत आलेख उत्पाद का एक उपआलेख होता है।<ref>{{citation
   | last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
   | last2 = Joret | first2 = Gwenäel
@@ Line 205: / Line 204: @@
   | year = 2020}}</ref>
-इस परिणाम का उपयोग यह दिखाने के लिए किया गया है कि समतल आलेख में परिबद्ध [[कतार संख्या]], परिबद्ध थू संख्या|गैर-दोहरावीय रंगीन संख्या और निकट-रेखीय आकार के [[सार्वभौमिक ग्राफ|सार्वभौमिक]] आलेख होते है। इसमें शीर्ष रैंकिंग के लिए भी एप्लिकेशन है<ref>{{citation
+इस परिणाम का उपयोग यह दिखाने के लिए किया जाता है कि समतल आलेख में परिबद्ध [[कतार संख्या|संख्या]], रंगीन संख्या और निकट-रेखीय आकार के [[सार्वभौमिक ग्राफ|सार्वभौमिक]] आलेख होते है। इसमें शीर्ष वर्गों के लिए भी उपकरण होते है<ref>{{citation
   | last1 = Bose | first1 = Prosenjit
   | last2 = Dujmović | first2 = Vida | author2-link = Vida Dujmović
@@ Line 224: / Line 223: @@
 | doi = 10.19086/aic.27351
   | s2cid = 195874032
-  }}</ref> समतलीय रेखांकन का V शीर्ष वाले दो समतलीय आलेखों के लिए, समय O(v) में यह निर्धारित करना संभव है कि वे आलेख सिद्धांत है या नहीं है(आलेख समरूपता समस्या भी देखें)।<ref>{{cite book |first1=I. S. |last1=Filotti |first2=Jack N. |last2=Mayer |chapter=A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus |title=Proceedings of the 12th Annual ACM Symposium on Theory of Computing |pages=236–243 |year=1980 |doi=10.1145/800141.804671 |isbn=978-0-89791-017-0|s2cid=16345164 |url=https://hal.inria.fr/inria-00076553/file/RR-0008.pdf }}</ref>
+  }}</ref> समतलीय रेखांकन का V शीर्ष वाले दो समतलीय आलेखों के लिए, O(v) में यह निर्धारित करना संभव होता है कि वह आलेख सिद्धांत है या नहीं है (आलेख समरूपता समस्या भी देखें)।<ref>{{cite book |first1=I. S. |last1=Filotti |first2=Jack N. |last2=Mayer |chapter=A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus |title=Proceedings of the 12th Annual ACM Symposium on Theory of Computing |pages=236–243 |year=1980 |doi=10.1145/800141.804671 |isbn=978-0-89791-017-0|s2cid=16345164 |url=https://hal.inria.fr/inria-00076553/file/RR-0008.pdf }}</ref>
 ==सामान्यीकरण==
-[[शीर्ष ग्राफ|शीर्ष आलेख]] एक ऐसा आलेख है जिसे एक शीर्ष को हटाकर समतल बनाया जा सकता है, और के-एपेक्स आलेख एक ऐसा आलेख है जिसे अधिकतम k शीर्ष को हटाकर समतल बनाया जा सकता है।
+[[शीर्ष ग्राफ|शीर्ष आलेख]] एक ऐसा आलेख होता है जिसे एक शीर्ष को हटाकर समतल बनाया जा सकता है, और के-एपेक्स आलेख एक ऐसा आलेख होता है जिसे अधिकतम k शीर्ष को हटाकर समतल बनाया जा सकता है।
-[[1-तलीय ग्राफ|1-तलीय आलेख]] एक ऐसा आलेख है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ समतल में खींचा जा सकता है, और के-प्लानर आलेख एक ऐसा आलेख है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ खींचा जा सकता है।
+[[1-तलीय ग्राफ|1-तलीय आलेख]] एक ऐसा आलेख होता है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ समतल में खींचा जा सकता है, और के-योजना आलेख एक ऐसा आलेख होता है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ खींचा जा सकता है।
-[[मानचित्र ग्राफ़|मानचित्र आलेख]] एक ऐसा आलेख होता है जो दो क्षेत्रों को जोड़कर समतल में बहुत सारे सरलता से जुड़े हुए आंतरिक-विच्छेदित क्षेत्रों के एक समूह से बनता है, जब वे कम से कम एक सीमा बिंदु साझा करते है। जब अधिकतम तीन क्षेत्र एक बिंदु पर मिलते है, तो परिणाम एक समतलीय आलेख होता है, लेकिन जब चार या अधिक क्षेत्र एक बिंदु पर मिलते है, तो परिणाम गैर-तलीय हो सकता है।
+[[मानचित्र ग्राफ़|मानचित्र आलेख]] एक ऐसा आलेख होता है जो दो क्षेत्रों को जोड़कर समतल में बहुत सारे सरलता से जुड़े हुए आंतरिक-विच्छेदित क्षेत्रों के एक समूह से बनता है। जब अधिकतम तीन क्षेत्र एक बिंदु पर मिलते है, तो परिणाम एक समतलीय आलेख होता है, लेकिन जब चार या अधिक क्षेत्र एक बिंदु पर मिलते है, तो परिणाम गैर-तलीय हो सकता है।
-टॉरॉइडल आलेख एक ऐसा आलेख है जिसे [[ टोरस्र्स |टोरस्र्स]] पर क्रॉसिंग के बिना अंतर्निहित किया जा सकता है। अधिक सामान्यतः, आलेख का जीनस (गणित) एक द्वि-आयामी सतह का न्यूनतम जीनस होता है जिसमें आलेख को अंतर्निहित किया जा सकता है, समतलीय आलेख में जीनस शून्य होता है और नॉनप्लानर [[टोरॉयडल ग्राफ|टोरॉयडल]] आलेख में जीनस एक होता है। प्रत्येक आलेख को किसी (ओरिएंटेबल, संपर्क) बंद द्वि-आयामी सतह (हैडल के साथ क्षेत्र) में क्रॉस किए बिना अंतर्निहित किया जा सकता है और इस प्रकार आलेख का जीनस अच्छी तरह से परिभाषित होता है। यदि आलेख को जीनस जी के साथ एक (ओरिएंटेबल, संपर्क, बंद) सतह में क्रॉसिंग के बिना अंतर्निहित किया जा सकता है, तो इसे अधिक या समान जीनस के साथ सभी (ओरिएंटेबल, संपर्क, बंद) सतहों में क्रॉसिंग के बिना अंतर्निहित किया जा सकता है। आलेख सिद्धांत में अन्य अवधारणाएँ भी है जिन्हें एक्स कुछ क्वालीफायर के साथ एक्स जीनस कहा जाता है, सामान्यतः ये बिना किसी योग्यता के जीनस की उपरोक्त परिभाषित अवधारणा से भिन्न होते है। विशेष रूप से एक आलेख का गैर-उन्मुखी जीनस (इसकी परिभाषा में गैर-उन्मुखी सतहों का उपयोग करके) उस आलेख के जीनस (इसकी परिभाषा में उन्मुखी सतहों का उपयोग करके) से एक सामान्य आलेख के लिए भिन्न होता है।
+टॉरॉइडल आलेख एक ऐसा आलेख होता है जिसे [[ टोरस्र्स |टोरस्र्स]] पर क्रॉसिंग के बिना अंतर्निहित किया जा सकता है। अधिक सामान्यतः, आलेख का जीनस (गणित) एक द्वि-आयामी सतह का न्यूनतम जीनस होता है जिसमें आलेख को अंतर्निहित किया जा सकता है, समतलीय आलेख में जीनस शून्य होता है और नॉनयोजना [[टोरॉयडल ग्राफ|टोरॉयडल]] आलेख में जीनस एक होता है। प्रत्येक आलेख को किसी बंद द्वि-आयामी सतह में क्रॉस किए बिना अंतर्निहित किया जा सकता है और इस प्रकार आलेख का जीनस अच्छी तरह से परिभाषित होता है। यदि आलेख को जीनस जी के साथ एक सतह में क्रॉसिंग के बिना अंतर्निहित किया जा सकता है, तो इसे अधिक या समान जीनस के साथ सभी सतहों में क्रॉसिंग के बिना अंतर्निहित किया जा सकता है। आलेख सिद्धांत में अन्य अवधारणाएँ भी होती है जिन्हें एक्स क्वालीफायर के साथ एक्स जीनस कहा जाता है, सामान्यतः ये बिना किसी योग्यता के जीनस की उपरोक्त परिभाषित अवधारणा से भिन्न होते है। विशेष रूप से एक आलेख का गैर-उन्मुखी जीनस (इसकी परिभाषा में गैर-उन्मुखी सतहों का उपयोग करके) उस आलेख के जीनस (इसकी परिभाषा में उन्मुखी सतहों का उपयोग करके) से एक सामान्य आलेख से भिन्न होता है।
-किसी भी आलेख को बिना क्रॉसिंग के त्रि-आयामी अंतरिक्ष में अंतर्निहित किया जा सकता है। वास्तव में, किसी भी आलेख को दो समतल समूहअप में क्रॉसिंग के बिना खींचा जा सकता है, जहां दो विमानों को एक दूसरे के ऊपर रखा जाता है और किनारों को किसी भी स्थान पर एक विमान से दूसरे तक कूदने और नीचे गिरने की अनुमति होती है (सिर्फ नहीं) आलेख शीर्ष) जिससे कि किनारे अन्य किनारों के साथ प्रतिच्छेदन से बच सकें। इसकी व्याख्या इस प्रकार की जा सकती है कि किसी भी विद्युत संकलक संजाल को दो-तरफा [[सर्किट बोर्ड|परिपथ बोर्ड]] के साथ बनाना संभव होता है जहां बोर्ड के किनारों के बीच विद्युत संपर्क बनाया जा सकता है (जैसा कि सामान्य वास्तविक जीवन परिपथ बोर्डों के साथ संभव है, विद्युत संपर्क के साथ) बोर्ड के ऊपरी हिस्से में तार के टुकड़ों के माध्यम से और नीचे की तरफ बोर्ड पर बने तांबे के ट्रैक के माध्यम से प्राप्त किया गया और बोर्ड के किनारों के बीच ड्रिलिंग छेद के माध्यम से विद्युत संपर्क प्राप्त किया गया, तारों को छेद के माध्यम से पारित किया गया और उन्हें टांका लगाया गया। पटरियों में), इसकी व्याख्या इस तरह भी की जा सकती है कि किसी भी सड़क संजाल को बनाने के लिए केवल पुलों या सिर्फ सुरंगों की जरूरत होती है, दोनों की नहीं (2 स्तर पर्याप्त है, 3 की जरूरत नहीं है)। साथ ही, तीन आयामों में क्रॉसिंग के बिना आलेख खींचने का प्रश्न तुच्छ है। चूँकि, प्लेनर आलेख का एक त्रि-आयामी एनालॉग [[ लिंक रहित एम्बेडिंग |लिंक रहित अंतर्निहित]] द्वारा प्रदान किया जाता है, आलेख जिन्हें त्रि-आयामी अंतरिक्ष में इस तरह से अंतर्निहित किया जा सकता है कि कोई भी दो चक्र एक दूसरे के साथ संख्या को नहीं जोड़ रहे है। कुराटोस्की और वैगनर के समतलीय आलेख के लक्षण वर्णन के अनुरूप, ऐसे आलेख जिनमें K<sub>5</sub> सम्मलित नहीं है या K<sub>3</sub> एक नाबालिग के रूप में, लिंकलेस एंबेडेबल आलेख को उन आलेख के रूप में चित्रित किया जा सकता है जिनमें [[पीटरसन परिवार|पीटरसन]] वर्ग के सात आलेखों में से कोई भी नाबालिग के रूप में सम्मलित नहीं है। आउटरप्लेनर और प्लेनर आलेख के लक्षण वर्णन के अनुरूप, कॉलिन डी वेरडीयर आलेख अधिकतम दो या तीन में अपरिवर्तनीय होते है, लिंकलेस एंबेडेबल आलेख वे आलेख होते है जिनमें कॉलिन डी वेरडीयर अधिकतम चार में अपरिवर्तनीय होते है।
+किसी भी आलेख को बिना क्रॉसिंग के त्रि-आयामी स्थान में अंतर्निहित किया जा सकता है। वास्तव में, किसी भी आलेख को दो समतल उपसमूह में क्रॉसिंग के बिना खींचा जा सकता है। इसकी व्याख्या इस प्रकार की जा सकती है कि किसी भी विद्युत संकलक संजाल को दो-तरफा [[सर्किट बोर्ड|परिपथ बोर्ड]] के साथ बनाना संभव होता है जहां बोर्ड के किनारों के बीच विद्युत संपर्क बनाया जा सकता है (जैसा कि सामान्य वास्तविक जीवन परिपथ बोर्डों के साथ संभव होता है, विद्युत संपर्क के साथ) बोर्ड के ऊपरी हिस्से में तार के टुकड़ों के माध्यम से और नीचे की तरफ बोर्ड पर बने तांबे के ट्रैक के माध्यम से प्राप्त किया जाता है और बोर्ड के किनारों के बीच ड्रिलिंग छेद के माध्यम से विद्युत संपर्क प्राप्त किया जाता है, इसकी व्याख्या इस तरह भी की जा सकती है कि किसी भी संजाल को बनाने के लिए केवल सुरंगों की जरूरत होती है। चूँकि, योजना आलेख का एक त्रि-आयामी अनुरूप [[ लिंक रहित एम्बेडिंग |संपर्क रहित अंतर्निहित]] द्वारा प्रदान किया जाता है, इस आलेख को त्रि-आयामी स्थान में अंतर्निहित तब किया जा सकता है जब कोई भी दो चक्र एक दूसरे के साथ संख्या को नहीं जोड़ते है। कुराटोस्की और वैगनर के समतलीय आलेख के वर्णन के अनुरूप, ऐसे आलेख जिनमें K<sub>5</sub> सम्मलित नहीं है या K<sub>3</sub> के रूप में, संपर्क अंतर्निहित आलेख को उन आलेख के रूप में चित्रित किया जा सकता है जिनमें [[पीटरसन परिवार|पीटरसन]] वर्ग के सात आलेखों में से कोई भी संख्या के रूप में सम्मलित नहीं होते है। आउटरयोजना और योजना आलेख के वर्णन के अनुरूप, कॉलिन डी वेरडीयर आलेख अधिकतम दो या तीन में अपरिवर्तनीय होते है, संपर्क अंतर्निहित आलेख वह आलेख होते है जिनमें कॉलिन डी वेरडीयर अधिकतम चार में अपरिवर्तनीय होते है।
 ==यह भी देखें==
@@ Line 241: / Line 240: @@
 * मोटाई (आलेख सिद्धांत), समतलीय आलेख की सबसे छोटी संख्या जिसमें किसी दिए गए आलेख के किनारों को विभाजित किया जा सकता है
 * [[समतलता]], एक पहेली कंप्यूटर गेम जिसमें उद्देश्य एक समतल आलेख को एक समतल पर अंतर्निहित करना है
-* [[ अंकुर (खेल) ]], एक पेंसिल-और-पेपर गेम जहां गेम खेलने के हिस्से के रूप में कुछ बाधाओं के अधीन एक प्लानर आलेख का निर्माण किया जाता है
+* [[ अंकुर (खेल) ]], एक पेंसिल-और-पेपर गेम जहां गेम खेलने के हिस्से के रूप में कुछ बाधाओं के अधीन एक योजना आलेख का निर्माण किया जाता है
 * तीन उपयोगिताएँ समस्या, एक लोकप्रिय पहेली

Anonymous

Search

समतल आलेख: Difference between revisions

Namespaces

More

Page actions

Revision as of 03:15, 10 July 2023

Contents

समतलीयता मानदंड

कुराटोव्स्की और वैगनर के प्रमेय

अन्य मानदंड

गुण

यूलर का सूत्र

औसत डिग्री

मुद्रण आलेख

समतलीय आलेख घनत्व

दोहरा आलेख

तलीय रेखांकन के वर्ग

अधिकतम समतलीय आलेख

आउटरयोजना आलेख

हैलिन आलेख

समतलीय आलेख

उत्तल तलीय आलेख

शब्द-प्रतिनिधित्व योग्य समतलीय आलेख

प्रमेय

समतलीय आलेख की गणना

अन्य परिणाम

सामान्यीकरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

समतल आलेख: Difference between revisions

Revision as of 03:15, 10 July 2023

समतलीयता मानदंड

कुराटोव्स्की और वैगनर के प्रमेय

अन्य मानदंड

गुण

यूलर का सूत्र

औसत डिग्री

मुद्रण आलेख

समतलीय आलेख घनत्व

दोहरा आलेख

तलीय रेखांकन के वर्ग

अधिकतम समतलीय आलेख

आउटरयोजना आलेख

हैलिन आलेख

समतलीय आलेख

उत्तल तलीय आलेख

शब्द-प्रतिनिधित्व योग्य समतलीय आलेख

प्रमेय

समतलीय आलेख की गणना

अन्य परिणाम

सामान्यीकरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories