ग्राफ़ की शब्दावली और आसन्नता के निरूपण

ट्री से सामान्य संबंधों तक

रूटेड ट्री में हर गैर-रूट नोड का एक parent था और चक्र वर्जित थे। ग्राफ़ अधिक सामान्य है: वह शीर्षों (vertices) और उनके बीच की एज (edges) को दर्शाता है। ग्राफ़ में चक्र, दो शीर्षों के बीच कई रास्ते या अलग-अलग हिस्से हो सकते हैं। उसमें अपने-आप कोई रूट, parent या बायाँ/दायाँ child नहीं होता। बाद में ट्रैवर्सल किसी स्रोत से शुरू होकर parent लिंक बना सकता है, लेकिन वे ट्रैवर्सल के परिणाम हैं, मूल ग्राफ़ की परिभाषा नहीं।

पूर्वज्ञान: सीमित ऐरे और मैट्रिक्स, वैध इंडेक्स, C फ़ंक्शन, struct रिकॉर्ड और जीवित रिकॉर्ड तक पॉइंटर से पहुँच। पहले का बाइनरी ट्री पाठ उपयोगी शब्दावली देता है; लिंक्ड लिस्ट पाठ तार्किक संबंध और भंडारण-क्रम का अंतर बताता है। ज़रूरी C सिंटैक्स नीचे दोहराया गया है। यह पाठ निरूपण सिखाता है, BFS, DFS, सबसे छोटे रास्ते के एल्गोरिदम या संपूर्ण ग्राफ़-थ्योरी नहीं। BFS और DFS अलग अगले पाठ हैं।

इस्तेमाल करने से पहले ग्राफ़ का मॉडल बताएँ

हमारा चलने वाला प्रोग्राम सरल, अनिर्देशित और अभारित ग्राफ़ (simple undirected unweighted graph) संभालता है:

• शीर्ष अलग लेबल 0 से n - 1 तक हैं, जहाँ 0 <= n <= 6 है।
• एज {u,v} दो अलग शीर्ष जोड़ती है। स्वयं-लूप और दोहराई/समानांतर एज नहीं हैं। यहाँ “सरल” की यही पाबंदियाँ हैं।
• Undirected अर्थात अनिर्देशित में {u,v} और {v,u} एक ही एज हैं। एज पर दोनों दिशाओं में चला जा सकता है।
• Unweighted अर्थात अभारित में हर एज एक कदम है; उसकी अलग लागत, दूरी या समय नहीं रखा गया है।

शीर्ष का लेबल पहचान है, उसकी डिग्री, प्राथमिकता या स्रोत से दूरी नहीं। किसी अलग-थलग शीर्ष से कोई एज न जुड़ी हो, फिर भी वह मौजूद है। n = 0 में कोई शीर्ष या एज नहीं; n = 1 में एक अलग-थलग शीर्ष है और कोई एज नहीं।

इसके विपरीत निर्देशित (directed) ग्राफ़ में u -> v आर्क होता है। उल्टा आर्क v -> u अलग है और उसका मौजूद होना आवश्यक नहीं। दिशा अनदेखी करने को न कहा जाए तो ट्रैवर्सल बाहर जाने वाले आर्क पर चलता है। तब “A से B तक पहुँच सकते हैं” का अर्थ “B से A तक भी पहुँच सकते हैं” नहीं होता। आगे निर्देशित निरूपण की तुलना करेंगे, लेकिन यह प्रोग्राम असममित मैट्रिक्स को जानबूझकर अस्वीकार करता है क्योंकि उसका अनुबंध अनिर्देशित है।

पड़ोसी, डिग्री, रास्ते और घटक

एज से जुड़े शीर्ष आसन्न (adjacent) या पड़ोसी हैं। इस सरल अनिर्देशित मॉडल में degree(u), u से जुड़ी एज की संख्या और उसके अलग पड़ोसियों की संख्या, दोनों है। अलग-थलग शीर्ष की degree 0 है। हर एज अपने दोनों सिरों की डिग्री में एक-एक जोड़ती है, इसलिए डिग्रियों का योग 2m है, जहाँ m एज की संख्या है।

वॉक (walk) शीर्षों का ऐसा क्रम है जिसमें हर लगातार जोड़ी एज से जुड़ी है; शीर्ष दोहर सकते हैं। यहाँ पाथ (path) में कोई शीर्ष नहीं दोहरता। उसकी लंबाई एज की संख्या है, लिखे हुए शीर्ष-लेबल की संख्या नहीं। इस सरल अनिर्देशित मॉडल में चक्र (cycle) उसी शीर्ष पर शुरू और खत्म होता है, उसमें कम-से-कम तीन एज हैं और कोई अन्य शीर्ष नहीं दोहरता। एक एज पर जाकर तुरंत लौटना वॉक है, ऐसा चक्र नहीं।

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

सबसे छोटे अभारित पाथ की एज की संख्या दूरी है। अलग पाथ की लंबाई अलग हो सकती है। केवल एज या पड़ोसी लिख देने से दूरी या ट्रैवर्सल-क्रम नहीं निकलता।

हल सहित ट्रेस 1: एक ग्राफ़, उसकी गिनती और रास्ते

n = 5 लें और पाँच एज {0,1}, {0,3}, {1,2}, {1,3}, {3,4} रखें। इस सेट में हर अनिर्देशित एज एक बार लिखी है।

डिग्री योग 2 + 3 + 1 + 3 + 1 = 10 = 2 x 5 है। पाँचों शीर्ष एक component में हैं। 0,1,3,0 लंबाई 3 का चक्र है। 0 से 4 के पाथ में 0,3,4 (दो एज) और 0,1,3,4 (तीन एज) शामिल हैं। छोटी दूरी 2 है; बड़ा पाथ मौजूद होने से वह नहीं बदलती। BFS आगे ऐसी दूरियाँ क्रमबद्ध तरीके से निकालेगा।

इस ग्राफ़ में चक्र है, इसलिए यह ट्री नहीं। इसका अपना कोई रूट नहीं। पड़ोसी सूचियों को लेबल के क्रम में रखना स्पष्ट प्रस्तुति-चुनाव है; इससे न शीर्षों की संख्यात्मक प्राथमिकता बनती है, न हर ट्रैवर्सल के लिए यही क्रम अनिवार्य होता है।

आसन्नता मैट्रिक्स: हर क्रम वाली जोड़ी के लिए एक कोशिका

u और v आसन्न हों तो A[u][v] = 1, अन्यथा 0 रखें। पहला इंडेक्स पंक्ति का शीर्ष है; दूसरा स्तंभ का शीर्ष। उदाहरण का सक्रिय 5 गुणा 5 मैट्रिक्स है:

स्वयं-लूप नहीं हैं, इसलिए विकर्ण शून्य है। मैट्रिक्स सममित है: A[u][v] = A[v][u], क्योंकि अनिर्देशित एज दोनों क्रम वाले स्थानों पर आती है। पंक्ति का योग उस शीर्ष की डिग्री है। सभी कोशिकाएँ जोड़ने से हर एज दो बार गिनी जाती है। एक बार गिनने के लिए विकर्ण के ऊपर केवल u < v वाली कोशिकाएँ जोड़ें या पूरे योग को 2 से भाग दें।

कोशिका में 1 का अर्थ सीधी एज मौजूद है; उससे उस पंक्ति के हर अन्य शीर्ष की सबसे छोटी दूरी नहीं बताई जाती। A[u][v] = 0 केवल सीधी एज का अभाव है; अप्रत्यक्ष पाथ फिर भी हो सकता है। जैसे A[0][4] = 0 है, लेकिन 0,3,4 पाथ है। मैट्रिक्स की पंक्तियाँ और स्तंभ ट्रैवर्सल के parent नहीं रखते।

आसन्नता सूचियाँ: हर शीर्ष की एक पड़ोसी-सूची

हर u के लिए केवल उसके पड़ोसियों के लेबल रखें। ऊपर की पड़ोसी तालिका adjacency-list निरूपण है। “List” से पड़ोसियों का क्रम समझें; डायनैमिक रूप से आवंटित लिंक्ड नोड आवश्यक नहीं। अलग कार्यान्वयन लिंक्ड नोड, बढ़ने वाले ऐरे या सघन भंडारण इस्तेमाल कर सकते हैं।

हमारा छोटा सुरक्षित प्रोग्राम हर शीर्ष के लिए निश्चित आकार की पड़ोसी-पंक्ति और degree गिनती रखता है। u के लिए केवल neighbor[u][0] से neighbor[u][degree[u]-1] तक सक्रिय हैं। उसके बाहर रखा शून्य अनुपयोगी भंडारण है, अतिरिक्त पड़ोसी 0 नहीं। degree[u] = 0 हो तो सूची खाली है, भले उसकी पंक्ति के लिए जगह मौजूद हो। पड़ोसी पंक्ति में स्थान k खुद शीर्ष-लेबल नहीं है: neighbor[1][1] = 2 का अर्थ शीर्ष 1 का दूसरा सूचीबद्ध पड़ोसी शीर्ष 2 है।

अनिर्देशित एज {u,v} के लिए u की पंक्ति में v और v की पंक्ति में u, दोनों आते हैं। इसलिए कुल सक्रिय पड़ोसी प्रविष्टियाँ 2m हैं। सरल ग्राफ़ में वही पड़ोसी दो बार न जोड़ें। रूपांतरण v को 0 से ऊपर स्कैन करता है, इसलिए बढ़ती सूचियाँ दोबारा भी उसी तरह बनती हैं। कोई अलग पड़ोसी-क्रम वही एज दर्शा सकता है, हालाँकि बाद के ट्रैवर्सल का visit-क्रम बदल सकता है।

रूपांतरण का पूरा C11 प्रोग्राम

यह प्रोग्राम मैट्रिक्स जाँचकर सीमित पड़ोसी-पंक्तियों में बदलता है, सूचियाँ छापता है और अनिर्देशित एज गिनता है। यह ग्राफ़ ट्रैवर्सल नहीं करता।

#include <stdio.h>

enum { CAP = 6 };

typedef struct {
    int n;
    int adj[CAP][CAP];
} Graph;

typedef struct {
    int degree[CAP];
    int neighbor[CAP][CAP];
} Lists;

int valid_graph(const Graph *g) {
    if (g == NULL || g->n < 0 || g->n > CAP) {
        return 0;
    }
    for (int u = 0; u < g->n; u = u + 1) {
        for (int v = 0; v < g->n; v = v + 1) {
            int x = g->adj[u][v];
            if (x != 0 && x != 1) {
                return 0;
            }
            if (u == v && x != 0) {
                return 0;
            }
            if (x != g->adj[v][u]) {
                return 0;
            }
        }
    }
    return 1;
}

int make_lists(const Graph *g, Lists *out) {
    if (out == NULL || !valid_graph(g)) {
        return 0;
    }
    Lists result = {0};
    for (int u = 0; u < g->n; u = u + 1) {
        for (int v = 0; v < g->n; v = v + 1) {
            if (g->adj[u][v] == 1) {
                int position = result.degree[u];
                result.neighbor[u][position] = v;
                result.degree[u] = position + 1;
            }
        }
    }
    *out = result;
    return 1;
}

int edge_count(const Graph *g) {
    if (!valid_graph(g)) {
        return -1;
    }
    int total = 0;
    for (int u = 0; u < g->n; u = u + 1) {
        for (int v = u + 1; v < g->n; v = v + 1) {
            total = total + g->adj[u][v];
        }
    }
    return total;
}

int main(void) {
    const Graph g = {5, {
        {0, 1, 0, 1, 0, 0},
        {1, 0, 1, 1, 0, 0},
        {0, 1, 0, 0, 0, 0},
        {1, 1, 0, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0}
    }};
    Lists lists = {0};
    if (!make_lists(&g, &lists)) {
        return 1;
    }
    for (int u = 0; u < g.n; u = u + 1) {
        printf("%d:", u);
        for (int k = 0; k < lists.degree[u]; k = k + 1) {
            printf(" %d", lists.neighbor[u][k]);
        }
        printf("\n");
    }
    printf("edges: %d\n", edge_count(&g));
    return 0;
}

ठीक यही आउटपुट है:

0: 1 3
1: 0 2 3
2: 1
3: 0 1 4
4: 3
edges: 5

C रिकॉर्ड, इनपुट का वादा और सुरक्षित सीमाएँ

enum { CAP = 6 }; पूर्णांक स्थिरांक का नाम देता है। Graph में n के बाद छह गुणा छह int मैट्रिक्स है; Lists में छह degree गिनतियों के बाद छह-स्लॉट वाली छह पड़ोसी पंक्तियाँ हैं। अंदर-अंदर ब्रेस से रिकॉर्ड और उनके ऐरे को घोषणा के क्रम में आरंभिक मान दिए जाते हैं। Lists result = {0} केवल पहले तत्व को नहीं, हर degree और हर पड़ोसी स्लॉट को शून्य करता है।

&g जीवित Graph रिकॉर्ड का पता देता है। const Graph *g वही पता लेकर उसके माध्यम से पढ़ने देता है; g->n का अर्थ (*g).n है। पॉइंटर का मान कॉपी होकर जाता है, लेकिन उसका अनुसरण मूल रिकॉर्ड तक पहुँचाता है। Lists *out लिखने योग्य आउटपुट रिकॉर्ड बताता है; *out = result तैयार रिकॉर्ड उसमें कॉपी करता है। यहाँ stdio.h से उपलब्ध NULL का अर्थ कोई ऑब्जेक्ट नहीं। इनपुट Graph और आउटपुट Lists अलग, बिना एक-दूसरे की मेमोरी पर चढ़े, जीवित और आरंभिक मानों वाले ऑब्जेक्ट होने चाहिए। NULL को त्रुटि की तरह संभाला गया है; dangling pointer या मनगढ़ंत पते इन जाँचों से सुरक्षित नहीं बनते। कोई डायनैमिक आवंटन नहीं है।

valid_graph पहले पॉइंटर और n जाँचता है, फिर केवल सक्रिय n गुणा n भाग। हर सक्रिय कोशिका 0 या 1 हो, विकर्ण 0 हो और सममित स्थान बराबर हों। अनुपयोगी पंक्तियाँ/स्तंभ आरंभिक मानों वाला भंडारण हैं, ग्राफ़ का हिस्सा नहीं। || में पहले की शर्त सही हो तो आगे नहीं पढ़ते, जिससे NULL से पहुँच रुकती है। && में दोनों शर्तें चाहिए। ! शून्य जाँचता है। != असमान, = असाइनमेंट और == तुलना है। for लूप पहले इंडेक्स आरंभ करता है, हर पुनरावृत्ति से पहले सीमा जाँचता है और बॉडी के बाद अपडेट करता है।

रूपांतरण किसी भी लेखन से पहले अमान्य ग्राफ़ या NULL आउटपुट को अस्वीकार करता है। पहले स्थानीय शून्य-आरंभित परिणाम बनता है और केवल सफलता पर out में कॉपी होता है। विफलता 0 लौटाती है और दिए गए जीवित आउटपुट का हर फ़ील्ड अपरिवर्तित रखती है। सफलता 1 लौटाती है। इनपुट कभी नहीं बदलता।

हर शीर्ष के अधिकतम n - 1 <= 5 पड़ोसी हो सकते हैं क्योंकि स्वयं-लूप नहीं है और हर स्तंभ एक बार देखा जाता है। लिखने से पहले position अब तक मिले पड़ोसियों की संख्या है, इसलिए छह-स्लॉट पंक्ति में सबसे बड़ा लिखा स्थान अधिकतम 4 है। यह सबसे बड़े पड़ोसी-लेबल से अलग है, जो 5 हो सकता है। खाली ग्राफ़ सफलतापूर्वक बदलता है और सभी गिनतियाँ शून्य रहती हैं; एक शीर्ष पर एक खाली सूची मिलती है। edge_count अमान्य इनपुट पर -1 और वैध ग्राफ़ पर 0 से 15 लौटाता है, इसलिए विफलता-संकेत वैध गिनती नहीं हो सकता। वह केवल u < v जोड़ता है। सभी इंडेक्स और गिनती का अंकगणित सीमित है और int में समाता है।

printf में %d पूर्णांक छापता है और \n नई पंक्ति शुरू करता है। main, परिणाम इस्तेमाल करने से पहले रूपांतरण का status जाँचता है। कॉल क्रम से चलती हैं; साथ-साथ बदलाव नहीं माना गया है।

हल सहित ट्रेस 2: अलग हिस्सों वाले ग्राफ़ का रूपांतरण

n = 4 और एज {0,2}, {1,2} लें; शीर्ष 3 अलग-थलग है। सक्रिय मैट्रिक्स की पंक्तियाँ [0,0,1,0], [0,0,1,0], [1,1,0,0], [0,0,0,0] हैं। हर पंक्ति को स्तंभ 0 से 3 तक स्कैन करने पर:

• पंक्ति 0: 0,1 छोड़ें; लेबल 2 को स्थान 0 पर जोड़ें; 3 छोड़ें। सूची [2], degree 1।
• पंक्ति 1: सूची [2], degree 1।
• पंक्ति 2: 0 को स्थान 0 और 1 को स्थान 1 पर जोड़ें। सूची [0,1], degree 2।
• पंक्ति 3: कुछ न जोड़ें। सूची [], degree 0।

सक्रिय प्रविष्टियाँ चार हैं, लेकिन एज दो। दो component हैं: {0,1,2} और {3}। स्रोत 0 से 2 होकर 1 तक पहुँच सकते हैं, हालाँकि A[0][1] शून्य है; 3 तक नहीं पहुँच सकते। हर पंक्ति बदलने से अलग-थलग शीर्ष भी दर्ज होता है, लेकिन यह प्रक्रिया खुद component नहीं खोजती और उनके नंबर नहीं बनाती।

हल सहित ट्रेस 3: निर्देशित निरूपण का अनुबंध अलग है

अलग निर्देशित ग्राफ़ में आर्क 0 -> 1, 0 -> 2 और 2 -> 1 लें। u से v की ओर आर्क हो तो A[u][v] = 1 रखें। पंक्तियाँ [0,1,1], [0,0,0], [0,1,0] हैं। बाहर जाने वाली सूचियाँ 0:[1,2], 1:[], 2:[1] हैं। पंक्ति-योग outdegree 2,0,1 और स्तंभ-योग indegree 0,2,1 हैं। सभी शीर्षों पर इनमें से हर योग तीन आर्क के बराबर है; दो से भाग नहीं देते।

शीर्ष 0 से 1 तक पहुँचते हैं, लेकिन 1 से बाहर जाने वाले आर्क से न 0, न 2 तक पहुँचते हैं। उल्टी प्रविष्टियाँ तभी जोड़ें जब वैसे आर्क मौजूद हों। यह मैट्रिक्स जानबूझकर असममित है और ऊपर का valid_graph इसे स्वीकार नहीं करता। निर्देशित ग्राफ़ संभालने के लिए अनुबंध/जाँच में सोचकर बदलाव चाहिए; अनिर्देशित प्रोग्राम में सममिति को चुपचाप वैकल्पिक न मानें।

भंडारण और पहुँच का अंतर, सही सीमाओं सहित

सामान्य n गुणा n मैट्रिक्स में n का वर्ग कोशिकाएँ हैं, चाहे एज कम हों। इंडेक्स वैध हों तो किसी निश्चित एज की जाँच एक कोशिका पढ़कर होती है। u के सभी पड़ोसी निकालने के लिए उसकी पंक्ति के n संभावित स्तंभ देखने होते हैं।

सामान्य सघन adjacency-list निरूपण में n सूचियों की जानकारी और पड़ोसी प्रविष्टियाँ होती हैं: सरल अनिर्देशित ग्राफ़ में 2m, निर्देशित बाहर-जाने वाली सूचियों में m। बनी हुई u की सूची स्कैन करने में degree(u) प्रविष्टियाँ दिखती हैं। बिना क्रमबद्ध सूची में एक निश्चित पड़ोसी खोजने में पूरी सूची देखनी पड़ सकती है; adjacency list अपने-आप स्थिर-समय edge lookup नहीं देती।

हमारा शुरुआती कार्यान्वयन जानबूझकर CAP का वर्ग पड़ोसी स्लॉट और CAP गिनतियाँ आरक्षित रखता है, जैसे CAP का वर्ग मैट्रिक्स स्लॉट। यह सघन सूची की मेमोरी-बचत का प्रदर्शन नहीं है। यह दिखाता है कि तार्किक रूप से कौन-सी प्रविष्टियाँ सक्रिय हैं और पड़ोसी-सूची वही ग्राफ़ कैसे दर्शाती है। रूपांतरण सक्रिय n गुणा n मैट्रिक्स स्कैन करता है; पूरा सीमित परिणाम आरंभ करने में आरक्षित जगह भी छुई जाती है। औपचारिक जटिलता-विश्लेषण और सघन आवंटन आगे के विषय हैं।

एक सटीक उपमा

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

मुख्य बातें

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

पहले स्वयं करें, फिर मिलाएँ

1. पहले पाँच-शीर्ष वाले ग्राफ़ में अलग-थलग शीर्ष 5 जोड़ें; एज वही रखें। क्या बदलेगा? उत्तर: n = 6 होगा; सक्रिय शून्य पंक्ति और स्तंभ तथा खाली पड़ोसी-सूची जुड़ेंगे। एज 5, degree-योग 10 ही रहेंगे और अब दो component होंगे।
2. सरल अनिर्देशित ग्राफ़ की सूचियाँ 0:[1], 1:[0,2], 2:[1], 3:[] हैं। एज गिनें और 0 से 2 का पाथ दें। उत्तर: चार पड़ोसी प्रविष्टियाँ दो एज हैं। पाथ 0,1,2 की लंबाई 2 है। शीर्ष 3 अलग-थलग है; 0 से 3 तक पाथ नहीं है।

छह मौलिक अभ्यास प्रश्न

ठीक एक विकल्प चुनें। ये मौलिक शुरुआती अभ्यास हैं, पिछले वर्ष के प्रश्न, पूरा मॉक या संपूर्ण GATE CS कवरेज नहीं। हर प्रश्न का बताया ग्राफ़-मॉडल इस्तेमाल करें।

1

सरल अनिर्देशित ग्राफ़ की डिग्रियाँ 2, 3, 1, 3, 1 हैं। उसमें कितनी एज हैं?

A. 10 B. 3 C. 5 D. 4

2

पहले हल किए ग्राफ़ में A[0][4] = 0 है। कौन-सा निष्कर्ष सही है?

A. 0 से 4 तक कोई पाथ नहीं हो सकता। B. सीधी एज {0,4} नहीं है; पाथ 0,3,4 फिर भी है। C. शीर्ष 4 मौजूद नहीं है। D. 0 से 4 की सबसे छोटी दूरी शून्य है।

3

निर्देशित आर्क 0->1, 0->2 और 2->1 के लिए बाहर-जाने वाली आसन्नता पंक्तियाँ लें। शीर्ष 1 की outdegree और indegree क्या हैं?

A. 2 और 0 B. 1 और 1 C. 2 और 2 D. 0 और 2

4

पहले ग्राफ़ की बदली हुई Lists में degree[1] = 3 है और neighbor[1] की शुरुआत [0,2,3] है। neighbor[1][1] का अर्थ क्या है?

A. शीर्ष 1 का दूसरा सूचीबद्ध पड़ोसी शीर्ष 2 है। B. शीर्ष 1 पर स्वयं-लूप है। C. शीर्ष 1 की degree 1 है। D. 1 से 1 की दूरी 2 है।

5

0,1,2,3 वाला सरल अनिर्देशित ग्राफ़ केवल एज {0,2} और {1,2} रखता है। कौन-सा कथन सही है?

A. चारों लेबल भंडारण में होने से एक component है। B. 0 और 1 के बीच सीधी एज न होने से तीन component हैं। C. दो component {0,1,2} और {3} हैं; शीर्ष 3 की पड़ोसी-सूची खाली है। D. degree शून्य होने से शीर्ष 3 हटाना होगा।

6

ठीक दिखाए C प्रोग्राम के भंडारण के बारे में कौन-सा कथन सही है?

A. उसकी निश्चित पड़ोसी पंक्तियाँ अपने-आप केवल 2m पूर्णांक स्लॉट आरक्षित रखती हैं। B. वह CAP का वर्ग पड़ोसी स्लॉट और CAP गिनतियाँ रखता है, हालाँकि हर पंक्ति के केवल degree[u] स्लॉट सक्रिय हैं। C. अनुपयोगी पंक्ति स्लॉट का हर शून्य 0 नाम का पड़ोसी है। D. आसन्नता सूची के लिए हमेशा malloc और लिंक्ड नोड चाहिए।

समझाए गए उत्तर

1: C

A गलत है: 10 degree का योग है, जिसमें हर अनिर्देशित एज दोनों सिरों पर गिनी जाती है।

B गलत है: 3 अधिकतम degree है, कुल एज नहीं।

C सही है: degree-योग 10 है, इसलिए m = 10/2 = 5।

D गलत है: पाँच शीर्ष के ट्री में n-1 = 4 एज होतीं, लेकिन यह ग्राफ़ ट्री होना ज़रूरी नहीं।

2: B

A गलत है: आसन्नता सीधी एज बताती है, पूरी पहुँच नहीं।

B सही है: {0,3} और {3,4} दोनों हैं, इसलिए दो-एज का अप्रत्यक्ष पाथ है।

C गलत है: n=5 में 0 से 4 तक लेबल मौजूद हैं, किसी खास एज पर निर्भर नहीं।

D गलत है: यह आसन्नता-कोशिका है, दूरी नहीं; अलग शीर्ष दो एज दूर हैं।

3: D

A गलत है: आने और जाने की गिनतियाँ उलट गई हैं।

B गलत है: 1 से कोई आर्क नहीं निकलता, और दो अलग आर्क उसमें आते हैं।

C गलत है: निर्देशित ग्राफ़ में उल्टा आर्क अपने-आप नहीं जुड़ता।

D सही है: पंक्ति 1 पूरी शून्य है; स्तंभ 1 में शीर्ष 0 और 2 से दो एक हैं।

4: A

A सही है: पहला इंडेक्स शीर्ष की पंक्ति चुनता है; स्थान 1 उसकी दूसरी प्रविष्टि है, जिसमें लेबल 2 है।

B गलत है: दूसरा इंडेक्स सूची का स्थान है, दूसरा सिरा नहीं। स्वयं-लूप के लिए लेबल 1 रखा जाता, जो इस ग्राफ़ में वर्जित है।

C गलत है: पड़ोसी का स्थान नहीं, degree[1] गिनती 3 देता है।

D गलत है: पड़ोसी पंक्तियाँ लेबल रखती हैं, दूरियाँ नहीं।

5: C

A गलत है: भंडारण होने से पाथ नहीं बनते।

B गलत है: पाथ 0,2,1 से 0 और 1 अप्रत्यक्ष रूप से जुड़े हैं।

C सही है: 0,1,2 शीर्ष 2 से जुड़े हैं; अलग-थलग 3 अपना component है।

D गलत है: अलग-थलग शीर्ष ग्राफ़ का वैध सदस्य है।

6: B

A गलत है: 2m सक्रिय पड़ोसी प्रविष्टियों की गिनती है; कम एज होने पर भी निश्चित ऐरे पूरी क्षमता आरक्षित रखते हैं।

B सही है: कार्यान्वयन निश्चित भंडारण रखता है और degree सक्रिय सदस्य तथा अनुपयोगी कोशिका अलग करता है।

C गलत है: सक्रिय शुरुआती हिस्से के बाहर के स्थान सदस्य नहीं, चाहे कोई मान रखा हो।

D गलत है: पड़ोसी क्रम ऐरे में हो सकता है; यह प्रोग्राम डायनैमिक मेमोरी नहीं लेता।

अगला कदम और सीमा

आगे यही स्पष्ट आसन्नता नियम BFS और DFS में इस्तेमाल करें। उनकी visited स्थिति और चुना स्रोत ट्रैवर्सल का व्यवहार तय करते हैं; अकेला निरूपण नहीं। यह मौलिक बुनियाद मौजूदा कोर्स का परीक्षा-वर्ष नहीं बदलती और पूरे पाठ्यक्रम कवरेज का दावा नहीं करती। हिंदी सीखने में सहायता है।