ग्राफ सिद्धांत - रंग
ग्राफ़ रंग कुछ भी नहीं है, लेकिन कुछ बाधाओं के तहत ग्राफ घटकों जैसे कि कोने, किनारों और क्षेत्रों को लेबल करने का एक सरल तरीका है। एक ग्राफ़ में, कोई भी दो आसन्न कोने, आसन्न किनारों, या आसन्न क्षेत्र न्यूनतम संख्या में रंगों के साथ रंगीन नहीं होते हैं। इस संख्या को कहा जाता हैchromatic number और ग्राफ को एक कहा जाता है properly colored graph।
ग्राफ़ की रंगाई करते समय, ग्राफ़ पर सेट की जाने वाली बाधाएँ रंग, रंग क्रम, रंग निर्दिष्ट करने का तरीका आदि हैं। एक रंग किसी शीर्ष या किसी विशेष क्षेत्र को दिया जाता है। इस प्रकार, एक ही रंग वाले कोने या क्षेत्र स्वतंत्र सेट बनाते हैं।
वर्टेक्स रंग
वर्टेक्स रंग एक ग्राफ 'जी' के कोने को रंगों का एक असाइनमेंट है जैसे कि दो आसन्न कोने एक ही रंग के नहीं हैं। सीधे शब्दों में कहें, एक किनारे के कोई दो कोने एक ही रंग के नहीं होने चाहिए।
क्रोमेटिक नंबर
ग्राफ 'जी' के वर्टेक्स रंग के लिए आवश्यक रंगों की न्यूनतम संख्या को एक्स (जी) द्वारा चिह्नित जी के क्रोमेटिक नंबर के रूप में कहा जाता है।
1 (G) = 1 यदि और केवल यदि 'G' एक शून्य ग्राफ है। यदि If G ’शून्य ग्राफ नहीं है, तो G (G) not 2।
Example
Note - एक ग्राफ 'जी' को एन-कवर करने योग्य कहा जाता है यदि कोई शीर्ष रंग है जो अधिकांश एन रंगों, यानी एक्स (जी)। एन का उपयोग करता है।
क्षेत्र का रंग
रीजन कलरिंग एक प्लानर ग्राफ के क्षेत्रों के लिए रंगों का एक असाइनमेंट है जैसे कि दो आसन्न क्षेत्रों में एक ही रंग नहीं है। दो क्षेत्रों को कहा जाता है कि यदि उनके पास एक सामान्य किनारा है।
Example
निम्नलिखित ग्राफ पर एक नज़र डालें। क्षेत्र 'एईबी' और 'बीफसी' आसन्न हैं, क्योंकि उन दोनों क्षेत्रों के बीच एक सामान्य बढ़त है।
इसी प्रकार, अन्य क्षेत्र भी आसन्न के आधार पर रंगीन होते हैं। यह ग्राफ निम्नानुसार रंगीन है -
Example
Kn की वर्णनात्मक संख्या है
- n
- n–1
- [n/2]
- [n/2]
K 4 के साथ इस उदाहरण पर विचार करें ।
पूर्ण ग्राफ में, प्रत्येक शीर्ष शेष (n - 1) कोने के समीप है। इसलिए, प्रत्येक शीर्ष को एक नए रंग की आवश्यकता होती है। इसलिए K n = n की वर्णक्रमीय संख्या ।
ग्राफ रंग के अनुप्रयोग
ग्राफ सिद्धांत ग्राफ़ सिद्धांत में सबसे महत्वपूर्ण अवधारणाओं में से एक है। इसका उपयोग कंप्यूटर विज्ञान के कई वास्तविक समय के अनुप्रयोगों में किया जाता है जैसे -
- Clustering
- डेटा माइनिंग
- छवि कैप्चरिंग
- छवि विभाजन
- Networking
- संसाधन आवंटन
- शेड्यूलिंग प्रक्रियाएं