यह समस्या गंध करती है जैसे ग्राफ़ सिद्धांत में कोई जवाब होना चाहिए, लेकिन यह मुझे पता है कि किसी भी ग्राफ सिद्धांत समस्याओं से मेल नहीं खाता है। (नोट: यह वास्तव में एक असली दुनिया की समस्या है, आसान पढ़ने के लिए काल्पनिक)ग्राफ से "जोड़ी" बनाएं?
कल्पना कीजिए कि मेरे घर में शतरंज के खिलाड़ियों का भी एक क्रमांकित समूह है। मेरे पास खेलने के लिए बहुत सारी टेबल और शतरंज सेट हैं, लेकिन मुझे "जोड़ना" बनाना है (सुनिश्चित नहीं है कि इसके लिए ग्राफ सिद्धांत शब्द है या मेलअप की एक सूची है जैसे कि हर कोई किसी को बजाता है। शतरंज के खिलाड़ी सभी किसी ऐसे व्यक्ति को खेलना पसंद करेंगे जो उन्होंने पहले कभी नहीं खेला है।
यदि मेरे पास खेले गए प्रत्येक खिलाड़ी से एक सूची है, तो मैं आसानी से पिछले मैचअप दिखाते हुए एक ग्राफ बना सकता हूं। उदाहरण के लिए, एक बी और सी निभाई है, और सी डी निभाई है:
A----B
|
|
C----D
मुझे पता है कि मैं बी मिलान कर सकते/सी और ए/डी एक जोड़ी बनाने के लिए।
लेकिन पिछले matchups का ग्राफ इस तरह दिखता है:
A----B
\ |
\ |
C D
तो मैं एक जोड़ी बनाने के लिए सक्षम नहीं होगा। बी केवल सी खेल सकता है, जो ए और डी (जो पहले से ही खेले हैं) एक-दूसरे को खेलेंगे।
तो, मैं कैसे जान सकता हूं (ब्रूट फोर्स के अलावा कुछ विधि के माध्यम से) चाहे मैं एक जोड़ी बना सकता हूं या नहीं? यह एक पेड़ या चक्र नहीं है जिसे मैं ढूंढ रहा हूं, लेकिन क्या कोई अन्य ग्राफ प्रॉपर्टी है जिसके लिए मैं परीक्षण कर सकता हूं?