Common graph
ग्राफ सिद्धांत में, गणित का एक क्षेत्र, सामान्य ग्राफ समरूपता घनत्वों में असमानताओं से संबंधित चरम ग्राफ सिद्धांत की एक शाखा से संबंधित हैं। मोटे तौर पर, एक सामान्य ग्राफ है यदि यह "आम तौर पर" एक उपग्राफ के रूप में दिखाई देता है, इस अर्थ में कि किसी भी ग्राफ और उसके पूरक में प्रतियों की कुल संख्या एक ही शीर्ष पर सभी संभावित प्रतियों का एक बड़ा अंश है। स्वाभाविक रूप से, यदि इसकी कुछ प्रतियां हैं, तो इसकी भरपाई करने के लिए इसके पूरक में इसकी बहुत सारी प्रतियां होनी चाहिए। सामान्य ग्राफ समरूपता घनत्व असमानताओं से संबंधित अन्य ग्राफ धारणाओं से निकटता से संबंधित हैं। उदाहरण के लिए, सामान्य ग्राफ सिडोरेंको ग्राफ का एक अधिक सामान्य मामला है। परिभाषा एक ग्राफ आम है यदि असमानता किसी भी ग्राफॉन के लिए होती है, जहां किनारों की संख्या है और समरूपता घनत्व है। असमानता तंग है क्योंकि निचली सीमा हमेशा तब पहुंचती है जब स्थिर ग्राफॉन होता है। परिभाषा की व्याख्याएँ एक ग्राफ के लिए, हमारे पास और संबंधित ग्राफॉन के लिए, क्योंकि पूरक से संबंधित ग्राफॉन है। इसलिए, यह सूत्र हमें एक निकट पर्याप्त सन्निकटन लेने के लिए बहुत ही अनौपचारिक अंतर्ज्ञान प्रदान करता है, जो भी इसका अर्थ है, और "अनुमानित" ग्राफ में ग्राफ की लेबल की गई प्रतियों के मोटे तौर पर अंश के रूप में देखें। फिर, हम मान सकते हैं कि मात्रा मोटे तौर पर है और बाद वाले की व्याख्या इन और की प्रतियों की संयुक्त संख्या के रूप में कर सकते हैं। इसलिए, हम देखते हैं कि यह लागू होता है। इसका मतलब है कि सामान्य ग्राफ आमतौर पर उपग्राफ के रूप में दिखाई देता है। दूसरे शब्दों में, यदि हम किनारों और गैर-किनारों को एक ही शीर्ष पर पूर्ण ग्राफ के किनारों के 2-रंग के रूप में सोचते हैं, तो सभी संभावित प्रतियों का कम से कम अंश एकवर्णी होता है। ध्यान दें कि एर्डोस-रेनी यादृच्छिक ग्राफ में संभावना के साथ खींचे गए प्रत्येक किनारे के साथ, प्रत्येक ग्राफ समरूपता में एकवर्णी होने की संभावना होती है। तो, सामान्य ग्राफ एक ग्राफ है जहाँ यह ग्राफ पर ग्राफ के एकवर्णी उपग्राफ के रूप में अपनी न्यूनतम संख्या को प्राप्त करता है। उपरोक्त परिभाषा को सामान्यीकृत समरूपता घनत्व का उपयोग करके इस तरह से समझा जा सकता है। उदाहरण जैसा कि ऊपर बताया गया है, सभी सिडोरेंको ग्राफ सामान्य ग्राफ हैं। इसलिए, कोई भी ज्ञात सिडोरेंको ग्राफ एक सामान्य ग्राफ का एक उदाहरण है, और, विशेष रूप से, सम लंबाई के चक्र आम हैं। हालाँकि, ये सीमित उदाहरण हैं क्योंकि सभी सिडोरेंको ग्राफ द्विदलीय ग्राफ हैं जबकि गैर-द्विदलीय सामान्य ग्राफ मौजूद हैं, जैसा कि नीचे दिखाया गया है। त्रिभुज ग्राफ गैर-द्विदलीय सामान्य ग्राफ का एक सरल उदाहरण है। 4 शीर्षों पर पूर्ण ग्राफ के एक किनारे को हटाकर प्राप्त ग्राफ आम है। गैर-उदाहरण-एक समय के लिए यह माना जाता था कि सभी ग्राफ सामान्य हैं। हालाँकि, यह पता चला है कि यह सामान्य नहीं है। विशेष रूप से, आम नहीं है, भले ही यह आम है। सबूत सिडोरेंको ग्राफ आम हैं एक ग्राफ एक सिडोरेंको ग्राफ है यदि यह सभी ग्राफों के लिए संतुष्ट करता है। उस मामले में,। इसके अलावा, जो समरूपता घनत्व की परिभाषा का अनुसरण करता है। फलन के लिए जेनसन की असमानता के साथ इसका संयोजनः इस प्रकार, सामान्य ग्राफ के लिए शर्तों को पूरा किया जाता है। त्रिभुज ग्राफ सामान्य है अभिन्न अभिव्यक्ति का विस्तार करें और चर के बीच समरूपता को ध्यान में रखेंः अभिव्यक्ति में प्रत्येक शब्द को छोटे ग्राफों के समरूपता घनत्व के संदर्भ में लिखा जा सकता है। समरूपता घनत्व की परिभाषा के अनुसारः जहां एक भाग पर शीर्ष और दूसरे पर शीर्ष पर पूर्ण द्विदलीय ग्राफ को दर्शाता है। यह इस प्रकार हैः चर और के बीच समरूपता के लिए धन्यवाद से संबंधित हो सकता हैः जहां अंतिम चरण अभिन्न कौची-श्वार्ज असमानता से अनुसरण करता है। अंत मेंः यह प्रमाण "किसी भी पक्ष में परिचित और अजनबियों के सेट पर" में प्रमेय 1 के निरंतर अनुरूप लेने से प्राप्त किया जा सकता है।