গ্রাফ রিপ্রেজেন্টেশন ও কানেক্টিভিটি

১ · গ্রাফ কীভাবে সংরক্ষণ করা হয়?

L18-এ আমরা গ্রাফকে গাণিতিকভাবে সংজ্ঞায়িত করেছি। কিন্তু কম্পিউটারে একটি গ্রাফ প্রকৃতপক্ষে সংরক্ষণ করতে দুটি প্রধান পদ্ধতি ব্যবহৃত হয় —

২ · Walk, Trail, ও Path

একটি গ্রাফে এক vertex থেকে আরেক vertex-এ যাওয়ার "রাস্তা" বোঝাতে তিনটি ভিন্ন, সুনির্দিষ্ট পরিভাষা ব্যবহৃত হয় —

• WalkWalkvertex ও edge-এর যেকোনো ক্রম যেখানে পরপর প্রতিটি জোড়া edge দ্বারা সংযুক্ত — vertex ও edge পুনরাবৃত্তি করা যায়। — vertex-edge-vertex-...-এর যেকোনো ক্রম, vertex বা edge পুনরাবৃত্তি করা যায়।
• Trail — একটি walk যেখানে কোনো edge পুনরাবৃত্তি হয় না (vertex পুনরাবৃত্তি হতে পারে)।
• Path — একটি trail যেখানে কোনো vertex-ও পুনরাবৃত্তি হয় না।

L20-এ আমরা দেখব Euler path মূলত একটি বিশেষ ধরনের trail (প্রতিটি edge ব্যবহার করে, কিন্তু vertex পুনরাবৃত্তি হতে পারে), আর Hamiltonian path একটি প্রকৃত path (প্রতিটি vertex ঠিক একবার)।

৩ · কানেক্টিভিটি

একটি গ্রাফ connected হয় যদি প্রতিটি জোড়া vertex-এর মধ্যে অন্তত একটি path থাকে। যদি কোনো গ্রাফ connected না হয়, তাহলে সেটি কয়েকটি connected componentConnected componentএকটি গ্রাফের সর্বোচ্চ (maximal) connected উপ-গ্রাফ — যে vertex-গুলো নিজেদের মধ্যে path-এর মাধ্যমে পৌঁছানো যায়, কিন্তু বাকি গ্রাফের সাথে নয়।-এ ভাগ হয়ে যায় — প্রতিটি component নিজে সম্পূর্ণ connected, কিন্তু অন্য component-এর সাথে কোনো path নেই।

from collections import deque

def is_connected(graph, start, all_vertices):
    visited = {start}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for neighbor in graph.get(v, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited == set(all_vertices)

# গ্রাফ ১: সংযুক্ত (সবাই একে অপরের সাথে path-এ যুক্ত)
graph_connected = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B", "D"],
    "D": ["C"],
}
vertices1 = ["A", "B", "C", "D"]
print("গ্রাফ ১ সংযুক্ত (connected)?", is_connected(graph_connected, "A", vertices1))

# গ্রাফ ২: বিচ্ছিন্ন — {A,B} ও {C,D} দুটি আলাদা component
graph_disconnected = {
    "A": ["B"],
    "B": ["A"],
    "C": ["D"],
    "D": ["C"],
}
vertices2 = ["A", "B", "C", "D"]
print("গ্রাফ ২ সংযুক্ত (connected)?", is_connected(graph_disconnected, "A", vertices2))